Сокол (схема подписи)

Falcon — это схема постквантовой подписи, выбранная NIST на четвертом этапе процесса постквантовой стандартизации . Его разработали Томас Прест, Пьер-Ален Фук, Джеффри Хоффштейн , Пол Киршнер, Вадим Любашевский, Томас Порнин, Томас Рикоссет, Грегор Зайлер, Уильям Уайт и Женфэй Чжан. ^{[1] [2] [3]} Он основан на методе хеширования и знака в рамках Джентри , Пейкерта и Вайкунтанатана. структуры ^[4] над NTRU решетками . Название Falcon является аббревиатурой от Fast Fourier компактных основанных на решетках сигнатур над N TRU .

Характеристики

В основе конструкции Falcon лежит использование нескольких инструментов для обеспечения компактности и эффективности, а также доказуемой безопасности. Для достижения этой цели использование решетки NTRU позволяет сделать размер подписей и открытого ключа относительно небольшим, а быстрая выборка Фурье обеспечивает эффективные вычисления подписей. ^[5]

С точки зрения безопасности, структура Джентри, Пейкерта и Вайкунтанатана имеет пониженную безопасность по сравнению с моделью квантового случайного оракула . ^[6]

Реализации и производительность

Авторы Falcon предоставляют эталонную реализацию на C. ^[7] согласно требованиям NIST ^[8] и один на Python для простоты. ^[9]

Набор параметров, предложенный Falcon, подразумевает подписи размером 666 байт для уровня безопасности NIST 1 (безопасность сравнима со взломом AES -128 бит). Генерация ключа может выполняться за 8,64 мс с пропускной способностью примерно 6000 подписей в секунду и 28000 проверок в секунду. ^[10]

С другой стороны, уровень безопасности NIST 5 (сравнимый со взломом AES -256) требует подписи размером 1280 байт, времени генерации ключа менее 28 мс и пропускной способности 2900 подписей в секунду и 13650 проверок в секунду. ^[11]

См. также

• Постквантовая криптография
• Решеточная криптография
• НТРУ
• Стандартизация постквантовой криптографии NIST

Ссылки

1. ^ Томас Прест; Пьер-Ален Фуке; Джеффри Хоффштейн; Пол Киршнер; Вадим Любашевский; Томас Порнин; Томас Рикоссе; Грегор Зейлер; Уильям Уайт; Чжэнфэй Чжан, Falcon: компактные сигнатуры на основе решетки быстрого Фурье поверх NTRU (PDF)

2. ^ Официальный сайт Сокола

3. ^ Список выбранных кандидатов NIST PQC

4. ^ Крейг Джентри; Крис Пейкерт; Винод Вайкунтанатан (2008). Люки для жестких решеток и новые криптографические конструкции . СТОК.

5. ^ Дэн Бонех; Озгур Дагделен; Марк Фишлин; Аня Леманн; Кристиан Шаффнер; Марк Жандри (2011). Случайные оракулы в квантовом мире . Азиякрипт.

6. ^ Эталонная реализация Falcon на C

7. ^ Реализация Falcon на Python

8. ^ Прием предложений по постквантовой криптографии NIST