Доказательства с нулевым разглашением: объяснение на 5 уровнях сложности

Специалист в области компьютерных наук Амит Сахай (Amit Sahai), профессор Инженерной школы Самуэли при Калифорнийском университете в Лос-Анджелесе (UCLA), объясняет доказательства с нулевым разглашением на пяти уровнях сложности, от ребенка до эксперта, в этом видео от Уайрд. Концепция демонстрируется с помощью физических аналогий и обсуждается с возрастающей технической глубиной, делая одну из важнейших концепций криптографии доступной для каждого.

Эта стенограмма является доступной копией оригинальной стенограммы видео (opens in a new tab), опубликованной Уайрд. Она была слегка отредактирована для удобства чтения.

Введение (0:00)

Амит Сахай: Здравствуйте, меня зовут Амит Сахай, я профессор компьютерных наук в Инженерной школе Самуэли при UCLA. Сегодня меня попросили объяснить доказательства с нулевым разглашением на пяти уровнях возрастающей сложности.

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

Уровень 1: ребенок (0:41)

Амит Сахай: Какой твой любимый предмет?

Челси: Я бы сказала, математика. Некоторые маленькие задачки на самом деле могут быть очень большими и сложными. Это как головоломка.

Амит Сахай: Я люблю математику по той же причине. Сегодня я расскажу тебе о вещи, которая называется доказательством с нулевым разглашением. В доказательстве с нулевым разглашением участвуют два человека — прувер и верификатор. Я хочу доказать тебе, что что-то является правдой, но самое странное в том, что я хочу доказать тебе это, не объясняя причин. Помню, когда я впервые услышал об этом, я подумал: подождите, что? Как такое вообще возможно?

Итак, что ты видишь на этой фотографии?

Челси: Много пингвинов.

Амит Сахай: Да. Среди всех этих пингвинов спрятался тупик. Хочешь попробовать найти его? Видишь, где он? Я знаю, где он, но не хочу тебе говорить. Ты мне веришь?

Челси: Да.

Амит Сахай: А что, если бы я мог доказать тебе, что знаю, где находится тупик, не раскрывая его местоположения? Давай я тебе покажу. Я взял эту фотографию и поместил ее за этим плакатом. Почему бы тебе не заглянуть в это отверстие?

Челси: Я вижу тупика.

Амит Сахай: Итак, когда ты смотришь на эту доску, мы не знаем, где именно находилась фотография, верно? Был ли угол фотографии здесь, и в таком случае тупик находился бы на этой стороне? Или угол фотографии был здесь, и тогда тупик был бы на другой стороне? Это очень простой пример доказательства с нулевым разглашением. Я убедил тебя, что знаю, где находится тупик, но ты не узнала ничего больше.

Челси: Почему вы изучаете доказательства с нулевым разглашением?

Амит Сахай: Когда я впервые узнал о них, я просто подумал, что это очень круто. Но оказалось, что они еще и очень полезны — и не только для поиска тупиков. Если ты просто вводишь свой пароль, а хакер взламывает компьютер, он может просто получить твой пароль. Что, если бы вместо этого мы могли как-то использовать доказательство с нулевым разглашением для входа в систему? Ты бы просто смогла доказать, что ты Челси, ничего им не раскрывая. Если бы это было возможно, это было бы потрясающе, потому что даже если бы хакер взломал компьютер, он бы ничего не узнал — ведь даже сам компьютер ничего не узнает.

Итак, Челси, своими словами, что такое доказательство с нулевым разглашением?

Челси: Доказательство с нулевым разглашением — это доказательство утверждения. Вы не показываете им, почему или что именно. Вы просто показываете им крошечный фрагмент или просто делаете какой-то странный фокус, который на самом деле не фокус, и они будут убеждены. И вы не показали им почему, или что-то в этом роде.

Уровень 2: подросток (3:31)

Амит Сахай: Ты когда-нибудь раньше слышал термин «доказательство с нулевым разглашением»?

Подросток: Нет, не слышал.

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

Отлично. «Мою собаку зовут Даг».

Подросток: Вы поняли, какая была комбинация?

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

Подросток: Так какова точная цель доказательства с нулевым разглашением? Это как доказать что-то, но не давая достаточно информации, которая могла бы поставить под угрозу то, что вы доказываете?

Амит Сахай: Люди не доверяют друг другу. И если бы я мог доказать кому-то, что сделал что-то правильно, не раскрывая своих секретов, то этот человек доверял бы мне больше.

Подросток: Как это связано с компьютерными технологиями? Это личное взаимодействие?

Амит Сахай: Предположим, ты хочешь обмениваться сообщениями с кем-то, кого ты знаешь. Вы бы, наверное, сначала встретились и придумали какой-нибудь секретный код, верно? А потом писали бы друг другу сообщения с помощью этого кода. Но что, если вы никогда раньше не встречались с этим человеком? Что, если ты хочешь обмениваться секретными сообщениями со мной, а мы никогда раньше не виделись? Как бы мы могли это сделать?

Подросток: Понятия не имею.

Амит Сахай: Звучит невыполнимо, правда? Но это не так. Ты бы не стал использовать физический замок или физическую коробку. Вместо этого мы бы использовали математику для таких вещей. Ты мог бы взять сообщение и зашифровать его с помощью математики. А затем я мог бы доказать тебе, что знаю ключ, открыть его и отправить обратно тебе. Таким образом, я бы доказал тебе, что знаю математический ключ от математического сейфа.

Итак, основываясь на том, что мы сегодня обсудили, своими словами, что такое доказательство с нулевым разглашением?

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

Уровень 3: студент колледжа (6:13)

Амит Сахай: Что ты изучаешь?

Студент колледжа: Я студент первого курса факультета компьютерных наук в Инженерной школе Витерби при Университете Южной Калифорнии (USC). Я интересуюсь всем, что связано с данными, интернетом, блокчейном и криптовалютой.

Амит Сахай: Ты когда-нибудь слышал о доказательствах с нулевым разглашением?

Студент колледжа: Только мельком.

Амит Сахай: На самом деле, сфера блокчейна — это одна из областей, где мы видим внедрение доказательств с нулевым разглашением, и я думаю, что это только начало. По своей сути, доказательство с нулевым разглашением — это взаимодействие между двумя людьми. Я должен быть в состоянии убедить тебя в том, что некое утверждение истинно, но ты не будешь иметь ни малейшего представления о том, почему оно истинно.

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

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

Возможно, то, что ты действительно хочешь сделать, — это предоставить доказательство с нулевым разглашением того, что у тебя есть как минимум 0.3 Биткоина, не раскрывая адрес твоего аккаунта. Оказывается, я могу взять это утверждение и преобразовать его в карту стран. Эту карту стран можно будет раскрасить в три цвета только в том случае, если у тебя есть как минимум 0.2 Биткоина.

Студент колледжа: Как мы превратим что-то подобное в доказательство с нулевым разглашением?

Амит Сахай: Конечно, первый шаг — мы должны стереть все цвета. Я положил цвет внутрь каждого из этих конвертов. Теперь, откуда ты знаешь, что это правильная раскраска? Ты не знаешь. Ты должен выбрать любые две соседние страны — можешь выбирать их как угодно, случайным образом.

Студент колледжа: Можно мне эти две?

Амит Сахай: Здесь у нас зеленый, а здесь — синий. Как видишь, это два разных цвета. Так что у тебя есть небольшая уверенность в том, что мне удалось раскрасить это правильно, но не такая уж большая, потому что я показал тебе только две страны. Один из способов получить больше уверенности — открыть больше конвертов, но это означало бы раскрытие информации. Я не хочу этого делать.

Поэтому вместо этого я попрошу тебя отвернуться. А теперь давай поменяем эти цвета.

Можешь выбрать две страны случайным образом, и мы снова покажем два цвета.

Студент колледжа: Я возьму эту и эту.

Амит Сахай: Умно с твоей стороны проверить ту же самую, которая у тебя уже была. Но, как видишь, теперь она не зеленая, а синяя. А эта, с другой стороны, зеленая. Цвета, которые я показывал тебе в прошлый раз, не работают с этими новыми цветами. Но это работает для той раскраски, которую я показываю тебе прямо сейчас. Таким образом, мы сделали невозможным для тебя собрать все кусочки воедино. И если ты сделаешь это тысячу раз, и я каждый раз буду правильно показывать тебе разные цвета, ты будешь действительно убежден. Вот и все — это и есть все доказательство с нулевым разглашением.

Студент колледжа: То есть это похоже на вероятностное доказательство?

Амит Сахай: Да. В реальных реализациях мы бы не использовали конверты — использовалось бы шифрование. Но таков протокол.

Студент колледжа: Каковы более широкие последствия применения доказательств с нулевым разглашением? Должны ли они быть более практичными для внедрения, или они должны структурно что-то доказывать?

Амит Сахай: Речь идет не о том, чтобы сделать что-то более эффективным. Речь идет о том, чтобы делать вещи, которые мы просто не знали, как делать раньше. Я действительно могу доказать тебе, не раскрывая никаких своих секретов, что веду себя честно. Я мог бы доказать тебе, что правильно подписал какой-то зашифрованный документ, не раскрывая, что это за секретный документ. Эта способность менять правила игры — реально менять то, что мы можем делать — это то, что привносит нулевое разглашение.

Студент колледжа: Как вы думаете, где мы могли бы укрепить доверие с помощью доказательств с нулевым разглашением?

Амит Сахай: Один отличный пример — это выборы. Если бы вы могли доказать, что выборы были проведены правильно — что каждый голос был учтен, и все это привело к победе одного человека с определенным результатом — с нулевым разглашением, тогда вам не пришлось бы раскрывать реальные голоса каждого человека. И тем не менее, все могли бы убедиться, что все было сделано правильно.

Уровень 4: аспирант (11:59)

Амит Сахай: Очень рад видеть тебя здесь и поговорить с тобой, Илай. Можешь немного рассказать о своих исследованиях?

Илай: Мои исследования связаны с криптографией. В частности, я работаю над некоторыми протоколалами многосторонних вычислений. Тот, над которым я работаю прямо сейчас, — это система для вычисления агрегированной статистики, чтобы поставщики услуг, такие как Google Chrome или Tesla, могли собирать эту статистику, ничего не узнавая о данных отдельных пользователей. Мне, как пользователю, не нужно сообщать Firefox, что мой любимый сайт — mylittlepony.com. Но они могут знать, сколько пользователей заходит на mylittlepony.com каждый день.

Амит Сахай: Это потрясающе. Многосторонние вычисления близки и дороги моему сердцу. Очевидно, что доказательства с нулевым разглашением — это доказательство чего-либо другому человеку без раскрытия деталей того, что именно вы доказываете. Но, на мой взгляд, нулевое разглашение на самом деле идет еще дальше. Это всеобъемлющая концепция, которую часто можно встретить в многосторонних вычислениях, где вы хотите выполнить какую-то задачу, не раскрывая ничего, кроме того, что абсолютно необходимо для ее выполнения.

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

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

Илай: Когда вы впервые начали думать о доказательствах как об интерактивной игре, где мы разговариваем друг с другом, сделало ли это возможным нулевое разглашение?

Амит Сахай: Абсолютно. И идея о том, что случайность может быть полезна для доказательства чего-либо — опять же, кажется такой нелогичной, если мы думаем о платоновском идеале доказательства. Там нет ни случайности, ни недетерминизма.

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

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

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

Амит Сахай: Каковы некоторые из узких мест в плане эффективности?

Илай: Одна из самых крутых вещей в доказательствах с нулевым разглашением заключается в том, что их так много видов — мне нравится называть их вкусами. В целом, когда вы используете доказательства с нулевым разглашением на практике, главное узкое место, как правило, находится на стороне прувера.

Амит Сахай: Можно ли взять работу прувера и разбить ее на множество параллельных вычислений?

Илай: Это такой интересный вопрос. Я думаю, что мы, как отрасль, до сих пор не знаем на него ответа. Одна из самых крутых вещей, которые я видел за последние три или четыре года, — это переход от теории к практике: видеть, как все эти удивительные системы, которые люди придумывали в течение последних 30 лет, начинают становиться достаточно эффективными для их создания.

Амит Сахай: Без сомнения. И особенно с облачными вычислениями — использование мощи облака для обеспечения доказательств с нулевым разглашением было бы потрясающим. Также в сфере блокчейна, если вы хотите ускорить генерацию доказательств, было бы здорово, если бы это можно было делать распределенным образом. Одна из моих надежд заключается в том, что сила многосторонних вычислений состоит в объединении людей, которые взаимно не доверяют друг другу. Можем ли мы взять эту силу криптографии и использовать ее, чтобы помочь справиться с колоссальным уровнем недоверия, который существует в обществе прямо сейчас?

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

Уровень 5: эксперт (17:10)

Амит Сахай: Шан-Хуа, так здорово снова тебя видеть. Кажется, в последний раз мы встречались в 2017 году или около того.

Шан-Хуа: Думаю, мы как-то созванивались в Zoom во время пандемии, но приятно видеть тебя лично. На самом деле, в 86-м году я посещал курс по криптографии у профессора Леонарда Адлемана, буквы «A» в RSA. Он поручил мне статью Гольдвассер, Микали и Чарли Ракоффа о доказательстве с нулевым разглашением. Так что это действительно была моя самая первая презентация в этой стране — о нулевом разглашении.

Амит Сахай: Это потрясающе. Это почти гипнотическая концепция.

Шан-Хуа: Также интересно, как математически сформулировать эти концепции. Например, у нас есть данные. В конечном итоге из данных, посредством интеллектуального анализа данных, вы можете получить информацию. А затем у вас появляется это слово — «знание». О знании давно ведутся споры даже в философии. Что такое знание? Но здесь представлен очень увлекательный способ, которым математики или специалисты в области компьютерных наук хотят зафиксировать это знание. Оно не называется «доказательством с нулевой информацией». Так каково твое мнение о том, почему «знание», а не «информация» или «доказательство с нулевыми данными»? Очевидно, что данные там есть, так что это не может быть нулевыми данными.

Амит Сахай: Абсолютно. Я не думаю, что у нас до сих пор есть полностью удовлетворительный ответ на этот вопрос. Что было таким прекрасным озарением, так это идея о том, что нулевое разглашение — это то, что вы уже можете предсказать. Если вы уже можете предсказать ответ, значит, вы не получаете никаких знаний в результате этого взаимодействия. Это озарение — способность точно предсказывать будущее, что является свидетельством отсутствия новых знаний, — было таким прекрасным, удивительным озарением.

Шан-Хуа: Ну, здесь нет нулевой информации. По сути, с точки зрения вычислений и безопасности, важно то, сколько знаний вы получаете, а не то, сколько информации вы получили и сколько у вас данных. Данные не сразу подразумевают знание. Но люди не всегда могут это различить.

Амит Сахай: Верно. Например, в медицинских исследованиях — как было бы здорово иметь лекарство и доказать, что оно работает в этой модели, не раскрывая структуру соединения?

Шан-Хуа: Как бы ты сказал, каковы следующие направления в этой области?

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

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

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

Шан-Хуа: Я думаю, что в глубине души студенты часто спрашивают меня, каковы будущие направления — как с точки зрения криптографии, доказательств с нулевым разглашением, в реальном мире, так и в математических вычислениях.

Амит Сахай: Это отличный вопрос. Хотел бы я видеть будущее. Я не могу, но позволь мне попытаться. Я думаю, что за последние несколько десятилетий мы так много сделали в криптографии, но так мало понимаем. Самый фундаментальный аспект — это понимание сложности: как мы получаем сложные задачи? Как нам на самом деле создавать математически сложные задачи, чтобы затем использовать их для создания эффективных программ и доказательств с нулевым разглашением?

Шан-Хуа: Полагаю, в квантовых вычислениях нужны еще более сложные задачи.

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

Шан-Хуа: Но я уверен, что они станут стимулом для создания прекрасной математики.

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