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

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

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

Свойства

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

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

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

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

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

• генерируется случайный бит $s$ , а также случайная величина $v_{0}$ ; если $v_{0}$ меньше заданной константы $c_{0}$ , то коэффициент будет равен нулю;
• Генерируется случайное 63-битное значение ${\displaystyle v_{1}}$ , и используется таблица констант: получается индекс $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}}}$ .

После получения подходящих многочленов $f$ , $g$ , $F$ , $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 )}$ из сообщения $m$ и модификатора входа хэш-функции $r$ .
• вычисление двух коротких значений $s_{1}$ и $s_{2}$ , таких, что ${\displaystyle s_{1}+s_{2}h=c{\pmod {q}}}$ , используя знание секретного ключа ${\displaystyle f,g,F,G}$ .

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

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

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

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

Литература

• Thomas Prest; Pierre-Alain Fouque; Jeffrey Hoffstein; Paul Kirchner, (PDF)
• Craig Gentry; Chris Peikert; Vinod Vaikuntanathan (2008). . .
• Dan Boneh; Özgür Dagdelen; Marc Fischlin; Anja Lehmann; Christian Schaffner; Mark Zhandry (2011). . 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.

Ссылки