Гомоморфное шифрование – схема шифрования, которая позволяет производить вычисления над зашифрованными данными без их расшифровки.

Пример:

В поликлинике применяются электронные медицинские карты, которые хранятся в зашифрованном виде.

Сначала рассмотрим обычную (не гомоморфную) схему:

Когда врачу нужно внести новую запись, карта сначала расшифровывается, врач вносит запись, затем карта зашифровывается обратно. У этой схемы есть очевидный минус: пока врач вносит данные, карта находится в расшифрованном виде, и данные из неё могут быть украдены.

image

Наличие гомоморфного шифрования могло бы решить эту проблему. В гомоморфной схеме новая запись зашифровывается и добавляется в карту. Карта при этом не расшифровывается.

image

∎

У гомоморфного шифрования большое количество потенциальных применений, наиболее известные примеры:

Защищённые облачные вычисления. Данные хранятся в облаке в зашифрованном виде. При этом любое редактирование файлов также происходит в зашифрованном виде

Секретный поиск. Запрос в поисковую систему передаётся в зашифрованном виде. Система выполняет поиск и возвращает ответ, также в зашифрованном виде. Хотя поисковая система обрабатывает запрос, содержание запроса остаётся скрыто от неё. Подобным образом можно проводить любые вычисления

Электронное голосование. Бюллетень передаётся в систему в зашифрованном виде. Система голосования подсчитывает результаты выборов, не расшифровывая бюллетени, тем самым сохраняя тайну голосования

Виды гомоморфных схем

Гомоморфные схемы делятся на два вида:

  • Частично гомоморфные – позволяет проводить только ограниченный набор операций, например, только умножение
  • Полностью гомоморфные – позволяет проводить любые операции над данными

Для реализации полностью гомоморфной системы над двоичными данными достаточно реализовать логические функции NOT, OR, AND, что позволит построить любую логическую схему. Или, что эквивалентно, сложение и умножение в целых числах, так как:
$AND(x, y) = xy$
$NOT(x) = 1 - x$
$OR(x, y) = x + y - xy$

Частично гомоморфное шифрование. RSA

Примеры частично гомоморфных систем известны достаточно давно. Так, криптосистема RSA является гомоморфной по умножению. Если даны два шифротекста:

$E(m_1) = c_1 = m_1 ^ e \bmod n $
$E(m_2) = c_2 = m_2 ^ e \bmod n $

То перемножим их, получим:

$c_1 * c_2 = (m_1 * m_2) ^ e \bmod n = E(m_1 * m_2)$

То есть шифротекст для произведения открытых текстов. Однако, система RSA не является гомоморфной по сложению, а, следовательно, не является полной.

Криптосистема Джентри

Принципиальную возможность построения полной гомоморфной криптосистемы продемонстрировал в 2009 году криптограф Крейг Джентри в своей диссертации (Craig Gentry “A fully homomorphic encryption scheme”). Криптосистема работает с битами и позволяет проводить действия логического умножения и сложения по модулю два.

Описание схемы шифрования

Генерация ключей

$p$ – большое простое число, секретный ключ

Шифрование:
$m$ – открытый текст, $m \in \{0, 1\}$
$r$ – небольшое случайное число
$q$ – случайное число, много больше $r$
$E(m) = 2r + pq + m = с$

Расшифрование

$D(c) = c \bmod p \bmod 2 = (2r + pq + m) \bmod p \bmod 2 = m$

Гомоморфность

Сложение по модулю 2:
$c_1 + c_2 = 2r_1 + pq_1 + m_1 + 2r_2 + pq_2 + m_2 = 2(r_1 + r_2) + p(q_1 + q_2) + (m_1 + m_2) = E(m_1 + m_2)$

Умножение:
$c_1c_2 = (2r_1 + pq_1 + m_1)(2r_2 + pq_2 + m_2) = 2(2r_1r_2 + r_1m_2 + r_2m_1) + p(q_1q_2p + 2r_1 + m_1 + r_2 + m_2) + m_1m_2 = E(m_1m_2)$

Число $r$ (называемое ошибкой) увеличивается в процессе проведения операций, и после того, как оно превысит $p$, расшифрование станет невозможным. Поэтому пока схема ещё не полностью гомоморфная: она позволяет делать операции сложения и умножения, но лишь ограниченное количество раз.

Bootstrapping

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

Схема bootstrapping:

  1. Выбираем новый ключ $p_{new}$
  2. Зашифровываем текущий ключ $p$ на новом ключе
  3. Зашифровываем шифротекст $c$ на новом ключе
  4. Гомоморфно расшифровываем $c$ на ключе $p$, и в результате получаем исходное сообщение $m$, зашифрованное уже на $p_{new}$ и очищенное от ошибки

image

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

Применение гомоморфного шифрования

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

Дело в том, что у системы Джентри, как и у всех последующих систем, одна и та же проблема – они очень медленные. Первым реализациям системы Джентри на вычисление несложных битовых операций требовалось около 30 минут. Дальнейшие оптимизации позволили гомоморфно вычислить AES (ставший де-факто стандартом для измерения производительности) за несколько часов. На данный момент гомоморфные вычисления в миллионы раз медленнее, чем обычные. По этой причине они пока неприменимы на практике.

📢тг-канал