За гранью нулевого знания: Что дальше в программируемой криптографии?

Программируемая криптография

Хотя шифрование существует уже тысячи лет, программируемая криптография - это современная технология. Описанная как "криптография общего назначения... [или] выразительный язык для формул", эта идея заключается в том, что такой криптографический примитив, как доказательство ZK, можно сделать достаточно гибким и адаптивным, чтобы разработчик мог запрограммировать на его основе практически любую функцию. Что может существовать непрерывная логическая цепочка от нажатия человеком кнопки на сайте до математического доказательства, гарантирующего безопасность криптографической операции.

https://youtu.be/qAfprVCBhdQ?t=1024

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

Доказательства ZK были впервые придуманы в 1989 году, но оставались в основном теоретическими до 2012 года, когда был открыт тип доказательства ZK, называемый zk-SNARK. Этот новый примитив позволил ZK-доказательствам доказать или подтвердить подлинность практически любой функции или произвольного вычисления.

С тех пор как zkSNARKS стал возможен, ресурсы и таланты были направлены на создание zCash, zkRollups, zkEVMs и множества других приложений, начинающихся на букву z. Оказалось, что децентрализованные системы, такие как Ethereum, и блокчейн в целом, стали идеальным стимулом для того, чтобы заинтересовать людей криптографией, превратив некогда непрактичную область исследований в активную экосистему с реальными приложениями для конечных пользователей.

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

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

Относительно интуитивное сравнение

Чтобы лучше понять общий ландшафт программируемой криптографии, давайте начнем с того, что очень приблизительно определим, где находятся MPC, FHE и IO по отношению к ZK и друг к другу. В этом разделе, да и во всех последующих разделах, мы будем отказываться от нюансов, точности и формальности в пользу простоты и доступности.

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

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

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

Многосторонние вычисления (MPC)

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

В отличие от ZK, MPC - это совместная работа. Она позволяет разным сторонам сотрудничать в одном и том же вычислении, каждая из которых вносит свои собственные данные, чтобы получить какой-то общий результат, который нужен всем.

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

Проблемы миллионеров

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

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

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

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

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

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

Хотя для MPC не существует таких знаменитых мысленных экспериментов, как "Проблема миллионера", FHE решает фундаментальный недостаток безопасности: "необходимость расшифровки перед обработкой данных".

https://www.zama.ai/post/the-revolution-of-fhe

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

Если все получится, FHE станет одной из самых мощных технологий сохранения конфиденциальности. И кто знает? Через 10 лет у нас могут появиться даже FHE-EVM.

Управление шумом

По сравнению с MPC и ZK, FHE - на данный момент - находится на более теоретическом или менее практическом конце спектра. Технология была признана целесообразной только в 2009 году, когда Крейг Джентри придумал, как справиться с шумом.

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

Прорывом Джентри стала техника под названием "бутстраппинг", которая позволила уменьшить шум и увеличить количество вычислений с зашифрованными данными в системах FHE. Bootstrapping берет шифротекст и расшифровывает его гомоморфно, что означает снижение уровня шума на зашифрованном фрагменте данных, не раскрывая их сути. В результате мы получаем шифротекст с гораздо меньшим количеством предварительно заданного шума, что позволяет нам выполнять дальнейшие вычисления с этим шифротекстом. Бутстраппинг, в общем, позволяет обойти необходимость увеличения пространства для роста шума по мере увеличения сложности вычислений. Мы можем ограничить пространство несколькими операциями и многократно использовать бутстрап для вычисления произвольно больших вычислений без ущерба для исходных данных.

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

Неразличимая обфускация (iO)

Если FHE превращает все элементы вычисления в "черный ящик", то iO превращает само вычисление в "черный ящик".

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

По словам Амита Сахаи, профессора, известного тем, что объяснял детям доказательства ZK, и одного из исследователей, придумавших, как построить iO на хорошо обоснованных предположениях, iO работает по принципиально иной парадигме, чем предыдущие криптографические системы. IO предполагает, что противник уже может читать Ваши мысли (метафора для Вашего компьютера). Ваши секреты уже известны, поэтому их невозможно скрыть. Единственное, что Вы можете сделать, это затушевать то, что противник уже видит.

https://youtu.be/v2RR_c5hn1E

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

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

Технически, существует черный ящик больше, чем iO. Это буквально называется "затуманивание черного ящика". Но это все равно невозможно.

Хорошо обоснованные предположения

Никто не знал, как построить iO, до 2013 года, когда мультилинейные карты были предложены Гаргом, Джентри, Халеви, Райковой, Сахаи, Уотерсом. Компьютерную программу можно разбить на части, как пазл, а затем затушевать с помощью мультилинейных карт. Непонятные части можно собрать заново, чтобы добиться той же функциональности, что и у оригинальной программы, не раскрывая ее внутренностей.

Мультилинейные карты - это обобщение билинейных карт или пар, используемых в криптографии эллиптических кривых (ECC). Хотя билинейные карты являются основой существующих криптографических схем, таких как подписи BLS, они не являются достаточно сложными и выразительными для iO. И хотя мультилинейные карты могли работать с iO, эта новая алгебраическая структура легко поддавалась атакам и не была безопасной, так что полагаться на мультилинейные карты криптографам было в целом не по душе. Поле снова застряло.

Затем, в 2020 году, Джайн, Лин и Сахай предложили решение, которое, несмотря на свою необычность и новизну, было достаточно простым, чтобы криптографы могли рассуждать о нем. Вместо того, чтобы полагаться на недавно разработанные предположения, такие как мультилинейные карты, эта версия iO могла быть построена на более стандартных и обоснованных предположениях, которые изучаются уже несколько десятилетий, таких как обучение с ошибками (LWE). Благодаря этому последнему прорыву iO снова стал возможным. Святой Грааль был все еще в пределах досягаемости.

Неприрученная дикая природа

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

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

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

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

В презентации Сахаи приводится цитата из статьи Стивена Вайнберга (Steven Weinberg) 2003 года в журнале Nature под названием "Четыре золотых урока", которая подчеркивает еще одну причину работать над тем, что в настоящее время не представляется возможным.

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

Программируемая криптография изучается различными командами, включая PSE и 0xPARC, соорганизаторов двухдневного мероприятия под названием Programmable Cryptography Conference, которое состоится в Стамбуле, Турция, 16 ноября & 17 ноября 2023 года.

Приходите поздороваться!

Или найдите PSE онлайн в Discord.

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

1. Эта статья перепечатана из[Privacy and Scaling Explorations]. Все авторские права принадлежат оригинальному автору[kichong]. Если у Вас есть возражения против этой перепечатки, пожалуйста, свяжитесь с командой Gate Learn, и они незамедлительно рассмотрят их.
2. Предупреждение об ответственности: Мнения и взгляды, выраженные в этой статье, принадлежат исключительно автору и не являются инвестиционным советом.
3. Перевод статьи на другие языки осуществляется командой Gate Learn. Если не указано, копирование, распространение или плагиат переведенных статей запрещены.