О ГОМОМОРФНЫХ КРИПТОСИСТЕМАХ

Буртыка Филипп Борисович

Магистрант 2 года, кафедра информатики
и вычислительного эксперимента ЮФУ, г. Ростов-на-Дону

Е-mail: bbfilipp@yandex.ru

Трепачева Алина Викторовна

Магистрант 2 года, кафедра информатики
и вычислительного эксперимента ЮФУ, г. Ростов-на-Дону

Е-mail: alina666dmalina@yandex.ru

Предложена  простая схема гомоморфного шифрования. Рассмотрена возможность шифрования вычисляемого над данными полинома в криптосистеме «Полли Крэкер».

Введение

Полностью гомоморфная криптографическая система с приемлемой скоростью работы — необходимое условие для обеспечения работоспособности многих современных криптографических приложений. Она позволила бы осуществлять поиск, статистические вычисления, электронное голосование [17], схемы обязательств [17], защищенное делегирование вычислений [10, 11], многосторонние секретные вычисления [17] и любые другие операции над зашифрованными данными, что избавило бы от необходимости искать компромисс между конфиденциальностью и удобством. Это дало бы мощный толчок для развития облачных платформ, решило бы вопрос с утечками персональных данных пользователей многих интернет-сервисов, сильно упростило бы жизнь организациям, работающим с чувствительными медицинскими или финансовыми данными. В 2009 сотрудник IBM Крейг Джентри [12] представил систему, которая позволяет производить операции с зашифрованными данными, хранящимися в «облаках». Информация ни на одном из этапов её передачи и обработки не расшифровывается; единственным ключом владеет клиент. В работе [11] была предложена схема полностью гомоморфного шифрования над целыми DGHV. В работах [8] и [9] она была усовершенствована. Однако, схема до сих пор не является достаточно удобной для практического применения. Причиной этого является сложная и громоздкая процедура перешифрования. В работе [9] была предложена т.н. метод замены модулей, который исключает процедуру перешифрования, однако также достаточно трудоемок в вычислительном плане.

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

 1.     О полностью гомоморфном шифре простой замены

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

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

Как обычно, обозначим криптосистему как пятерку множеств , где:  — множество открытых текстов;

— множество шифртекстов;

 —ключевое множество,

—семейство параметризованных элементами множества  отображений шифрования;

—семейство параметризованных элементами множества  отображений расшифрования. Выполняется: .

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

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

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

Замечание 2: Достоинством приведенной конструкции является то, что степень вычисляемого полинома  не ограничена.  Другое достоинство в том, что коэффициенты  скрываются от сервера.

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

В качестве приложения можно привести секретный калькулятор, как в работе [4].

2. Шифрование вычисляемого полинома в криптосистеме «Полли Крэкер».

Рассмотрим обобщенный вариант криптосистемы «Полли Крэкер» [6]. Пусть  — конечное поле,  — кольцо полиномов от  переменных, на множестве мономов  задано некоторое мономиальное упорядочение .

Секретный ключ:  В качестве секретного ключа выступает базис Грёбнера  идеала  по отношению к мономиальному упорядочению .

Публичный ключ: Выбирается набор полиномов  такой, что .

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

Шифрование: Пусть  — открытый текст, тогда соответствующий шифртекст вычисляется так: . Здесь  - случайные полиномы из .

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

Безопасность приведенной криптосистемы сводится к сложности задачи вычисления базисов Грёбнера для идеалов полиномиального кольца. В общем случае известно, что эта задача является EXPSPACE-трудной. Однако, на практике всё зависит от конкретного выбора параметров.

«Полли Крэкер» обладает гомоморфными свойствами. А именно, если имеются два шифртекста , то: 1) их сумма  - это шифровка  2) их произведение:  - это шифровка . Однако, стоит отметить, что «Полли Крэкер» не является в строгом смысле полностью гомоморфной [11] [13], так как во время вычислений размер шифртекста экспоненциально растет. Тем не менее, если арифметическая схема, которую нужно вычислить над данными, выражается в виде полинома маленькой степени, то можно воспользоваться криптосистемой «Полли Крэкер» для организации секретных вычислений.

Модификация «Полли Крэкер»

Зафиксируем, как в предыдущем пункте два представления конечного поля  —  и , где— неприводимые полиномы, . Найдем между ними изоморфизмы , .

Установим в криптосистеме «Полли Крэкер» поле , . Поле  скрывается,  — публичное. Как следствие, вместо набора многочленов  публикуется набор , где  переход  осуществляется соответствующей подстановкой в коэффициенты .

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

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

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

 3.  Шифрование вычисляемого полинома в схеме из работы [4]

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

1) Выбирается случайным образом секретное число  .

2) Для случайно выбирается число , затем выбирается , так чтобы выполнялось .

3) Клиент отправляет на сервер линейные многочлены  и функцию .

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

Данная схема используется авторами [4] для организации защищенного калькулятора.

 Модифицируем теперь схему из [4] таким образом, чтобы от сервера скрывались не только данные , над которыми производятся вычисления, но и сама функция . Воспользуемся для этого вариантом криптосистемы «Полли Крэкер», предложенным Коблицом в работе [13].

 «Полли Кракер» из работы [13]

 Пусть пространство открытых текстов  — это конечное поле , где  для некоторого простого числа  и .

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

1) Выбирается случайным образом  — секретный ключ.

2) Из идеала  кольца полиномов  выбираются полиномы . Это публичный ключ.

 Шифрование:

1) Выбираются случайным образом полиномы .

2) Вычисляется шифртекст  для  открытого сообщения .

Расшифрование:  вычисляется .

 Замечание1: Безопасность этой криптосистемы основывается на том факте, что в общем случае решение системы полиномиальных уравнений над конечным полем является NP – трудной задачей.

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

 Модификация схемы вычислений из работы [4]

Для того чтобы скрывать в [4] не только данные , но и вычисляемую функцию , будем шифровать  с помощью «Полли Крэкер». А именно, последовательность действий будет следующая.

 1) Клиент выбирает полиномиальную функцию  и точку  в которой нужно её вычислить ( - некоторое поле).

2) Генерируются полиномы  такие, что .

3) Выбираются случайным образом полиномы .

4) Вычисляется .

5) Выбирается случайным образом секретный элемент .

6) Для случайно выбирается , затем выбирается , так чтобы выполнялось .

7) Клиент отправляет на сервер линейные многочлены  и многочлен.

8) Сервер осуществляет подстановку  и возвращает  клиенту.

9) Клиент вычисляет  по схеме Горнера (очевидно справедливо).

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

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

Список литературы:

1.       Ван дер Варден Б. Л. Алгебра: пер. с нем. – М.: Наука, 1976. – 648 c.

2.       Деундяк В. М., Маевский А. Э. Введение в теорию помехоустойчивых систем передачи данных: учебник –  Ростов н/Д: ЮФУ, 2008. – 249 с.

3.       Кренделев С. Ф. Гомоморфное шифрование. Защищенные облачные вычисления, презентация: Режим доступа http://www.ruscrypto.org/netcat_files/File/ruscrypto.2011.008.zip, свободный

4.       Защищенные облачные вычисления. Гомоморфное  шифрование / С. Кренделев, О. Косырькова, А. Жиров, М. Усольцева, М. Яковлев. – Новосибирск: Лаборатория НГУ-Parallels, 2011. – 7 c.

5.       Титов С. С., Торгашова А. В. Генерация неприводимых многочленов связанных степенной зависимостью корней // Доклады Томского государственного университета систем управления и радиоэлектроники. – Томск: Издательство ТУСУР, 2010. – № 2(22) Ч.1. – С. 310—318

6.       Ackermann P. and Kreuzer M. Grobner basis cryptosystems. Applicable Alg. in Eng. // Commun. and Comput., 17:173–194, 2006.

7.       Zvika Brakerski and Vinod Vaikuntanathan: Fully Homomorphic Encryption from Ring-LWE and Security for Key. Dependent Messages. In Advances in Cryptology – CRYPTO 2011 // Lecture Notes in Computer Science. 2011. – Vol. 6841. – P. 505—524.

8.       Jean-Sébastien Coron, Avradip Mandal, David Naccache and Mehdi Tibouchi: Fully Homomorphic Encryption over the Integers with Shorter Public Keys. In Advances in Cryptology – CRYPTO 2011 // Lecture Notes in Computer Science, 2011. – Vol. 684. – P. 487—504.

9.       Jean-Sébastien Coron, David Naccache and Mehdi Tibouchi. Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers. In Advances in Cryptology – CRYPTO 2012 // Lecture Notes in Computer Science, 2012. – Vol. 7237. – P. 446—464.

10.  Kai-Min Chung, Yael Kalai and Salil Vadhan. Improved delegation of computation using fully homomorphic encryption // In Proceedings of the 30^th Annual Conference on Advances in Cryptology. Lecture Notes in Computer Science, CRYPTO'10. – Berlin, Heidelberg: Springer-Verlag, 2010. – Vol. 6223. – P. 483—501.

11.  Ronald Cramer, Rosario Gennaro and Berry Schoenmakers. A secure and optimally efficient multi-authority election scheme // In Proceedings of the 16^th Annual International Conference on the Theory and Application of Cryptographic Techniques. Lecture Notes in Computer Science, EUROCRYPT'97. – Berlin, Heidelberg: Springer-Verlag, 1997. – Vol. 1233. – P. 103—118.

12.  Fully homomorphic encryption over the integers / M. van Dijk, C. Gentry, S. Halevi and V. Vaikuntanathan // In H. Gilbert (Ed.), EUROCRYPT 2010, LNCS, Springer, 2010. – Vol. 6110. – P. 24—43.

13.  Fellows M. and Koblitz N. Combinatorial cryptosystems galore! – Contemp.Math., 168:51–61, 1994.

14.  Rosario Gennaro, Craig Gentry, and Bryan Parno. Non-interactive veriable computing: Outsourcing computation to untrusted workers // In Proceedings of the 30^th Annual Cryptology Conference, of Lecture Notes in Computer Science, CRYPTO'10. – Berlin, Heidelberg: Springer-Verlag, 2010. –Vol. 6223. – P. 465—482.

15.  Craig Gentry. A fully homomorphic encryption scheme // PhD thesis. – Stanford University. – 2009. – URL: http://crypto.stanford.edu/craig.

16.  Craig Gentry. Computing arbitrary functions of encrypted data // In Communications of the ACM, 2010. – Vol. 53, N. 3. – P. 97—105.

17.  Doerte K. Rappe. Homomorphic cryptosystems and their applications.  // Cryptology ePrint Archive, Report. – 2006. – URL: http://eprint.iacr.org/.

18.  Ronald L. Rivest, Adi Shamir and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems // Commun. ACM, 21:120—126, February, 1978.

19.  Berry Schoenmakers. Internet Technology Fully Auditable Electronic Secret-Ballot Elections, 2000.