Введение
NTRUSign, также известный как NTRU Signature Algorithm, является алгоритмом цифровой подписи на основе криптографии с открытым ключом NTRU, основанным на схеме подписи GGH. Первоначальная версия NTRUSign называлась Polynomial Authentication and Signature Scheme (PASS) и была опубликована на CrypTEC’99. Улучшенная версия PASS получила название NTRUSign и была представлена на rump session конференции Asiacrypt 2001 года и опубликована в рецензируемой форме на конференции RSA 2003 года. Публикация 2003 года содержала рекомендации по параметрам для обеспечения 80-битной безопасности. Последующая публикация 2005 года пересмотрела рекомендации по параметрам для 80-битной безопасности, представила параметры, обеспечивающие заявленные уровни безопасности 112, 128, 160, 192 и 256 бит, и описала алгоритм для получения наборов параметров с любым желаемым уровнем безопасности. Компания NTRU Cryptosystems, Inc. подала заявку на патент на этот алгоритм. NTRUSign предполагает отображение сообщения в случайную точку в 2N-мерном пространстве, где N – один из параметров NTRUSign, и решение задачи о ближайшем векторе в решетке, тесно связанной с решеткой NTRUEncrypt. Утверждается, что NTRUSign быстрее, чем другие алгоритмы при низких уровнях безопасности, и значительно быстрее при высоких уровнях безопасности. Однако анализ показал, что исходная схема небезопасна и может привести к раскрытию информации о секретном ключе. Алгоритм основан на методологии "хеширование и подпись" (в отличие от преобразования Фиата — Шамира) и заявляет о достижении меньшего размера подписи. NTRUSign находится на рассмотрении для стандартизации рабочей группой IEEE P1363.
NTRUSign, also known as the NTRU Signature Algorithm, is an NTRU public key cryptography digital signature algorithm based on the GGH signature scheme. The original version of NTRUSign was Polynomial Authentication and Signature Scheme (PASS), and was published at CrypTEC'99. The improved version of PASS was named as NTRUSign, and was presented at the rump session of Asiacrypt 2001 and published in peer reviewed form at the RSA Conference 2003. The 2003 publication included parameter recommendations for 80 bit security. A subsequent 2005 publication revised the parameter recommendations for 80 bit security, presented parameters that gave claimed security levels of 112, 128, 160, 192 and 256 bits, and described an algorithm to derive parameter sets at any desired security level. NTRU Cryptosystems, Inc. have applied for a patent on the algorithm. NTRUSign involves mapping a message to a random point in 2N dimensional space, where N is one of the NTRUSign parameters, and solving the closest vector problem in a lattice closely related to the NTRUEncrypt lattice. NTRUSign is claimed to be faster than those algorithms at low security levels, and considerably faster at high security levels. However, analysis had shown that original scheme is insecure and would leak knowledge of private key. It is based on "hash and sign" (contrasting Fiat–Shamir transformation) methodology, and claims to achieve smaller signature size. NTRUSign is under consideration for standardization by the IEEE P1363 working group.
Безопасность
В 2000 году У, Бао, Йе и Дэн показали, что подпись PASS, исходная версия NTRUSign, может быть легко подделана без знания секретного ключа. NTRUSign не является схемой цифровой подписи с нулевым разглашением, и протокол подписей раскрывает информацию о секретном ключе, как впервые отметили Джентри и Шидло. Нгуен и Регев продемонстрировали в 2006 году, что для исходных, невозмущенных наборов параметров NTRUSign злоумышленник может восстановить секретный ключ, имея всего 400 подписей. Современные реализации используют возмущения для увеличения длины протокола, необходимой для восстановления секретного ключа: подписывающий сдвигает точку, представляющую сообщение, на небольшую случайную величину перед вычислением самой подписи. NTRU утверждает, что для проведения какой-либо полезной атаки на основе протокола возмущенных подписей требуется как минимум 230 подписей, и, вероятно, значительно больше. В 2012 году была представлена атака на схему с возмущениями, для которой требовалось несколько тысяч подписей при стандартных параметрах безопасности. pqNTRUSign заявляет о 128-битной классической и квантовой безопасности для их заданного набора параметров.