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

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

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

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

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

В 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], хеш-функций, стойким к коллизиям, закрытой информации поисковых систем и сделать возможным широкое использование «облачных» вычислений, гарантируя конфиденциальность обработанных данных.

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

[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.
  • А. О. Жиров, О. В. Жирова, С. Ф. Кренделев Безопасные облачные вычисления с помощью гомоморфной криптографии

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