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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 10:35, 5 декабря 2015.
Fully Homomorphic Encryption with Relatively

Small Key and Ciphertext Sizes

Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes.PNG
Авторы N.P. Smart [@: 1]
F. Vercauteren[@: 2]
Опубликован 2010 г.
Сайт Public Key Cryptography 2010
Перевели Stanislav Dontsov
Год перевода 2015 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. В данной статье авторами представлена полностью гомоморфная схема шифрования с сравнительно небольшими размерами ключа и шифротекста.

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

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

Ключевые слова: шифрование, полное гомоморфное шифрование.

Ведение

Полное гомоморфное шифрование с открытым ключом было подобно Святому Граалю криптографии на протяжении долгого времени. В 2009 году проблема была решена Крейгом Джентри [1] [2] при помощи свойств идеальных решёток.

Разные криптосхемы используют решётки для аргументации своей крипто стойкости (например такие, как NTRU криптосистема [3]), в других криптосистемах решётки важны для понимания самого алгоритма [4]. Соответственно криптосистема Крейга Джентри попадает под последнюю категорию. В этой статье авторы представляют полностью гомоморфную схему, которая может быть описана с помощью элементарной теории полей алгебраических чисел, и, следовательно, не нуждается в решетках для объяснения алгоритмов шифрования и дешифрования. Тем не менее, предложенная ниже схема относится к категории схем, атаки на которые производятся с помощью решёток.

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

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

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

Обозначения

Булевы шары

С учётом заданного полинома определим -норму матрицы и -норму:

-норма:
-норма:

Для положительного значения , определим два соответствующих шара с центрами в:

Посмотрим внимательно. У нас есть следующие простые включения шаров и . Теперь определим новый булев полушар:

Сокращения

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

Нотации
  • Нотация , означает присваивание значение слева (a) значению справа (b).
  • Нотация , означает выбрать значение слева (a) из множества А справа используя равномерное распределение.

Идеалы в числовых полях

Поскольку в основе разработки схемы авторов лежат числа и простого числового поля, необходимо вспомнить некоторые основные свойства таких полей. Для этого можно посмотреть книгу-введение в элементарную теорию вычислений на поле простых чисел [5].

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

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

Нормальной практикой считается представлять базис как матрицу размерности . Матрица заполняется элементами , где , то есть мы берём строчно-ориентированное представление. Получая нормальную форму Эрмита (НФЭ) этого базиса автоматически получается нижний треугольный базис, в котором на главной диагонали выполняется . Обратите внимание, что последнее свойство НФЭ базиса следует только для матрицы, соответствующий идеалам [6] (идеалам, которые используют различную ориентацию).

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

то, для не делящихся на простые идеалы делящие представимы двумя элементами:

.

Мы определили, что степени остатков будут равны степени полинома . Сокращение по модулю дает гомоморфизм:

.

Нас будут интересовать простые идеалы вычетов первой степени. Они могут быть представлены посредством двух элементов , где - норма идеала, а - корень полинома по модулю .

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

Matrix.PNG

где . Не сложно увидеть, что НФЭ матрицы определяется как:

где в первом столбце и второй строке (а так же и в последующих строках) стоят целые числа по модулю .

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

Ограниченная гомоморфная схема

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

Сама схема

Cхема шифрования состоит из пяти алгоритмов:

  1. KeyGen / алгоритм генерации ключей (самый сложный)
  2. Encrypt / алгоритм шифрования
  3. Decrypt / алгоритм дешифрации
  4. Add / алгоритм суммирования
  5. Mult / алгоритм мультипликации

Схема параметризуется тремя переменными: . Типичным набором параметров для схемы будут выступать: . Позже мы вернемся к обсуждению влияния этих параметров на безопасность и производительность схемы.

KeyGen():

  1. представьте исходный текст в ;
  2. выберите унитарный (единичный) неприводимый многочлен степени ;
  3. проделайте следующие итерации пока не станет простым числом
    • .
    • .
    • результирующий вектор от .
  4. НОД в поле .
  5. пусть - уникальный корень
  6. применим алгоритм Евклида для нахождения НОД в чтобы получить , так, что: .
  7. .
  8. Открытый ключ - , в то время как закрытый ключ .

Encrypt(M,PK):

  1. представим как
  2. если , то завершить алгоритм
  3. вывести

Decrypt(c,SK):

  1. представим как
  2. вывести

Add(,PK):Add( c 1 , c 2 {\displaystyle c {1},c {2}} ,PK):

  1. представим как
  2. вывести

Mult(,PK):Mult( c 1 , c 2 {\displaystyle c {1},c {2}} ,PK):

  1. представим как
  2. вывести

Анализ Схемы

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

KeyGen алгоритм: мы можем пронаблюдать, что алгоритм генерации ключей генерирует элементы первостепенной нормы в числовом поле , определенном . По сути мы построили небольшую образующую простого идеала первой степени . Чтобы найти двухэлементное представление необходимо выбрать правильный корень из по модулю . Поскольку , мы получаем, что , итак и имеют по крайней мере один общий корень по модулю . Более того будет ещё один общий корень, потому как в противном случае будет генерировать два различных простых идеалов, что явно невозможно. Это объясняет тот факт, что имеет первую степень; мы используем , чтобы выбрать точный нужный корень , что соответствует идеалу , порожденному . Двухэлементное представление идеала , тогда будет выглядеть просто: .
Encrypt алгоритм: К сообщению два раза добавляют разные случайные полиномы и получают результирующий полином . -норма малых полиномов контролируется параметром . Затем шифрование сводится к простому уменьшению по модулю при помощи двухэлементного представления . Как указывалось ранее, это просто соответствует оценке в по модулю . Кроме того, обратите внимание, что это из этого следует, что .
Decrypt алгоритм: По определению шифрования мы имеем, что и - принципиал порождённый . Соответственно мы можем теперь написать:
,
Понятно, что если мы захотим восстановить , то дешифрация начнётся только когда . Заметим, что строго определено , где было получено в алгоритме генерации ключа (KeyGen). Деление на приводит к следующему равенству
.
Приведённое уравнение показывает, что если , то простое округление будет результатом правильного деления . Это позволяет выполнять верную дешифрацию, рассчитывая на компьютере выражение . Поэтому важной частью является получение ограничения на .
TemplateTheoremIcon.svg Теорема Лемма 1
Пусть и - нормированный многочлен, а степень и степень , да и результирующий вектор , тогда существует многочлен такой, что: и .
Доказательство
Мы знаем, что НОД , значит существуют полиномы , такие, что их степени соответственно меньше и и в то же время . Известно (исходя из следствий 6.15 в [10] ) что полиномы и заданы следующим образом: , а , где и являются решением:
, где - матрица Сильвестра многочленов .

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

В оставшейся части статьи мы будем считать, что . Определим
.
Теперь мы имеем, что:
.
Джентри в разделе 7.4 [2] получает несколько границ для представленного выше элемента, но для 2-нормы (и это легко получить) границы аналогичны границам для -нормы. Чтобы проиллюстрировать два крайних случая, то есть, когда может колебаться от абсолютной экспоненты до линейно относительных , мы даем следующую лемму, которая также поясняет, почему мы предлагаем использовать на практике.
TemplateTheoremIcon.svg Теорема Лемма 2
Пусть и , тогда и .
Доказательство
Пусть и , тогда , из которого немедленно следует ограничение на . Аналогично пишем , затем с для и . Поскольку все очевидно меньше, чем получим границу на .
Благодаря этому, мы можем заключить, что:
,
потому дешифрация будет продолжаться настолько долго, насколько:
.
Заметим, что ожидаемая величина будет примерно равна поскольку результирующий вектор будет около . Поэтому для мы имеем
,
и пока и мы наконец получаем упрощенную функцию расшифровки:
,
где это . Обратите внимание, если мы заинтересованы в округлении к ближайшему целому числу и затем беря это число по модулю 2, мы можем принимать B, как по модулю . Более того Лемма 1 подразумевает, что все коэффициенты полинома будут меньше чем , поскольку - результирующий вектор от и таким образом . Это означает, что приведение по модулю в генерации ключа не будет иметь никакого эффекта в большинстве случаев. Тем не менее, это оказажется необходимым предположением в обеспечении равномерного распределение, когда мы переходим к полной, а не частичной, гомоморфной схеме.
Для нашего алгоритма KeyGen каждый коэффициент имеет размер примерно ?, что означает, что у нас есть оценка:
.
Для , таким образом, мы получаем оценку . В остальной части статьи мы будем также иногда используют вместо . Обратите внимание, что если кто-то хочет, сравнить данную схему со схемой Джентри, следует принимать во внимание что наши границы сформулированы для -нормы, в то время как Джентри работает с 2-нормой.
And и Mult алгоритмы: Очевидно, что оба алгоритма являются правильными. Тем не менее, мы должны принять во внимание, как ошибки влияют на алгоритмы: отдельно алгоритм Добавления (Add) и алгоритм Умножения (Mult). В частности дешифрация будет происходить за полиномиальное , если . Однако, когда мы применяем алгоритмы Add и Mult на зашифрованном тексте значение начинает лежать в шарах всё большего и большего радиуса. Как только мы теряем гарантию на то, что текст послание будет расшифровано верно. Именно поэтому представленная схема ограниченно гомоморфна, так как благодаря этому мы имеем возможность использовать алгоритмы Add и Mult ограниченное число раз.
Пусть и обозначают два зашифрованных текста соответствующих двум случайно полученным и , где - сообщения, а - случайные числа, то есть . Предположим:
,
,
где . Тогда:
и .
Первоначально мы начинали с зашифрованного текста лежащего в . После выполнения схемы с мультипликативной глубиной , мы ожидаем, что зашифрованный текст будет соответствовать полиномиальному , лежащему в шаре вместе c . Таким образом, можно расшифровать только вывод такой схемы, где , то есть:
.

Анализ безопасности

Мы рассмотрим три аспекта безопасности: восстановление ключа, однонаправленность шифрования и семантику безопасности. В то время как, семантика безопасности основывается на впервые обнаруживаемых нетрадиционных проблемах, другие два понятия крепко связаны с уже хорошо изученными проблемами в теории чисел. Это свойственно так же и для других понятий в криптографии: например, ключ восстановления в схеме шифрования ElGamal связаны с DLP проблемой и семантикой безопасности (которая сравнительно малоизвестна для математиков) проблемы DDH. Что ж, покажем, что представленная схема является в некотором смысле специализацией и оптимизацией схемы Джентри.

Связь с схемой Джентри

Для обсуждения безопасности в более широк смысле, сначала покажемь, что наша схема является специализацией и упрощением схемы Джентри [1]. Порождающий элемент эквивалентен частному базису идеала схемы Джентри, тогда общий базис - двуэлементное представление вида . Идеал схемы Джентри просто принимается за идеал . Таким образом, мы видим, что наш алгоритм KeyGen - это специализированная форма KeyGen'а схемы Джентри: в частности мы используем компактное двуэлементное представление общего базиса вместо громоздкого НФЭ представления у Джентри.

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

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

Восстановление ключей

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

TemplateDifinitionIcon.svg Определение «Определение 1 : Проблема малого главного идеала»
Представление главного идеала в виде любых двух элементов НФЭ приводит к вычислению малого порождающего элемента идеала

Это одна из основных проблем в теории чисел, которая легла в основу предыдущих криптографических предложений (например в [11]). В настоящее время существует два подхода к решению данной проблемы.

Подход первый заключается в детерминированном методе, основанном на алгоритме Шенкса (алгоритме больших и малых шагов [12]. Применение данного алгоритма на практике занимает следующее время:

,

где - дискриминант , регулятор, минимальная логарифмическая реализация . Ясно, что может быть ограничена .

Второй подход к решению данной проблемы заключается в использовании субэкспоненциального алгоритма Бухмана (Buchmann) для единиц и групп класса, которые описаны в [7] и главе 6 книги [5]. Этот метод имеет сложность

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

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

Односторонность шифрования

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

,

где , для некоторого целого значения .

Сведём данную проблему к проблему решётки. Для этого рассмотрим порождённую строками матрицы рассматриваемой нами ранее. Рассмотри вектор вектор решётки

.

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

Тем не менее, лежащая в основе решетка уже хорошо изучена в теории алгоритмических (приложения LLL, описанные в [13] [14] [15]). Решетка генерируется матрицей, такой как , а именно матрицой Эрмита в нормальной форме, в которой все, кроме одного диагонального элемента равны единице (это, вероятно, наиболее изученная проблема решетки с вычислительной точки зрения в теории чисел). Хоть мы и не в состоянии свести алгоритма нашей схемы к худшей или же средней сложности, основная проблема решетки уже хорошо изучена.

Тем не менее, для последующего использования, мы вкратце вспомним результат полученный Джентри для данной проблемы. Хотя следует иметь в виду, что Джентри работал с общей решеткой, возникающей из НФЭ идеала, а не с той, которая используется в нашей схеме. Наиболее известной атакой на схему Джентри является сокращение одной из решёток, связанное с проблемой декодирования с ограниченным расстоянием (bounded distance decoding problem - BDDP). В частности, это связано с возможностью найти короткий/близкий вектор к мультипликативному множителю в решетке размерности N. Если мы положим, что:

,

то считается, что решения проблемы BDDP имеет сложность (см [2] [Раздел 7.7]). Мы будем ссылаться на значение как на уровень безопасности нашей ограниченной гомоморфной схемы.

Семантика безопасности

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

TemplateDifinitionIcon.svg Определение « Определение 2 (Проблема полиномов смежных классов)»
Претендент сначала выбирает и запускает алгоритм генерации ключа чтобы определить значения . Если , претендент выполняет:
  1. ,
  2. .

Если , претендент выполняет:

  1. .
Определив сталкиваемся с проблемой определения : или .

Проблема была названа авторами именно так (Polynomial Coset Problem), потому что она сходна с проблемой идеалов смежных классов (Ideal Coset Problem) Джентри из [1]. Проблема в основном говорит, о том, что никто не может определить, является ли оценкой некоторого малого многочлена на или это случайная величина по модулю . Обратите внимание, что размер пространства примерно схож с , поскольку имеет размер . Так что, если гораздо меньше, чем , мы пытаемся выделить достаточно небольшое пространство в большом. Обратите внимание, что в случае, когда мы создаем значение из , а когда мы создаем значение из , так как мы заинтересованы в том, чтобы простейший шифротекст был устойчив к взлому.

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

TemplateTheoremIcon.svg Теорема Теорема 1
Предположим, что имеется алгоритм , который разрушает семантику безопасности нашей ограниченной гомоморфной схемы с преимуществом . Тогда существует алгоритм , работает примерно с такой же сложностью по времени, как , который решает Проблемe полиномов смежных классов с преимуществом .
Доказательство

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

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


Полностью гомоморфная схема

Перейдем теперь к преобразованию частично гомоморфной схемы в полную гомоморфную схема. Мы показали, что наша схема является специализацией схемы Джентри, теперь нам осталось лишь преобразовать параметры нашей ограниченной схемы к схеме Джентри. И мы можем это сделать так как наш зашифрованный текст представлен в виде целого числа, а не в виде вектора. Мы будем отталкиваться от предположения, что наша схема сохраняет свойство безопасности в рамках ключевых параметров шифрования. Нам необходимо определить новый алгоритм Recrypt() который будет брать зашифрованный раннее и презашифровывать его в , который так же будет исправлять ошибки. Интуитивно он действует как "очищающий" алгоритм для "грязного" шифротекста .

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

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

Теперь мы можем описать работу алгоритма повторного шифрования.

Recrypt (c, PK): Этот алгоритм принимает на входе "грязный" зашифрованный текст , а затем, исправляя ошибки, производит более "чистый" зашифрованный текст и того же сообщения. Перезашифровка работает, выполняя гомоморфную дешифрацию шифрования шифртекста. В приложении к статье авторы подробно объясняю алгоритм Recrypt(c, PK) и делают анализ насколько сложно , применять его для значений из реальной жизни.

Обратите внимание что у нас есть , будем требовать чтобы дополнительная информация спрятанная в открытом ключе (внесённая нами, как мы понмим, в случае полного гомоморфного шифрования) не ставила под угрозу безопасность схемы. Джентри в своей работе, для снижения рисков безопасности использует проблему разреженных подклассов суммы (sparse subset-sum problem - SSSP). То же самое, предположительно должны сделать и мы. Проблема разреженных подклассов сумм, как полагают, по крайней мере использует шагов (конечно предполагая, что мы не находимся в разреженных подклассах, т.е ). Если мы возьмем немного больше, чем , то мы должны выбрать такой , что:

,

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

Увеличение пространства для шифруемых сообщений

Покажем теперь, что наша схема является более мощной в сравнении с схемой Джентри. В работе [1] свойство полной гомоморфности может быть применено только к однобитовым сообщениям, так как алгоритм Recrypt для полноразмерных сообщений является относительно сложным. Покажем теперь, что мы можем получить полностью гомоморфное шифрование N-битовых сообщений (а затем обсудим, что это на самом деле означает и какого успеха мы добились). Во-первых вернёмся головой к нашей основной схеме. Мы изменили алгоритм Keygen для реализации вывода всего многочлена по модулю в роли секретного ключа как противоположность параметру . Пусть итоговый полином будет определён как . Так мы получаем шифрование модифицированное для получения на вход любых сообщений над полем , то есть любой бинарный полином степени меньшей чем . Тогда дешифрацию нужно производить по по-хитрому: а именно каждый коэффициент из дешифровать отдельно:

.

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

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

.

Секретный ключ теперь будет принимать иные значения: в случае если , то , иначе - . Сначала мы применяем хитрый алгоритм Recrypt, рассмотренный чуть выше, получаем новые "чистые" зашифрованные биты сообщения, то есть мы получаем:

.

Если мы просто хотим провести шифрование входящего текста (не шифрованного ранее) мы вычисляем:

.

Следует отметить, что пересборка шифротекста служит причиной рост вероятности совершения ошибки остаточного члена с коэффициентом . Подобная проблема является наследством умножения вектора ошибок на .

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

.

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

Итоги реализации

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

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

,

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

.

В следующей таблице вы сможете увидеть зависимость параметров от роста величины :

8 4096 2^25 5 0.3 2^36 8 0.0
9 11585 2^31 6 0.8 2^40 7 0.3
10 32768 2^41 7 1.2 2^48 8 0.8
11 92681 2^54 8 1.7 2^61 9 1.2
12 262144 2^73 10 2.1 2^80 11 1.6
13 741455 2^100 12 2.5 2^107 13 2.1

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

6 7 8 9 10 11 12 13
7 7 7 8 8 8 8 8

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

Несмотря на проблемы с получением полностью гомоморфной схемы, мы всё таки протестировали алгоритмы частично гомоморфной схемы на настольном компьютере x86-64 платформы с процессором Intel Core 2 (6600 - 2,4 ГГц) с использованием библиотеки NTL и C-компилятора GCC 4.3.2. Мы были не в состоянии генерировать ключи для параметра , а меньшие значения ключей занимало по несколько часов. Проблема заключалась в алгоритме KeyGen: было необходимо вычислять множество результирующих и затем тестировать их на простоту. Так происходило потому, что выход полученного расчета имел размерность в бит (что ж, не только мы работаем с большими числами). Более общая версия KeyGen позволяет вычислять на безквадратных неосновных результирующих. Но даже в этом случае получения ключей, скажем для , кажется пугающим. Таким образом, мы не приводим тестов для алгоритма Keygen. Время (в миллисекундах), и фактическое значение d рассчитанное для специфичного ключа, представлены в следующей таблице:

Encrypt Decrypt Mult
8 4.2 0.2 0.2 1.0 0.0
9 38.8 0.3 0.2 1.5 1.0
10 386.4 0.6 0.4 2.0 1.0
11 3717.2 3.0 1.6 2.5 1.5

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

Приложение: анализ процедуры повторного шифрования

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

,

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

.

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

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

,

итоговое значение будет:

.

Приведенное выше уравнение является производным от изучения четырёх возможных случаев значений :

Итог
0 0
1 0
0 1
1 1

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

.

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

5 6 7 8 9 10 11 12 13 14
3 3 3 4 4 4 4 4 4 4
5 5 5 5 6 6 6 6 6 6

Таким образом, мы видим, что значение , по существу, либо 3, либо 4, а значение будет 5 или 6.

Алгоритм вторичного шифрования принимает на вход шифрованный текст и открытый ключ и состоит из следующих отдельных этапов:

  1. Записываем первые бит вещественных чисел как матрицу размерности для и .
  2. Шифруем каждый бит открытым ключом чтобы получить матрицу размерностью заполненную "исправленными" значениями.
  3. Умножаем каждую строку матрицы на соответствующий шифрованный параметр элемента , чтобы получить . Так мы получаем матрицу в которой зашифрованы только ненулевых строк.
  4. Вычисляем сумму каждого столбца как вес Хэмминга, используя симметричный многочлен: таким образом мы понижаем сумму значений и приближаем её к сумме , вещественных чисел обозначенных с точностью в бит. Точнее говоря обозначим за j-ый бит веса Хемминга i-ой колонны матрицы (для и ) и сформируем матрицу right hand side размерностью с всякий раз когда правая сторона определена, а в других местах стоят нули.
  5. Объединим строки матрицы так, чтобы определить новую матрицу размерности у которой сумма строк равна сумме строк матрицы .
  6. Применяем суммирование для снижения строк матрицы до одной / двух (каждый набор из трех строк уменьшается до двух, а затем эта процедура повторяется).
  7. Выполняем итоговое суммирование и выводим зашифрованный бит.

Уместно напомнить, что в нашей схеме и выбирается так, чтобы , где - уровень безопасности нашей схемы определяющий . Значение примерно эквивалентно , таким образом является очень большим. Зашифрованные сообщения это целые числа по модулю p, каждое такое верно расшифрованное сообщение (число) может находится в булевом шаре заданного радиуса. "Чистые" сообщения ( что предварительно прошли процедуру исправления ошибок) лежат в булевом шаре радиуса , соответственно если у нас растёт размер такого сообщения, то и растёт радиус, а значит сообщение становится более "грязным". Вспомним, что у мы имеем следующие параметры: пусть и - два зашифрованных сообщения соответствующих двум случайным числам и (где - сообщения, а - случайные составляющие, то есть ). Для зашифрованного сообщения определим - радиус булева шара содержащего соответствующий многочлен , то есть мы имеем . Тогда:

,
.

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

Этап 1 и Этап 2

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

Этап 3

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

Этап 4

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

.

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

Для каждого столбца матрицы выполним следующую функцию для того, чтобы вычислить кодирование битов веса Хемминга j-го стобца где :

  • установим ,
  • для проделаем
    • для проделаем
    • .
  • вернём .

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

, , , .

Таким образом, мы имеем:

,
,
,
.

Определяя биты (для и ) весов Хемминга столбцов, сумма итоговых вещественных чисел представленных строками матрицы определяется как:

.

Поскольку нас интересует только сумма по модулю 2, мы видим, что сумма большая, чем сумма по модулю 2 соответствует сумме строк матрицы размерности с (правая часть определена в ноль в любом случае). Поэтому в зависимости от и мы получаем следующие матрицы :

  • в случае :
  • в случае :
  • в случае :

Этап 5

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

  • в случае :
  • в случае :
  • в случае :

Этап 6

Будем уменьшать количество строк до двух в наших матрица, для этого применим сумматор с запоминанием переноса. Сначала применим единую цепь сумматоров чтобы делать вычисления в первых трех строках наших матриц , вывод сумматоров будет состоять из двух строк, где первая строка просто содержит поэлементное сложение трех строк по модулю 2, а вторая строка содержит сумму произведений каждой пары строк из трёх подающихся на вход. Примечание: мы игнорируем любые переполнения в битах, соответствующие двоичному весу и выше. Если матрица имеет четыре ряда, то мы просто добавим эту четвертую строку к результату и ещё раз применить другую цепь сумматоров с запоминанием переноса. В любом случае в конце этой стадии мы получаем матрицу размерности . Итак, теперь оценки выглядят следующим образом:

  • в случае :
  • в случае :
  • в случае :

Этап 7

В финальном этапе мы складываем две получившиеся строки матрицы вместе и представляем итоговое выражение как:

,

тогда для :

,
,

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

  • в случае :
  • в случае :
  • в случае :

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

(3,5) (4,5) (4,6)

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

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

Глубина
5, 6, 7 (3, 5) 7
8 (4, 5) 7
9, 10, 11, 12, 13, 14 (4, 6) 8

Напомним, что величина оригинального определяется отношением и эквивалентно . Чтобы достичь полного гомоморфного шифрования мы требуем выполнения отношения:

,

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

,

что показывает, что для возможно получить полную гомоморфическую схему шифрования. Это соответствует или иначе выражаясь .

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

Авторы хотели бы поблагодарить eCrypt NoE за оказание поддержки при создании данной научной работы. Первый автор был награждён Лондонским Королевским Обществом премией Wolfson Merit Award. Второй автор получил докторскую стипендию исследовательского фонда Flanders. Авторы хотели бы также поблагодарить Флориан Гесс, Стивен Гэлбрейт и Джо Сильверман за ценные замечания по ранним версиям этой статьи и Крейга Джентри за подробное объяснение его работы [1].

Связаться с авторами

  1. Dept. Computer Science, University of Bristol, Merchant Venturers Building, Woodland Road, Bristol, BS8 1UB, United Kingdom, E-mail: nigel@cs.bris.ac.uk
  2. COSIC - Electrical Engineering, Katholieke Universiteit Leuven, Kasteelpark Arenberg 10, B-3001 Heverlee, Belgium., E-mail: fvercaut@esat.kuleuven.ac.be

Литература

  1. 1,0 1,1 1,2 1,3 1,4 1,5 1,6 C. Gentry. Fully homomorphic encryption using ideal lattices. In Symposium on Theory of Computing - STOC 2009, ACM, 169-178, 2009.
  2. 2,0 2,1 2,2 C. Gentry. A fully homomorphic encryption scheme. Manuscript, 2009.
  3. J. Hoffstein, J. Pipher and J.H. Silverman. NTRU: a ring-based public key cryptosystem. Algorithmic number theory - ANTS III, Springer-Verlag LNCS 1423,267-288, 1998.
  4. O. Goldreich, S. Goldwasser and S. Halevi. Public-key cryptosystems from lattice reduction problems. In Advances in Cryptology - CRYPTO '97, Springer-Verlag LNCS 1294, 112-131, 1997.
  5. 5,0 5,1 H. Cohen. A Course in Computational Algebraic Number Theory. Springer GTM 138, 1993.
  6. J. Ding and R. Lindner. Identifying ideal lattices. IACR eprint 2009/322.
  7. 7,0 7,1 J. Buchmann. A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. Seminaire de Theorie des Nombres - Paris 1988-89, 27-41, 1990.
  8. C. Thiel. On the complexity of some problems in algorithmic algebraic number theory. PhD thesis, Universit?at des Saarlandes, Saarbr?ucken, Germany, 1995.
  9. S. Hallgren. Fast quantum algorithms for computing the unit group and class group of a number field. In Symposium on Theory of Computing - STOC 2005, ACM 468-474, 2005.
  10. J. Von Zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 1999.
  11. J. Buchmann, M. Maurer and B. M?oller. Cryptography based on number fields with large regulator. Journal de Theorie des Nombres de Bordeaux, 12, 293-307,2000.
  12. J. Buchmann. Zur Komplexit?at der Berechungung von Einheiten und Klassenzahlen algebraischer Zahlk?orper, Habilitationsschrift, 1987.)
  13. A.K. Lenstra, H.W. Lenstra, Jr. and L. Lovasz. Factoring polynomials with rational coeffcients. Mathematische Ann., 261, 513-534, 1982.
  14. P.Q. Nguyen and J. Stern The two faces of lattices in cryptology. In Cryptography and Latticesm - CaLC 2001, Springer-Verlag LNCS 2146, 146-180, 2001.
  15. B.M.M. de Weger. Algorithms for Diophantine Equations. PhD thesis, University of Leiden, 1987.