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

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

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

Частично гомоморфные системы

В ниже описанных примерах обозначение $\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)$

Другие частично гомоморфные криптосистемы

• Криптосистема Окамото - Очияма
• Криптосистема Накаче - Штерна
• Криптосистема Дамгарда - Журика
• Криптосистема Боне-Го - Ниссима
• Криптосистема Бенало

Полностью гомоморфное шифрование

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

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

Литература

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

Ссылки

• Философия криптографии: возможности гомоморфизма // Cnews, 30.06.09