Полностью гомоморфное быстрое шифрование

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 10:39, 28 июня 2016.
Faster Fully Homomorphic Encryption
Faster Fully Homomorphic Encryptions.png
Авторы Damien Stehle[@: 1],
Ron Steinfeld[@: 2]
Опубликован 2011 г.
Сайт Homepage of Damien Stehle
Перевели Pavel Shagaev
Год перевода 2015 г.
Скачать оригинал
Аннотация.В статье описывается два улучшения к полностью гомоморфной схеме Гентри (Gentry) основанной на идеальной решётке и её анализе:
  1. проводиться более детальный анализ одного из сложнейших предположении(связанного с проблемой разбросанности подмножества сумм)
  2. описывается вероятностный алгоритм расшифровки, который может быть реализован при помощи алгебраической схемы низкой мультипликативной степени.
Объединив вместе эти усовершенствования, приводит к полностью гомоморфной быстрой схеме с сложностью элементарных операции добавления/увеличения переменной, где - параметр безопасности. Это улучшение также применимо к полностью гомоморфным схемам Смарта(Smart) и Веркотерена(Vercauteren) [PKC’2010] и к схеме ВанДейка [Eurocrypt’2010].
Ключевые слова: полностью гомоморфное преобразование, идеальная решётка, SSSP.

Введение

Гомоморфные схемы шифрования позволяют любому участнику открыто преобразовать набор шифртекста от некоторого открытого текста в шифртекст от некоторой функции от открытого текста, ничего не зная об открытом тексте. Такие схемы могут быть полезными для построения протоколов, сохраняющих конфиденциальность. Например, это требуется в приложениях облачных вычислений: пользователь способен сохранить зашифрованную информацию на сервере и разрешить серверу обрабатывать эту информацию без раскрытия данных на сервере. На протяжении 30 лет все известные гомоморфные схемы шифрования поддерживают только ограниченный набор функции , который ограничивает их применение. Теоретическая проблема построения полной гомоморфной схемы шифрования – поддержка произвольных функций только недавно была решена успешной работой Гентри [1]. Совсем недавно были представлены ещё две полностью гомоморфных схемы [2][3] использующие схему Гентри. Основной инструмент всех этих схем это использование решёток в евклидовом пространстве, которые ранее обеспечивали мощное средство для разработки многих криптографических примитивов (см., например, [4] для последнего обзора).

Главным аспектом полностью гомоморфных схем Гентри и последующих схем является то, что шифртекст подвергается операции повторного шифрования. Шифртекст в схеме Гентри содержит компонент случайного ‘шума’, который растет в размере с ростом шифртекста, обрабатываемом при вычислении гомоморфной функции как её открытого текста. Иногда размер шума в шифртексте превышает определённый порог, тогда становится невозможна корректная расшифровка шифртекста. Это ограничивает число гомоморфных операций, которые могут быть использованы. Чтобы обойти это ограничение применяется операция повторного шифрования, которая позволяет ‘очистить’ шифртекст, то есть имея шифртекст для некоторого открытого текста вычисляется новый шифртекс для того же (возможно для различных ключей), в котором размер шума меньше, чем в исходном . Периодичной ‘очистки’ шифртекста (например, после каждого вычисления выхода функции ) позволяет вычислять сколь угодно большие цепи из .

Операция повторного шифрования осуществляется путём расшифровки цепи гомоморфной схемы шифрования, давая ‘очищение’ (понижение шума) для бит из обновленного шифртекста и секретного ключа схемы. Это гомоморфное вычисление цепи расшифровки конечно же должно быть возможно без какого-либо обновления шифртекста – условие именуемое ‘способностью к самонастройке’. Таким образом сложность (в частности, глубины цепи или мультипликативная степень) схемы цепи расшифровки имеет принципиальное значение для возможности и сложности полной гомоморфной схемы. К сожалению, относительно высокая сложность расшифровки цепи в схемах [1][2][3], вместе с напряженностью в отношении между условием способности к самонастройке и безопасностью лежащей в основе трудных проблем, предполагает наличие большого числа параметров и в результате приводит к схемам шифрования с высокой битовой сложностью.

Наш вклад. Мы представили улучшения к полностью гомоморфной схеме Гентри [1] и провели их анализ, который снижает сложность схемы. В целом, беря в качестве параметра безопасности (т.е. все известные атаки на схему потребляют время ), мы добились сложности на обновление зашифрованного текста, соответствующего одному биту открытого текста. Это та сложность, которую придётся заплатить за использование полностью гомоморфной схемы. Для сравнения, Гентри [5] заявляет границу в , хотя доказательства неполны эта граница, как утверждается, имеет место для схемы после Оптимизации 1 и 2 , но анализ не включает рост сложности шифртекста и не объясняет, какая схема расшифровки применяется гомоморфно. Например, расшифровка схемы из [3](Лемма 6.3) является слишком сложной для нахождения границы. Эти проблемы может быть решены, используя раздел 6.2 настоящей статьи, и граница действительно будет иметь место.

Уменьшение сложности возможно по двум причинам. Во-первых, мы проводим более детализированный анализ безопасности проблемы разбросанности подмножества сумм(SSSP) по сравнению с идеальной решёткой, сравнение анализов приведено в [1]. SSSP вместе с проблемой декодирование с ограниченным расстоянием (BDD) являются двумя основными проблемами, лежащими в основе безопасности полностью гомоморфной схемы Гентри. В своём анализе безопасности проблемы BDD, Гентри использует хорошо известную границу сложности схожую с проблемой вычисление кратчайшего вектора в решетке (SVP), но в анализе SSSP Гентри предполагает наличие точного SVP оракула. Наш новый анализ SSSP принимает во внимание сложность, приближающуюся к SVP, что делает его более согласованным с предположениями, лежащими в основе анализа проблемы BDD, что приводит к меньшему выбору параметров. Во-вторых, мы смягчаем определение полностью гомоморфного шифрования для обеспечения незначительной, но не нулевой, вероятности ошибки расшифровки. Затем мы показываем, что благодаря случайности, лежащей в основе процесса генерации ключа ‘SplitKey’(расщепление ключа), используемой Гентри в своем алгоритме расшифровки(т.е. алгоритма расшифровки самонастраивающейся схемы), если позволить расшифровывать с незначительной вероятностью ошибок, то округление точности, используемое в представлении шифрованных компонент, может быть примерно в два раза выше, по сравнению с точностью в работе [1], которая гарантирует нулевую вероятность ошибки. Понижение точности зашифрованного текста позволяет нам уменьшить степень цепи расшифровки. Мы сосредотачиваемся на схеме Гентри [1], но наши улучшения в равной степени относятся и к другим связанным схемам [2][3]

Обозначения. Векторы будут обозначены жирным шрифтом. Если , то означает евклидову норму . Мы также используем обозначение по Ландау , . Если растёт до бесконечности, мы говорим, что функцией можно пренебречь, если она сравнима для некоторого . Если случайное значение, то означает её среднее, означает вероятность события “”. Мы говорим, что последовательность событий выполняется с большой вероятностью, если для пренебрежимо малой функции . Мы также будем использовать нижеупомянутую границу Хефдинга(Hoeffding) [6].

TemplateLemmaIcon.svg Лемма «Лемма 1.1»
Пусть независимые случайные величины со средним , где для некоторых . Пусть . Тогда для


Замечание. Из-за ограничения объёма статьи некоторые подробности даются только в приложении к полной её версии, которые могут быть получены на веб-сайтах авторов. К ним относятся: очерк самонастраивающегося преобразования Гентри [1], адаптированного для обработки расшифровки ошибок; доказательство того, что идеальная выборка распределения Гентри[7] является с большой вероятностью просто определителем, когда рассматривается кольцо  ; доказательства лемм 3.2 и 3.3; и применение наших улучшений к другим полностью гомоморфным схемам шифрования.

Повторение

Для подробного введения в вычислительные аспекты решёток, мы рекомендуем [8]. В статье [9] содержится интуитивное описание полностью гомоморфной схемы Гентри.

Решетки в евклидовом пространстве

Определение: - мерной решёткой называют множество линейных комбинаций линейно-независимых векторов , т.е. . Вектора называют базисными для . Базис является Эрмитовой нормальной формой(Hermite Normal Form - HNF) если для и в ином случае. Эрмитова нормальна форма решетки уникальна и может быть вычислена за полиномиальное время для любого базиса, возможно, делая его наихудшим базисом [10]. С базисом решётки мы связываем фундаментальный параллелепипед Для вектора мы обозначим через уникальный вектор такой, что Заметим, что , где округление до ближайшего целого числа (вверх, в случае вещественного числа, что является одинаковом расстоянии до двух последовательных целых чисел).

Минимальный является нормой любого кратчайшего ненулевого вектора в Как правило, i-ый минимальный является радиусом наименьшего шара, содержащего линейно независимых вектора решётки. Мы определили в качестве широты решётки значение Теперь мы определим два параметризированных семейства алгоритмических проблем, которые являются основными для евклидовых решёток. Пусть - функция измерения. Проблема вычисления функции для нахождения кратчайшего вектора ( (Shortest Vector Problem)) состоит в нахождении вектора такого, что выступающего в качестве исходного для базиса Проблема вычисления функции для декодирования с ограниченным расстоянием ( (Bounded Distance Decoding)) состоит в нахождении вектора выступающего в качестве исходного для базиса приближающегося к вектору и нахождение целевого вектора расстояние между которым и Решение и проблем, вообще говоря, вычислительно сложные задачи. Лучший алгоритм для их решения при [11][12] требует экспоненциального времени для вычисления. С другой стороны, наименьшее можно достичь за полиномиальное время экспоненциально – до поли-логарифмических факторов в показателе [13][14][15]. Для промежуточных наилучшей стратегии можно добиться путём иерархических сокращений в [14] и, придерживаясь следующей гипотезы.

Гипотеза “правила приближенного подсчёта” решетки(Lattice “Rule of Thumb” Conjecture).

Существуют абсолютные константы такие, что для различных и любой решётки размерности и широты , возможно разрешить (соответственно и ) за время меньшее, чем при

Давайте обсудим гипотезу. Часто рассматривают интервал решетки Если , то будет эквивалентно для различных при этом нахождение гарантирует получение нескольких кратчайших векторов, из которых легко найти решение Аналогично, если и то сокращение решётки даст базис первые два вектора которого охватывают подрешетку, содержащую вектора приближающихся к и . Исходя из этого задача SVP может быть решена благодаря двумерному сокращению. Это объясняет почему мы рассматриваем а не более общий . Заметим, что для большинства распространённых решёток нет априорных доводов ожидать значительно большего . В итоге, когда , сложность кажется не зависит от . Экспериментальный результат в работе [16] представляется в соответствии с этой гипотезой.

Алгоритмические улучшения были предложены (например, [17][18]), но они только привели к улучшению констант, без изменения общей структуры гипотезы. Гипотеза выглядит устойчиво, даже если учесть квантовые компьютеры [19]. Мы будем рассматривать её для двух семейств решеток: как известно, для них не существует алгоритма, на сколько-нибудь лучше, чем для остальных решёток.

Для решетки мы определим детерминант как для любого базиса . Вдобавок, теорема Минковского(Minkowski’s theorem) даёт нам связь между минимальным значением и определителем.

TemplateTheoremIcon.svg Теорема Теорема 2.1 [20]
Пусть – n-мерная решётка, – компактное выпуклое множество, симметричное относительно начала координат, а целое число. Если , то содержит, по крайней мере, ненулевых пар точек из .
Доказательство
Без доказательства.


Идеальные решётки

Пусть унитарный неприводимый многочлен степени . Через обозначим кольцо . Пусть (целый) идеал , т. е. подмножество , замкнутое относительно сложения и умножения на произвольные элементы из . По отображениям полиномов на коэффициенты векторов, мы видим, что идеал соответствует подрешетке из : таким образом мы можем рассмотреть как решетку и как идеал. Идеальная решетка для является подрешеткой , что соответствует идеалу . Далее идеальная решетка будет неявно относиться к -идеальной решетке. Для обозначим через его евклидову норму (как вектор). Мы определим мультипликативный фактор расширения для кольца как . Обычно выбирают с , для которого [1].

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

Если является идеальной решеткой для , то мы имеем : простой способ доказать это – заметить, что вращение любого кратчайшего ненулевого вектора составляют базис полно-ранговой подрешетки , и используя неравенство .

Гомоморфное шифрование

В этом разделе мы рассмотрим определения, связанные с гомоморфным шифрованием. Наши определения основаны на работах [1][5], но мы немного смягчим определение правильности расшифровки, чтобы дать возможность появления незначительной вероятности ошибки. Это очень важно для нашего вероятностного улучшение алгоритма повторного шифрования Гентри (Genty’s Recrypt algorithm).

TemplateDifinitionIcon.svg Определение «Определение 2.1.»
Гомоморфная схема шифрования “Hom”(англ. сокращение от гомоморфизм) состоит из четырех алгоритмов:
  • Генерация ключа (KeyGen): Учитывая параметр безопасности , возвращает секретный ключ и открытый ключ .
  • Шифрование (Enc): Учитывая открытый текста и открытый ключ , возвращает зашифрованный текст .
  • Расшифрование (Dec): Учитывая зашифрованного и секретный ключ , возвращает открытый текст .
  • Оценка (Eval): Учитывая открытый ключ , t-входную схему (состоящую из суммирующих и умножающих вентилей по модулю 2), и набор шифртекстов (соответствующих входным битам ), возвращает зашифрованный (соответствующий выходным битам ).

"Hom" называется правильным для семейства схем с бит входа, если для любого и входных битов ,следующее равенство с подавляющей вероятностью имеет место, чем случайность в алгоритмах KeyGen и Enc:

где и для .

"Ноm" называется компактным, если для любой схемы с входных битов, битовый-размер зашифрованного текста ограничен фиксированным многочленном

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

TemplateDifinitionIcon.svg Определение «Определение 2.2.»
Пусть обозначает гомоморфную схему шифрования. Мы определим две схемы:
  • Dec-Add: Принимает в качестве входных значений секретный ключ и два шифртекста , вычисляет .
  • Dec-Mult: принимает в качестве входных значений секретный ключ и два шифртекста , вычисляет .
    "Ноm" называется способным к самонастройке, если условие верно для Dec-Add и Dec-Mult.

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

TemplateTheoremIcon.svg Теорема Теорема 2.2 [1]
Учитывая самонастраивающуюся гомоморфную схему шифрования "Ноm", и параметр , можно построить другую гомоморфную схему шифрования , которая будет компактна и правильна для всех схем размера . Кроме того, если схема "Hom" семантически безопасна, то и схемы будет такой же.
Доказательство
Без доказательства.


Резюме по полностью гомоморфной схеме Гентри

Теперь мы дадим обзор по полностью гомоморфных схему шифрования Гентри [1][5].

Частично гомоморфные схемы

Сначала напомним о частично гомоморфных схемах шифрования Гентри [5], которые поддерживают ограниченное число умножений. Это основное для самонастраивающихся схем, изложенное в пункте 3.3. Схема, описанная в блоке 1, шифрует в кольце для подходящих неприводимых многочленов степени . В данной работе мы будем считать c степени 2. Здесь является функцией от параметров безопасности .

Процедура генерации ключей создает два взаимно простых идеала и кольца . Идеал имеет базис . Для упрощения схемы (и оптимизации её эффективности), удобный выбор, который мы изложили в этой статье, это взять : Сокращение по модулю соответствует снижению коэффициентов вектор / многочлен по модулю 2. Идеал порождается алгоритмом генерации идеала (IdealGen), что с учетом , даёт "хороший" секретный базис (состоящий из коротких, почти ортогональных векторов) и вычисляет его Эрмитову нормальную форму для получения "плохого" открытого базиса . Предложения по конкретных реализаций IdealGen приведены в [5], [7] и [2]</ref>. Для получения оценки сложности равной , будем считать, что является идеалом степень 1, который в случае осуществления [2], а также случая с вероятностью экспоненциально близкой к 1 для распределения рассмотренного в [7] (смотри полную версию). Параметр , связанный с IdealGen, является нижней границей радиуса из наибольшего шара в начале координат, который содержится внутри . Во всех случаях мы имеем (см., например, [5]). Используя алгоритм округления Бабаева [15] с , расшифровщик может восстановить точки из ближайшие к любому целевому вектору на расстоянии из (см. [5]).

  • KeyGen : Выполнить IdealGen для создания секретного / открытого базиса для идеал таких, что содержится в расположенном в центре шаре радиусом . Возвращается открытый и секретный ключи .
  • Inc : Учитывая открытый текст и открытый ключ , выполнить Samp, чтобы получить с . На выходе - зашифрованный текст .
  • Dec: Учитывая зашифрованный текст и секретный ключ sk, возвращает .
  • Eval: Учитывая открытый ключ , цепь и шифртексе для каждого суммирующегоь или умножающего шлюза в , выполните или операцию в ,соответственно, на соответствующий шифртекст. Возвращаемое значение - зашифрованный текст соответствующий выходу .
Блок. 1. SomHom, частичная гомоморфная схема шифрования Гентри.

Пространство открытого текста – подмножество из , поэтому считаем, что это множество . Алгоритм шифрования используется алгоритм выборки Samp, который, принимает для вектора , образца "короткого" вектор в смежном классе . Конкретных реализаций алгоритма Samp приведены в [5]. Связанный с Samp является параметром , который (возможно, вероятностный) является границей нормы векторов на выходе Samp. Для обеих реализаций, можно положить Чтобы зашифровать сообщение , создается образец из смежного класса , и результате уменьшается по модулю открытого базиса . Предполагается, что . Таким образом, за счет сокращения по модулю секретного базиса можно восстановить , а затем открытый текст может быть восстановлен за счет сокращения по модулю .

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

Модифицирование частичной гомоморфной схемы

Гентри [5] ввел модификации в SomHom: он упростил алгоритм расшифровки для того, чтобы построить полностью гомоморфную схему. Модифицированная схема отличается от оригинальной схемы в алгоритмах генерации ключей и дешифрования, о чем подробно показано в блоке 2.

  • KeyGen ' : Выполнить KeyGen ' для получения . Из вычислить вектор такой, что содержит шар радиусом (см. [5]). Возвращается открытый и секретный ключи .
  • Dec ': Принимая зашифрованный текст и секретный ключ , возвращает .
Блок. 2. Алгоритмы измененной частичной гомоморфной схемы шифрования SomHom ', которые отличаются от алгоритмов SomHom.

Гентри показал следующее для доказательства правильность Dec '.

TemplateLemmaIcon.svg Лемма «Лемма 3.1 (адаптировано из [5]).»
Зашифрованный текст с правильно расшифровывается в открытий тест по функции . Кроме того, если , то каждый коэффициент из находится в пределах 1/8 часть целого.


Пусть будет цепью по модулю 2, состоящую из складывающих и умножающих шлюзов с двумя входами и одним выходом. Пусть обозначает обобщенную схему полученную из заменой складывающего и умножающего шлюзов по модулю 2 на и операции кольца соответственно. Будем говорить, что схема является разрешенной, если для любого набора входов в с для , мы получим . Допущенная схема, которая вычисляется гомоморфно на шифровании открытых текстов даст зашифрованный текст , который правильно расшифровывает в , а также с коэффициентами из , находящимися в пределах 1/8 часть целого. Как и в [3], мы характеризуем разрешенную схему через максимальную степень многочлена вычисляемого в схеме. Примечание, что Гентри [1][5] рассматривает глубину схемы, которая является менее гибкой.

TemplateLemmaIcon.svg Лемма «Лемма 3.2.»
Пусть будет цепью по модулю 2, и обозначает соответствующую обобщенную схему над , вычисляющую из (суммарной) степени . Схема допускается, если . В частности, предполагается, что имеет коэффициенты из , схема допускается, если удовлетворяет


Замечание. Многочлен , упомянутый выше, одиножды вычисляется обобщенной схемой . Для произвольной схемы по модулю 2, многочлен может отличаться от многочлена , вычисляемого схемой по модулю 2. В частности, многочлен может иметь недвоичные целые коэффициенты, и некоторые из них могут быть кратн 2. Однако, для схем , для которых имеет бинарные коэффициенты (условие в лемме), мы имеем (это условие на также необходимо, но не явно указано в [3]).

Расплющенная самонастраивающаяся схема Гентри

Чтобы сделать её самонастраивающейся, Гентри [5] измененил SomHom ' за счёт "сплющивания" цепи расшифровки. Он перенёс некоторые вычислений для расшифровки в этап шифрования, путем предоставления дополнительной информации в открытых ключах. Это результат в самонастраивающейся схеме SqHom описан в блоке 3. Схема представляет три новые целочисленных параметра . Обратите внимание, что мы включили оптимизации 2 из[5], что стало возможным благодаря выбору .

  • KeyGen" :
  • Выполнить KeyGen ' для получения и .
  • Создать равномерный битовый вектор с весом Хемминга и .
  • Создать равномерный и независимый от вектора. Вычислить .
  • Вернуть и .
  • Enc" : Выполнить Enc из SomHom ' для создания зашифрованного текста . Для вычислить на битах (1 бит до запятой, и бит после) такое, что , где означает постоянный коэффициент полинома . Возвращается зашифрованный текст .
  • Dec" : Учитывая расширение зашифрованного текста и секретный ключ , возвращает .
  • Eval" : Такой же, что и для SomHom ' (во время пересчёта , как и в алгоритме Enc").
Блок 3. Алгоритмы сплющенной схемы SqHom.

Обратите внимание, что , по модулю 2. Следовательно, с точки зрения правильности расшифровки, SqHom отличается от SomHom ' только из-за ошибок округления. Следующая лемма обеспечивает достаточной точностью (см. также [3]). В разделе 5 мы покажем, что можно усреднить с использованием вероятностного анализа ошибок.

TemplateLemmaIcon.svg Лемма «Лемма 3.3.»
Если , то шифртекст из SqHom с и правильно расшифровывается алгоритмом Dec", и сумма находится в пределах 1/4 целого числа.


Для возможности самонастройки, мы должны быть в состоянии осуществить расширение схем расшифровки Dec-Add и Dec-Mult со схемной степенью меньше, чем степенная вместимость схемы. Это показано далее - в понятиях размера скрытого подмножества в секретном ключе.

TemplateTheoremIcon.svg Теорема Теорема 3.1 (адаптировано из [3]).
Предполагая, что находиться в пределах 1/4 целого числа, расширенная схема расшифровки Dec-Add и Dec-Mult для схемы SqHom с параметром точностью может быть вычислена схемой степени .
Доказательство

Чтобы расшифровать , мы должны вычислить . Выполняются следующие действия:

1. Вычислить при .
2. Пусть будет битом представления . Для нахождения -го:
2.1 Для вычисляется - вес Хэмминга битового вектора .
2.2 Вычисляется .
Обратите внимание, потому, что только из -ых ненулевой, каждый весом Хэмминга не будет больше и, следовательно, его двоичное представление имеет не более бит. Шаг 1 требует единственного умножения по модулю 2 для каждого выходного бита, следовательно, имеет степень 2. Для шага 2.1, мы воспользуемся следующим.


TemplateLemmaIcon.svg Лемма «Лемма 3.4 (адаптировано из [3]).»
Пусть двоичный вектор, а двоичное представление его веса Хэмминга. Тогда для любого , биты могут быть представлены через оценку из целочисленного многочлена степени .


Мы подводим итог, что шаг 2.1 может быть вычислен по схеме степени . Используя модификацию '3-на-2' [21], ван Дейк(van Dijk) и другие [3] показывают, что шаг 2.2 может быть осуществлён в цепи степени . Суммарная степень схемы расшифровки, таким образом, , следовательно, и Dec-Add (соответственно и Dec-Mult) составляет .

Объединяя теорему 3.1 с леммами 3.2 и 3.3, получим:

TemplateLemmaIcon.svg Лемма «Следствие 3.1.»
Схема SqHom является самонастраивающейся, пока


Менее Пессимистичная Сложность Анализ SSSP

Семантическая безопасность схем Гентри SomHom и SomHom ' опирается на сложности ограниченного расстояния задачи декодирования. Как объясняется в разделе 2, эта сложность предположения асимптотически хорошо понятна (с гипотезой “правила приближенного подсчёта” сокращения решетки). Когда схема SqHom превращается в самонастраивающуюся, добавляется другая сложность - сложность характерной проблемы SplitKey. Чтобы быть точным, семантические атаки против SqHom либо направлены на эффективность алгоритма BDD идеальной решетки или же на эффективность алгоритма задачи SplitKey (см. [1].[Т. 10]). В работе [1]. [Т. 11.1.3], показана проблема разбросанности подмножества векторных сумм (SVSSP), чтобы уменьшить сложность проблемы SplitKey.

TemplateDifinitionIcon.svg Определение «Определение 4.1 SVSSP,
Пусть и являются функцией параметра сложности . Пусть J сгенерирована при помощи KeyGen, а В - Эрмитова нормальна форма идеала IJ. Принятые решения SVSSP выглядят следующим образом: нужно находить отличия между значением , выбранными случайно из , и им же, но в зависимости от существование вектора с весом Хэмминга и .

Для нашего выбора I=(2), мы имеем , где является Эрмитовой нормальной формой J. Далее, мы используем . Обычная парадоксальная атака дня рождения работает за время . Для достижения сложности , нам нужно, чтобы и . Перейдем теперь к анализу другой атаки, основанной на понижении решетки.
Рассмотрим решетку: .

Исходя из , мы имеем . Кроме того, где , есть отображение . Кроме того, существование вектора решения s следует из того,что .

Предположим, что ограничение вычислительной мощности . Сокращение решётки гипотезой "приближенного подсчёта" предполагает, что мы не можем найти векторы в L с нормами , предполагая, что . Помимо необычной малости минимума решетки, нет никаких оснований полагать, что оставшиеся существенно различаются: разрыв решетки и амплитуда решетки должны быть схожи. Итак, имеем пар ненулевых кратных векторов с нормой . В то же время, теорема Минковского (Теорема 2.1) утверждает, что существует гораздо больше векторов решетки нормы .

TemplateLemmaIcon.svg Лемма «Лемма 4.1. »
Предполагая, что ,
мы имеем:


Заметим, что если соблюдены условие в лемме 4.1, то для любого λ≥1, шар радиуса содержит более чем m пар ненулевых точек из L, поэтому разрыв решетки должен быть . Представляется разумным предположить, что точек решетки, которые не кратны s не предоставляют информацию для решения SVSSP. Кроме того, мы эвристически предполагаем, что сокращение решетки вернет один из важных векторов с вероятностью , если они представляют собой долю от общего числа векторов решетки норм . В этих условиях, если вычислительные усилия для сокращения решетки ограничиваются до , и если мы хотим, чтобы граница вероятности нахождения соответствующих вектор была , достаточно установить параметры так, чтобы: .

Так как , далее предполагается, что . Заметим, что это условие является менее ограничительным, чем использованное в [1]. (т.е.).

Замечание. В алгоритме KeyGen, требования SVSSP удовлетворяют . Это не приводит к какому-либо сокращению безопасности, как например, если злоумышленник может угадать i такое, что = 1, а затем переставит индексы i и .

Замечание. Наш анализ отличается двумя способами с одним из [1], опираясь на [22]: для согласования сложности анализа идеальной BDD, мы рассматриваем приближенные SVP решения, а не точные. Во-вторых, мы не рассмотрим атаку на протокол с повторной передачей(‘replay’ attack) из [22] (что привело бы к более запутанным константам), наоборот, как в случае сервера, поддерживающего RSA, дан только один экземпляр SSSP.

Улучшение алгоритма очистки шифртекста

Как поясняется в доказательстве теоремы 3.1, главный компонент в степени алгоритма расшифровки происходит за счёт добавления рациональных . Он вычисляется для степени , и все другие компоненты степени являются незначительными по сравнению с этим. Напомним, что , а следовательно , и выбираются независимо и с равномерным распределением(independently with identical distribution – iid), и что . Мы должны выбирать первые независимо и с равномерным распределением для получения достаточной точности р, что существенно для половины раздела 3.3. Это будет иметь влияние при извлечении квадратного корня из степени цепи расшифровки.

Использование меньшей точности

Во-первых, просуммируем для , так как они выбраны независимо, а затем добавим остальные . Первая сумма будет представлена 6-ю битами (1 бит до запятой и 5 бит после), и мы добьемся того, что она с большой вероятностью находится в пределах 1/16 от . Возьмём на отрезке 1/16 от и представим его 6-ю битами. Последняя сумма даст результат на отрезке 1/8 от , и может быть посчитана цепью с постоянной степенью. Используя лемму 3.1, получаем, что результат находится в пределах 1 / 4 от целого числа.
Теперь мы сосредоточимся на первой сумме. Пусть фиксированная точка, приближенная к с определенной точностью p. Мы имеем с . Так как для выбраны независимо и с равномерным распределением , таким же будет и для . Кроме того, мы будем уверены, что для любого . Следующая лемма показывает границу возможных ошибок для суммы .

TemplateTheoremIcon.svg Теорема Лемма 5.1.
Пусть равномерно распределенные величины со значениями в интервале и такие, что для любых k. Тогда с вероятностью пренебрежимо малой по отношению к λ.
Доказательство
Применим неравенство Хефдинга (Hoeffding’s inequality) к . Получим для любого х>0. Получим

Мы используем эту лемму с и (т. е. с числом ненулевых для ). Это указывает, что достаточно взять , чтобы с вероятностью пренебрежимо близкой к 1 выполнялось . Т.е. усечение результат до 5 бит после запятой не может добавить погрешности более 1/32.

Объяснение вычисления в Объяснение вычисления c k {\displaystyle c {k}} в E n c ″ {\displaystyle Enc''}

Для того, чтобы иметь возможность применить лемму 5.1, мы должны быть уверены, что для любого . Для выполнения этого, и для того, чтобы этот подсчёт использовал ограниченную оценку сложности, должны быть вычислено особо тщательно. Из и необходимо вычислить (1+р)-бит приближения к . Так как J является идеалом степень 1, вектор на самом деле целое число по модулю det(J). Таким образом, мы заинтересованы в вычислении . Это вычисление объясняется ниже.
Входы: Векторы и точность p.
Выход: с точность (1+р) вещественного при
1. ;
2. Вычислить с точностью ближайшее число до .
3. Вычислить точно .
4. Сокращать по модулю 2, сохраняя при этом его знак (результат принадлежит интервалу ).
5. Округлить с точности (1 + р) до ближайшего числа .

TemplateTheoremIcon.svg Теорема Лемма 5.2.
Вышеописанный алгоритм правильным. Кроме того, если вектор выбирается равномерно из с равномерно случайным выбором знака при координате принадлежащей , то , где .
Доказательство
На 2 шаге алгоритма мы получим . Так как точна и принадлежит , то мы получим . Таким образом, на шаге 3, получим . Округление на шаге 5 приводит к .

Чтобы доказать второе утверждение, мы используем симметрию распределения . Это означает, что . Воспользуемся теперь тем же свойством, чтобы показать, что . На шаге 2, изменение на влечёт изменение на . Это означает, что на шаге 3, изменение на также влечёт изменение на . В связи с симметрией округления до ближайшего, это отражается и на и на шаге 5.
Заметим, что округления до ближайшего не так благоприятно сказывается на результате: выше доказана сильная зависит от симметрии округления по отношению к 0.


Сокращение глубины цепи расшифровки

Теперь мы хотим, вычислить , где являются фиксированными действительными точками с точностью . Вместо вычисления Веса Хэмминга для , как доказано в теоремы 3.1, мы вычислим только биты (для ), которые будут способствовать подсчёту  : наиболее значимые биты оказываются бесполезными при сокращении по модулю 2. Самое интересное, что эти ненужные наиболее значимые биты были те, требующих для вычисления схемы высокой степени. Более точно, мы имеют:

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


TemplateLemmaIcon.svg Лемма «Теорема 5.1.»
Схема является самонастраивающейся до тех пор, пока


Асимптотическая эффективность

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

Оптимизация параметров в схема Гэнтри

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

Условия [9] В этой статье
Сопротивление BDD к атаке на решётку
Сопротивление SSSP к атаке парадокса дня рождений
Сопротивление SSSP к атаке на решётку
Достижение самонастройки

Для выполнения этих условий, положим и . В работе [5], эти значения были следующими: , и соответственно.


Битовая сложность

Процедура состоит в расширении шифртекста , как описано в алгоритме из , шифрования битов расширенного шифртекста на новом открытом ключе , а затем применения гомоморфно алгоритма , используя зашифрованные биты шифртекста и зашифрованный секретный ключ (под ). Мы также рассмотрим сложность гомоморфного вычисления элементарных суммирующих/умножающих шлюзов.
Давайте сначала найдём границу сложности вычисления в , вызываемого раз в алгоритме из блока 4. Во-первых, отметим, что шаги 1 и 2 не должно быть выполнены без , но возможны во времени генерации ключей, т. е. в . Обратите внимание, что во времени 3 этапа , следует также обратить внимание на выполнение сокращения по модулю (2) так, чтобы допущение леммы 5.2 было выполнено. Величина полученная на шаге 3 алгоритма из блока 4 кодируется на битах, и её вычисление может быть выполнено в элементарных операциях, используя быструю целочисленную арифметических [23]. Вычислительные расходы в пунктах 4 и 5 являются незначительными. В целом, вычисления в может быть сделано за элементарных операций.
Секретный ключ содержит бит. Битовая длина зашифрованного секретного ключа равна . Для шифрования бит по , мы используем , как описано в [5], то есть, мы рассматриваем сами биты как зашифрованные значения.
Теперь объясним, как реализуется алгоритм . Сконцентрируемся на самой трудозатратной части, т. е. на (гомоморфном) вычислении веса Хэмминга векторов из . Пусть - такой вектор. Как поясняется в [1]. [Л. 5] (которая опирается на [24] Лемма 1), достаточно вычислить хорошо развитую форму многочлена . Напомним, что в разделе 5 показано, что мы заинтересованы только в нескольких коэффициентах результата, соответствующих одночленам степени . Для простоты (и с незначительным увеличением расходов), в любом случае, вычислим полную развитую форму, а затем выбросим ложные коэффициенты. Наша схема здесь отличается от тех, что представлены в [2], [5] (гл. 9) тем, что мы используем быстрое умножение многочленов и древовидную конструкцию, вместо умножения по учебнику (school-book) и схему Горнера(Horner’s method), чтобы снизить общую асимптотическую сложности. Обратите внимание, что цепь над целыми числами, и оценивается целочисленный многочлен, чьи интересующие нас коэффициенты имеют небольшую мультипликативную степень на входах. Вычислим развитую форму с помощью бинарного дерева:

  • На уровне 0, мы имеем линейные множители .
  • На уровне , находятся многочленов степени , которые являются результатом линейных множителей, отвечающие за их бинарные поддеревья.
  • Порождающий элемент двух узлов получается путем умножения двух его потомков, с квазилинейным временем умножения для многочленов над кольцами, которые использует только операции кольца [25].


Размер каждой цепи, которая позволяет перейти от потомков на уровне к порождающему элементу на уровне , составляет . Вследствие этого, общее число суммирующих/умножающих целочисленных шлюзов равно . При гомоморфном вычислении этой схемы, каждых шлюз соответствует суммированию/умножению по модулю , то есть, благодаря нашему выбору , каждое суммирование/умножение двух целых чисел по модулю , будет иметь битовую длину . Следовательно, общая сложность составит . Таким образом, на повторное шифрование(Recrypt) 1-го бита открытого текста затрачивается элементарных операций (по сравнению с границей утверждаемой в [5] (гл. 12)). И стоимость гомоморфного вычисления на простых суммирующих/умножающих шлюзах также составит . Секретный и открытый ключ соответственно закодированы на и битах.


Открытые проблемы

Было бы интересно смягчить наши предположения и и доказать в случае других вариантов (см. полную версию F для ). Важный вопрос заключается в оценке практического воздействия наших результатов (см. [2] для реализации схемы Гентри). В конце работы [5], Гентри предлагает использовать, не являющийся независимым векторов для снижения затрат. Идея заключается в кодировании векторов с использованием только . Это приводит к более быстрой амортизированной стоимости за бит открытого текста из области определения . Тем не менее, так и не ясно, как гомоморфно расшифровать такой вариант, когда существует ограничение на более сложные схемах шлюзов, чем на сложении и умножении по модулю 2.


Благодарности:Мы благодарим Ali Akhavi, Guillaume Hanrot, Steven Galbraith, Craig Gentry и Paul Zimmermann за полезные обсуждения. Мы также благодарим анонимные отзывы, за указание на важную ошибку в разделе 4. Первый автор была частично поддержан грантом LaRedA ANR, а второй автор исследовательским грантом Macquarie University(MQRF) и ARC Discovery Грант DP0987734.

Меньшие ключи

В работе [5], Гентри предлагает повторное использование той же ключевой пары для всех уровней полностью гомоморфной схемы выведенной из теоремы 2.2. Это позволяет значительно снизить ключевые размеры самонастраивающейся полностью гомоморфной схемы. Эта стратегия может считаться безопасной, если основная самонастраивающаяся гомоморфная схема шифрования принимает во внимание безопасность сообщения, зависящего от ключа (KDM-Secure [5] (Т. 4.3.2)). Наша низкая степенная расшифровка может провалиться с не-ничтожной вероятностью после первого обновления зашифрованного текста, так как наш способ не обрабатывает зависимости шифртекста с секретным ключом. Чтобы обойти эту проблему, мы внесём случайность в зашифрованный текст, чтобы отказаться от возможного несоблюдения независимости с секретным ключом. Обратите внимание, что этот способ является особенным в модифицированной схемы Гентри, обеспечивающую конфиденциальность схемы [1]. Рассмотрим алгоритм из . Условия, необходимые для вероятностной методики, описанные в разделе 5 работы, является тем, что шифртекст (где и ) не зависит от . Этот факт, вместе с независимостью и равномерным распределения , означает, что ошибки округления в вычислении , также являются независимыми и с равномерным распределением, что по мере необходимости применяется в границах Гёфдинга. В приложении, где повторно используются ключи, внутренняя случайность в может зависеть от (в связи с предыдущей очисткой). Чтобы это обойти, мы придадим случайный характер шифртекста в другом зашифрованном тексте для того же сообщения , но с внутренней случайностью , почти независящей от . Более точно, учитывая , распределения с незначительным статистическим расстоянием от ( -независимые) распределения , где является равномерным распределением на центрированном шаре радиуса , где - любая незначительная функция от , такая, что (например, ). Мы вычислили , добавив к шифрованный 0 с достаточно большой случайностью по сравнению с случайностью в , т. е. мы задали , где выборка из . Если мы заменим радиус расшифровки на из леммы 3.2, то правильность схемы сохранится, так как и , и декодируются в один и тот же открытий текст с помощью алгоритма . Это имеет незначительный эффект для асимптотической эффективности (см. раздел 6,1). Предположим, что с . Рассмотрим статистическое расстояние между распределениями и . Так как шара радиуса содержится в пересечении двух шаров радиусов , соответствующих и , получим, что статистические расстояние между сферами не более чем и, следовательно, незначительно.


Контакты авторов материала

  1. CNRS, Laboratoire LIP (U. Lyon, CNRS, ENS de Lyon, INRIA, UCBL), 46 Allée d’Italie, 69364 Lyon Cedex 07, France, E-mail: damien.stehle@gmail.com www.perso.ens-lyon.fr
  2. Centre for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, NSW 2109, Australia, E-mail: ron.steinfeld@mq.edu.au ̃rons/ www.ics.mq.edu.au

Реквизиты

Шагаев Павел Николаевич, МГТУ им. Н.Э. Баумана, ИУ-8, e-mail:shagaev-pavel@mail.ru

Литература

  1. 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 1,10 1,11 1,12 1,13 1,14 1,15 1,16 1,17 1,18 Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proc. of STOC, pp. 169–178. ACM, New York (2009)
  2. 2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 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)
  3. 3,0 3,1 3,2 3,3 3,4 3,5 3,6 3,7 3,8 3,9 van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010)
  4. Micciancio, D., Regev, O.: Lattice-based Cryptography. In: Post-Quantum Cryptography. Springer, Heidelberg (2008)
  5. 5,00 5,01 5,02 5,03 5,04 5,05 5,06 5,07 5,08 5,09 5,10 5,11 5,12 5,13 5,14 5,15 5,16 5,17 5,18 5,19 5,20 Gentry, C.: A fully homomorphic encryption scheme. PhD thesis, Stanford Univer- sity (2009), http://crypto.stanford.edu/craig (manuscript)
  6. Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301), 13–30 (1963)
  7. 7,0 7,1 7,2 Gentry, C.: Toward basing fully homomorphic encryption on worst-case hardness. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 116–137. Springer, Hei- delberg (2010)
  8. Micciancio, D., Goldwasser, S.: Complexity of lattice problems: a cryptographic perspective. Kluwer Academic Press, Dordrecht (2002)
  9. Gentry, C.: Computing arbitrary functions of encrypted data. Communications of the ACM 53(3), 97–105 (2010)
  10. 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)
  11. Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proc. of STOC, pp. 99–108. ACM, New York (1983)
  12. Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: Proc. of STOC, pp. 351–358. ACM, New York (2010)
  13. Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)
  14. 14,0 14,1 Schnorr, C.P.: A hierarchy of polynomial lattice basis reduction algorithms. Theoret. Comput. Sci. 53, 201–224 (1987)
  15. 15,0 15,1 Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6, 1–13 (1986)
  16. Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008)
  17. Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell’s inequality. In: Proc. of STOC, pp. 207–216. ACM, New York (2008)
  18. Klein, P.N.: Finding the closest lattice vector when it’s unusually close. In: Proc. of SODA, pp. 937–941. ACM, New York (2000)
  19. Ludwig, C.: A faster lattice reduction method using quantum search. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 199–208. Springer, Heidelberg (2003)
  20. Cassels, J.W.S.: An Introduction to the Geometry of Numbers, 2nd edn. Springer, Heidelberg (1971)
  21. Karp, R.M.: A survey of parallel algorithms for shared-memory machines. Technical report (1988)
  22. 22,0 22,1 R. A. Mollin. Algebraic Number Theory. Chapman and Hall/CRC Press, 1999.
  23. C. P. Schnorr. A hierarchy of polynomial lattice basis reduction algorithms. Theoret. Comput. Sci., 53:201�224, 1987.
  24. J. Boyar, R. Peralta, and D. Pochuev. On the multiplicative complexity of boolean functions over the basis (∧, ⊕, 1). Theoret. Comput. Sci., 235(1):43�57, 2000.
  25. D. G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Inf., 28(7):693�701, 1991.