Русская Википедия:Falcon (криптоалгоритм)
Шаблон:Значения Falcon (Шаблон:Lang-en) — постквантовый алгоритм криптографической подписи поверх решёток Шаблон:Iw.
Представлен в Шаблон:Iw 30 ноября 2017 года, авторы — Томас Прест, Пьер-Ален Фуке, Джеффри Хоффштейн, Полом Киршнер, Вадим Любашевский, Томас Порнин, Томас Рикоссе, Грегор Зайлер, Уильям Уайт, Чжэнфей Чжан. Использует преимущества нескольких инструментов для обеспечения компактности и эффективности с доказуемой безопасностью. Использование решётки NTRU позволяет сделать размер подписи и открытого ключа относительно небольшим, в то время как быстрое преобразование Фурье обеспечивает эффективное вычисление подписи. При этом с точки зрения безопасности NTRU обладает пониженной безопасностью по сравнению с моделью квантового случайного оракула.
Эталонные реализации выполнены на Си и Python.
Свойства
Для обеспечения безопасности используется гауссов семплер, что гарантирует малую утечку информации о секретном ключе вплоть до практически бесконечного количества подписей (более 264). Компактность обеспечивается благодаря использованию решёток NTRU — подписи существенно короче, чем в любой схеме подписи на основе решёток с теми же гарантиями безопасности, а открытые ключи имеют примерно такой же размер.
Алгоритм масштабируем — его асимптотическая сложность <math>O(n \log n)</math> позволяет использовать долговременные параметры безопасности при умеренных затратах. Усовершенствованный алгоритм генерации ключей 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 являются многочлены степени <math>n</math> с целыми коэффициентами. Степень <math>n</math> обычно является степенью двойки (обычно 512 или 1024). Вычисления производятся по модулю многочлена одной переменной степени <math>n</math>, обозначаемого <math>\phi</math> (который всегда имеет вид <math>\phi = x^{n} + 1 </math>).
Математически в алгоритме некоторые многочлены интерпретируются как векторы, а другие – как матрицы. Полином <math>f</math> по модулю <math>\phi</math> обозначает квадратную матрицу <math>n \times n</math>, строками которой являются <math>x^{i}f \pmod \phi </math> для всех <math>i</math> от 0 до <math>n-1</math>. Сложение и умножение таких матриц сводится к сложению и умножению многочленов по модулю <math>\phi</math>. Поэтому Falcon реализован в терминах операций над многочленами, даже в операциях с матрицами, определяющими решётку.
Генерация ключевой пары
Генерация ключевой пары включает в себя генерацию случайных многочленов <math>f</math> и <math>g</math> с простым распределением гаусса и решение уравнения NTRU для вычисления <math>F</math> и <math>G</math>. Генерация <math>f</math> и <math>g</math>:
- генерируется случайный бит <math>s</math>, а также случайная величина <math>v_0</math>; если <math>v_0</math> меньше заданной константы <math>c_0</math>, то коэффициент будет равен нулю;
- Генерируется случайное 63-битное значение <math>v_{1}</math>, и используется таблица констант: получается индекс <math>k</math> первого значения <math>c_{k}</math>, которое не больше <math>v_{1}</math> (элементы таблицы индексируются, начиная с 1, и идут по убыванию, последний равен 0, что гарантирует уникальность решения).
- если <math>v_0 < c_0</math>, то новый коэффициент многочлена равен 0; в противном случае его значение равно <math>(-1)^{s}k </math>; все операции выполняются систематически, то есть тест на <math>v_{0}</math> выполняется в постоянном времени, а поиск <math>v_{1}</math> в таблице выполняется всегда, независимо от результата теста на <math>v_{0}</math>; поиск в таблице выполняется путем чтения всех элементов таблицы;
- решении уравнения NTRU; при решении уравнения NTRU вычисляются многочлены различных степеней, коэффициенты которых являются большими целыми числами; используется RNS (система остаточных чисел) для больших целых чисел, поэтому работа происходит с ожидаемой длиной целых чисел, а не с их истинной длиной.
В итоге, открытый ключ <math>pk </math>, соответствующий закрытому ключу <math>sk = (f, g, F, G)</math> – это многочлен <math>h \in Z_{q} [x]/(\phi) </math> такой, что:
- <math>h = gf^{-1} \pmod {\phi,q} </math>.
После получения подходящих многочленов <math>f</math>, <math>g</math>, <math>F</math>, <math>G</math>, вторая часть генерации ключа заключается в их обработке в подходящий формат. Под подходящим форматом подразумевается, компактность и возможность быстро генерировать подписи. К такому формату можно прийти с помощью Falcon-дерева. Чтобы вычислить Falcon-дерево, нужно вычислить <math>LDL^*</math>-разложение <math>G=BB^*</math>, где:
- <math>B = \ \ \ \begin{vmatrix}g\ \ -f\\
G\ \ \ \ F\end{vmatrix} </math>. Это эквивалентно вычислению ортогонализации Грамма — Шмидта для <math>B = L \times B</math>.
Вычисление подписи
Принцип алгоритма создания подписи:
- вычисление хэш-значение <math>c \in Z_{q} [x]/(\phi)</math> из сообщения <math>m</math> и модификатора входа хэш-функции <math>r</math>.
- вычисление двух коротких значений <math>s_1</math> и <math>s_2</math>, таких, что <math>s_1 + s_2 h = c \pmod q</math>, используя знание секретного ключа <math>f, g, F, G</math>.
Преимущества и недостатки
Главными преимуществами алгоритма являются компактность, быстрота и несколько режимов работы (классический, режим восстановления сообщения, режим восстановления ключа). Кроме того, Falcon можно превратить в схему IBE (шифрование на основе идентификации) и в схему кольцевой подписи. Falcon является самой компактной схемой из всех постквантовых схем подписи. Но существуют и недостатки, в первую очередь это сложность для понимания и реализации и плохая устойчивость побочного канала к перехвату.
Сравнение размера открытого ключа с другими алгоритмами подписи на уровне NIST 5 (размеры в байтах): <graph>{ "version": 2, "width": 1100, "height": 200, "data": [ { "name": "table", "values": [ { "x": "RSA-4096", "y": 800 }, { "x": "ECDSA-256", "y": 900 }, { "x": "DILITHIUM", "y": 1200 }, { "x": "Dual ModeMS", "y": 1200 }, { "x": "Falcon", "y": 1100 }, { "x": "MQDSS", "y": 100 }, { "x": "pqNTRUSign", "y": 3000 }, { "x": "Picnic", "y": 90 }, { "x": "qTESLA", "y": 9500 }, { "x": "SPHINCS+", "y": 90 } ] } ], "scales": [ { "name": "x", "type": "ordinal", "range": "width", "zero": false, "domain": { "data": "table", "field": "x" } }, { "name": "y", "type": "linear", "range": "height", "nice": true, "domain": { "data": "table", "field": "y" } } ], "axes": [ { "type": "x", "scale": "x" }, { "type": "y", "scale": "y" } ], "marks": [ { "type": "rect", "from": { "data": "table" }, "properties": { "enter": { "x": { "scale": "x", "field": "x" }, "y": { "scale": "y", "field": "y" }, "y2": { "scale": "y", "value": 0 }, "fill": { "value": "steelblue" }, "width": { "scale": "x", "band": "true", "offset": -1 } } } } ] }</graph>Сравнение размера подписи с другими алгоритмами подписи на уровне NIST 5 (размеры в байтах): <graph>{ "version": 2, "width": 1100, "height": 200, "data": [ { "name": "table", "values": [ { "x": "RSA-4096", "y": 800 }, { "x": "ECDSA-256", "y": 900 }, { "x": "DILITHIUM", "y": 1200 }, { "x": "Dual ModeMS", "y": 1400 }, { "x": "Falcon", "y": 1050 }, { "x": "MQDSS", "y": 100 }, { "x": "pqNTRUSign", "y": 80000 }, { "x": "Picnic", "y": 100000 }, { "x": "qTESLA", "y": 9000 }, { "x": "SPHINCS+", "y": 80000 } ] } ], "scales": [ { "name": "x", "type": "ordinal", "range": "width", "zero": false, "domain": { "data": "table", "field": "x" } }, { "name": "y", "type": "linear", "range": "height", "nice": true, "domain": { "data": "table", "field": "y" } } ], "axes": [ { "type": "x", "scale": "x" }, { "type": "y", "scale": "y" } ], "marks": [ { "type": "rect", "from": { "data": "table" }, "properties": { "enter": { "x": { "scale": "x", "field": "x" }, "y": { "scale": "y", "field": "y" }, "y2": { "scale": "y", "value": 0 }, "fill": { "value": "steelblue" }, "width": { "scale": "x", "band": "true", "offset": -1 } } } } ] }</graph>
Литература
- Шаблон:Citation
- Шаблон:Cite conference
- Шаблон:Cite conference
- 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.
Ссылки
