Введение

Криптосистема с открытым ключом, использующая криптографию на решётках.

NTRU — это криптосистема с открытым исходным кодом и открытым ключом, использующая криптографию на решётках для шифрования и расшифровки данных. Она состоит из двух алгоритмов: NTRUEncrypt, предназначенного для шифрования, и NTRUSign, предназначенного для цифровых подписей. В отличие от других популярных криптосистем с открытым ключом, она устойчива к атакам с использованием алгоритма Шора. NTRUEncrypt был запатентован, но в 2017 году перешел в общественное достояние. NTRUSign запатентован, однако его можно использовать в программном обеспечении под лицензией GPL.

История

Первая версия системы, получившая название NTRU, была разработана в 1996 году математиками Джеффри Хоффштейном, Джилл Пиффер и Джозефом Сильверманом. В том же году разработчики NTRU объединились с Дэниелом Лиманом и основали компанию NTRU Cryptosystems, Inc., получив патент на криптосистему. Название "NTRU", выбранное для компании и вскоре применённое и к системе, изначально произошло от каламбура "Number Theorists 'R' Us" или, альтернативно, расшифровывалось как "Number Theory Research Unit" (Исследовательский отдел теории чисел). В 2009 году компания была приобретена корпорацией Security Innovation, специализирующейся на безопасности программного обеспечения. В 2013 году Дэмиен Стел и Рон Штейнфельд создали версию NTRU с доказанной безопасностью, которая добавляет защиту от потенциальных атак, устраняя алгебраическую структуру, вызывавшую у них опасения. Однако, несмотря на более чем 20 лет исследований, до сих пор не был найден конкретный способ атаки на оригинальный NTRU, использующий его алгебраическую структуру. NTRU стал финалистом в третьем раунде проекта по стандартизации постквантовой криптографии, а NTRU Prime – альтернативным кандидатом.

Выступление

При эквивалентной криптографической стойкости NTRU выполняет ресурсоемкие операции с закрытым ключом значительно быстрее, чем RSA. Время выполнения операции дешифрования RSA возрастает пропорционально кубу размера ключа, в то время как время выполнения операции NTRU возрастает квадратично. В 2010 году Департамент электротехники Университета Лёвена отметил, что "[при использовании] современной видеокарты GTX280 можно достичь пропускной способности до 200 000 шифрований в секунду при уровне безопасности 256 бит. Если сравнивать это с симметричным шифром (что является не совсем обычным сравнением), то это всего лишь примерно в 20 раз медленнее, чем современная реализация AES".

Устойчивость к атакам на основе квантовых компьютеров

В отличие от RSA и криптографии на эллиптических кривых, NTRU, насколько известно, не уязвим для атак с использованием квантовых компьютеров. В обзоре 2009 года Национальный институт стандартов и технологий отметил, что "существуют жизнеспособные альтернативы как для шифрования с открытым ключом, так и для электронных подписей, которые не уязвимы для алгоритма Шора", и что "из различных криптографических схем, основанных на решётках, которые были разработаны, семейство криптографических алгоритмов NTRU представляется наиболее практичным". Проект Европейского Союза PQCRYPTO (Horizon 2020 ICT 645622) оценивает версию NTRU Stehle–Steinfeld, обладающую доказанной безопасностью (а не оригинальный алгоритм NTRU), в качестве потенциального европейского стандарта. Однако версия NTRU Stehle–Steinfeld "значительно менее эффективна, чем исходная схема".