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

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

Представлен в проекте постквантовой криптографии NIST^[en] 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-512	8,64	5948,1	27930	666
Falcon-1024	27,45	2913,0	13650	1280

Основные элементы править

Основными элементами в Falcon являются многочлены степени $n$ с целыми коэффициентами. Степень $n$ обычно является степенью двойки (обычно 512 или 1024). Вычисления производятся по модулю многочлена одной переменной степени $n$ , обозначаемого $\phi$ (который всегда имеет вид $\phi =x^{n}+1$ ).

Математически в алгоритме некоторые многочлены интерпретируются как векторы, а другие – как матрицы. Полином $f$ по модулю $\phi$ обозначает квадратную матрицу $n\times n$ , строками которой являются $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-битное значение $v_{1}$ , и используется таблица констант: получается индекс $k$ первого значения $c_{k}$ , которое не больше $v_{1}$ (элементы таблицы индексируются, начиная с 1, и идут по убыванию, последний равен 0, что гарантирует уникальность решения).
если $v_{0}<c_{0}$ , то новый коэффициент многочлена равен 0; в противном случае его значение равно $(-1)^{s}k$ ; все операции выполняются систематически, то есть тест на $v_{0}$ выполняется в постоянном времени, а поиск $v_{1}$ в таблице выполняется всегда, независимо от результата теста на $v_{0}$ ; поиск в таблице выполняется путем чтения всех элементов таблицы;
решении уравнения NTRU; при решении уравнения NTRU вычисляются многочлены различных степеней, коэффициенты которых являются большими целыми числами; используется RNS (система остаточных чисел) для больших целых чисел, поэтому работа происходит с ожидаемой длиной целых чисел, а не с их истинной длиной.

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

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

.

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

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

.

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

Вычисление подписи править

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

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

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

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

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

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

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