НТРУСайн

NTRUSign , также известный как алгоритм подписи NTRU , представляет собой NTRU с открытым ключом, алгоритм цифровой подписи основанный на схеме подписи GGH . Первоначальная версия NTRUSign представляла собой схему полиномиальной аутентификации и подписи ( PASS ) и была опубликована на CrypTEC'99. ^[1] Улучшенная версия PASS получила название NTRUSign, была представлена на итоговой сессии Asiacrypt 2001 и опубликована в рецензируемой форме на конференции RSA 2003. ^[2] Публикация 2003 года включала рекомендации по параметрам для 80-битной безопасности. В последующей публикации 2005 года были пересмотрены рекомендации по параметрам для 80-битной безопасности, представлены параметры, которые обеспечивают заявленные уровни безопасности 112, 128, 160, 192 и 256 бит, и описан алгоритм для получения наборов параметров на любом желаемом уровне безопасности. Компания NTRU Cryptosystems, Inc. подала заявку на патент на алгоритм.

NTRUSign включает в себя отображение сообщения в случайной точке в 2 N -мерном пространстве, где N — один из параметров NTRUSign, и решение ближайшей векторной задачи в решетке, тесно связанной с решеткой NTRUEncrypt . Утверждается, что NTRUSign работает быстрее этих алгоритмов на низких уровнях безопасности и значительно быстрее на высоких уровнях безопасности. Однако анализ показал, что исходная схема небезопасна и приведет к утечке секретного ключа. ^[3]^[4]

Модернизированный вариант pqNTRUSign был представлен на конкурс NIST по стандартизации пост-квантовой криптографии . ^[5] Он основан на методологии «хеш-и-знак» (в отличие от преобразования Фиата – Шамира ) и утверждает, что обеспечивает меньший размер подписи.

NTRUSign находится на рассмотрении рабочей группы IEEE P1363 на предмет стандартизации . ^{[ нужна ссылка ]}

Безопасность [ править ]

В 2000 году Ву, Бао, Йе и Дэн продемонстрировали, что подпись PASS, исходной версии NTRUSign, можно легко подделать, не зная закрытого ключа. ^[6] NTRUSign не является схемой подписи с нулевым разглашением , и расшифровка подписей приводит к утечке информации о закрытом ключе, как впервые заметили Джентри и Шидло. ^[3] Нгуен и Регев продемонстрировали в 2006 году, что для исходных неизмененных наборов параметров NTRUSign злоумышленник может восстановить закрытый ключ всего с 400 подписями. ^[4]

В текущих предложениях используются изменения для увеличения длины расшифровки, необходимой для восстановления закрытого ключа: подписывающий смещает точку, представляющую сообщение, на небольшую секретную величину, прежде чем будет вычислена сама подпись. NTRU заявил, что как минимум 2 ³⁰ необходимы подписи и, возможно, значительно больше, прежде чем расшифровка искаженных подписей позволит провести какую-либо полезную атаку. В 2012 году была представлена атака на схему с нарушениями, потребовавшая нескольких тысяч подписей для стандартных параметров безопасности. ^[7]

pqNTRUSign заявляет о 128-битной классической и квантовой безопасности для данного набора параметров.

Ссылки [ править ]

^ Хоффштейн, Джеффри; Лиман, Дэниел; Сильверман, Джозеф Х. (1999). «Полиномиальные кольца и эффективная аутентификация с открытым ключом» (PDF) . Международный семинар по криптографическим методам и электронной коммерции (CrypTEC'99) . Городской университет Гонконга Press.
^ Хоффштейн, Джеффри; Хоугрейв-Грэм, Ник; Пайфер, Джилл; Сильверман, Джозеф Х.; Уайт, Уильям (2003). «NTRUSign: цифровые подписи с использованием решетки NTRU» (PDF) . Темы криптологии — CT-RSA 2003 . ЛНКС. Том. 2612. Спрингер. стр. 122–140.
^ Jump up to: ^а ^б http://www.szydlo.com/ntru-revised-full02.pdf ^{[ пустой URL PDF ]}
^ Jump up to: ^а ^б П. Нгуен и О. Регев, «Изучение параллелепипеда: криптоанализ сигнатур GGH и NTRU», доступно по адресу https://cims.nyu.edu/~regev/papers/gghattack.pdf.
^ «Представление NIST Post Quantum Crypto» . Бортовая безопасность . Архивировано из оригинала 29 декабря 2017 г. Проверено 20 марта 2018 г.
^ У, Хунцзюнь; Бао, Фэн; Да, Динфэн; Дэн, Роберт Х. (2000). «Криптоанализ схемы полиномиальной аутентификации и подписи» (PDF) . АЦИСП 2000 . ЛНКС. Том. 1841. Спрингер. стр. 278–288.
^ Дукас, Лео; Нгуен, Фонг (2012). «Изучение зонотопа и многое другое: криптоанализ контрмер NTRUSign» (PDF) . АЗИЯКРИПТ 2012 . ЛНКС. Том. 7658. Спрингер. стр. 433–450. дои : 10.1007/978-3-642-34961-4_27 . Проверено 7 марта 2013 г.

Внешние ссылки [ править ]

[1] Хоффштейн, Джеффри; Лиман, Дэниел; Сильверман, Джозеф Х. (1999). «Полиномиальные кольца и эффективная аутентификация с открытым ключом» (PDF) . Международный семинар по криптографическим методам и электронной коммерции (CrypTEC'99) . Городской университет Гонконга Press.

[2] Хоффштейн, Джеффри; Хоугрейв-Грэм, Ник; Пайфер, Джилл; Сильверман, Джозеф Х.; Уайт, Уильям (2003). «NTRUSign: цифровые подписи с использованием решетки NTRU» (PDF) . Темы криптологии — CT-RSA 2003 . ЛНКС. Том. 2612. Спрингер. стр. 122–140.

[:0-3] Jump up to: ^а ^б http://www.szydlo.com/ntru-revised-full02.pdf ^{[ пустой URL PDF ]}

[:1-4] Jump up to: ^а ^б П. Нгуен и О. Регев, «Изучение параллелепипеда: криптоанализ сигнатур GGH и NTRU», доступно по адресу https://cims.nyu.edu/~regev/papers/gghattack.pdf.

[5] «Представление NIST Post Quantum Crypto» . Бортовая безопасность . Архивировано из оригинала 29 декабря 2017 г. Проверено 20 марта 2018 г.

[6] У, Хунцзюнь; Бао, Фэн; Да, Динфэн; Дэн, Роберт Х. (2000). «Криптоанализ схемы полиномиальной аутентификации и подписи» (PDF) . АЦИСП 2000 . ЛНКС. Том. 1841. Спрингер. стр. 278–288.

[7] Дукас, Лео; Нгуен, Фонг (2012). «Изучение зонотопа и многое другое: криптоанализ контрмер NTRUSign» (PDF) . АЗИЯКРИПТ 2012 . ЛНКС. Том. 7658. Спрингер. стр. 433–450. дои : 10.1007/978-3-642-34961-4_27 . Проверено 7 марта 2013 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]