Использование полностью однородной схемы шифрования Джентри

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 22:43, 30 октября 2015.
Implementing Gentry’s Fully-Homomorphic Encryption Scheme
Gentry.PNG
Авторы Craig Gentry and Shai Halevi Supported by DARPA grant DARPA-BAA 10-81,IBM Research
Опубликован 2011 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация Мы опишем практическую реализацию для полностью однородной схемы шифрования (STOC 2009) по аналогии с используемой в более ранних работах схемой Смарта и Верткаутерена (PKC 2010). Смарт и Верткаутерен реализовали так называемую "относительно однородную" схему, но не смогли реализовать функционалы, необходимые для получения полной работающей схемы. Мы покажем некоторые оптимизации, которые позволяют нам реализовывать все аспекты схем, в том числе загрузочные функционалы.
Наша основная оптимизация состоит в методе генерации ключей для основного относительно однородного шифрования, не требующем полной инверсии многочленов. Это снижает асимптотическую сложность от до при работе с размерными решетками (и на практике сокращает время расчетов от многих часов/дней до нескольких секунд /минут). Другие оптимизации включают технику деления для шифрования, тщательный анализ степени шифруемого многочлена и некоторые компромиссы пространства/времени для полностью однородных схем.
Мы проверили нашу реализацию с решетками разных размеров, соответствующих разным уровням безопасности. От "мини" размерности в 512 к «малой», «средней» и «большой» в 2048, 8192, и 32768 бит, соответственно. Размер открытого ключа изменяется от 70 Мегабайт для "малых" установок, до 2,3 Гигабайта для "больших". Время для реализации одной операции (на 1-CPU 64 – разрядном компьютере с большим объемом памяти) составляет от 30 секунд для "малых" установок и до 30 минут для «больших».

Введение

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

В 2009 году Джентри описал первое правдоподобное построение для полностью однородных криптосистем [2]. Построение Джентри состоит из нескольких этапов: сначала он построил "относительно однородную" схему, которая поддерживает работу с многочленами малых степеней в зашифрованных данных, далее было необходимо "разогнать" процедуру расшифровки, чтобы она могла быть выражена как многочлен, малой степени, полученный из схемы, и, наконец, он применил эту трансформацию для получения полностью однородной схемы. Решающим моментом в этом процессе является необходимость получить схему, которая может работать с многочленами достаточно высоких степеней, и, в то же время, выполняющую такую процедуру расшифровки, которая может быть выражена как многочленом достаточно малой степени. Как только степень оцениваемых многочленов превышает степень многочлена из процедуры расшифровки, схема будет "загружаема", и она может быть преобразована в полностью однородную.

Для загружаемых схем Джентри описал в работе [2] относительно однородные схемы, которые похожи на GGH схемы [3] [4] для идеальных решеток. Позже Джентри доказал в работе [5], что при соответствующей процедуре генерации ключей, безопасность таких схем может быть сведена к самым сложным решеточным задачам для идеальных решеток.

Эта относительно однородная схема еще не является загружаемой, и поэтому Джентри описал в работе [2] преобразование для процедуры расшифровки через уменьшение степени многочлена расшифровки. Это делается путем добавления к открытым ключам дополнительной информации о секретном ключе через задание «редких субсистем» (SSSP). А именно, открытый ключ расширяется набором таких векторов, что только некоторые из набора составляют в целом секретный ключ. Текст шифровки для базовой схемы может быть "обработан после" с помощью этой дополнительной информации, и обработанный текст может быть расшифрован многочленом малой степени; таким образом, мы получаем загружаемую схему.

Стейль и Стейнфельд описали в работе [6] две оптимизации для схемы Джентри; в одной уменьшается количество векторов в SSSP субсистемах, а в другой могут быть снижена степень многочлен расшифровки (за счет определения малой вероятности ошибок при расшифровке). Отметим, что в нашем случая мы используем только первую оптимизацию, мы не используем вторую оптимизации потому, что вероятность ошибки при расшифровке слишком велика для наших параметров. Некоторые улучшения процедуры генерации ключей Джентри обсуждаются в работе [7].

Реализация Смарта и Верткаутерена

Первая попытка реализовать схему Джентри была сделана в 2010 году на Смартом и Верткаетереном в работе [8]. Они выбрали для реализации вариант схемы с использованием «идеальных решеток» для простого определителя. Такие структуры могут быть представлены только за счет двух целых чисел (независимо от их размера), причем Смарт и Верткаутерен описали метод расшифровки, где секретный ключ представляется одним целым числом. Смарт и Верткаутерен смогли реализовать относительно однородную схему, но они не смогли до конца реализовать технику Джентри при достаточно больших параметрах. В результате они не смогли получить загружаемую или полностью однородную схему.

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

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

Наша реализация

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

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

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

В отличие от работы [8], мы отделяем размерность от размера целых чисел, выбираемых при генерации ключей. Разделение этих двух параметров позволяет нам отделить функционалы от безопасности. А именно, мы можем получить разделяемую схему при любой заданной размерности, но, конечно же, схемы в малых размерностях не будут безопасными. Наш (довольно грубый) анализ показывает, что схема может быть практически безопасной при размерности или , и мы используем этот анализ для обозначения некоторых проблем, в размерностях от до .

Структура работы

Мы приводим некоторые основы в разделе 2, а затем описываем нашу реализацию базовой «относительно однородной» схемы шифрования в разделах с 3 по 7. Описания наших оптимизаций, специфических для загружаемых функционалов, приводится в полной версии данной работы [9].

История вопроса

Обозначения. В настоящем работе мы используем для обозначения скалярного умножения и для обозначения других типов умножения. Для целых чисел обозначим сокращение по модулю как или . Мы используем , когда операция отображает целые числа в интервал , и используем , когда операция отображает целые числа в интервал . Мы используем , когда интервал не имеет значения (например, ). Например, мы имеем против , но .

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

Структуры

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

Каждая структура (размерности ) имеет бесконечное число базисов. Если и это два структурных базиса для , то есть существует унимодальная матрица (то есть имеет целые входы и ), удовлетворяющая равенству . Так как унимодальна, будет инвариантно при различных базисах для , и мы можем обратиться к нему как . Это значение является размером группы , если является целочисленной структурой. Для базиса структуры мы задаем полуоткрытый параллелепипед . Объем точно совпадает с . Для и базиса , мы используем для обозначения такого вектора , что . При заданных и , может быть эффективно вычислено как . (Напомним, что обозначает округление до ближайшего целого числа и есть дробная часть).

Каждая полная структура имеет уникальный базис нормальной формы Эрмита (HNF), где для всех , для всех , а для всех будет . При заданном базисе для , можно эффективно вычислить посредством Гауссова исключения. HNF является в некотором смысле «наименее открытым" базисом для , и таким образом, обычно выступает в качестве открытого ключа для структуры [8].

Короткие векторы и декодирование ограниченных расстояний. Длина кратчайшего ненулевого вектора в структуре обозначается как , и теорема Минковского утверждает, что для любой -мерной структуры мы имеем . Для случайных структур значение служит порогом: для мы не ожидаем найти ни одного ненулевого вектора размера в структуре , а для мы ожидаем найти много векторов размера в .

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

Гама и Нгуен провели обширные опыты с структурами, размеров 100-400 [10], и пришли к выводу, что для таких размеров целесообразно решать -BDDP задачу, когда . В более общем смысле, лучшим алгоритмам для решения -BDDP задачи в -мерных структурах потребуется время порядка . В частности, известные в настоящее время алгоритмы могут решить -BDDP задачу за время от до , где является параметром, который зависит от конкретных свойств алгоритма. (Экстраполяция Гама-Нгуен экспериментов дает нам ожидания в ).

Идеальные структуры

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

Пусть будет идеальной цепочкой - то есть, подмножеством из , замкнутым при сложении или умножении элементов из . Так как аддитивно замкнута, то векторы коэффициентов, связанные с элементами образуют структуру. Мы называем идеальной структурой, чтобы подчеркнуть двойственную природу этого объекта, как алгебраически идеального и как решетку. является дополнительной решеткой, но она также имеет мультипликативную структуру. Сочетание двух идеальных структур и будет аддитивно замкнутым множеством , где является умножением в цепочке. Для простоты, мы будет использовать главные идеалы для - то есть, идеалы с одним генератором. Идеал , порожденный , соответствует структуре, порожденной векторами ; мы называем это вращательным базисом для структуры .

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

Криптосистемы GGH типа

Напомним вкратце "очищенный вариант" GGH криптосистемы Мицианцио [3] [4]. Секретный и открытый ключи являются "хорошим" и "плохим" базисом для некоторой структуры . В частности, держатель ключей создает хороший базис, задавая в качестве базиса для коротких, "почти ортогональных" векторов. Затем он устанавливает открытый ключ как Эрмитову нормальную форму той же структуры .

Зашифрованный текст в GGH криптосистемах это вектор с, близкий к структуре , и сообщение, которое зашифровано в этом тексте находится в расстоянии от с до ближайшего вектора структуры. Чтобы зашифровать сообщение m, отправитель выбирает короткий "вектор ошибок" е, который кодирует m, а затем определяет зашифрованный текст, как . Обратим внимание, что, если e достаточно короткий (то есть, меньше, чем ), то тогда он действительно отвечает расстоянию между c и ближайшим узлом решетки.

Для расшифровки, держатель ключей использует свой «хороший» базис для восстановления e , задав , а затем восстанавливает m из e. Причинная расшифровка работает так, что, если параметры выбраны правильно, то параллелепипед секретных ключей будет объемным параллелепипедом, который содержит шар радиуса больше , так что e будет точкой внутри , которая равна c по модулю L. С другой стороны, параллелепипед открытых ключей будет сильно искажен, и не будет содержать сферу большого радиуса, что делает его бесполезным для решения BDDP задачи.

Относительно однородные криптосистемы Джентри

Схему Джентри для относительно однородного шифрования [2] можно рассматривать как GGH тип схемы для идеальных структур.

Открытый ключ содержит "плохой" базис для идеальной структуры , наряду с некоторым базисом для "малой" идеальной I (который используется для встраивания сообщений в вектор ошибок). Например, небольшая идеальная структура I может быть задана как I = (2), множество векторов со всеми четными коэффициентами.

Зашифрованным текст в схеме Джентри является вектор, близкий к J-точке, с сообщением, встроенным в расстоянии до ближайшего узла. В частности, пространство открытого текста {0, 1} встраивается в кодированием как и как . Для закодированных бит мы полагаем для случайного, малого вектора r, а затем выводим зашифрованный текст .

Секретный ключ в схеме Джентри (играющий роль "хорошего базиса" для J) является коротким вектором . Расшифровка предполагает вычисление дробной части . Так как для некоторого , то . Но берется в и, таким образом, и имеют те же дробные части, . Если и достаточно короткие - в частности, если у нас есть гарантии, что все коэффициенты имеют значение меньше 1/2 - тогда точно равна . Из расшифровщик может восстановить e, а затем восстановить . Фактическая процедура расшифровки немного отличается. В частности, адаптируется так, чтобы расшифровка могла быть реализована как (когда I = (2)).

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

Версия Смарта и Верткаутерена. Смарт и Верткаутерен в [8] работают над цепочкой , где и n это степень при двойке. Идеальная J устанавливается как главный идеал при выборе вектора случайным образом из некоторого n-мерного куба, при условии, что определитель (v) простой, а затем устанавливая . Известно, что такие идеалы могут быть неявно представлены через два целых числа, а именно через определитель и корень r для по модулю d (простое доказательство этого факта может быть получено на основании нашей леммы 1). В частности, Эрмитова нормальная форма для этой идеальной структуры


Легко заметить, что понижение вектора a по модулю HNF (J) состоит из оценки связанных многочленов в узлах r по модулю d и вывода вектора (См. раздел 5). Следовательно, шифрование вектора для может быть сделано путем выбора случайных небольших многочленов и их оценки для r и вывода целого .

Смарт и Верткаутерен также описывают процедуру расшифровки, которая использует одно целое число в качестве секретного ключа, задавая . Забегая вперед, отметим, что наша процедура расшифровки из раздела 6 очень похожа на эту, за исключением того, что для удобства мы заменяем рациональное деление модульным умножением .

Генерация ключей

Мы изменяем подход Смарта и Верткаутерена [8], в том, что мы также используем главные идеальные структуры в цепочках многочленов по модулю , при n в качестве степени двойки. Мы не требуем, чтобы эти структуры имели простые определители, вместо этого нам только нужно, чтобы Эрмитова нормальная форма имела такой же вид, как в уравнении (1). Во время генерации ключей мы выбираем v наугад в случайном кубе, проверяем, чтобы HNF форма имела правильную форму, и работаем с главным идеалом (V). У нас есть два параметра: размерность n, которая должна быть степенью двойки, и бит размер t для коэффициентов в генерирующем многочлене. Генерация ключей состоит из следующих шагов:

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

i-я строка является циклическим сдвигом v на i позиций вправо, при отбрасывании "переполненных элементов ". Обратим внимание, что i-ой строке соответствуют коэффициенты многочлена . Отметим, что также как и V, вся структура будет замкнута при "повороте": А именно, для любого вектора , вектор также будет в .

2. Вычисляется инверсия для по модулю , а именно такой целочисленный многочлен степени не более n - 1, что . В частности, эта константа будет определителем структуры , который должен быть равен результату для многочленов и (так как унитарна). Ниже мы обозначаем результат через d, а вектор коэффициентов через . Легко проверить, что матрица

является инверсией для V, а именно . Один из способов вычислить многочлен это применение расширенного GCD Эвклидова алгоритма для и . В разделе 4 приведены более эффективные методы вычисления .

3. Также проверяется, чтобы многочлен хорошо проводил генерацию. v будет считаться хорошим, если Эрмитова нормальная форма для V имеет тот же вид, что и в уравнении (1), а именно все, кроме крайнего левого, столбцы равны единичной матрице. Для простоты, в нашем подходе v считается хорошим, это условие проверяется при расчете инверсий. Найджелом Смартом было отмечено, HNF форма имеет правильную форму даже при нечетном и свободном от квадратов определителе. Действительно, в наших проверках это условие выполняется с вероятностью примерно в 0,5, независимо от размера и бит длины, а случаи невыполнения обычно связаны с четными определителями v.

Проверка HNF формы. Далее в лемме 1 мы докажем, что HNF форма для структуры имеет правильную форму тогда и только тогда, когда структура содержит вектор вида . А именно, тогда и только тогда, когда существует такой целочисленный вектор и целое число, что

Умножая последнее равенство справа на W, мы получаем эквивалентное условие

Другими словами, должно существовать такое целое r, что вторая строка в W за вычетом r раз первой строки, дает вектор целых чисел, делимых на d:

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

TemplateLemmaIcon.svg Лемма «Лемма 1»
Эрмитова нормальная форма для матрицы V из уравнения (2) равна единичной матрице во всех, кроме левого, столбцах, тогда и только тогда, когда структура, распределенная по строчкам V содержит вектор вида


Замечание 1. Отметим, что доказательство леммы 1 показывает, в частности, что если Эрмитова нормальная форма V равна единичной матрице во всех, кроме левого, столбцах, то она должна иметь вид, указанный в уравнении (5). А именно, первым столбцом будет , при и для всех i. Следовательно, эта матрица может быть получена из двух целых чисел d и r.

Открытые и секретные ключи

В принципе открытый ключ является Эрмитовой нормальной формой V, но, как мы объясняем в замечании 1 и разделе 5, для сохранения открытых ключей достаточно только двух целых чисел d и r. Точно так же, секретный ключ представляет из себя пару , но, как мы объясним в разделе 6.1, будет достаточно сохранить только нечетные коэффициенты w и отбросить v.

Обращение многочлена Обращение многочлена v ( x )   {\displaystyle v(x)\ }

Самые быстрые из известных методов для обращения многочлена по модулю основаны на FFT моделе: мы можем оценивать по всем корням (либо по множеству комплексных чисел или конечных чисел), далее мы вычисляем (где инверсия проводится для соответствующего поля), а затем интерполируем для всех значений. Если результат для v и имеет N бит, то эта процедура потребует операций над -разрядными числами, что приведет к времени работы в общей сложности. Это в целом близко к оптимуму, так как простое выписывание коэффициентов многочлена занимает время . Тем не менее, в разделе 6.1 мы покажем, что для секретного ключа достаточно использовать только один из коэффициентов (где ). Это повышает вероятность того, что мы сможем вычислить этот коэффициент за время, пропорциональное N, а не пропорциональное nN. Хотя инверсия многочленов хорошо изучена, насколько мы знаем, вопрос о вычислении лишь для одного коэффициента инверсии не рассматривался раньше. Ниже мы опишем алгоритм, применяемый в данном случае.

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

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

Используемый далее метод применяет уравнение (6), а также связь между коэффициентами для инверсии w и для прямых многочленов

Шаг первый: многочлен . Отметим, что хотя многочлен и определяется с помощью комплексных чисел , но все коэффициенты являются целыми числами. Мы начинаем с того, что покажем, как вычислить два нижних коэффициента для , а именно многочлен . Заметим, что поскольку , то мы можем написать как

Заметим также, что для обоих многочленов и все нечетные степени для х имеют нулевые коэффициенты. Более того, приведенные равенства имеют место, если мы используем и вместо самих и (так как мы оцениваем эти многочлены только для корней ), а также для A,B все нечетные степени х имеют нулевые коэффициенты (так как мы уменьшаем по модулю при четном n). Таким образом, мы можем рассматривать многочлены , вдвое меньших степеней и использовать только ненулевые коэффициенты A, B, соответственно. Эти многочлены определяются как и . Таким образом, мы свели задачу вычисления n элементов для n многочленов к вычислению только n/2 элементов, для n/2 многочленов , . Рекурсивно повторяя этот процесс, мы получаем многочлен . Детали этого процесса описаны в разделе 4.1.

Шаг второй: восстановление и . Напомним, что если является свободным, тогда , что является свободным членом из , и тогда . Напомним также, что линейный член в имеет коэффициент . Покажем, что свободным членом из является . Во-первых, заметим, что равен сумме w, оцененных для всех корней , а именно:

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

где равенство выполняется, так как i-м корнем для является , где имеет 2ю степень. Очевидно, что членом, соответствующим j= 0 в уравнении (7), будет , тогда остается показать, что все другие слагаемые равны нулю. Это следует из того, что является 2й степенью величины, отличной от ± 1 для всех j = 1, 2,. . . , n - 1, а суммирование по всем нечетным степеням такого корня равно нулю.

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

Подробности первого шага

Мы обозначаем и , а для мы обозначим . Мы осуществляем шагов для вычисления многочленов , со степенями не более чем , и, кроме того, многочлен имеет такие два первых коэффициента, как и . А именно,

Уравнение (8) справедливо для по умолчанию. Предположим, что мы вычислили Uj, Vj для некоторых таких , что уравнение (8) выполнено, и покажем, как вычислить , . Из уравнения (6) мы знаем, что , поэтому мы можем выразить как

Обозначая и учитывая, что является корнем для при любых i, мы рассматриваем многочлены:

( с коэффициентами )
( с коэффициентами )

и соблюдаем следующие правила:


  • Так как являются корнями для , то редукция по модулю не имеет значения при оценке , по . Мы имеем и аналогично (для всех i).
  • Нечетные коэффициенты для , равны нулю. Для это выполнено потому, что оно получено из , а для потому, что оно получено из (при ). Редукция по модулю оставляет все нечетные коэффициенты нулевыми потому, что четные.

Мы задаем

,

Таким образом, что второе равенство подразумевает, чтобы и для любых x. В сочетании с первым равенством, мы получаем

По гипотезе индукции мы также имеем такие , что .

Шифрование

Для того, чтобы зашифровать бит с открытым ключом B (который представляется через два целых числа d, r), мы сначала выбираем случайный 0, ± 1 "шумовой вектор" , значения которого равны 0 с некоторой вероятностью q, и ± 1, с вероятностью (1 - q)/2 .

Затем мы задаем , а текстом шифровки будет вектор

Теперь покажем, что с также может быть представлено лишь одним числом. Напомним, что В (следовательно и ) имеют специальную форму

,

Зададим , а также через целочисленный многочлен . Тогда мы получаем , для некоторого целого числа s, удовлетворяющего . Следовательно, для дробной части выполнено , , а для вектора зашифрованного текста . Очевидно, что этот вектор может быть представлены целым числом . Таким образом, для шифрования бита b нам нужно только оценить многочлен шума в точке r, затем умножить результат на два и добавить бит b (все по модулю d). Теперь опишем эффективную процедуру для этого.

Эффективная процедура шифрования

Самыми трудозатратными операциями во время шифрования являются оценки степени (n-1) многочлена u в точке r. Оценка с использованием правила Горнера делает n- 1 умножение, но известно, что для малых коэффициентов мы можем уменьшить число умножений до , см. работы [[11][12]]. Более того, мы отмечаем, что этот быстрый алгоритм оценки не сложно получить, и оценить им k многочленов за время . Прежде всего, заметим, что оценка многих 0, ± 1 многочленов в одной точке х может быть сделана так же быстро, как простая оценка одного многочлена. В самом деле, как только мы вычислим все степени , то мы можем далее оценивать каждый многочлен просто суммированием подмножеств сумм этих степеней. Это является гораздо более быстрым способом, чем умножение, а главной трудозатратной задачей будет вычисление степеней х, которую мы решаем только один раз для всех многочленов.

Далее, заметим, что оценка отдельного многочлена степени (n- 1) в точке х может быть сделана быстрее при помощи подпрограммы, которая оценивает два многочлена степени (n/2-1) в одной и той же точке x. А именно, при заданном , мы разбиваем его на "нижнюю половину" и "верхнюю половину" . Оценивая эти два уменьшенных многочлена, мы получаем и , а затем мы можем вычислить , полагая . Если подпрограмма для оценки двух меньших многочленов также возвращает значение , то нам нужно еще одно умножение, чтобы получить значение .

Эти два наблюдения позволяют использовать рекурсивный подход к оценке 0, ± 1 многочленов степени n - 1. А именно, мы многократно сокращаем степень в два раза за счет удвоения числа многочленов, и как только степень становится достаточно мала, мы используем "тривиальной подход" для вычисления всех степеней для х. Для анализа этого подхода, обозначим через число умножений, необходимое для оценки k многочленов степени (n - 1). Тогда мы получаем . Чтобы увидеть границу , мы обратим внимание на то, что, как только мы оценили верхнюю и нижнюю половины для всех k многочленов, нам нужно одно умножение на многочлен, чтобы совместить половины и еще одно умножение для вычисления (необходимого на следующем уровне рекурсии) из (вычисленного в предыдущем этапе). Очевидно, что проведение рекурсивных запросов требует меньше операций умножения "тривиальный подход" при . Кроме того, легко заметить, "тривиальный подход" лучше при .

Таким образом, мы получаем рекуррентную формулу

Решая это уравнение, мы получаем . В частности, количество умножений, необходимых для оценки одного многочлена степени (n - 1) будет равно .

Мы утверждаем, что эта "более эффективная" процедура основывается на предположении, что у нас есть достаточно памяти, чтобы одновременно хранить все эти частично оцениваемые многочлены. В наших экспериментах мы смогли работать только в размерах до , а использование подхода для больших измерений требует слишком много памяти. Более сложные реализация могут взять доступный объем памяти во внимание, и остановить рекурсию заранее, чтобы сохранить пространство за счет увеличения времени работы. Альтернативный подход, конечно, состоит в сохранении промежуточных результатов на диск. Необходимо проведение дополнительных экспериментов, чтобы определить, какой подход дает более высокую производительность и для каких параметров.

Эвклидова норма и новые шифротексты

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


Грубо говоря, если шумовой вектор имеет бит энтропии, то мы ожидаем наличия ищущих атак, имеющих возможность восстановить его за время , поэтому мы должны гарантировать, что шум имеет, по крайней мере, 2λ бит энтропии для параметра безопасности λ. А именно, для размерности n нам нужно выбрать такое достаточно малое q, чтобы было выполнено . Еще одна "гибридная" атака заключается в выборе малых случайных подмножества степени r (например, только 200 из них) и "надеяться", что они включают в себя все коэффициенты шума. Если это осуществляется, то мы можем искать малый вектор в этой низкой размерности структуры (например, при размерности 200). Например, если мы будем работать в размерности n = 2048 и использовать только 16 ненулевых элементов для шума, тогда затем, выбрав 200 из 2048 записей, мы получим вероятность в включения всех из них (а значит, мы может восстановить исходный шум, решая уравнений в размерности 200). Такая же атака будет иметь вероятность успеха , если мы используем 24 ненулевые записи.


Для наших открытых мы выбрали (довольно агрессивные) условия, когда число ненулевых элементов в шумовом векторе составляет от 15 до 20. Мы отметим, что увеличение шума будет иметь умеренное влияние на показатели производительности нашей полностью однородной схемы, например, при использовании 30 ненулевых элементов, вероятно, размер ключа (и времени работы) увеличиться примерно на 5-10%.

Расшифровка

Процедура расшифровки берет на входе зашифрованный текст с (который представляет собой вектор ) и она также имеет две матрицы V, W. Вектор , который использовался во время шифрования, извлекается в виде , а затем выводит младший разряд для первого значения из a, а именно: . Причина, по которой эта процедура расшифровки работает, состоит в том, что ряды V (и, следовательно, для W) практически ортогональны друг к другу, и, следовательно, оператор для W мал. А именно, для любого вектора х, наибольшее значение в (по абсолютной величине) не намного больше, чем наибольшее значение в самом х. В частности, процедура успешна, когда все элементы меньше, чем d/2.Чтобы увидеть это, заметим, что расстояние между c и узлом в решетке , а именно для некоторого целого вектора y. Следовательно, мы имеем

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

Оптимизированная процедура расшифровки

Покажем теперь, что зашифрованный бит b может быть восстановлен значительно более простой процедурой: напомним, что вектор зашифрованного текста c расшифровывается в бит b, когда расстояние от c до ближайшего вектора в структуре имеет вид , причем все значения для не превышают d/2 по абсолютной величине. Как мы уже говорилось ранее, в этом случае мы имеем , что эквивалентно условию .

Напомним теперь, что и, следовательно, С другой стороны, мы имеем

Объединяя эти два уравнения, мы получаем, что любые дешифруемые тексты должны удовлетворять равенству

Другими словами, для всех i мы имеем . В связи с этим Достаточно отобрать только один элемент из (который должен быть нечетным), а затем восстановить бит b как .


Насколько однородна схема?

Мы провели несколько экспериментов, чтобы понять для каких степеней и для какого числа одночленов относительно однородная схема сможет работать, и помочь нам выбрать параметры. В этих экспериментах мы сгенерировали пару ключей для параметров n (размер) и t (бит длина), и для каждой пары, где мы зашифровали много бит, оценивается шифротекст для элементарных однородных многочленов различных степеней и числа переменных, расшифрованные результаты, и проверяется, вернули ли мы к многочлену теже биты открытого текста.


Рис. 1. Поддерживаемые степени и количества переменных, бит-длина для многочленов генерации, все тесты проводились в размерности n = 128

В частности, для каждой пары ключей, мы протестировали многочлены от 64 до 256 переменных. Для каждого фиксированного числа m переменных, мы делали по 12 тестов. В каждом тесте мы зашифровывали m бит, оценили все элементарные симметричные многочлены в этих переменных (степени до m), расшифровали результаты, и сравнили их с результаты применения тех же многочленов к открытому бит тексту. Для каждого параметра m, мы записали максимальную степень, для которой во всех 12 тестах, расшифровка давала правильные значения. Мы называем это "максимально поддерживаемой степенью" для этих параметров.


В этих экспериментах мы использовали новые шифротексты, эвклидовой длины примерно в , независимо от размера. Это было сделано, при задании всем значениям шумового вектора u нулевых значений с вероятностью и значений ± 1 с вероятностью в для каждого. При таком выборе, степень многочленов, которые могут быть оценены относительно однородной схемой, не зависят от размерности m: мы испытали различных размерности, от 128 до 2048 с разными сочетаниями для t и m, и самая большая поддерживаемая степень была почти одинакова во всех этих измерениях. После этого мы проверили все остальные сочетания в размерности n = 128.


Результаты приведены на рисунке 1. Как и ожидалось, максимально поддерживаемая степень растет линейно с параметром бит длины t, и медленно убывает с числом переменных (так как их увеличение приводит к увеличению числа корней).


Эти результаты могут быть более или менее объяснены в предположении, что радиус расшифровки секретного ключа составляет примерно и что размер шума в оценке примерно составляет , где с близко к эвклидовой норме для новых шифротекстов (то есть, с ≈ 9). Для элементарных симметричных многочленов, число мономов в точности равно . Следовательно, для обработки многочленов степени deg с переменными m, нам нужно установить t настолько большим, чтобы для того, чтобы шум был в рамках радиуса секретного ключа. Пытаясь привести в соответствие данные рисунка 1 с этими утверждениями, мы заметим, что с на самом деле не постоянно, а оно становиться чуть меньше, когда t становится чуть больше. Для t = 64 мы имеем , при t = 128 мы имеем , при t = 256 мы получаем , а при t = 384 мы имеем . Мы предполагаем, что это небольшое отклонение связано с тем, что норма отдельных мономов не совсем точно равна , а имеет некоторое распределение по размеру, и, как следствие норма для суммы всех этих мономов несколько отличается на значение от ожидаемого .

Благодарности

Мы благодарим Найджела Смарта за отличные комментарии. Мы также благодарим CRYPTO рецензентов за их полезные комментарии и Таль Рабина, Джон Ганнелса, и Гжегож Швирца за проведение дискуссий.


Литература

1. Avanzi, R.M.: Fast evaluation of polynomials with small coefficients modulo an integer. Web document (2005), http://caccioppoli.mac.rub.de/website/papers/trick.pdf

2. Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008)

3. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st ACM Symposium on Theory of Computing – STOC 2009, pp. 169–178. ACM, New York (2009)

4. Gentry, C.: Toward basing fully homomorphic encryption on worst-case hardness. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 116–137. Springer, Heidelberg (2010) 148 C. Gentry and S. Halevi

5. Gentry, C., Halevi, S.: Implementing gentry’s fully-homomorphic encryption scheme. Cryptology ePrint Archive, Report 2010/520 (2010), http://eprint.iacr.org/

6. Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997)

7. Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010)

8. Micciancio, D.: Improving lattice based cryptosystems using the hermite normal form. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 126–145. Springer, Heidelberg (2001)

9. Ogura, N., Yamamoto, G., Kobayashi, T., Uchiyama, S.: An improvement of key generation algorithm for gentry’s homomorphic encryption scheme. In: Echizen, I.,Kunihiro, N., Sasaki, R. (eds.) IWSEC 2010. LNCS, vol. 6434, pp. 70–83. Springer, Heidelberg (2010)

10. Paterson, M.S., Stockmeyer, L.J.: On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM Journal on Computing 2(1), 60–66 (1973)

11. Peikert, C., Rosen, A.: Lattices that admit logarithmic worst-case to average-case connection factors. In: Proceedings of the 39th Annual ACMSymposium on Theory of Computing – STOC 2007, pp. 478–487. ACM, New York (2007)

12. Rivest, R., Adleman, L., Dertouzos, M.: On data banks and privacy homomorphisms. In: Foundations of Secure Computation, pp. 169–177. Academic Press, London (1978)

13. Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420–443. Springer, Heidelberg (2010)

14. Stehl´e, D., Steinfeld, R.: Faster fully homomorphic encryption. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 377–394. Springer, Heidelberg (2010)

Литература

  1. ivest, R., Adleman, L., Dertouzos, M.: On data banks and privacy homomorphisms. In: Foundations of Secure Computation, pp. 169–177. Academic Press, London (1978)
  2. 2,0 2,1 2,2 2,3 Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st ACM Symposium on Theory of Computing – STOC 2009, pp. 169–178. ACM, New York (2009)
  3. 3,0 3,1 Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997) heory of Computing – STOC 2009, pp. 169–178. ACM, New York (2009)
  4. 4,0 4,1 Micciancio, D.: Improving lattice based cryptosystems using the hermite normal form. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 126–145. Springer, Heidelberg (2001)
  5. Gentry, C.: Toward basing fully homomorphic encryption on worst-case hardness. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 116–137. Springer, Heidelberg (2010) 148 C. Gentry and S. Halevi
  6. Stehl´e, D., Steinfeld, R.: Faster fully homomorphic encryption. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 377–394. Springer, Heidelberg (2010)
  7. Ogura, N., Yamamoto, G., Kobayashi, T., Uchiyama, S.: An improvement of key generation algorithm for gentry’s homomorphic encryption scheme. In: Echizen, I.,Kunihiro, N., Sasaki, R. (eds.) IWSEC 2010. LNCS, vol. 6434, pp. 70–83. Springer, Heidelberg (2010
  8. 8,0 8,1 8,2 8,3 Stehl´e, D., Steinfeld, R.: Faster fully homomorphic encryption. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 377–394. Springer, Heidelberg (2010)
  9. Gentry, C., Halevi, S.: Implementing gentry’s fully-homomorphic encryption scheme. Cryptology ePrint Archive, Report 2010/520 (2010), http://eprint.iacr.org/
  10. Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008)
  11. Avanzi, R.M.: Fast evaluation of polynomials with small coefficients modulo an integer. Web document (2005))
  12. Paterson, M.S., Stockmeyer, L.J.: On the number of nonscalar multiplications nec- essary to evaluate polynomials. SIAM Journal on Computing 2(1), 60–66 (1973)]