Некоторое время назад я прошел курс CS355 (продвинутая криптография) в Стэнфорде. Нас преподавали трое аспирантов Дэна: Дима Коган, Флориан Трамер и Саба Эскандарян. Каждый из трех докторантов имеет свои особенности, и их направления исследований также сильно различаются. Дима фокусируется на технологии защиты конфиденциальности PIR (Private Information Retri), Флориан — на исследованиях в области машинного обучения и блокчейна, а Саба — на доказательстве с нулевым разглашением.
Курс CS355 охватывает практически весь контент в области криптографии с древних времен до наших дней. От самой ранней односторонней функции (Односторонняя функция) до эллиптического уравнения (ECC) и спаривания и, наконец, до некоторых популярных MPC, нулевого разглашения, поиска частной информации (PIR), полностью гомоморфного алгоритма и так далее в последние годы. . Поскольку занятия закончились только два дня назад, я организовал серию заметок, пока содержание знаний еще оставалось в моей поверхностной памяти. Содержание курса очень интересное. Остальной информацией я поделюсь с вами позже, когда у меня будет время ~
В этом выпуске мы поговорим о популярном в последнее время полностью гомоморфном шифровании (FHE) и сопутствующей ему технологии решетчатого шифрования.
Что такое полностью гомоморфное шифрование?
Я думаю, что многие друзья слышали о названии «Полное гомоморфное шифрование» (FHE). В последние годы появляется все больше и больше тем, касающихся защиты личной жизни, а также широко популяризируется ряд прикладных технологий криптографии, включая гомоморфное шифрование.
Чтобы лучше понять эту тему, я хотел бы кратко представить определение полностью гомоморфного шифрования.
Обзор системы шифрования
Прежде чем мы начнем, давайте рассмотрим самую традиционную систему шифрования.
Мы все знаем, что если вы хотите построить систему шифрования, вам часто нужен ключ. С помощью этого ключа мы можем зашифровать информацию открытого текста в зашифрованный текст на одном конце, а затем использовать ключ для изменения зашифрованного текста обратно в его первоначальный вид на другом конце. Без этого Ключа другим людям было бы трудно узнать, какую информацию мы передали.
Иллюстрация выше в основном показывает общую картину всех распространенных систем шифрования. Все системы шифрования, если использовать более формальный метод описания, несомненно, делают три вещи:
Друзья, которые что-то знают об алгоритмах шифрования, наверняка знают общие некоторые. алгоритмы шифрования, такие как AES, RSA и т. д. Каждый также должен знать, что вообще говоря, системы шифрования делятся на два типа: системы симметричного шифрования и системы асимметричного шифрования. Три шага, которые мы здесь описываем, на самом деле применимы к любой системе шифрования. Если он симметричен, то ключ, используемый для шифрования и дешифрования, один и тот же. Если это асимметричная система, то для шифрования используется открытый ключ, а для дешифрования — другой закрытый ключ.
В исследованиях криптографии всякий раз, когда мы видим определение новой системы, нам часто приходится указывать свойства, которыми должна обладать система.
Основное значение семантической безопасности заключается в том, что наблюдатель не может различить два зашифрованных сообщения. Таким образом, если злоумышленник подслушает сеть и увидит зашифрованную информацию, которую я отправляю, при условии, что используемая мной система шифрования семантически безопасна, то я могу быть уверен, что злоумышленник не сможет получить никакой информации о зашифрованном контенте из зашифрованного текста.
После удовлетворения двух вышеуказанных свойств система шифрования становится надежной.
### Гомоморфное шифрование: случайные особые свойства
Поняв, что представляет собой система шифрования, мы можем обратить внимание на этот зашифрованный текст, который выглядит как случайно сгенерированный искаженный код. Мы все знаем, что мы не получим никакой информации, просто взглянув на сам зашифрованный текст. Но значит ли это, что если нет ключа и есть только зашифрованный текст, мы ничего не сможем сделать?
Мы все знаем ответ: не совсем.
Это свойство мы называем аддитивным гомоморфизмом. Это означает, что зашифрованный зашифрованный текст сохраняет тонкую алгебраическую связь с предыдущим исходным текстом. Если мы сложим зашифрованный текст, мы сможем получить новый зашифрованный текст, сложив исходный текст. Таким же образом можно заключить, что существуют и аддитивно-гомоморфные алгоритмы шифрования. Мы можем перемножить зашифрованный текст, сгенерированный мультипликативно гомоморфным алгоритмом, а затем получить зашифрованный текст, соответствующий результату перемножения исходных текстов. В ходе всего процесса нам не нужно знать никакой информации, связанной с ключом, мы просто объединяем зашифрованный текст, который выглядит как случайный искаженный код.
Например: Система анонимного голосования.
Далее давайте приведем пример, наглядно описывающий практичность гомоморфного шифрования.
Мы все знаем, что такое онлайн-голосование: если руководитель компании хочет инициировать волну голосования, выберите, следует ли компании использовать систему 996. Затем начальник может попросить ИТ-специалиста настроить сервер и позволить сотрудникам сделать свой выбор: проголосовать 0, чтобы означать, что они не хотят, и проголосовать 1, что означает, что они хотят. После заключительного периода голосования босс может подсчитать все голоса. Если итоговая сумма всех голосов превысит половину числа сотрудников, в компании стартует 996 человек.
Этот механизм голосования кажется очень простым, но есть большая проблема конфиденциальности: если начальник хочет, чтобы все сотрудники были 996, но он намеренно инициирует это голосование только для того, чтобы выудить правоохранительные органы и увидеть, какой сотрудник не желает работать сверхурочно, тогда начальник Он может спокойно поручить своему младшему брату подслушивать в Интернете, записывать решения, представленные каждым сотрудником, и наконец посмотреть, кто проголосовал 0. В результате сотрудники очень боятся и не смеют выражать свои чувства.
Если мы сможем использовать аддитивный алгоритм гомоморфного шифрования, то эту проблему можно легко решить.
Конечно, эта система еще очень несовершенна: например, ИТ-отдел может напрямую помочь начальнику расшифровать голоса каждого и записать их в документ. Существуют и другие криптографические инструменты, которые могут помочь нам решить эту проблему. Из-за нехватки места дальнейшие пояснения здесь даваться не будут.
Но на этом этапе мы должны почувствовать силу алгоритма гомоморфного шифрования. Мы можем понять это так: с помощью алгоритма гомоморфного шифрования пользователи могут выполнять своего рода безопасные прокси-вычисления (безопасные делегированные вычисления) с ненадежным удаленным сервером (облаком). Пользователи могут использовать технологию гомоморфного шифрования, чтобы зашифровать свои конфиденциальные личные данные и передать их облаку.Затем облако может выполнить определенную степень вычислений над зашифрованными данными и, наконец, получить зашифрованный результат, который хочет пользователь, и вернуть его в облако.пользователь. Наконец, пользователь может использовать ключ дешифрования, чтобы открыть результат. На протяжении всего соглашения делегированная сторона (облако) никогда не сможет увидеть какую-либо полезную информацию, связанную с личным вводом.
### Классификация гомоморфных систем шифрования
После приблизительного понимания двух самых основных гомоморфных свойств становится очень легко понять другие концепции. С систематической точки зрения гомоморфные системы шифрования грубо делятся на четыре категории: частичный гомоморфизм, приблизительный гомоморфизм, полный гомоморфизм конечных серий и полный гомоморфизм.
Далее давайте по очереди рассмотрим конкретные определения каждой категории.
Частично гомоморфное шифрование
Самая элементарная стадия гомоморфного шифрования называется частично гомоморфным шифрованием, которое определяется как зашифрованный текст, обладающий только одним гомоморфным свойством. Этот этап включает в себя два режима аддитивного гомоморфизма и мультипликативного гомоморфизма, которые мы описали выше.
Мы получаем зашифрованный текст, соответствующий перемножению этих двух сообщений! Это свойство мультипликативного гомоморфизма: мы можем продолжать накладывать новые зашифрованные тексты поверх этого зашифрованного текста, так что мы можем получить любое умножение между зашифрованными текстами.
Как мы говорили в предыдущем параграфе, если мы хотим умножить частные входные данные и получить линейную комбинацию между ними, простой частично гомоморфный алгоритм шифрования (RSA, Эль-Гамаль) не может быть выполнен. Значит, нам нужно перейти к следующему этапу.
Следующим этапом частично гомоморфного шифрования является приблизительно гомоморфное шифрование, которое на один шаг приближается к полностью гомоморфному шифрованию, которого мы хотим достичь. Если у нас есть приблизительно гомоморфный алгоритм шифрования, то мы можем одновременно вычислять сложение и умножение зашифрованного текста. Однако следует отметить, что, поскольку этот этап приблизительно гомоморфен (несколько гомоморфен), количество сложений и умножений, которые можно выполнить, очень ограничено, и функция F, которую можно вычислить, также находится в ограниченном диапазоне.
На данном этапе существует не так много распространенных примеров приблизительно гомоморфного шифрования, если говорить о наиболее понятном примере, то это должен быть алгоритм циклического группового шифрования, основанный на спаривании.
Выше мы кратко рассмотрели алгоритм шифрования Эль-Гамаля, основанный на обычных циклических группах. Мы все знаем, что этот алгоритм аддитивно гомоморфен, что означает, что он может получать линейные комбинации между произвольными зашифрованными текстами. Фактически, в некоторых специальных циклических группах мы также можем обнаружить некоторые слабые свойства мультипликативного гомоморфизма.
Это ограничение доказывает, что система приближенно гомоморфна, поскольку мы не можем вычислить функцию F произвольной логики и глубины.
Полностью уровневое гомоморфное шифрование
Достигнув следующего этапа, мы становимся на шаг ближе к цели полного гомоморфизма.
Этот этап называется полностью гомоморфным шифрованием конечных серий. На этом этапе мы уже можем выполнять любую комбинацию сложения и умножения зашифрованного текста без каких-либо ограничений на количество раз.
Полностью гомоморфное шифрование (FHE)
После многих вызовов наконец-то дело дошло до полностью гомоморфного шифрования (FHE), которое мы и ждем.
Как следует из названия, полностью гомоморфная система шифрования не имеет ограничений на методы расчета.Мы можем произвольно комбинировать зашифрованные тексты для формирования новых зашифрованных текстов без ключа, и новый зашифрованный текст, независимо от вычислительной сложности, может быть полностью восстановлен до исходного текста.
Когда мы достигнем этой стадии, ранее упомянутое вычисление безопасного агента станет возможным. Если мы сможем найти более эффективную полностью гомоморфную систему шифрования, мы сможем безопасно проксировать все локальные вычисления в облако без утечки каких-либо данных!
Определение полностью гомоморфной системы шифрования
Прежде чем приступить к обсуждению истории полностью гомоморфных систем ниже, мы можем систематически определить формальное определение полностью гомоморфных систем. Полностью гомоморфная система шифрования имеет четыре алгоритма:
## Исторический обзор полностью гомоморфного шифрования
Прежде чем начать изучать, как реализуется алгоритм полностью гомоморфного шифрования, мы могли бы также взглянуть на то, как возникла концепция полностью гомоморфного шифрования.
Концепция FHE (полностью гомоморфного) была фактически предложена в конце 1970-х годов. В 1978 году Ривест, Адлеман и Дертузос, несколько громких имен в криптографии, впервые упомянули в своей статье «О банках данных и гомоморфизмах конфиденциальности» идею системы, которая могла бы выполнять определенные вычисления с зашифрованным текстом и косвенно работать с исходным текстом. Позже эта идея была резюмирована и названа полностью гомоморфным шифрованием.
Видно, что концепция полностью гомоморфного шифрования предлагалась уже давно. Удивительно, но в 1976 году, за два года до публикации статьи, только что был предложен протокол обмена ключами Диффла-Хеллмана! Это показывает, что воображение специалистов по криптографии по-прежнему очень богато.
Когда была предложена концепция FHE, все академическое сообщество было тронуто ею и начало десятилетия поисков, пытаясь найти идеальный алгоритм с полностью гомоморфными свойствами. Но за последние несколько десятилетий люди испробовали все мыслимые варианты, но не смогли найти вариант, который удовлетворял бы всем условиям полной гомоморфности и безопасность которого можно было бы легко доказать.
До 2009 года у доктора философии Крейга Джентри, который учился в Стэнфорде, внезапно возникла идея, и он преодолел трудности алгоритма FHE. В своей докторской диссертации он впервые предложил разумную и безопасную полностью гомоморфную систему шифрования! Эта система основана на предположении об идеальной решетке. Полностью гомоморфную систему, предложенную Gentry09, часто называют полностью гомоморфной системой шифрования первого поколения.
В статье Джентри он также упомянул важную концепцию, называемую начальной загрузкой. Начальная загрузка — это особый метод обработки зашифрованного текста. После обработки он может «обновить» зашифрованный текст с шумом, близким к критическому значению, в новый зашифрованный текст с очень низким уровнем шума. Благодаря начальной загрузке шум системы конечных серий никогда не может превысить критическое значение, таким образом становясь полностью гомоморфной системой. Таким образом, мы можем гомоморфно вычислить F любого размера.
После крупного прорыва Джентри весь круг криптографии снова впал в безумие, и все начали пытаться найти более эффективную и универсальную полностью гомоморфную систему, основанную на идеях, предложенных Джентри.
В 2011 году два больших парня, Бракерски и Вайкунтанатан, предложили новую полностью гомоморфную систему шифрования, основанную на обучении с ошибками (LWE), еще одном предположении о решеточном шифровании. В том же году Бракерски, Джентри и Вайкунтанатан завершили работу над системой и официально опубликовали ее. Полностью гомоморфную систему, которую они изобрели, сокращенно называют системой BGV. Система BGV представляет собой гомоморфную систему шифрования ограниченного уровня, но ее можно превратить в полностью гомоморфную систему с помощью начальной загрузки. По сравнению с системой, предложенной Gentry09, система BGV использует более реалистичное предположение LWE. Вообще говоря, мы называем систему BGV полностью гомоморфной системой шифрования второго поколения.
В 2013 году Джентри вернулся. Джентри, Сахай и Уотерс запустили новую полностью гомоморфную систему шифрования GSW. Система GSW похожа на BGV тем, что она обладает полностью гомоморфными свойствами конечных рядов. Она основана на более простом предположении LWE и может быть полностью гомоморфной посредством начальной загрузки. Обычно мы называем систему GSW полностью гомоморфной системой шифрования третьего поколения.
После 2013 года криптосфера в основном процветала. На основе исходной полностью гомоморфной системы трех поколений появились различные новые разработки, предназначенные для оптимизации и повышения эффективности работы систем BGV и GSW. IBM разработала полностью гомоморфную вычислительную библиотеку HElib с открытым исходным кодом на основе системы BGV и успешно перенесла ее на основные мобильные платформы. В то же время стоит отметить еще один проект с открытым исходным кодом TFHE. TFHE основан на системе GSW с добавлением различных оптимизаций и ускорений и сейчас очень известен.
Помимо разработки традиционных полностью гомоморфных библиотек, многие команды также изучают, как лучше ускорить расчет полностью гомоморфных алгоритмов шифрования с помощью гетерогенного оборудования, такого как графический процессор, FPGA и ASIC. Например, cuFHE — это известная система полностью гомоморфного шифрования с графическим ускорением на базе CUDA.
С сегодняшней точки зрения, прошло 11 лет с тех пор, как Джентри постучался в дверь полностью гомоморфной системы. В настоящее время исследования FHE в отрасли процветают, и многие люди изучают полностью гомоморфные системы с разных точек зрения и требований приложений. На сегодняшний день у нас уже есть множество возможных методов реализации FHE, но все еще стремятся к эффективности работы системы FHE. Если взять в качестве примера современную библиотеку FHE, гомоморфное вычисление некоторой относительно простой логики на мобильной платформе может занять от десятков миллисекунд до десятков секунд. Эти единицы времени чрезвычайно медленны для компьютерных систем.
Как заставить систему FHE работать более эффективно на гетерогенных платформах, до сих пор остается неразгаданной загадкой. Если эта проблема когда-нибудь будет решена, то преобразование всех компьютерных вычислений в полностью гомоморфные и предоставление агентам возможности выполнять вычисления в сторонних облаках станет лёгким будущим.
Связь между FHE и MPC
Прежде чем закончить статью, хотелось бы добавить несколько слов о взаимосвязи FHE и MPC. MPC означает Secure Multi-Party Computation, то есть доверенные многосторонние вычисления. Обычно это означает, что несколько сторон имеют свои собственные входные данные и не хотят раскрывать их другим, но они хотят использовать свои собственные входные данные для совместного вычисления функции F и обмена результатами вычислений.
MPC на самом деле является областью, которая очень хорошо известна и изучается в течение длительного времени. С тех пор, как в прошлом веке криптограф Яо Цичжи выпустил свою книгу «Искаженные схемы», область MPC получила широкое признание, и было сделано много прорывов. Сейчас у нас уже есть много библиотек MPC, которые можно использовать, и они также обладают определенной эффективностью работы.
У друзей, знакомых с MPC, может возникнуть много вопросов после знакомства с трудной историей полностью гомоморфных систем шифрования: почему нельзя полностью заменить гомоморфное шифрование непосредственно протоколом MPC?
Действительно, протокол MPC может полностью заменить протокол FHE. Нам нужно только использовать пользовательский и частный ввод в качестве стороны в протоколе, а затем использовать удаленный прокси-вычислительный сервер в качестве другой стороны, что соответствует условиям выполнения протокола MPC.Только посредством определенных взаимодействий прокси-вычисления могут быть выполнены. понял. И сервер не может видеть частный ввод.
Но есть очень важный момент, который мы упустили из виду: поскольку MPC является интерактивным, пользователю и серверу необходимо вместе выполнять вычисления и взаимодействовать для завершения протокола. Это противоречит самому фундаментальному требованию вычислений агента FHE. Если пользователю необходимо все время оставаться онлайн, чтобы выполнить соглашение, а также оплатить часть вычислительных мощностей, то фактически расчет вообще не «проксируется», и обе стороны только производят дополнительные расчеты в целях информационной безопасности. . Это также объясняет, почему в области MPC произошел большой прорыв, но область FHE до сих пор неизвестна, поскольку эти две системы решают совершенно разные проблемы.
## Следующая остановка: полностью гомоморфная система шифрования GSW.
Учитывая это, каждый должен иметь очень глубокое представление о полностью гомоморфной системе шифрования.
Следующей остановкой мы сможем узнать об упомянутой выше полностью гомоморфной системе шифрования GSW. Хотя это третье поколение полностью гомоморфных систем, я думаю, что среди трех систем Gentry09, BGV и GSW GSW — это система с наименьшим количеством предположений, самой простой структурой и самой легкой для понимания. И сейчас существует множество библиотек с открытым исходным кодом (таких как TFHE), построенных на основе системы GSW.
Из-за нехватки места мы закончим эту статью на этом. В следующей статье мы сможем сначала изучить основы системы GSW: систему шифрования на основе решетки и проблему LWE. Как только проблема LWE будет понята, проблема, которую решает GSW, станет очень ясной.
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
Предварительное исследование полностью гомоморфного шифрования: определение и исторический обзор FHE
Автор: Стивен Юэ
Некоторое время назад я прошел курс CS355 (продвинутая криптография) в Стэнфорде. Нас преподавали трое аспирантов Дэна: Дима Коган, Флориан Трамер и Саба Эскандарян. Каждый из трех докторантов имеет свои особенности, и их направления исследований также сильно различаются. Дима фокусируется на технологии защиты конфиденциальности PIR (Private Information Retri), Флориан — на исследованиях в области машинного обучения и блокчейна, а Саба — на доказательстве с нулевым разглашением.
Курс CS355 охватывает практически весь контент в области криптографии с древних времен до наших дней. От самой ранней односторонней функции (Односторонняя функция) до эллиптического уравнения (ECC) и спаривания и, наконец, до некоторых популярных MPC, нулевого разглашения, поиска частной информации (PIR), полностью гомоморфного алгоритма и так далее в последние годы. . Поскольку занятия закончились только два дня назад, я организовал серию заметок, пока содержание знаний еще оставалось в моей поверхностной памяти. Содержание курса очень интересное. Остальной информацией я поделюсь с вами позже, когда у меня будет время ~
В этом выпуске мы поговорим о популярном в последнее время полностью гомоморфном шифровании (FHE) и сопутствующей ему технологии решетчатого шифрования.
Что такое полностью гомоморфное шифрование?
Я думаю, что многие друзья слышали о названии «Полное гомоморфное шифрование» (FHE). В последние годы появляется все больше и больше тем, касающихся защиты личной жизни, а также широко популяризируется ряд прикладных технологий криптографии, включая гомоморфное шифрование.
Чтобы лучше понять эту тему, я хотел бы кратко представить определение полностью гомоморфного шифрования.
Обзор системы шифрования
Прежде чем мы начнем, давайте рассмотрим самую традиционную систему шифрования.
Мы все знаем, что если вы хотите построить систему шифрования, вам часто нужен ключ. С помощью этого ключа мы можем зашифровать информацию открытого текста в зашифрованный текст на одном конце, а затем использовать ключ для изменения зашифрованного текста обратно в его первоначальный вид на другом конце. Без этого Ключа другим людям было бы трудно узнать, какую информацию мы передали.
В исследованиях криптографии всякий раз, когда мы видим определение новой системы, нам часто приходится указывать свойства, которыми должна обладать система.
Основное значение семантической безопасности заключается в том, что наблюдатель не может различить два зашифрованных сообщения. Таким образом, если злоумышленник подслушает сеть и увидит зашифрованную информацию, которую я отправляю, при условии, что используемая мной система шифрования семантически безопасна, то я могу быть уверен, что злоумышленник не сможет получить никакой информации о зашифрованном контенте из зашифрованного текста.
После удовлетворения двух вышеуказанных свойств система шифрования становится надежной.
Поняв, что представляет собой система шифрования, мы можем обратить внимание на этот зашифрованный текст, который выглядит как случайно сгенерированный искаженный код. Мы все знаем, что мы не получим никакой информации, просто взглянув на сам зашифрованный текст. Но значит ли это, что если нет ключа и есть только зашифрованный текст, мы ничего не сможем сделать?
Мы все знаем ответ: не совсем.
Это свойство мы называем аддитивным гомоморфизмом. Это означает, что зашифрованный зашифрованный текст сохраняет тонкую алгебраическую связь с предыдущим исходным текстом. Если мы сложим зашифрованный текст, мы сможем получить новый зашифрованный текст, сложив исходный текст. Таким же образом можно заключить, что существуют и аддитивно-гомоморфные алгоритмы шифрования. Мы можем перемножить зашифрованный текст, сгенерированный мультипликативно гомоморфным алгоритмом, а затем получить зашифрованный текст, соответствующий результату перемножения исходных текстов. В ходе всего процесса нам не нужно знать никакой информации, связанной с ключом, мы просто объединяем зашифрованный текст, который выглядит как случайный искаженный код.
Например: Система анонимного голосования.
Далее давайте приведем пример, наглядно описывающий практичность гомоморфного шифрования.
Мы все знаем, что такое онлайн-голосование: если руководитель компании хочет инициировать волну голосования, выберите, следует ли компании использовать систему 996. Затем начальник может попросить ИТ-специалиста настроить сервер и позволить сотрудникам сделать свой выбор: проголосовать 0, чтобы означать, что они не хотят, и проголосовать 1, что означает, что они хотят. После заключительного периода голосования босс может подсчитать все голоса. Если итоговая сумма всех голосов превысит половину числа сотрудников, в компании стартует 996 человек.
Этот механизм голосования кажется очень простым, но есть большая проблема конфиденциальности: если начальник хочет, чтобы все сотрудники были 996, но он намеренно инициирует это голосование только для того, чтобы выудить правоохранительные органы и увидеть, какой сотрудник не желает работать сверхурочно, тогда начальник Он может спокойно поручить своему младшему брату подслушивать в Интернете, записывать решения, представленные каждым сотрудником, и наконец посмотреть, кто проголосовал 0. В результате сотрудники очень боятся и не смеют выражать свои чувства.
Если мы сможем использовать аддитивный алгоритм гомоморфного шифрования, то эту проблему можно легко решить.
Конечно, эта система еще очень несовершенна: например, ИТ-отдел может напрямую помочь начальнику расшифровать голоса каждого и записать их в документ. Существуют и другие криптографические инструменты, которые могут помочь нам решить эту проблему. Из-за нехватки места дальнейшие пояснения здесь даваться не будут.
Но на этом этапе мы должны почувствовать силу алгоритма гомоморфного шифрования. Мы можем понять это так: с помощью алгоритма гомоморфного шифрования пользователи могут выполнять своего рода безопасные прокси-вычисления (безопасные делегированные вычисления) с ненадежным удаленным сервером (облаком). Пользователи могут использовать технологию гомоморфного шифрования, чтобы зашифровать свои конфиденциальные личные данные и передать их облаку.Затем облако может выполнить определенную степень вычислений над зашифрованными данными и, наконец, получить зашифрованный результат, который хочет пользователь, и вернуть его в облако.пользователь. Наконец, пользователь может использовать ключ дешифрования, чтобы открыть результат. На протяжении всего соглашения делегированная сторона (облако) никогда не сможет увидеть какую-либо полезную информацию, связанную с личным вводом.
После приблизительного понимания двух самых основных гомоморфных свойств становится очень легко понять другие концепции. С систематической точки зрения гомоморфные системы шифрования грубо делятся на четыре категории: частичный гомоморфизм, приблизительный гомоморфизм, полный гомоморфизм конечных серий и полный гомоморфизм.
Далее давайте по очереди рассмотрим конкретные определения каждой категории.
Частично гомоморфное шифрование
Самая элементарная стадия гомоморфного шифрования называется частично гомоморфным шифрованием, которое определяется как зашифрованный текст, обладающий только одним гомоморфным свойством. Этот этап включает в себя два режима аддитивного гомоморфизма и мультипликативного гомоморфизма, которые мы описали выше.
Мы получаем зашифрованный текст, соответствующий перемножению этих двух сообщений! Это свойство мультипликативного гомоморфизма: мы можем продолжать накладывать новые зашифрованные тексты поверх этого зашифрованного текста, так что мы можем получить любое умножение между зашифрованными текстами.
Приблизительное гомоморфное шифрование (несколько гомоморфное шифрование)
Как мы говорили в предыдущем параграфе, если мы хотим умножить частные входные данные и получить линейную комбинацию между ними, простой частично гомоморфный алгоритм шифрования (RSA, Эль-Гамаль) не может быть выполнен. Значит, нам нужно перейти к следующему этапу.
Следующим этапом частично гомоморфного шифрования является приблизительно гомоморфное шифрование, которое на один шаг приближается к полностью гомоморфному шифрованию, которого мы хотим достичь. Если у нас есть приблизительно гомоморфный алгоритм шифрования, то мы можем одновременно вычислять сложение и умножение зашифрованного текста. Однако следует отметить, что, поскольку этот этап приблизительно гомоморфен (несколько гомоморфен), количество сложений и умножений, которые можно выполнить, очень ограничено, и функция F, которую можно вычислить, также находится в ограниченном диапазоне.
На данном этапе существует не так много распространенных примеров приблизительно гомоморфного шифрования, если говорить о наиболее понятном примере, то это должен быть алгоритм циклического группового шифрования, основанный на спаривании.
Выше мы кратко рассмотрели алгоритм шифрования Эль-Гамаля, основанный на обычных циклических группах. Мы все знаем, что этот алгоритм аддитивно гомоморфен, что означает, что он может получать линейные комбинации между произвольными зашифрованными текстами. Фактически, в некоторых специальных циклических группах мы также можем обнаружить некоторые слабые свойства мультипликативного гомоморфизма.
Это ограничение доказывает, что система приближенно гомоморфна, поскольку мы не можем вычислить функцию F произвольной логики и глубины.
Полностью уровневое гомоморфное шифрование
Достигнув следующего этапа, мы становимся на шаг ближе к цели полного гомоморфизма.
Этот этап называется полностью гомоморфным шифрованием конечных серий. На этом этапе мы уже можем выполнять любую комбинацию сложения и умножения зашифрованного текста без каких-либо ограничений на количество раз.
Полностью гомоморфное шифрование (FHE)
После многих вызовов наконец-то дело дошло до полностью гомоморфного шифрования (FHE), которое мы и ждем.
Как следует из названия, полностью гомоморфная система шифрования не имеет ограничений на методы расчета.Мы можем произвольно комбинировать зашифрованные тексты для формирования новых зашифрованных текстов без ключа, и новый зашифрованный текст, независимо от вычислительной сложности, может быть полностью восстановлен до исходного текста.
Когда мы достигнем этой стадии, ранее упомянутое вычисление безопасного агента станет возможным. Если мы сможем найти более эффективную полностью гомоморфную систему шифрования, мы сможем безопасно проксировать все локальные вычисления в облако без утечки каких-либо данных!
Определение полностью гомоморфной системы шифрования
Прежде чем приступить к обсуждению истории полностью гомоморфных систем ниже, мы можем систематически определить формальное определение полностью гомоморфных систем. Полностью гомоморфная система шифрования имеет четыре алгоритма:
Прежде чем начать изучать, как реализуется алгоритм полностью гомоморфного шифрования, мы могли бы также взглянуть на то, как возникла концепция полностью гомоморфного шифрования.
Концепция FHE (полностью гомоморфного) была фактически предложена в конце 1970-х годов. В 1978 году Ривест, Адлеман и Дертузос, несколько громких имен в криптографии, впервые упомянули в своей статье «О банках данных и гомоморфизмах конфиденциальности» идею системы, которая могла бы выполнять определенные вычисления с зашифрованным текстом и косвенно работать с исходным текстом. Позже эта идея была резюмирована и названа полностью гомоморфным шифрованием.
Видно, что концепция полностью гомоморфного шифрования предлагалась уже давно. Удивительно, но в 1976 году, за два года до публикации статьи, только что был предложен протокол обмена ключами Диффла-Хеллмана! Это показывает, что воображение специалистов по криптографии по-прежнему очень богато.
Когда была предложена концепция FHE, все академическое сообщество было тронуто ею и начало десятилетия поисков, пытаясь найти идеальный алгоритм с полностью гомоморфными свойствами. Но за последние несколько десятилетий люди испробовали все мыслимые варианты, но не смогли найти вариант, который удовлетворял бы всем условиям полной гомоморфности и безопасность которого можно было бы легко доказать.
До 2009 года у доктора философии Крейга Джентри, который учился в Стэнфорде, внезапно возникла идея, и он преодолел трудности алгоритма FHE. В своей докторской диссертации он впервые предложил разумную и безопасную полностью гомоморфную систему шифрования! Эта система основана на предположении об идеальной решетке. Полностью гомоморфную систему, предложенную Gentry09, часто называют полностью гомоморфной системой шифрования первого поколения.
В статье Джентри он также упомянул важную концепцию, называемую начальной загрузкой. Начальная загрузка — это особый метод обработки зашифрованного текста. После обработки он может «обновить» зашифрованный текст с шумом, близким к критическому значению, в новый зашифрованный текст с очень низким уровнем шума. Благодаря начальной загрузке шум системы конечных серий никогда не может превысить критическое значение, таким образом становясь полностью гомоморфной системой. Таким образом, мы можем гомоморфно вычислить F любого размера.
После крупного прорыва Джентри весь круг криптографии снова впал в безумие, и все начали пытаться найти более эффективную и универсальную полностью гомоморфную систему, основанную на идеях, предложенных Джентри.
В 2011 году два больших парня, Бракерски и Вайкунтанатан, предложили новую полностью гомоморфную систему шифрования, основанную на обучении с ошибками (LWE), еще одном предположении о решеточном шифровании. В том же году Бракерски, Джентри и Вайкунтанатан завершили работу над системой и официально опубликовали ее. Полностью гомоморфную систему, которую они изобрели, сокращенно называют системой BGV. Система BGV представляет собой гомоморфную систему шифрования ограниченного уровня, но ее можно превратить в полностью гомоморфную систему с помощью начальной загрузки. По сравнению с системой, предложенной Gentry09, система BGV использует более реалистичное предположение LWE. Вообще говоря, мы называем систему BGV полностью гомоморфной системой шифрования второго поколения.
В 2013 году Джентри вернулся. Джентри, Сахай и Уотерс запустили новую полностью гомоморфную систему шифрования GSW. Система GSW похожа на BGV тем, что она обладает полностью гомоморфными свойствами конечных рядов. Она основана на более простом предположении LWE и может быть полностью гомоморфной посредством начальной загрузки. Обычно мы называем систему GSW полностью гомоморфной системой шифрования третьего поколения.
После 2013 года криптосфера в основном процветала. На основе исходной полностью гомоморфной системы трех поколений появились различные новые разработки, предназначенные для оптимизации и повышения эффективности работы систем BGV и GSW. IBM разработала полностью гомоморфную вычислительную библиотеку HElib с открытым исходным кодом на основе системы BGV и успешно перенесла ее на основные мобильные платформы. В то же время стоит отметить еще один проект с открытым исходным кодом TFHE. TFHE основан на системе GSW с добавлением различных оптимизаций и ускорений и сейчас очень известен.
Помимо разработки традиционных полностью гомоморфных библиотек, многие команды также изучают, как лучше ускорить расчет полностью гомоморфных алгоритмов шифрования с помощью гетерогенного оборудования, такого как графический процессор, FPGA и ASIC. Например, cuFHE — это известная система полностью гомоморфного шифрования с графическим ускорением на базе CUDA.
С сегодняшней точки зрения, прошло 11 лет с тех пор, как Джентри постучался в дверь полностью гомоморфной системы. В настоящее время исследования FHE в отрасли процветают, и многие люди изучают полностью гомоморфные системы с разных точек зрения и требований приложений. На сегодняшний день у нас уже есть множество возможных методов реализации FHE, но все еще стремятся к эффективности работы системы FHE. Если взять в качестве примера современную библиотеку FHE, гомоморфное вычисление некоторой относительно простой логики на мобильной платформе может занять от десятков миллисекунд до десятков секунд. Эти единицы времени чрезвычайно медленны для компьютерных систем.
Как заставить систему FHE работать более эффективно на гетерогенных платформах, до сих пор остается неразгаданной загадкой. Если эта проблема когда-нибудь будет решена, то преобразование всех компьютерных вычислений в полностью гомоморфные и предоставление агентам возможности выполнять вычисления в сторонних облаках станет лёгким будущим.
Связь между FHE и MPC
Прежде чем закончить статью, хотелось бы добавить несколько слов о взаимосвязи FHE и MPC. MPC означает Secure Multi-Party Computation, то есть доверенные многосторонние вычисления. Обычно это означает, что несколько сторон имеют свои собственные входные данные и не хотят раскрывать их другим, но они хотят использовать свои собственные входные данные для совместного вычисления функции F и обмена результатами вычислений.
MPC на самом деле является областью, которая очень хорошо известна и изучается в течение длительного времени. С тех пор, как в прошлом веке криптограф Яо Цичжи выпустил свою книгу «Искаженные схемы», область MPC получила широкое признание, и было сделано много прорывов. Сейчас у нас уже есть много библиотек MPC, которые можно использовать, и они также обладают определенной эффективностью работы.
У друзей, знакомых с MPC, может возникнуть много вопросов после знакомства с трудной историей полностью гомоморфных систем шифрования: почему нельзя полностью заменить гомоморфное шифрование непосредственно протоколом MPC?
Действительно, протокол MPC может полностью заменить протокол FHE. Нам нужно только использовать пользовательский и частный ввод в качестве стороны в протоколе, а затем использовать удаленный прокси-вычислительный сервер в качестве другой стороны, что соответствует условиям выполнения протокола MPC.Только посредством определенных взаимодействий прокси-вычисления могут быть выполнены. понял. И сервер не может видеть частный ввод.
Но есть очень важный момент, который мы упустили из виду: поскольку MPC является интерактивным, пользователю и серверу необходимо вместе выполнять вычисления и взаимодействовать для завершения протокола. Это противоречит самому фундаментальному требованию вычислений агента FHE. Если пользователю необходимо все время оставаться онлайн, чтобы выполнить соглашение, а также оплатить часть вычислительных мощностей, то фактически расчет вообще не «проксируется», и обе стороны только производят дополнительные расчеты в целях информационной безопасности. . Это также объясняет, почему в области MPC произошел большой прорыв, но область FHE до сих пор неизвестна, поскольку эти две системы решают совершенно разные проблемы.
Учитывая это, каждый должен иметь очень глубокое представление о полностью гомоморфной системе шифрования.
Следующей остановкой мы сможем узнать об упомянутой выше полностью гомоморфной системе шифрования GSW. Хотя это третье поколение полностью гомоморфных систем, я думаю, что среди трех систем Gentry09, BGV и GSW GSW — это система с наименьшим количеством предположений, самой простой структурой и самой легкой для понимания. И сейчас существует множество библиотек с открытым исходным кодом (таких как TFHE), построенных на основе системы GSW.
Из-за нехватки места мы закончим эту статью на этом. В следующей статье мы сможем сначала изучить основы системы GSW: систему шифрования на основе решетки и проблему LWE. Как только проблема LWE будет понята, проблема, которую решает GSW, станет очень ясной.