Когда человек думает о шифровании, первые использования, которые приходят на ум, это шифрование в покое и шифрование при передаче. Первое позволяет хранить некоторые данные на зашифрованных жестких дисках, съемных устройствах или даже в облачных базах данных и обеспечивает гарантию, что только законный владелец может видеть или редактировать содержимое исходного текста. Шифрование при передаче гарантирует, что данные, передаваемые по Интернету, доступны только для их назначенных получателей, даже если они проходят через общедоступные маршрутизаторы или каналы. Оба сценария основаны на шифровании, с дополнительной гарантией целостности, что данные также не были подделаны злонамеренным злоумышленником посреди. Это известно как аутентифицированное шифрование: после шифрования данных никто в цепочке не может вывести ни одного бита данных (конфиденциальность), и никто не может изменить шифротекст без его обнаружения (целостность/аутентичность).

Некоторые сценарии совместного использования требуют, чтобы некоторая нетривиальная обработка была разрешена даже для зашифрованных текстов. Это область методов сохранения конфиденциальности, или используемого шифрования, одним из которых является полностью гомоморфное шифрование (FHE). В качестве примера можно привести электронное голосование в облаке: избиратели могут, например, зашифровать свой бюллетень, затем какая-то организация в центре будет собирать все бюллетени для подсчета количества голосов, и только окончательный результат будет опубликован. К сожалению, при аутентификационном шифровании субъекту в середине пришлось бы расшифровать все бюллетени, чтобы выполнить такое вычисление, и он увидел бы отдельные голоса в открытом виде, что довольно громоздко. Теоретически мы могли бы перетасовать бюллетени (некоторые протоколы электронного голосования действительно полагаются на это), но, в отличие от бумажных бюллетеней, традиционные криптографические механизмы, гарантирующие честность, также значительно затрудняют отвязку зашифрованного бюллетеня от личности его отправителя. В схеме электронного голосования можно добавить аппаратную стену вокруг организации, которая подсчитывает голоса. Это, например, цель доверенных анклавов выполнения. Такие анклавы значительно усложнили бы злоумышленнику взаимодействие с сущностью. Но в этом случае сбой в аппаратном обеспечении может привести к утечке ключа дешифрования, и, в отличие от программных ошибок, уязвимости в конструкции оборудования не могут быть легко устранены.

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

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

На этой схеме изображены 3 сценария электронного голосования: на самом левом изображении доверенное лицо перетасовывает и расшифровывает отдельные голоса перед их публикацией. Мы должны доверять лицу, выполняющему вычисления, чтобы обеспечить конфиденциальность голосующих и правильный подсчет голосов. На центральном изображении используется Доверенная Область, которой доверяют в обеспечении целостности и конфиденциальности, для выполнения той же вычислительной операции. На правом изображении используется гомоморфное шифрование: зашифрованные голоса могут быть сложены (в публичном доступе) до расшифровки результата. E( ) означает операцию шифрования, а D( ) - расшифровку.

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

Аутсорсинг FHE часто представляется как альтернатива безопасным ограждениям, основанная на сложности математической проблемы, а не на практических препятствиях. FHE полностью устойчив к пассивным атакам через боковые каналы или другим нарушениям хост-облака. Представьте себе, что кто-то должен аутсорсить вычисления, но данные действительно чувствительны. Этот человек, вероятно, будет неохотно использовать облачный VM, если кто-то другой может быть root на машине. Он, вероятно, также будет колебаться запускать его в ограждении, таком как SGX, зная, что ЦП и память хостов облака постоянно мониторятся на нагрузку, мощность, температуру. Возможно, из этих измерений можно извлечь какую-то информацию. Этот человек может быть заверен обещанием FHE, что извлечение любого единичного бита информации требует решения математической проблемы постквантового уровня, независимо от любого вида измерений, которые мы могли бы собрать.

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

FHE часто представляется в виде открытого ключа. Есть:

1. Ключ расшифровки: Это мастер-ключ криптосистемы, из которого можно получить все остальные ключи. Ключ расшифровки обычно генерируется локально и никогда не передается, и единственный человек, который может расшифровать FHE-шифр, - это владелец ключа расшифровки.
2. Ключ шифрования: В режиме открытого ключа, когда сторона, предоставляющая первоначальный шифртекст, не является владельцем ключа дешифрования, этот среднего размера ключ обычно состоит из случайных шифрований нуля. Поскольку FHE поддерживает аффинные функции, этого достаточно для шифрования любого сообщения.
3. Ключ оценки: Этот ключ должен быть предоставлен любой стороне, которая будет оценивать функцию на шифртекстах. Этот ключ также безопасен для публикации или передачи, как любой открытый ключ. Размер ключа оценки варьируется от пустого до очень большого, в зависимости от того, является ли функция для оценки линейной или произвольной.

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

Сценарии FHE

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

Режим аутсорсинга

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

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

С текущими аппаратными возможностями режим аутсорсинга все еще немного медленный для использования в полной общности на практике - мы обычно можем рассчитывать на коэффициент накладных расходов времени выполнения в 1 миллион и накладных расходов памяти в 1 тысячу для нелинейных случаев использования. Однако аппаратное обеспечение FHE в настоящее время разрабатывается для сокращения этой разницы, как Проект Darpa DPRIVEилиCryptoLight.

В настоящее время в практике используется режим аутсорсинга для случаев использования PIR (Private Information Retrieval), где сервер (Боб) имеет большую открытую базу данных, клиент (Алиса) отправляет запрос, и индекс, который запрашивается, должен оставаться конфиденциальным. Такие схемы PIR получают значительную выгоду от линейности и компактности гомоморфных зашифрованных операций, в то время как небольшая мультипликативная глубина схем сохраняет вычислительные затраты в разумных пределах.

Эта таблица подводит итоги плюсов и минусов режима аутсорсинга.

Режим двустороннего вычисления

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

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

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

Режим агрегации

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

Режим клиент-сервера

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

Как гомоморфное шифрование обеспечивает легитимность вычисленной функции?

Всегда проще использовать FHE в совместных сценариях, где у каждого участника есть стимул честно следовать протоколу. FHE может использоваться, например, для вычисления статистики между двумя юридическими лицами одной и той же группы в двух разных странах: такие нормативные акты, как GDPR, позволяют публиковать некоторые статистические данные, но в целом не позволяют собирать все индивидуальные данные в одном месте. В этом случае использование FHE возможно, и у всех участников есть стимул честно следовать протоколу. В сценарии, не предполагающем совместной работы, самый простой способ убедиться в том, что соответствующая функция вычислена, — это ввести избыточность. Например, в сценариях аутсорсинга и агрегации гомоморфные вычисления являются полностью публичными и могут быть детерминированы. До тех пор, пока две или более независимых сущностей в конечном итоге получают один и тот же выходной зашифрованный текст, вычисления являются правильными, и результат можно безопасно расшифровать. Чем больше избыточность, тем больше мы можем быть уверены в результате, что, конечно же, является компромиссом с эффективностью.

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

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

Как FHE гарантирует, что конечный получатель расшифрует только конечный результат, а не промежуточные переменные?

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

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

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

Строительные блоки гомоморфного шифрования

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

Другими словами, когда задается вопрос о том, может ли данная схема открытого текста быть запущена гомоморфно и с какой ценой (по времени и накладным расходам памяти), PHE может ответить отрицательно на этот вопрос. LHE отвечает утвердительно, но может устанавливать произвольно высокую стоимость для сложных схем. FHE также отвечает «да» и, кроме того, предоставляет ключи, алгоритмы шифрования и дешифрования, а также то, как гомоморфно оценить универсальный набор вентисов еще до того, как будет определена схема открытого текста. Таким образом, FHE является единственным режимом, который гарантирует, что память и время выполнения гомоморфного вычисления остаются пропорциональными исходной схеме открытого текста. Для этого все известные сегодня схемы FHE имеют дело с зашумленными шифротекстами, которые становятся все более и более зашумленными по мере выполнения вычислений. Чтобы избежать перетекания шума в выполняемые вычисления и приводить к ошибкам расшифровки, эти схемы регулярно выполняют довольно дорогостоящую операцию, называемую начальной загрузкой, которая снижает шум до управляемого уровня. Подробнее о специфике каждого вида схем, о начальной загрузке и о том, как свести к минимуму шум и другие затраты с помощью компиляторов FHE, читайте во второй статье этой серии!

Отказ от ответственности:

1. Эта статья печатается с [копиякриптография кафе], Все права принадлежат оригинальному автору [Николас Гама и Сандра Гуаш]. Если есть возражения по поводу этой публикации, пожалуйста, свяжитесь со Gate Learnкоманда и они быстро обработают это.
2. Отказ от ответственности по обязательствам: Взгляды и мнения, выраженные в этой статье, являются исключительно мнениями автора и не являются инвестиционными советами.
3. Переводы статьи на другие языки выполняются командой Gate Learn. Если не указано иное, копирование, распространение или плагиат переведенных статей запрещены.