Falcon (криптоалгоритм)
Falcon () — постквантовый алгоритм криптографической подписи поверх решёток .

Представлен в  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 или 1024). Вычисления производятся по модулю многочлена одной переменной степени , обозначаемого  (который всегда имеет вид ). 

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

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

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

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

 .

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

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

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

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

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

Литература 
 
 
 
 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.

Ссылки 
 
 
 
 
 

Криптография на решётках
Криптография