Введение

Крыжовник - цифровая подпись, основанная на алгебраических решётках. Схема построена на парадигме Фиата-Шамира и сложности решения классических задач на решётках - LWR (Learning With Rounding, обучение с округлением) и SIS (Shortest Integer Solution, нахождение короткого целочисленного решения) в модулях над кольцом целых чисел кругового расширения. В кратком виде со схемой можно познакомится в презентации, текущую версию схемы можно найти здесь.

Безопасность

Предлагаемые параметры цифровой подписи и их уровни безопасности (классические/квантовые) представлены в следующей таблице.

Название \(n\) \(k\) \(\ell\) \(\nu\) \(\mu\) \(w\) \(s\) \(d\) \(\gamma\) #итераций MSIS MLWR MSIS (квант.) MLWR (квант.)
Крыжовничек
(70 / 65 бит безоп.) 		256 3 2 23 19 20 4 3 1048096 2.7 84 70 77 65
Крыжовник
(116 / 106 бит безоп.)		 256 4 3 23 19 39 4 3 1048096 12.9 120 116 110 106
Крыжовнище
(161 / 147 бит безоп.)		 256 4 3 23 19 50 4 3 1048096 60.8 164 161 150 147

В обоих случаях мы полагаем (консервативно), что сложность нахождения короткого вектора в решетке размерности \(d\) равна \(8d\cdot2^{0.292d }\), что асимптотически соответствует сложности классического алгоритма просеивания.


Скрипт для рассчёта параметров доступен по ссылке . Для его работы необходим файл estimator.py проекта Estimate all the {LWE, NTRU} schemes!

Реализация

Экспериментальную (неоптимизированную) реализацию Крыжовника на C/C++ можно найти в открытом доступе в репозитории Github под лицензией GNU GPL v3.

В следующей таблице представлены размеры ключей и подписи в сравнении с одним из набором параметров подписи Dilithium, сопоставимым по уровню безопасности. Также представлено среднее время работы алгоритмов подписи.

\(|\textsf{sk}|\) \(|\textsf{vk}|\) \(|\textsf{sig}|\) \(\textsf{KeyGen}\) \(\textsf{Sign}\) \(\textsf{Verif}\)
Крыжовничек 3k 2.4k 1.9k 2.08M 24.6M 2.6M
Dilithium 2.05k 1.2k 2.0k 133k 700k 150k

Время работы алгоритмов \(\textsf{KeyGen}\), \(\textsf{Sign}\), \(\textsf{Verif}\) дано в числе тактов ЦП Intel Xeon(R) E-2146G 3.50GHz x 12. Измерение среднего значения времени было произведено на \(N=1000\) тестах. Заметим, что для ускорения работы могут использоваться наработки из схемы KEM Saber, так как она основана на той же задаче LWR.

Публикации и доклады

  • Е. А. Киршанова, Н. С. Колесников, Е. С. Малыгина, С. А. Новоселов, “Проект стандартизации постквантовой цифровой подписи”, ПДМ. Приложение, 2020, № 13, 44–51. SibeCrypt'20. [MathNet]. Полная версия: PDF.
  • Киршанова Е., Колесников Н., Малыгина Е., Новосёлов С. "Цифровая подпись на алгебраических решётках" [доклад]. PDF.

Список дел

  • ускорение скорости работы схемы, добавление оптимизаций из Saber
  • уточнение битовой сложности

Контакты

Разработчики: