Полностью гомоморфное шифрование: технология, которая вычисляет на секретах

Крейг Джентри доказал это в 2009 году, после почти трёх десятилетий размышлений криптографов о том, возможно ли это в принципе. Идея такова: вы шифруете свои данные, передаёте их кому-то другому, тот выполняет вычисления над ними, возвращает результат, и когда вы расшифровываете этот результат, он оказывается верным. Человек, выполнявший вычисления, никогда не видел ваших данных. Не очищенную версию. Не хэш. Фактические исходные значения — никогда не раскрытые, даже на долю микросекунды. Это полностью гомоморфное шифрование — форма шифрования, позволяющая третьей стороне выполнять вычисления над вашими данными без их расшифровки.

Так что же такое FHE (полностью гомоморфное шифрование)? Это не фокус. Это математическое свойство определённых схем шифрования. Вы отправляете кому-то запертый ящик. Они переставляют содержимое. Вы открываете его — и расстановка верна. У них никогда не было ключа.

Почему альтернативы не справляются

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

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

Доверенные среды выполнения (TEE), такие как Intel SGX, создают защищённую область памяти, которую не может прочитать даже операционная система. Чувствительные вычисления происходят внутри анклава. Это действительно полезно, однако вы доверяете производителю оборудования и рассчитываете, что в реализации анклава нет эксплуатируемых уязвимостей. В SGX они были.

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

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

Механика, кратко

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

Звучит ограниченно — две операции. Но это не так. Сложение и умножение над двоичными полями дают вам вентили AND и XOR, а они — произвольные цифровые схемы. Любую функцию, которую может вычислить компьютер, можно выразить через эти две операции. Это и есть мост от «арифметики над зашифрованными числами» к «произвольным вычислениям над зашифрованными данными».

Структурная проблема — шум. Каждая операция FHE вносит небольшую ошибку в шифротекст. Ошибки накапливаются. При достаточном количестве операций шум подавляет сигнал — шифротекст становится нерасшифруемым. Прозрение Джентри заключалось в бутстрэппинге: гомоморфное вычисление схемы расшифровки над зашумлённым шифротекстом для получения нового шифротекста с низким шумом и тем же значением открытого текста. Иными словами, вы запускаете расшифровку внутри шифрования. Шум сбрасывается без того, чтобы данные когда-либо раскрывались.

Схемы, обрабатывающие ограниченное число операций до того, как шум становится критическим, называются уровневыми или частично гомоморфными. Именно бутстрэппинг обеспечивает «полноту» в FHE.

Где это применяется сейчас

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

Приватный инференс ML — наиболее очевидный случай применения. У клиента есть чувствительные входные данные. У сервера — проприетарная модель. FHE позволяет серверу вычислять модель на зашифрованных входных данных и возвращать зашифрованный результат. Ни одна из сторон не раскрывает то, что защищает. Zama реализует это для конкретных архитектур моделей. Глубина схемы предсказуема и управляема.

Приватный геномный анализ является эталонной рабочей нагрузкой с тех пор, как iDASH начал проводить соревнования по зашифрованной геномике в 2014 году. Оценка риска заболеваний, полногеномный поиск ассоциаций и выравнивание последовательностей — всё это имеет реализации на FHE. Геномные данные — один из немногих типов данных, где риск для приватности является постоянным и распространяется на людей, которые никогда не давали согласия на передачу чего-либо.

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

Конфиденциальность блокчейна — активная область. Смарт-контракты по умолчанию выполняются публично на цепочке. Системы на базе TFHE позволяют запускать логику контракта над зашифрованным состоянием, что открывает возможности для приватных аукционов, конфиденциального голосования и механизмов с закрытыми заявками, где корректность публично верифицируема, но входные данные не раскрываются. Проект fhEVM от Zama нацелен именно на это.

Основы безопасности

Безопасность FHE сводится к сложности задачи обучения с ошибками (LWE) и её кольцевого варианта (RLWE). Эти задачи ставят вопрос: имея множество приближённых линейных уравнений над кольцом или решёткой, восстановить секрет. Для ни одной из задач не известен полиномиальный алгоритм — ни на классическом, ни на квантовом оборудовании.

Это помещает FHE в семейство постквантовой криптографии. Постквантовая стандартизация NIST построена на задачах семейства LWE, что обеспечивает дополнительный контроль и уверенность в лежащих в основе допущениях. При этом LWE подвергается серьёзным атакам менее 20 лет. За RSA и эллиптическими кривыми стоит более 40 лет безуспешного криптоанализа. Уровень доверия высок, но не идентичен.

Параметры определяют безопасность. Степень многочлена, размер модуля и распределение шума должны быть выбраны таким образом, чтобы экземпляр LWE был сложным на требуемом уровне безопасности. Консорциум HomomorphicEncryption.org публикует рекомендуемые наборы параметров. Использование библиотечных значений по умолчанию, прошедших валидацию по этим рекомендациям, настоятельно предпочтительнее пользовательских конфигураций.

Конкурентный контекст

FHE — одна из нескольких технологий вычислений с сохранением приватности, и их всё чаще используют совместно, а не как взаимозаменяемые альтернативы.

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

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

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