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

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

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

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

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

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

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

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

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

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

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

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

Криптосистема 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 и при равном значении ключа обеспечивает ту же криптостойкость. Эль-Гамаль усовершенствовал алгоритм Диффи — Хеллмана и получил алгоритмы для шифрования и для обеспечения аутентификации. Является криптосистемой вероятностного шифрования. Её функция шифрования гомоморфна относительно операции умножения открытых текстов: криптограмма произведения может быть вычислена как произведение (попарное) криптограмм сомножителей. Если 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 ).

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

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

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

Проблемы с производительностью и их решение[править | править вики-текст]

Одной из существенных проблем известных полностью гомоморфных криптосистем является их крайне низкая производительность. В настоящее время существует два основных пути её повышения: использование "ограниченного гомоморфизма" (Leveled Fully Homomorphic Encryption)[7] и т. н. "метод упаковки шифртекстов"[8]. Первый подразумевает криптосистему, которая может выполнять операции двух видов (сложения и умножение), но в ограниченном количестве. Суть второго в том, что в один шифртекст записывается сразу несколько открытых текстов, и при этом в процессе одиночной операции такого пакетного шифртекста происходит одновременная обработка всех входящих в него шифртекстов.

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

  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. Описанных примерах обозначение \mathcal{E}(x) является функцией шифрования от сообщения x
  4. Daniele Micciancio. A First Glimpse of Cryptography's Holy Grail (англ.). Association for Computing Machinery (1 March 2010). Архивировано из первоисточника 24 мая 2013.
  5. Craig Stuntz. What is Homomorphic Encryption, and Why Should I Care? (англ.) (18 March 2010). Архивировано из первоисточника 24 мая 2013.
  6. Ron Rivest. Lecture Notes 15: Voting, Homomorphic Encryption (англ.) (29 October 2002). Архивировано из первоисточника 24 мая 2013.
  7. Brakerski Z., Gentry C., Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping // Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. — 2012. — С. 309-325.
  8. Буртыка Ф.Б. Пакетное симметричное полностью гомоморфное шифрование на основе матричных полиномов. // Труды Института Системного программирования: Том 26. — 2014. — № 5. — С. 99-115.

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

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

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