Falcon

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

Суть постквантового криптографического алгоритма состоит в том, чтобы продолжать обеспечивать свои характеристики безопасности даже при работе с квантовыми компьютерами. Квантовый компьютер очень эффективно взломал бы обычные алгоритмы асимметричного шифрования и цифровой подписи, основанные на теории чисел (RSA, DSA, Диффи-Хеллмана, Эль-Гамаля и их варианты на основе эллиптических кривых). Алгоритм основан на теоретической основе Джентри, Пейкерта и Вайкунтанатана для схем подписи на основе решетки. Структура реализуется поверх решеток NTRU. Название Falcon является аббревиатурой от Fast Fourier Attice-Based Compact Signs over NTRU .

Описание

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

С точки зрения безопасности NTRU обладает пониженной безопасностью по сравнению с моделью Quantum Random Oracle .

Основные характеристики алгоритма

Представлена эталонная реализация алгоритма на C и на Python.

• Безопасность: используется гауссов сэмплер, что гарантирует малую утечку информации о секретном ключе вплоть до практически бесконечного количества подписей (более 2⁶⁴ ).
• Компактность: благодаря использованию решеток NTRU подписи существенно короче, чем в любой схеме подписи на основе решеток с теми же гарантиями безопасности, а открытые ключи имеют примерно такой же размер.
• Скорость: использование быстрой выборки Фурье позволяет очень быстро реализовывать тысячи подписей в секунду на обычном компьютере, a проверка проходит в пять-десять раз быстрее.
• Масштабируемость: операции стоят O(n log n) для степени n , что позволяет использовать очень долговременные параметры безопасности при умеренных затратах.
• Экономия оперативной памяти: усовершенствованный алгоритм генерации ключей Falcon использует менее 30 килобайт оперативной памяти. Falcon совместим с небольшими встроенными устройствами с ограниченным объемом памяти.

Производительность

Используя эталонную реализацию на обычном настольном компьютере (Intel® Core® i5-8259U с тактовой частотой 2,3 ГГц, TurboBoost отключен), Falcon достигает следующей производительности:

Версия	Время генерации ключа (мс)	Пропускная способность (подписей/с)	Пропускная способность(проверок/с)	Размер сигнатуры (байт)
Falcon-512	8.64	5948.1	27930	666
Falcon-1024	27.45	2913.0	13650	1280

Смотрите также

• Постквантовая криптография
• Криптография на основе решетки

Примечания

1.↑ Thomas Prest; Pierre-Alain Fouque; Jeffrey Hoffstein; Paul Kirchner, Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU (PDF)

2. Falcon official website

3. List of NIST PQC selected candidates

4.↑ Craig Gentry; Chris Peikert; Vinod Vaikuntanathan (2008). Trapdoors for Hard Lattices and New Cryptographic Constructions. STOC.Trapdoors for Hard Lattices and New Cryptographic Constructions. STOC.

5.Dan Boneh; Özgür Dagdelen; Marc Fischlin; Anja Lehmann; Christian Schaffner; Mark Zhandry (2011). Random Oracles in a Quantum World. Asiacrypt.Random Oracles in a Quantum World. Asiacrypt.

6. Reference implementation of Falcon in C

7. Implementation of Falcon in Python

8. NIST Post-Quantum Cryptography Call for Proposals