Обеспечение NTRU безопасностью уровня задач над идеальными решетками наихудшего сценария

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:48, 27 сентября 2015.
Making NTRU as Secure as Worst-Case Problems over Ideal Lattices
NTRU.PNG
Авторы Damien Stehle[@: 1],
Ron Steinfeld[@: 2]
Опубликован 2011 г.
Сайт Homepage of Damien Stehle, Homepage of Ron Steinfeld
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал


Аннотация. NTRUEncrypt, предложенный в 1996 г. Хоффстайном, Пифером и Силверманом, среди известных схем шифрования, основанных на использовании решеток, является наиболее быстрой. Умеренные размеры ключа, отличная асимптотическая производительность и гипотетическое сопротивление атакам с помощью квантовых компьютеров предоставляют превосходную альтернативу схемам шифрования, основанным на использовании факторизации и дискретного логарифмирования. Однако, с момента официального представления был поднят ряд сомнений насчет безопасности. В представленной работе будут рассмотрены варианты изменения NTRUEncrypt с целью обеспечения доказуемой безопасности типовой модели при заданной квантовой стойкости задачи над типовыми решетками наихудшего сценария, приведенных к семейству решеток, связанных с некоторыми циклическими полями. Нашим основным вкладом будет являться освещение того факта, что в случае выбора полиномов закрытого ключа с помощью отклонения от дискретной нормы Гаусса открытый ключ, являющийся их коэффициентом, будет статистически неотличим от равномерного распределения на области определения. Безопасность следует из уже доказанной стойкости задачи R-LWE.
Ключевые слова: основанная на использовании решеток криптография, NTRU, доказуемая безопасность.

__NUMBEREDHEADINGS__

Введение

NTRUEncrypt, разработанный Хоффстайном, Пифером и Силверманом, был впервые представлен публике на дополнительной сессии Crypto'96 [1]. Несмотря на то, что описание основывалось на вычислениях над кольцом многочленов , где - простое число, - малое целое число, решение было признано настолько значимым, что с помощью него можно было выразить задачу над Евклидовыми решетками. [2]. На конференции ANTS'98 авторы NTRU представили усовершенствованную презентацию, включающую в себя исчерпывающую оценку практической безопасности против основанных на использовании решеток атак [3]. Мы будем ссылаться на следующий материал [4] для современной оценки анализов безопасности и производительности последних 15 лет. В настоящее время NTRUEncrypt является здравой альтернативой схемам шифрования, основанным на целочисленной факторизации и дискретном логарифмировании над конечными полями и эллиптическими кривыми, что отмечено его включением в стандарт IEEE P1363 [5]. Также его считают жизнеспособным решением постквантового шифрования с открытым ключом. [6]

В то время как число атак и практических улучшений NTRUEncrypt росло, то (в основном) теоретическая часть криптографии с доказуемой безопасностью, основанная на использовании решеток, остановилась в развитии. Точкой отсчета является 1996 год и признанное преобразование Аджтая наихудшего сценария в нормальный[7], породившее устойчивые к коллизиям хэш функции, взлом которых настолько сложен, насколько сложен взлом некоторых задач над решетками наихудших сценариев. Задачу Аджтая о нормальном сценарии в настоящее время называют Решением Малого Целого (от англ. Small Integer Solution problem - SIS). Еще одной важной вехой в данной области был 2005 год и озвучивание Реджевом задачи Изучения с Ошибками (от англ. Learning with Errors - LWE)[8]:LWE является одновременно надежным в нормальных сценариях (задачи наихудщих сценариев над решетками квантово сводятся к этому) и значительно гибким в плане реализации криптографических функций. В последние пару лет было представлено большое число криптографических схем, имеющих доказуемую безопасность уровня LWE и стойкость уровня SIS (и, поэтому, являются доказуемо безопасными при условии стойкости в задачах наихудшего сценария над решетками). В этот список входят безопасные схемы шифрования CPA и CCA, основанные на подлинности схемы шифрования, цифровые подписи и т.д. ([8],[9], [10], [11], [12], а также [13], [14]).

Основным препятствием для основанной на LWE и SIS криптографии является ограниченная эффективность. Ключ в большинстве случаев содержит случайную матрицу, заданную над для малого , размеры для параметра безопасности линейны; следовательно, требования к пространству и времени как минимум второй степени по отношению к параметру безопасности. В 2002 году Миччианчио[15] преуспел в сведении SIS к структурированным матрицам, при этом сохраняя преобразование наихудшего сценария в нормальный. Задача о наихудшем сценарии является сведением задач о типовых решетках к особому семейству циклических решеток. Структура матриц Миччианчио позволяет интерпретацию в рамках вычислений в кольце , где - размер решетки при наихудшем сценарии, - малое простое число. Труды Миччианчио привели к образованию семейства хэш-функций, устойчивых к атакам нахождения прообраза со сложностью квазилинейной в . Пейкерт, Розен, Любашевский и Миччианчио [16] позднее предложили рассматривать кольцо , где - неприводимый над множеством целых чисел разреженный многочлен с малыми коэффициентами (например, , для , являющегося степенью 2). Доказано, что получившаяся хэш-функция является устойчивой к коллизиям при заданной стойкости измененной задачи о нормальном сценарии; она была названа Ideal-SIS. Она обеспечивает ту же стойкость, что и сведение задачи о наихудшем сценарии над типовыми решетками к особому классу решеток (называемых идеальными). В 2009 году Штеле и др. [17] структурированный вариант LWE, оказавшийся таким же надежным, как и Ideal-SIS (при квантовом сведении), который позволял создавать асимптотически эффективные CPA-безопасные схемы шифрования. Параллельно, Любашевский и др в своей независимой работе[18] предложили вариант LWE на кольцах, названный R-LWE, чья большая гибкость позволяет создавать более естественные (и эффективные) криптографические конструкции.

Наши результаты. Высокая эффективность и промышленная стандартизация NTRUEncrypt сильно мотивировали изучение теоретических сторон безопасности. Более того, отсутствие такого исследования означает то, что безопасность была под сомнением на протяжении последних 15 лет. В данной работе данная проблема является адресованной. Мы приведем доказательство того, что умеренное изменение NTRUEncrypt является CPA-безопасным, при условии квантовой стойкости задач над идеальными решетками наихудшего сценария (для , для , являющегося степенью 2). Изменения в NTRUEncrypt приведены ниже. Напоминаем, что нашей основной задачей в данной работе является твердое доказательство теоретических оснований для безопасности NTRUEncrypt в асимптотическом плане. Мы обойдем стороною вопрос рассмотрения практических случаев, в частности, выбора конкретных параметров для заданных уровней безопасности. Что касается схем, основанных на использовании решеток, то в данном случае требуется оценка безопасности против атак, основанных на сокращении решеток, которые в данной работе не рассматриваются.

Нашим основным вкладом является изменение и анализ алгоритма генерации ключей. Закрытый ключ состоит из двух разреженных многочленов степени меньше и коэффициентами . Открытый ключ является их частным в поле (в том случае, если делитель не является необратимым, выборка производится заново). Простой информационно-теоретический аргумент показывает, что открытый ключ не может быть равномерно распределен по всему кольцу. Существует возможность расширить результаты работы [19], чтобы показать, что он "хорошо распространен" в кольце, но этого все равно не достаточно для убеждения в его криптографической псевдослучайности, что является необходимым условием для использования признанной стойкости R-LWE. Для того, чтобы распределение открытого ключа было статистически близким к равномерному, возьмем многочлены закрытого ключа в соответствии с дискретной нормой Гаусса с типовым отклонением . Важно отметить новую регулярность для кольца , где многочлен (, является степенью 2) имеет множителей по модулю простого числа : равномерно распределив в , нам бы хотелось, чтобы находилась на экспоненциально близком статистическом расстоянии от равномерного распределения, - случайное малое число, - малое число. Отметим, что схожие пределы регулярности могут получиться с помощью основанного на FFT метода, недавно представленного Любашевским, Пейкартом и Реджевым[20]. Дополнительную сложность для доказательства "равномерности" открытого ключа, которое мы вывели с помощью метода включения-исключения, является необходимость быть обратимыми в (делитель открытого ключа и является одним из таких ): таким образом мы производим выборку в соответствии с дискретной нормой Гаусса и не рассматриваем ее в случае отсутствия необратимости.

Краткое сравнение NTRUEncrypt и его доказуемо безопасной вариации

Пусть принадлежит кольцу , где - простое число. Пусть - целое число среднего размера, обычно являющееся степенью 2 того же порядка величины, что и . Наконец, пусть многочлен с малыми коэффициентами, взаимно простым с и таким, что пространство открытых текстов является большим. Обычно принимают или .

Закрытый ключ NTRUEncrypt представляет из себя пару многочленов , случайно выбранных с ранее заданными большими порциями нулей, их остальные коэффициенты лежат в . Для повышения эффективности дешифрования можно задать как . С большой вероятностью многочлен является обратимым по модулю и (в противном случае процесс генерация ключей начинается заново). Для того, чтобы зашифровать сообщение требуется провести случайную выборку элемента малой Евклидовой нормы и вычислить шифртекст . Следующий алгоритм позволяет обладателю закрытого ключа произвести дешифрование:

  • Вычислить . Если было верно сгенерировано, получим . Так как имеют малые коэффициенты, то логично ожидать, что после сокращения по модулю полученный результат будет .
  • Сократим последний результат по модулю . Результат должно быть равен .
  • Умножим результат предыдущего шага на инверсию (этот шаг является бессмысленным, если .

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

Для того, чтобы достичь CPA-безопасности, внесем некоторые изменения в NTRUEncrypt (который сохраняет свое квазилинейную сложность времени и пространства):

  1. Заменим на , является степенью 2. Используем неприводимость и тот факт, что - кольцо целых чисел циклического числового поля.
  2. Выберем простое , такое что имеет различных линейных множителей (например, ). Это позволит нам привести путем перебора R-LWE к кольцу [18], а также принять .
  3. Выберем из дискретной нормы Гаусса над , отбрасывая выборки, не являющиеся необратимыми над . Покажем, что существенным образом равномерно распределен над множеством обратимых элементов из . Можем также выбрать c выборкой из дискретной нормы Гаусса для упрощения дешифрования.
  4. Добавим малую величину ошибку в шифрование: , где выбраны из распределения ошибок R-LWE. Это позволяет нам получить CPA-безопасность из стойкостивариации R-LWE (схожей с вариацией LWE из [21]).

Текущие достижения и нерешенные проблемы

Данная работа не выходит за рамки колец является степенью 2. Очевидным недостатком является недостаток гибкости при выборе (в случае NTRU за степень берется заданное простое число, что предоставляет больше свободы). Задача R-LWE известна как стойкая, когда - циклический[18]. Решение обойтись циклическими многочленами порядка степени 2 обусловлено тем, что генерация ошибок R-LWE более эффективная, а описание схем - более простое. Немаловероятно, что полученные нами результаты могут быть верными и для более типовых колец. Интересным решением могут являться циклические кольца простого порядка (например, - простое), т.к. они являются большими подкольцами колец NTRU (можно показать, что стойкость сохраняется и на кольцах NTRU).

Занятной нерешенной проблемой является получение вариации CCA-безопасности нашей схемы в типовой модели при сохранении эффективности (с постоянными множителями). Выбор конкретных параметров, основанный на практической безопасности из предположения наихудшего сценария для SVP на идеальных решетках или нормального сценария стойкости R-LWE / Ideal-SIS, в данной работе также не рассматривается.

Авторы NTRUEncrypt также предложили схему подписи, основанную на схожей модели. История NTRUSign берет старт с NSS в 2001 году[22]. Его развитие было значительно более лихорадочным и противоречивым, с рядом криптоанализов и исправлений[4]. В результате нами был получен вариант NTRUSign с невозможностью подделки, относящийся к стойкости наихудшего сценария типовых задач над идеальными решетками в случай модели оракула. Мы изменили генерацию ключей NTRUSign и применили схему подписей GPV[10].

Равно как и NTRUEncrypt, гомоморфная схема Гентри[23] также имеет шифртексты, состоящие из единого элемента кольца. Она также допускает доказательство обеспечения безопасности при заданной квантовой стойкости типовых задач над идеальными решетками наихудшего сценария[24]. В соответствии с нашей оценкой безопасности измененная схема NTRUEncrypt позволяет шифровать и дешифровать бит открытых текстов за битовых операций, при этом достигая безопасности против -временных атак, для любого , что и для заданной стойкости наихудшего сценария -Ideal-SVP против -временных квантовых алгоритмов. Последнее положение считается верным для любого . Анализ Гентри[24], [25] можно свести к сопротивлению -временным атакам во время шифрования и дешифрования битов шифртекста за битовых операций при заданной стойкости -Ideal-SVP против -временных алгоритмов. Последнее положение считается неверным, когда [26], тем самым ограничивая силу нарушителя, с которой может справиться анализ. С другой стороны, схема Гентри является гомоморфной для операций сложения и умножения, в то время как наша ограничивается операцией сложения. Наша схема и схема Гентри выглядят очень схожими, но изучение связи между ними в данной работе рассматриваться не будет.

Замечание. Обозначим за соответственно) типовую -размерную Гауссову функцию (и, соответственно, распределение) с центром в 0 и отклонением , то есть (соответственно . Обозначим за экспоненциальное распределение на множестве целых чисел, где - ничтожно мала, и за - равномерное распределение на конечном множестве . Если - два распределения на изолированной области распределения , их статистическим расстоянием будет являться . Мы будем использовать запись , когда случайная переменная выбирается из распределения .

Примечание. В связи с ограничениями на размеры работы некоторые доказательства были опущены; они могут быть найдены в полной версии данной работы, доступной на сайтах авторов.

Предварительные знания

Решеткой (полного ранга) называют множество вида , где - линейные независимые вектора из . Целое называют размером решетки, - базисом . Минимумом ( соответственно) называют Евклидову (бесконечную соответственно) норму самого короткого вектора из . Если - базис матрицы , то базисным параллелепипедом называют множество . Модуль определителя является инвариантом решетки , который мы обозначим . -ый минимум для определяется как наименьшее , такое что содержит линейных независимых векторов нормы . Обратной к называют решетку .

Для решетки и зададим Гауссово распределение для решеток с носителем , отклонением и центром как . Опустим в случае, когда он равен . Расширим определение для любого (не обязательно подрешетка) задав . Для зададим параметр сглаживания как наименьшее такое что . Он измеряет то, насколько большим должен быть , чтобы вел себя как непрерывное распределение Гаусса. Обычно берется .

TemplateLemmaIcon.svg Лемма «Лемма 1 ([[27], Лемма 3.3]).»
Для любой полноранговой решетки


TemplateLemmaIcon.svg Лемма «Лемма 2 ([[28], Лемма 3.5]).»
Для любой полноранговой решетки


TemplateLemmaIcon.svg Лемма «Лемма 3 ([[27], Лемма 4.4]).»
Для любой полноранговой решетки


TemplateLemmaIcon.svg Лемма «Лемма 4 ([[10], Поправка 2.8]).»
Пусть - полноранговая матрица. Для любого


TemplateLemmaIcon.svg Лемма «Лемма 5 ([[10], Теорема 4.1]).»
Существует выполнимый за полиномиальное время алгоритм, на вход которого подается любой базис любой решетки ( соответственно) и выдает выборку из распределения, статистическим расстоянием которого до можно пренебречь (соответственно, экспоненциально мало) по отношению к .


Наиболее известной задачей над решетками является SVP. Рассматривая в качестве базиса решетку , он нацелен на поиск наименьшего вектора в . Его можно упростить до -SVP путем поиска ненулевого вектора, который не более, чем в раз длиннее решения, полученного SVP для заданной функции . Принято считать, что не существует субэкспоненциального квантового алгоритма, решающего вычислительные вариации -SVP в наихудшем сценарии для любой . Наименьшая среди известных достижимых за полиномиальное время является показательной функцией, вплоть до поли-логарифмических множителей в показателе степени.[26][29]

Идеальные решетки и Алгебраическая теория чисел

Идеальные решетки. Пусть - степень 2, а (неприводимый над ). Пусть - кольцо . - (целый) идеал , является подмножеством , замкнутое относительно операций сложения и умножения на случайные элементы из . Отображая многочлена в вектора отметим, что идеал соответствует полноранговой подрешетке : таким образом, мы можем рассматривать и как решетку, и как идеал. Идеальной решеткой является подрешетка из , которая соответствует ненулевому идеалу . Алгебраическая норма равна мощности аддитивной группы . Она эквивалентна , где рассматривается как решетка. Любой ненулевой идеал удовлетворяет . Далее под идеальной решеткой будем подразумевать -идеальную решетку.

Сводя SVP (и, соответственно, -SVP) к случаям, которые являются идеальными решетками, мы получаем Ideal-SVP (и, соответственно, -Ideal-SVP). Последнее неявно задается последовательностью многочленов , где - степень 2. Не известны алгоритмы, способные работать значительно лучше для (-)Ideal-SVP, чем для (-)SVP.

Свойства кольца . Для обозначим за его Евклидову норму (вектор). Определим мультипликативный множитель расширения как . Учитывая наш выбор , получим, что ([23], стр. 174).

Так как -циклический многочлен, то кольцо - максимального порядка (т.е. кольцо целых чисел) циклического поля , где - примитивный корень из единицы. Обозначим за канонические комплексные вложения: мы можем выбрать . в определим его норму как и его алгебраическую норму . Из арифметико-геометрического неравенства следует . Также, для тех циклических полей, которые мы рассматриваем, полиномиальная норма (норма вектора коэффициентов , выраженных как элементы из ) удовлетворяет . Также мы используем тот факт, что , где - идеал , образованный . Говоря более простыми словами, мы попытаемся использовать терминологию многочленов везде, где это будет возможно.

Пусть - простое число, такое что имеет различных линейных множителей по модулю (например, ): . Пусть . По теореме Дирихле в такой арифметической прогрессии существует бесконечное число простых чисел. Более того, по теореме Линника наименьший является , и много усилий было потрачено на уменьшение этой границы (текущий рекорд - [30]. Более того, мы можем записать как , где - примитивный корень из единицы по модулю . Это значит, что Китайская теорема об остатках в позволяет быстрое дискретное преобразование Фурье, поэтому произведение элементов в может быть выполнено за операция сложения и умножения по модулю ([31], Глава 8, [32], Раздел 2.1).

Задача R-LWE

Для и - распределение в определим как распределение, полученное выборкой пары () с . Задача R-LWE была представлена Любашевским и др.[18], а также была показана стойкость к определенным распределениям ошибок . Определения слегка формальные (см. ниже), в рамках данной работы важно помнить то, что выборки малы и могут быть получены за квазилинейное время.

Распределения ошибок , которые используются нами, являются адаптацией представленных ранее[18]. Они являются результатом выборки из семейства распределений , определение которому дано ниже. Для с положительными координатами определим эллипсоидальное распределение Гаусса как ряд векторов независимых распределений Гаусса (), где . Так как мы хотим определить R-LWE как полиномиальное выражение вместо так называемого "пространства [18], мы применим матричное преобразование к крайним распределениям Гаусса. Определим выборку из как выборку из , помноженную сначала (справа) на , а затем на . Отметим, что произведение векторов на матрицу соответствует комплексному дискретному преобразованию Фурье и может быть выполнено за комплекснозначных арифметических операций алгоритмом БПФ Кули-Таки. Более того, в числовом отношении это крайне устойчиво: если все операции выполняются с точностью до бит, то на выходной вектор будет удовлетворять , где - некоторая абсолютная константа и - вектор, полученный с помощью таких вычислений. Подробнее в этом источнике([33], Раздел 24.1). Теперь определим выборку из : вычислим выборку из с абсолютной ошибкой ; если результат лежит на расстоянии от двух идущих друг за другом целых чисел, то начинаем заново; в противном случае округлим до ближайшего целого числа и возьмем по модулю . Наконец, выборку распределения обозначим за выбран независимо от распределения .

Выборка из может быть произведена за время . Выборка из также может быть осуществлена за , и время счета ограничено величиной, которая соответствует геометрическому закону с параметром < 1. Более того, во всех наших криптографических приложениях можно заранее провести такие выборки автономно (т.е. до того, как станет известно сообщение , которое надо обработать).

TemplateLemmaIcon.svg Лемма «Лемма 6»
Предположим, что


Дадим определение нашей адаптации R-LWE.

TemplateDifinitionIcon.svg Определение «Определение 1»
Задача R-LWE с параметрами и (R-LWE) звучит следующим образом. Пусть . Разрешив доступ к оракулу , совершающему выборку из , , определим, выдает ли на выходе выборку из или из . Отличительное преимущество должно быть ( соответственно) над случайностью входа, выборки и внутренней случайностью алгоритма.

Из следующей теоремы следует, что R-LWE - стойкий при условии, что -Ideal-SVP наихудшего сценария не может быть эффективно решена с помощью квантовых компьютеров при малом . Недавно были внесены положительные изменения Любашевским и др.[20]: если число выборок, которые можно задать оракулу ограничено константой (данный случай рассмотрен нами), то результат будет также справедлив и для более простых, чем , и с еще более малым Ideal-SVP фактором аппроксимации . Это также должно позволить одновременно упростить измененный NTRUEncrypt и усилить гарантии его безопасности.

TemplateLemmaIcon.svg Лемма «Теорема 1 (Взята из [18]
Предположим, что ( соответственно) и . Существует случайных выполняющихся за полиномиальное (соответственно, субэкспоненциальное) время квантовых сведений -Ideal-SVP к R-LWE, ( соответственно).


Разница между [18] и представленной выше формулировкой в использовании полиномиального представления (путем применения комплексного БПФ к вектору ошибок), использовании вместо , где - кодифферент (здесь ) и отбрасывании ошибки в пользу ближайшего целого в случае расположения не на одинаковом расстоянии от двух идущих друг за другом целых чисел. Новая вариация остается стойкой из-за того, что выборка проходит шаг отклонения с высокой вероятностью, а также из-за того, что округление может быть выполнено на выборке оракула до фактической ошибки.

Вариации R-LWE. Для и - распределение в определим как распределение, полученное выборкой пары () с , где - множество обратимых элементов . Когда , вероятность того, что единичный элемент будет обратимым - ненулевая, и поэтому R-LWE остается стойким даже когда и соответственно заменены и . Назовем такой вариант R-LWE.

Более того, по аналогии с [21], Леммой 2 и объяснением в [20] в данном случае можно выбрать из распределения ошибки без привлечения потерь безопасности. Назовем R-LWE соответствующую модификацию R-LWE. Для полноты приведем доказательство. Предположим, что алгоритм может решить R-LWE. Используем для решения R-LWE. В основе принципа лежит перевод выборки в , где выполнена инверсия над . Этот перевод отображает в , а в себя.

Новые результаты по q-арным решеточным модулям

В данном разделе мы приведем строгие границы регулярности для кольца . Для этого нам надо сперва изучить два семейства -модулей.

Результаты двойственности для некоторых решеточных модулей

Пусть . Дадим определение следующему семейству -модулей для - произвольного идеала в :

.

Также обозначим как соответственно. Идеалы имеют вид , где - любое подмножество ( - корни по модулю ). Определим .

TemplateTheoremIcon.svg Теорема Лемма 7
Пусть . Пусть , и a^{\times} \in R_q^m \,\!</math> определено как . Тогда (рассматривая оба множества как -размерные решетки отождествляя ):
Доказательство
Сначала докажем, что . Пусть . . Наша цель - показать, что . Это эквивалентно тому, что постоянный коэффициент многочлена - 0 по модулю . Поэтому достаточно показать, что ). По определению . Далее, по модулю , получим:

Обе суммы в правой половине равенства равны 0 в , что подтверждает описанное ранее включение.

Для завершения доказательства достаточно показать, что . Этого можно добиться, если рассмотреть элементы при


Пояснение насчет отсутствия необычно коротких векторов в Пояснение насчет отсутствия необычно коротких векторов в L ( a , I S ) {\displaystyle L(a,I {S})\,\!}

Покажем, что для решетка крайне маловероятно содержит необычно короткие вектора с бесконечной нормой, т.е. более короткие, чем верхняя граница Минковского ( следует из того, что в кубе находится вершин . Отметим, что наша нижняя граница стремится к границе Минковского, когда стремится к 1, но постепенно отдаляется, когда уменьшается до . К счастью, мы будем использовать эту границу при для некоего малого , при котором граница близка к достижению.

TemplateTheoremIcon.svg Теорема Лемма 8
Пусть - степень 2, такая что можно разбить на линейных множителей по модулю . Тогда, для любого получим :
,
исключая с вероятностью равномерно случайного выбора из
Доказательство
Напомним, что для различных линейных множителей . Из Китайской теоремы об остатках известно, что (, соответственно) изоморфен (, соответственно) с изоморфизмом . Пусть : это степень порождающей функции .

Пусть - вероятность (по случайности ) того, что содержит ненулевой вектор с бесконечной нормой , где . Ограничим сверху суммарной границей, сложив вероятности всех возможных значений с бесконечной нормой , и . Так как независимы между собою, имеем , где .

Без проигрыша в общности предположим, что (вплоть до операций умножения над элементами : если это не так, то существует , такой что либо либо . В обоих случаях имеем , т.к. . Теперь предположим, что для некоторого мощности . Для любого имеем в независимости от значения , в то время как для имеем , и существует единственное значение , такое что . Более того, для любого значение является произвольным из . Таким образом, существуют различных в , таких что . Отсюда следует, что .

На данный момент мы показали, что вероятность ограничена сверху:

Пусть для степени - число , таких что для некоторого степени . Рассмотрим две границы для в зависимости от .

Предположим, что . Выдвинем утверждение, что . Действительно, произвольный для некоторого принадлежит идеалу , порожденного . Для любого ненулевого имеем , где неравенство обусловлено тем, что идеал - полноранговый подидеал , и последнее равенство обусловлено тем, что . Из арифметико-геометрического неравенства следует, что . Из эквивалентности норм сделаем вывод, что . Как видно, с учетом , так что .

Теперь предположим, что . Утверждаем, что . Действительно, т.к. степень , то вектор , образованный коэффициентами низшего разряда , связан с вектором , образованным коэффициентами низшего разряда нижней треугольной матрицей, чьи диагональные коэффициенты равны 1. Так как эта матрица не является единичной по модулю , то отобразив в характеризуется взаимно однозначным соответствием. Это обусловливает заявление.

Используя перечисленные выше границы для , тот факт, что число подмножеств мощности - , и тот факт, что число делится на - , получим выражение для описанной выше границы для :

Учитывая наш выбор , получим, что (это следует из ). Простое вычисление приведет нас к заявленной верхней границе для .


Улучшенные границы регулярности

Перейдем к исследованию равномерности распределения -кортежей из вида , где независимы и равномерно случайны в , и выбраны из некоторого распределения на , концентрированного на элементах с малыми коэффициентами. По аналогии с[15] назовем расстояние между крайним распределением и равномерным на регулярностью обобщенной функции рюкзака . Мы заинтересованы в случае для нашего приложения NTRU.

Значение регулярности в [[15], Раздел 4.1] применимо к случаю, когда равномерно распределенные случайные величины в целом кольце , и равномерно распределенные случайные величины в подмножестве элементов с коэффициентами величиною для некоторого . В данном случае, граница регулярности по [15] равна . К сожалению, этой границей нельзя пренебречь при малых , например, для . Для того, чтобы сделать ее экспоненциально малой в необходимо выполнение , что в конечном итоге ведет к неэффективным криптографическим функциям. Когда выбраны равномерно из целого кольца , фактическая регулярность не лучше, чем эта нежелательная граница регулярности. Причина в том, что содержит идеалов размера , и с вероятностью все попадут в один из таких идеалов (из-за чего также окажется в таком идеале), что не пренебрежимо при малом . Для обхода данной проблемы потребуем, чтобы были равномерны в , и выберем из дискретного распределения Гаусса. Покажем, что граница регулярности экспоненциально мала в даже при используя доказательство, схожее с применяемым в [[10], Раздел 5.1] для неструктурированных обобщенных рюкзаков на основе параметра сглаживания указанных ниже решеток. Отметим, что новые результаты регулярности могут быть использованы в генерации ловушек Ideal-SIS [[17], Раздел 3], тем самым увеличивая решетку до полностью разложенного . Также видно, что схема шифрования из[18] может быть представлена безопасной против субэкспоненциальных (квантовых) злоумышленников, подразумевая субэкспоненциальную (квантовую) стойкость типовой задачи над идеальными решетками наихудшего сценария.

TemplateLemmaIcon.svg Лемма «Теорема 2»
Пусть - степень 2, такая что разлагается на линейных множителей по модулю простого числа . Пусть . Тогда за исключением области имеем и расстояние равномерности - . В качестве следствия:
.


При использовании полученного результата становится интересным случай малой константы , поскольку это позволяет снизить типовое отклонение и, соответственно, меры случайности. Теперь необходимо выбрать небольшой (например, , что значительно снизит верхнюю границу статистического расстояния без сильного ослабления требований к типовому отклонению.

Для каждого - распределение , где - выборка из . Отметим, что описанное выше статистическое расстояние равно , где - расстояние равномерности . Для доказательства теоремы требуется показать, что граница расстояния , за исключением области .

Отображение индуцирует изоморфизм из фактор-группы в ее область (отметим, что является ядром ). Последнее является благодаря обратимости . Поэтому, статистическое расстояние эквивалентно расстоянию равномерности . По Лемме 4 имеем при большем, чем параметр сглаживания . Применим Лемму 2 к верхней границе , что сократит работу по поиску нижней границы минимальной обратной решетки - взаимно однозначное соответствие .

Следующий результат - прямое соответствие из лемм 2,4,7 и 8, а также теоремы 2 при .

TemplateLemmaIcon.svg Лемма «Лемма 9»
Пусть - степень 2, такая что разлагается на линейных множителей по модулю простого числа . Пусть . Тогда за исключением области имеем:


Исправленный алгоритм генерации ключей

Начиная с этого момента мы будем пользоваться результатами предыдущего раздела по модульным -арным решеткам для получения алгоритма генерации ключей NTRUEncrypt, при котором генерируемый открытый ключ получается из распределения, при котором Ideal-SVP сводится к R-LWE.

Алгоритм генерации ключей NTRUEncrypt

Новый алгоритм генерации ключей NTRUEncrypt представлен ниже. Многочлены закрытого ключей сгенерированы с помощью выборки дискретных норм Гаусса Гентри и др. (см. Лемма 5) и такого отвержения, что выходные многочлены обратимы по модулю . Выборка Гентри и др. может не являться выборкой дискретных норм Гаусса, но т.к. статистическое расстояние можно сделать экспоненциально малым, то на наши результаты влияние будет также экспоненциально малым. Более того, можно убедиться, что наши условия к типовым отклонений гораздо стороже, чем приведенные в Лемме 5. Положим, что с этого момента мы имеем идеальную выборку дискретных норм Гаусса.

Выбирая довольно большое типовое отклонение , мы можем применить результаты предыдущего раздела и получить (квази)-равномерное распределение открытого ключа. Сделаем выборку вида так, что она будет содержать инверсию 1 по модулю , что приведет к повышению эффективности процесса дешифрования NTRUEncrypt (как в исходной схеме NTRUEncrypt). Отметим, что условия отвержения на первом шаге эквиваленты условию , где - инверсия в .

Исправленный алгоритм генерации ключей:

Входные данные: .
Выходные данные: Пара ключей .
  1. Выберем из ; пусть ; если , то выборка производится заново.
  2. Выберем из ; если , то выборка производится заново.
  3. Получим закрытый ключ и открытый ключ .

Дальнейшие результаты позволяют убедиться, что при некотором выборе параметров алгоритм генерации ключей завершается за заданное полиномиальное время.

TemplateTheoremIcon.svg Теорема Лемма 10
Пусть - степень 2, такая что раскладывается на линейных множителей по модулю простого числа . Пусть для произвольного . Пусть . Тогда .
Доказательство
Ограничим вероятность того, что принадлежит . Дальнейшие результаты следуют из Китайской теоремы об остатках и суммарной границы. Имеем , и по теореме Минковского . Так как - идеал в , имеем и по Лемме 1 получаем . По Лемме 4: на расстоянии от равномерности на , поэтому имеем с вероятностью , что и требовалось доказать.


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

TemplateTheoremIcon.svg Теорема Лемма 11
Пусть - степень 2, такая что раскладывается на линейных множителей по модулю простого числа . Пусть . Многочлены закрытого ключа , полученные с помощью алгоритма, приведенного в этом разделе с вероятностью удовлетворяют следующим не равенствам:

Если , тогда с вероятностью .

Доказательство
Данная вероятность ниже вероятности того же события без отвержения, поделенной на вероятность отвержения. Вывод следует из Лемм 3, 10.


Равномерность открытого ключа

По описанному в предыдущем разделе алгоритму имеем многочлены независимо выбранные из дискретной нормы Гаусса для произвольного , но ограниченные (отвержением) до соответственно. Определим как дискретную норму Гаусса , ограниченную до .

Применим результаты Раздела 3, чтобы показать, что статистическая близость к равномерности доли двух распределений . Это включает в себя и случай, когда открытый ключ получен с помощью алгоритма из предыдущего раздела.

TemplateTheoremIcon.svg Теорема Теорема 3
Пусть - степень 2, такая что раскладывается на линейных множителей по модулю простого числа . Пусть . Пусть . Тогда
Доказательство
Для определим . Покажем, что за исключением области . Это непосредственно ведет к заявленной границе. Область , такая что эквивалентна области , такой что . Это следует из того, что эквивалентно , и - случайно равномерно распределено в , когда .

Заметим, что удовлетворяет , и поэтому множество решений последнего равенства . Поэтому:

Теперь используем тот факт, что , и так как , то элементы кольца должны принадлежать тому же идеалу . Значит, . По аналогии имеем . Используя метод включения-исключения, получим:

В оставшейся части доказательства покажем, что, за исключением области :

где . Граница следует из типовых вычислений.

Решая . Отметим, что так как , то мы имеем (для любого .

Для при условии применим Лемму 9 с . Так как , то предположение Леммы 9 о сохраняется, . Имеем : действительно, так как , то существуют элементы в . Придем к выводу, что за исключением области (возможно в соответствии с определенным подмножеством для каждого возможного ).

Для при условии выберем . Тогда имеем и поэтому . Используя для описанного выше результата для малого получим

В общем, мы имеем за исключением, возможно, области :

Придем к тому, что , что и требовалось доказать.

Решая . Для границ используем аналогичный подход. Пусть . Величину можно задать по аналогии с в . Обнаружим, что для любого имеем