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

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

История

Концепция гомоморфного шифрования была впервые сформулирована в 1978 году в работе Риверста, Адлемана и Дертузоса, которые предложили первую схему, обладающую ограниченными гомоморфными свойствами (схема RSA). Она позволяла выполнять операцию умножения над шифротекстами. Впоследствии были разработаны другие частично гомоморфные схемы, поддерживающие только сложение (схема Гольдвассер — Микали, 1982) или только умножение (схема Эль-Гамаля, 1985).

Долгое время считалось, что создание полностью гомоморфного шифрования (FHE), поддерживающего произвольные вычисления, невозможно. Однако в 2009 году американский криптограф Крейг Джентри в своей докторской диссертации представил первую теоретически реализуемую схему FHE. Его подход основывался на использовании решёток (lattice-based cryptography) и технике «бутстрэппинга» (bootstrapping), которая позволяет уменьшать накапливающийся при вычислениях шум, делая возможным выполнение неограниченного числа операций.

С 2009 года исследования в области FHE активно развивались. Были предложены более эффективные схемы, такие как BGV (Бракерски, Гентри, Вайкунтанатан, 2011) и CKKS (Чеон, Ким, Ким, Сон, 2017), которые значительно снизили вычислительные накладные расходы и расширили практическую применимость технологии. В настоящее время гомоморфное шифрование переходит из стадии теоретических исследований в стадию практических реализаций и коммерческих продуктов.

Классификация

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

Частично гомоморфное шифрование (Partially Homomorphic Encryption, PHE)

Схемы PHE поддерживают только одну математическую операцию (сложение или умножение) над шифротекстами, но могут выполнять её неограниченное количество раз. К ним относятся:

• Схема RSA: поддерживает только умножение. Шифротекст вычисляется как \(c = m^e \mod n\), где \(m\) — открытый текст, \(e\) — открытая экспонента, \(n\) — модуль. Произведение двух шифротекстов \(c_1 \cdot c_2\) соответствует шифротексту произведения исходных сообщений \(m_1 \cdot m_2\).
• Схема Эль-Гамаля: также поддерживает только умножение.
• Схема Гольдвассер — Микали: поддерживает только сложение (операция XOR для битовых данных).
• Схема Пайе (Paillier): поддерживает только сложение. Шифротекст вычисляется как \(c = g^m \cdot r^n \mod n^2\), где \(r\) — случайное число. Произведение двух шифротекстов \(c_1 \cdot c_2\) соответствует шифротексту суммы исходных сообщений \(m_1 + m_2\). Схема Пайе широко используется в приложениях, требующих только суммирования зашифрованных данных, например, в электронном голосовании.

Немного гомоморфное шифрование (Somewhat Homomorphic Encryption, SWHE)

Схемы SWHE поддерживают как сложение, так и умножение, но только для ограниченного числа операций. Это ограничение связано с тем, что каждая операция вносит шум в шифротекст, и при превышении определённого порога шума расшифровка становится невозможной. SWHE-схемы, как правило, являются предшественниками или упрощёнными версиями FHE-схем.

Полностью гомоморфное шифрование (Fully Homomorphic Encryption, FHE)

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

Принцип работы

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

\[ E(m_1) \oplus E(m_2) = E(m_1 + m_2) \]

где \(E\) — функция шифрования, \(\oplus\) — операция над шифротекстами, \(+\) — операция сложения над открытыми текстами.

Для схемы, поддерживающей умножение:

\[ E(m_1) \otimes E(m_2) = E(m_1 \times m_2) \]

где \(\otimes\) — операция умножения над шифротекстами.

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

Применение

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

Облачные вычисления

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

Обработка медицинских данных

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

Финансовый сектор

Банки и финансовые учреждения могут использовать гомоморфное шифрование для анализа транзакций, выявления мошеннических схем или оценки кредитоспособности клиентов, не раскрывая сами транзакции или персональные данные клиентов. Это позволяет соблюдать требования законодательства о защите персональных данных, в том числе Федерального закона № 152-ФЗ «О персональных данных».

Электронное голосование

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

Критика и ограничения

Несмотря на значительный прогресс, гомоморфное шифрование имеет ряд существенных ограничений.

• Высокая вычислительная сложность: FHE-схемы на несколько порядков медленнее, чем операции над незашифрованными данными. Даже простые операции могут занимать миллисекунды или секунды, что делает их непригодными для многих приложений реального времени.
• Размер шифротекста: Шифротексты в FHE-схемах значительно больше, чем исходные открытые тексты (иногда в тысячи раз). Это увеличивает требования к хранению и пропускной способности сети.
• Сложность реализации: Разработка и реализация безопасных и эффективных FHE-схем требует глубоких знаний в области криптографии и математики. Ошибки в реализации могут привести к уязвимостям.
• Ограниченная функциональность: Хотя FHE теоретически поддерживает любые вычисления, на практике эффективные реализации существуют только для определённых типов операций (например, арифметические схемы). Реализация сложных алгоритмов, таких как машинное обучение, остаётся вычислительно дорогой.

Перспективы

Исследования в области гомоморфного шифрования продолжаются. Основные направления включают:

• Разработка более эффективных схем: Учёные ищут способы снижения вычислительных накладных расходов и размера шифротекстов.
• Создание специализированных аппаратных ускорителей: Разработка чипов, оптимизированных для выполнения операций гомоморфного шифрования, может значительно повысить производительность.
• Интеграция с другими технологиями: Гомоморфное шифрование часто комбинируется с другими методами защиты конфиденциальности, такими как безопасные многосторонние вычисления (MPC) и дифференциальная приватность.

Источники

1. Rivest, R. L., Adleman, L., & Dertouzos, M. L. (1978). On data banks and privacy homomorphisms. Foundations of Secure Computation, 4(11), 169-180.
2. Gentry, C. (2009). Fully homomorphic encryption using ideal lattices. Proceedings of the 41st annual ACM symposium on Theory of computing (STOC '09), 169-178.
3. Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2011). Fully homomorphic encryption without bootstrapping. IACR Cryptology ePrint Archive, 2011, 277.
4. Cheon, J. H., Kim, A., Kim, M., & Song, Y. (2017). Homomorphic encryption for arithmetic of approximate numbers. Advances in Cryptology – ASIACRYPT 2017, 409-437.
5. Paillier, P. (1999). Public-key cryptosystems based on composite degree residuosity classes. Advances in Cryptology – EUROCRYPT '99, 223-238.
6. Федеральный закон от 27.07.2006 № 152-ФЗ «О персональных данных».