Что такое гомоморфное шифрование

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

Представьте, что вы помещаете числа в запертый ящик со специальными перчатками, встроенными в его стенки. Через перчатки можно изменять числа (складывать и умножать их), ни разу не открывая ящик. Увидеть результат после открытия ящика ключом может только его владелец.

Частично гомоморфное шифрование поддерживает один тип операций без ограничений: RSA (в классической формулировке) обладает мультипликативным гомоморфизмом: Шифр(m1)*Шифр(m2) = Шифр(m1*m2). Paillier обладает аддитивным гомоморфизмом: Шифр(m1)*Шифр(m2) = Шифр(m1+m2). Используется в электронном голосовании и поиске информации с сохранением конфиденциальности.

Ограниченно гомоморфное шифрование поддерживает и сложение, и умножение, но только ограниченное число умножений (глубину схемы). Шум увеличивается после каждого умножения; после достижения порога расшифрование завершается ошибкой. Первую конструкцию предложил Gentry (2009).

Полностью гомоморфное шифрование поддерживает произвольные вычисления (любую булеву или арифметическую схему) над зашифрованными данными. Gentry (2009) показал, что FHE возможно благодаря «перезагрузке» — гомоморфному вычислению схемы расшифрования, которое обновляет шифртекст и сбрасывает шум.

Большинство схем HE основано на решётках (BGV, BFV, CKKS). Шифрование добавляет шум в шифротекст. Сложение: шум растёт аддитивно. Умножение: шум растёт мультипликативно. Бутстрэппинг: гомоморфно расшифровывает шифротекст, возвращая шум к исходному уровню. Бутстрэппинг требует больших вычислительных затрат.

FHE всё ещё в 10^6 раз медленнее вычислений над открытым текстом. Для шифрования одного 32-разрядного целого числа требуется несколько килобайт шифротекста. Бутстрэппинг занимает несколько секунд на один вентиль. Практическое применение FHE ориентировано на конкретные рабочие нагрузки: вывод моделей машинного обучения, запросы к базам данных, анализ генома.

Большинство схем HE основано на трудной задаче обучения с ошибками (LWE) или кольцевого обучения с ошибками (RLWE), которая, как считается, устойчива к квантовым атакам. Взлом HE требует решения задачи RLWE — неизвестно ни одного квантового алгоритма, обеспечивающего значительное ускорение для её решения.

SEAL (Microsoft, поддерживает BFV/CKKS), HEAAN (Сеульский национальный университет, CKKS), OpenFHE (с открытым исходным кодом, BGV/BFV/CKKS/FHEW/TFHE), HElib (IBM, BGV). Все они имеют исследовательский уровень; промышленные внедрения встречаются редко и обычно ориентированы на конкретную предметную область.

Медицинская геномика: запрос к базе данных генов без раскрытия своего генома. Шифрованный вывод модели машинного обучения: облако запускает нейронную сеть на ваших данных, не видя их. Конфиденциальная аналитика: вычисление сводной статистики по зашифрованным данным пользователей. Вычисление финансовых рисков по конфиденциальным портфелям.

HE: одна сторона выполняет вычисления над данными, зашифрованными другой стороной. MPC: несколько сторон совместно выполняют вычисления, не раскрывая друг другу свои входные данные. Гибридный подход: HE используется для предварительной обработки без взаимодействия, а MPC — для интерактивных протоколов. Компромиссы: HE = высокая задержка; MPC = накладные расходы на обмен данными.

Каково ключевое ограничение частично гомоморфного шифрования (SHE)?

Гомоморфное шифрование позволяет выполнять вычисления над шифротекстом. PHE поддерживает одну операцию; SHE поддерживает ограниченную глубину; FHE поддерживает произвольные схемы с помощью бутстрэппинга. В основе лежат трудные задачи LWE/RLWE. Далее: математическая основа LWE.