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

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

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

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

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

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

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

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

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

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

Криптосистема RSA является популярной криптографической схемой с открытым ключом. Пусть m составной модуль и e открытая экспонента, тогда функция шифрования \mathcal{E}(x) = x^e \;\bmod\; m. Следовательно RSA гомоморфна для операции умножения :\mathcal{E}(x_1) \cdot \mathcal{E}(x_2) = x_1^e x_2^e \;\bmod\; m = (x_1x_2)^e \;\bmod\; m = \mathcal{E}(x_1 \cdot x_2)

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

В криптосистеме Эль-Гамаля в циклической группе G, если открытый ключ (G, q, g, h), где h = g^x и x секретный ключ, функция шифрования от сообщения m : \mathcal{E}(m) = (g^r,m\cdot h^r), для случайного элемента r \in  \{0, \ldots, q-1\}. Следовательно эта криптосистема гомоморфна для операции умножения

\mathcal{E}(x_1) \cdot \mathcal{E}(x_2) = (g^{r_1},x_1\cdot h^{r_1})(g^{r_2},x_2 \cdot h^{r_2}) = (g^{r_1+r_2},(x_1\cdot x_2) h^{r_1+r_2}) = \mathcal{E}(x_1 \cdot x_2)

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

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

\mathcal{E}(b_1)\cdot \mathcal{E}(b_2) = x^{b_1} r_1^2 x^{b_2} r_2^2 = x^{b_1+b_2} (r_1r_2)^2 = \mathcal{E}(b_1 \oplus b_2)

где \oplus есть сложение по модулю 2, (т.e. логическое сложение(«ИЛИ»)).

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

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

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

В 2009 году 25 июня впервые была предложена модель полностью гомоморфной алгебраической системы, то есть гомоморфной для операций умножения и сложения одновременно. Эта модель была представлена Крейгом Джентри (Craig Gentry), сотрудником подразделения IBM[6]. В этой работе «Полностью гомоморфное шифрование с использованием идеальных решёток» (англ. «Fully homomorphic encryption using ideal lattices») предлагается протокол гомоморфного шифрования, с помощью которого стало возможно реализовывать операции сложения и умножения над зашифрованными данными без предварительной расшифровки этих данных.[7]

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

Что касается производительности, то зашифрованные тексты в схеме Джентри остаются компактными, поскольку их длины не зависят вообще от сложности функции, которая оценивается по зашифрованным данным. Время вычисления линейно зависит только от числа выполняемых операций. Однако, схема непрактична для многих приложений, потому что размер зашифрованного текста и время вычисления резко возрастает, при возрастании уровня безопасности. Чтобы получить 2k безопасность против известных атак требуется много времени и ресурсов, так как время вычисления и размер зашифрованного текста — полиномы высокой степени k. Хотя недавно, Демиен Штехл и Рон Штеинфельд значительно уменьшили зависимость от k.[9]

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

Шнайер, Брюс[10]

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

  1. Ronald L. Rivest, Len Adleman, Michael L. Dertouzos. ON DATA BANKS AND PRIVACY HOMOMORPHISMS (англ.). Academic Press (1978). Архивировано из первоисточника 25 мая 2013.
  2. Dan Boneh, Eu-Jin Goh, Kobbi Nissim. Evaluating 2-DNF formulas on ciphertexts (англ.). Springer-Verlag (2005). Архивировано из первоисточника 25 мая 2013.
  3. Daniele Micciancio. A First Glimpse of Cryptography's Holy Grail (англ.). Association for Computing Machinery (1 March 2010). Архивировано из первоисточника 24 мая 2013.
  4. Craig Stuntz. What is Homomorphic Encryption, and Why Should I Care? (англ.) (18 March 2010). Архивировано из первоисточника 24 мая 2013.
  5. Ron Rivest. Lecture Notes 15: Voting, Homomorphic Encryption (англ.) (29 October 2002). Архивировано из первоисточника 24 мая 2013.
  6. Michael Cooney. IBM touts encryption innovation (англ.). Computer World (25 June 2009). Архивировано из первоисточника 24 мая 2013.
  7. IBM Researcher Solves Longstanding Cryptographic Challenge (англ.). Архивировано из первоисточника 30 мая 2013.
  8. Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices (англ.) (PDF). ACM (2009).
  9. Damien Stehle; Ron Steinfeld. Faster Fully Homomorphic Encryption (англ.) (PDF). International Association for Cryptologic Research (19 May 2010). Архивировано из первоисточника 24 мая 2013.
  10. Schneier, Bruce Homomorphic Encryption Breakthrough (англ.). Schneier on Security. Архивировано из первоисточника 24 мая 2013.

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

  • Гомоморфное шифрование Н. П. Варновский, А. В. Шокуров //Труды Института Системного программирования: Том 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.

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