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

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

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

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

Свойства

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

Алгоритм масштабируем — его асимптотическая сложность ${\displaystyle O(n\log n)}$ позволяет использовать долговременные параметры безопасности при умеренных затратах. Усовершенствованный алгоритм генерации ключей 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 являются многочлены степени ${\displaystyle n}$ с целыми коэффициентами. Степень ${\displaystyle n}$ обычно является степенью двойки (обычно 512 или 1024). Вычисления производятся по модулю многочлена одной переменной степени ${\displaystyle n}$, обозначаемого ${\displaystyle \phi }$ (который всегда имеет вид ${\displaystyle \phi =x^{n}+1}$).

Математически в алгоритме некоторые многочлены интерпретируются как векторы, а другие – как матрицы. Полином ${\displaystyle f}$ по модулю ${\displaystyle \phi }$ обозначает квадратную матрицу ${\displaystyle n\times n}$, строками которой являются ${\displaystyle x^{i}f{\pmod {\phi }}}$ для всех ${\displaystyle i}$ от 0 до ${\displaystyle n-1}$. Сложение и умножение таких матриц сводится к сложению и умножению многочленов по модулю ${\displaystyle \phi }$. Поэтому Falcon реализован в терминах операций над многочленами, даже в операциях с матрицами, определяющими решётку.

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

Генерация ключевой пары включает в себя генерацию случайных многочленов ${\displaystyle f}$ и ${\displaystyle g}$ с простым распределением гаусса и решение уравнения NTRU для вычисления ${\displaystyle F}$ и ${\displaystyle G}$. Генерация ${\displaystyle f}$ и ${\displaystyle g}$:

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

В итоге, открытый ключ ${\displaystyle pk}$, соответствующий закрытому ключу ${\displaystyle sk=(f,g,F,G)}$ – это многочлен ${\displaystyle h\in Z_{q}[x]/(\phi )}$ такой, что:

${\displaystyle h=gf^{-1}{\pmod {\phi ,q}}}$.

После получения подходящих многочленов ${\displaystyle f}$, ${\displaystyle g}$, ${\displaystyle F}$, ${\displaystyle G}$, вторая часть генерации ключа заключается в их обработке в подходящий формат. Под подходящим форматом подразумевается, компактность и возможность быстро генерировать подписи. К такому формату можно прийти с помощью Falcon-дерева. Чтобы вычислить Falcon-дерево, нужно вычислить ${\displaystyle LDL^{*}}$-разложение ${\displaystyle G=BB^{*}}$, где:

${\displaystyle B=\ \ \ {\begin{vmatrix}g\ \ -f\\G\ \ \ \ F\end{vmatrix}}}$.

Это эквивалентно вычислению ортогонализации Грамма — Шмидта для ${\displaystyle B=L\times B}$.

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

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

• вычисление хэш-значение ${\displaystyle c\in Z_{q}[x]/(\phi )}$ из сообщения ${\displaystyle m}$ и модификатора входа хэш-функции ${\displaystyle r}$.
• вычисление двух коротких значений ${\displaystyle s_{1}}$ и ${\displaystyle s_{2}}$, таких, что ${\displaystyle s_{1}+s_{2}h=c{\pmod {q}}}$, используя знание секретного ключа ${\displaystyle f,g,F,G}$.

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

Главными преимуществами алгоритма являются компактность, быстрота и несколько режимов работы (классический, режим восстановления сообщения, режим восстановления ключа). Кроме того, 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.

Ссылки

• Falcon official website
• List of NIST PQC selected candidates
• Reference implementation of Falcon in C
• Implementation of Falcon in Python
• NIST Post-Quantum Cryptography Call for Proposals