Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

NTRUSign , также известный как алгоритм подписи 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 в пост-Quantum Cryptography стандартизации конкуренции. [5] Он основан на методологии «знак решетки» (противопоставление преобразования Фиата-Шамира ) и претендует на достижение меньшего размера подписи.

NTRUSign рассматривается для стандартизации рабочей группой IEEE P1363 . [ необходима цитата ]

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

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

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

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

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

  1. ^ Хоффштейн, Джеффри; Лиман, Даниэль; Сильверман, Джозеф Х. (1999). «Полиномиальные кольца и эффективная аутентификация с открытым ключом» (PDF) . Международный семинар по криптографическим методам и электронной коммерции (CrypTEC'99) . Городской университет Гонконгской прессы.
  2. ^ Хоффштейн, Джеффри; Хаугрейв-Грэм, Ник; Пайфер, Джилл; Сильверман, Джозеф Н .; Уайт, Уильям (2003). «NTRUSign: Цифровые подписи с использованием решетки NTRU» (PDF) . Темы в криптологии - CT-RSA 2003 . LNCS. 2612 . Springer. С. 122–140.
  3. ^ а б http://www.szydlo.com/ntru-revised-full02.pdf
  4. ^ a b П. Нгуен и О. Регев, «Изучение параллелепипеда: криптоанализ подписей GGH и NTRU», доступно по адресу https://cims.nyu.edu/~regev/papers/gghattack.pdf
  5. ^ "Пост-квантовое представление криптовалюты в NIST" . Безопасность на борту . Проверено 20 марта 2018 .
  6. ^ Ву, Хунцзюнь; Бао, Фэн; Е, Динфэн; Дэн, Роберт Х. (2000). «Криптоанализ схемы полиномиальной аутентификации и подписи» (PDF) . ACISP 2000 . LNCS. 1841 . Springer. С. 278–288.
  7. ^ Дукас, Лео; Нгуен, Фонг (2012). «Изучение зонотопа и многое другое: криптоанализ контрмер NTRUSign» (PDF) . ASIACRYPT 2012 . LNCS. 7658 . Springer. С. 433–450. DOI : 10.1007 / 978-3-642-34961-4_27 . Проверено 7 марта 2013 .

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

  • Самый последний документ NTRUSign, включая наборы параметров для нескольких уровней безопасности
  • Реализация NTRUSign на Java