Falcon (криптоалгоритм) (Falcon (tjnhmkglikjnmb))

Перейти к навигации Перейти к поиску

Falcon (англ. Fast-Fourier Lattice-Based Compact Signs over NTRU) — постквантовый алгоритм криптографической подписи поверх решёток NTRU[англ.].

Представлен в проекте постквантовой криптографии NIST[англ.] 30 ноября 2017 года, авторы — Томас Прест, Пьер-Ален Фуке, Джеффри Хоффштейн, Полом Киршнер, Вадим Любашевский, Томас Порнин, Томас Рикоссе, Грегор Зайлер, Уильям Уайт, Чжэнфей Чжан. Использует преимущества нескольких инструментов для обеспечения компактности и эффективности с доказуемой безопасностью. Использование решётки NTRU позволяет сделать размер подписи и открытого ключа относительно небольшим, в то время как быстрое преобразование Фурье обеспечивает эффективное вычисление подписи. При этом с точки зрения безопасности NTRU обладает пониженной безопасностью по сравнению с моделью квантового случайного оракула.

Эталонные реализации выполнены на Си и Python.

Для обеспечения безопасности используется гауссов семплер, что гарантирует малую утечку информации о секретном ключе вплоть до практически бесконечного количества подписей (более 264). Компактность обеспечивается благодаря использованию решёток NTRU — подписи существенно короче, чем в любой схеме подписи на основе решёток с теми же гарантиями безопасности, а открытые ключи имеют примерно такой же размер.

Алгоритм масштабируем — его асимптотическая сложность позволяет использовать долговременные параметры безопасности при умеренных затратах. Усовершенствованный алгоритм генерации ключей Falcon использует менее 30 килобайт оперативной памяти, таким образом, Falcon совместим с небольшими встроенными устройствами с ограниченным объёмом памяти.

Кроме того, в версии Falcon-512 все операции выполняются с постоянным временем, в том числе операции с плавающей точкой.

Применение быстрого преобразования Фурье позволяет реализовывать тысячи подписей в секунду на обычном компьютере, a проверка проходит в пять-десять раз быстрее. Версия Falcon-512 имеет уровень безопасности NIST 1 (безопасность, сравнимая со взломом битов AES-128), а версия Falcon-1024 имеет уровень безопасности NIST 5 (сравнимый со взломом AES-256). Используя эталонную реализацию на обычном настольном компьютере (Intel Core i5-8259U с тактовой частотой 2,3 ГГц, TurboBoost отключён), Falcon достигает следующей производительности:

Версия Время генерации ключа (мс) Пропускная способность (подписей/с) Пропускная способность(проверок/с) Размер сигнатуры (байт)
Falcon-512 8,64 5948,1 27930 666
Falcon-1024 27,45 2913,0 13650 1280

Основные элементы

[править | править код]

Основными элементами в Falcon являются многочлены степени с целыми коэффициентами. Степень обычно является степенью двойки (обычно 512 или 1024). Вычисления производятся по модулю многочлена одной переменной степени , обозначаемого (который всегда имеет вид ).

Математически в алгоритме некоторые многочлены интерпретируются как векторы, а другие – как матрицы. Полином по модулю обозначает квадратную матрицу , строками которой являются для всех от 0 до . Сложение и умножение таких матриц сводится к сложению и умножению многочленов по модулю . Поэтому Falcon реализован в терминах операций над многочленами, даже в операциях с матрицами, определяющими решётку.

Генерация ключевой пары

[править | править код]

Генерация ключевой пары включает в себя генерацию случайных многочленов и с простым распределением гаусса и решение уравнения NTRU для вычисления и . Генерация и :

  • генерируется случайный бит , а также случайная величина ; если меньше заданной константы , то коэффициент будет равен нулю;
  • Генерируется случайное 63-битное значение , и используется таблица констант: получается индекс первого значения , которое не больше (элементы таблицы индексируются, начиная с 1, и идут по убыванию, последний равен 0, что гарантирует уникальность решения).
  • если , то новый коэффициент многочлена равен 0; в противном случае его значение равно ; все операции выполняются систематически, то есть тест на выполняется в постоянном времени, а поиск в таблице выполняется всегда, независимо от результата теста на ; поиск в таблице выполняется путем чтения всех элементов таблицы;
  • решении уравнения NTRU; при решении уравнения NTRU вычисляются многочлены различных степеней, коэффициенты которых являются большими целыми числами; используется RNS (система остаточных чисел) для больших целых чисел, поэтому работа происходит с ожидаемой длиной целых чисел, а не с их истинной длиной.

В итоге, открытый ключ , соответствующий закрытому ключу – это многочлен такой, что:

.

После получения подходящих многочленов , , , , вторая часть генерации ключа заключается в их обработке в подходящий формат. Под подходящим форматом подразумевается, компактность и возможность быстро генерировать подписи. К такому формату можно прийти с помощью Falcon-дерева. Чтобы вычислить Falcon-дерево, нужно вычислить -разложение , где:

.

Это эквивалентно вычислению ортогонализации Грамма — Шмидта для .

Вычисление подписи

[править | править код]

Принцип алгоритма создания подписи:

  • вычисление хэш-значение из сообщения и модификатора входа хэш-функции .
  • вычисление двух коротких значений и , таких, что , используя знание секретного ключа .

Преимущества и недостатки

[править | править код]

Главными преимуществами алгоритма являются компактность, быстрота и несколько режимов работы (классический, режим восстановления сообщения, режим восстановления ключа). Кроме того, Falcon можно превратить в схему IBE (шифрование на основе идентификации) и в схему кольцевой подписи. Falcon является самой компактной схемой из всех постквантовых схем подписи. Но существуют и недостатки, в первую очередь это сложность для понимания и реализации и плохая устойчивость побочного канала к перехвату.

Сравнение размера открытого ключа с другими алгоритмами подписи на уровне NIST 5 (размеры в байтах):

Графики недоступны из-за технических проблем. См. информацию на Фабрикаторе и на mediawiki.org.

Сравнение размера подписи с другими алгоритмами подписи на уровне NIST 5 (размеры в байтах):

Графики недоступны из-за технических проблем. См. информацию на Фабрикаторе и на mediawiki.org.

Литература

[править | править код]
  • Thomas Prest; Pierre-Alain Fouque; Jeffrey Hoffstein; Paul Kirchner, Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU (PDF)
  • Craig Gentry; Chris Peikert; Vinod Vaikuntanathan (2008). Trapdoors for Hard Lattices and New Cryptographic Constructions. STOC.
  • Dan Boneh; Özgür Dagdelen; Marc Fischlin; Anja Lehmann; Christian Schaffner; Mark Zhandry (2011). Random Oracles in a Quantum World. Asiacrypt.
  • Phong Q. Nguyen and Oded Regev. Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 271–288. Springer, Heidelberg, May / June 2006.
  • Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, and William Whyte. NTRUSIGN: Digital signatures using the NTRU lattice. In Marc Joye, editor, CT-RSA 2003, volume 2612 of LNCS, pages 122–140. Springer, Heidelberg, April 2003.
  • Nick Howgrave-Graham. A hybrid lattce-reduction and meet-in-the-middle attack against NTRU. In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 150–169. Springer, Heidelberg, August 2007.
  • Jean-Sébastien Coron and Jesper Buus Nielsen, editors. EUROCRYPT 2017, Part I, volume 10210 of LNCS. Springer, Heidelberg, April / May 2017.