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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

История[править | править вики-текст]

В 1978 году, всего спустя год после разработки известного алгоритма с открытым ключом RSA, его авторами Рональдом Ривестом, Леонардом Адлеманом, а также Майклом Дертузосом впервые было сформировано такое понятие, как гомоморфное шифрование[1]. Однако их первые попытки потерпели неудачу. Тогда авторы решили, что их идея не подлежит реализации. С тех пор более 30 лет было непонятно, возможно ли вообще гомоморфное шифрование. Хотя и были попытки создать такую систему. Например, система шифрования Шафи Гольдвассер и Сильвио Микали была предложена ими 1982 году, и она достигла значительного уровня безопасности. Эта система была лишь добавочным гомоморфным шифрованием и могла зашифровать всего лишь один бит. Такое же понятие было предложено в 1999 году Паскалем Пэйе. К сожалению его криптосистема оказалась тоже лишь добавочным гомоморфным шифрованием. Несколько лет спустя, в 2005 году Дэн Бонэ, Ю -Чжин Го и Коби Ниссим предложили систему шифрования, которая поддерживала неограниченное количество операций сложения, но самое большее одного умножения[2].

Области применения[править | править вики-текст]

  • Облачные системы

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

  • Электронное голосование

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

  • Поиск без раскрытия

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

Частично гомоморфные системы[править | править вики-текст]

Частично гомоморфные криптосистемы — это такие криптосистемы, которые гомоморфны относительно только одной операции (или сложения, или умножения).

В ниже описанных примерах обозначение \mathcal{E}(x) является функцией шифрования от сообщения x

Криптосистема RSA[править | править вики-текст]

Эта асимметричная криптосистема в настоящее время является широко распространенной в мире и называется так по первым буквам в именах создателей R. Rivest, A. Shamir, L. Adleman. Криптосистема RSA является популярной криптографической схемой с открытым ключом. Криптосистема RSA гомоморфна по умножению. Пусть n - модуль RSA, и e - открытый ключ шифрования. Функция шифрования имеет вид: E(x)=x^e\;\bmod\ n. Покажем гомоморфизм по умножению: E(m_1)*E(m_2)=m_1^e*m_2^e\;\bmod\ n=(m_1m_2)^e\;\bmod\ n=E(m_1m_2)

Криптосистема Эль-Гамаля[править | править вики-текст]

Данная система является альтернативой алгоритму RSA и при равном значении ключа обеспечивает ту же криптостойкость. Эль-Гамаль (Taher Elgamal) усовершенствовал алгоритм Диффи-Хеллмана и получил алгоритмы для шифрования и для обеспечения аутентификации. Криптосистема Эль Гамаля является криптосистемой вероятностного шифрования. Ее функция шифрования гомоморфна относительно операции умножения открытых текстов: криптограмма произведения может быть вычислена как произведение (попарное) криптограмм сомножителей. Если E(y,m_1)=(y^{r_1}m_1,g^{r_1}) и E(y,m2)=(y^{r_2}m_2,g^{r_2}),то E(y,m_1m_2) можно получить в виде (y^{r_1}y^{r_2}m_1m_2,g^{r_1}g^{r_2}).

Криптосистема Гольдвассер — Микали[править | править вики-текст]

В криптосистеме Гольдвассер - Микали, если открытым ключом является модуль m, тогда функция шифрования бита b: E(b)=x^br^2\;\bmod\ m для случайного элемента r\in{0,...,m-1}. Тогда эта криптосистема гомоморфна для операции умножения: E(b_1)*E(b_2)=x^{b_1}r_1^2x^{b_2}r_2^2=x^{b_1+b_2}(r_1r_2)^2=E(b_1\oplus b_2), где \oplus есть сложение по модулю 2.

Криптосистема Пэйе[править | править вики-текст]

В криптосистеме Пэйе, если открытый ключ является модулем m и случайное число g, тогда функция шифрования от сообщения x представлена в виде \mathcal{E}(x) = g^x r^m \;\bmod\; m^2, для случайной величины r \in  \{0, \ldots, m-1\}. Тогда гомоморфное свойство

\mathcal{E}(x_1) \cdot \mathcal{E}(x_2) = (g^{x_1} r_1^m)(g^{x_2} r_2^m) = g^{x_1+x_2} (r_1r_2)^m = \mathcal{E}( x_1 + x_2 \;\bmod\; m)

Криптосистема Бенало[править | править вики-текст]

В криптосистеме Бенало, если открытый ключ является модулем m, тогда функция шифрования сообщения x представлена в виде \mathcal{E}(x) = g^x r^c \;\bmod\; m, для случайного r \in  \{0, \ldots, m-1\}. Тогда гомоморфное свойство :

\mathcal{E}(x_1) \cdot \mathcal{E}(x_2) = (g^{x_1} r_1^c)(g^{x_2} r_2^c) = g^{x_1+x_2} (r_1r_2)^c = \mathcal{E}(x_1 + x_2 \;\bmod\; c )

Другие частично гомоморфные криптосистемы[править | править вики-текст]

Полностью гомоморфное шифрование[править | править вики-текст]

Каждый из описанных выше примеров, позволяет производить гомоморфные вычисления только для одной операции (или сложения или умножения) открытых текстов. Криптосистема, которая поддерживает и сложение и умножение (таким образом сохраняя структуру колец открытых текстов) известна как полностью гомоморфное шифрование и является более мощной. Используя такую систему, любая схема может быть гомоморфна оценена, позволяя эффективно создавать программы, которые могут быть запущены на шифровании ввода, чтобы произвести шифрование вывода. Так как такая программа никогда не расшифрует свой ввод, она может быть выполнена недостоверной стороной, не показывая её ввод и внутреннее состояние. У существования эффективной и полностью гомоморфной криптографической системы были бы большие практические реализации в аутсорсинге закрытых вычислений, например, в контексте облачных вычислений[3] В настоящее время это желаемая функция в современной архитектуре систем. Гомоморфное шифрование позволило бы объединить в одно целое различные услуги, не предоставляя данные для каждой услуги. Например, объединение в одно целое услуги различных компаний могло бы: 1) вычислить налог 2) текущий обменный курс 3) отправку, на сделку, не предоставляя истинные данные для каждой из этих услуг. [4]. Гомоморфное свойство различных криптографических систем может быть использовано для создания безопасных систем голосования[5], хеш-функций, стойким к коллизиям, закрытой информации поисковых систем и сделать возможным широкое использование «облачных» вычислений, гарантируя конфиденциальность обработанных данных.

Схема Гентри[править | править вики-текст]

Схему Гентри можно интерпретировать, опираясь на формулу: c\;\bmod\ 2=(m+q)\;\bmod\ 2
Фактически секретное число q задает, во что перейдет m бит в результате шифрования. Поскольку рассматриваются числа из \Z_2 , для произвольного q возможно всего два варианта:

\begin{cases}
     1\rightarrow 0\\
     0\rightarrow 1 \\
\end{cases}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;                                       
\begin{cases}
     1\rightarrow 1\\
     0\rightarrow 0 \\
\end{cases}
Таким образом, выбирая q, задается перестановка чисел, которая будет определять шифрование исходного бита m. Так как при шифровании можно выбирать разные q для разных чисел, то для функций от двух битов вариантов перестановок может быть 4, для n бит – 2^n.
Следовательно, с точки зрения безопасности шифрования данная схема эквивалентна подходу, при котором на вычисления отправляются просто все возможные входные комбинации входных значений (получаемые всеми перестановками) и после получения всех возможных ответов выбирается нужный по номеру изначально выбранной перестановки. Рассмотрим данный подход на примере вычисления произвольной функции f(m_1,m_2):

№ перестановки 0 1 2 3
m_1 0 0 1 1
m_2 0 1 0 1

На выходе получается таблица:

№ перестановки 0 1 2 3
f(m_1,m_2) f(0,0) f(0,1) f(1,0) f(1,1)

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

  1. Необходимо передавать огромное количество данных;
  2. Вычисление результата даже простых функций потребует огромного вычислительного ресурса

Для решения этих проблем можно кодировать таблицу аргументов с помощью функций m_1(k) и m_2(k) , где k – номер перестановки, передавать их как функции и в качестве результата получать функцию . Номер перестановки по-прежнему считается секретным, и, имея результат в виде f(k), можно вычислить её значение в точке k, получая конечный результат.
Обобщение этой методики формирует основу для алгоритмов. Пусть требуется вычислить функцию y_0 =  f(x_1,...,x_n). Для простоты в f используются только операции + и *. Тогда схема алгоритма будет такова:

  1. Набору чисел сопоставляется x_1,...,x_n функции g_1(k),...,g_n(k), такие, что \forall i=1,...,n g_i(k_0) = x_i, где k_0 будет секретным ключом.
  2. На вычислитель отправляются (в облако) полученные на предыдущем шаге функции g_1(k),...,g_n(k).
  3. В облаке вычисляется функция y(k)=f(g_1(k),...,g_n(k)). Важным моментом является то, что в качестве аргументов используются не конкретные значения, а функции как математические объекты.
  4. Результат вычислений отправляется нам.
  5. Вычисляется функция y_0=y(k_0), где y_0 является желаемым результатом.

Чтобы данный подход работал, на класс функций, к которым принадлежат g_i, налагается ряд ограничений:

  1. Эти функции должны кратко записываться, т. е. объем информации, передаваемой на сервер, должен быть существенно меньше списка пар «аргумент, значение».
  2. Этот класс должен быть замкнут относительно операций сложения и умножения, а также всех дополнительных операций, которые будут производиться над зашифрованными данными.
  3. класс должен быть достаточно велик, чтобы обеспечить устойчивость к атакам грубой силой.
  4. Должна быть возможность легкого конструирования функций из данного класса по уравнению x_i=g_i(k_0).
  5. Наконец, функции из этого класса должны быть легко вычислимы, по крайней мере в счетном количестве точек.

Примечания[править | править вики-текст]

[1]
[2]
[3]

Литература[править | править вики-текст]

  • Гомоморфное шифрование Н. П. Варновский, А. В. Шокуров //Труды Института Системного программирования: Том 12. (под Ред. В.П Иванникова) — М.:ИСП РАН, 2006, c. 27-36.
  • Вэнбо Мао. Современная Криптография. Теория и Практика. — Спб.: Вильямс, 2005.
  • Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone 11.5.2 The ElGamal signature scheme // Handbook of applied cryptography.
  • D. S. Maimut, A. Patrascu, E. Simion. Homomorphic encryption schemes and applications for secure digital world // JMEDS – 2012 — №4.
  • M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan Fully homomorphic encryption over the integers // In Proc. of Eurocrypt, volume 6110 of LNCS – 2010 – 28 p.
  • А. О. Жиров, О. В. Жирова, С. Ф. Кренделев Безопасные облачные вычисления с помощью гомоморфной криптографии

Ссылки[править | править вики-текст]