Доведення з нульовим розголошенням: пояснення на 5 рівнях складності

Вчений-інформатик Аміт Сахай (Amit Sahai), професор Інженерної школи Самуелі при Каліфорнійському університеті в Лос-Анджелесі (UCLA), пояснює доведення з нульовим розголошенням на п'яти рівнях складності, від дитини до експерта, у цьому відео від WIRED. Ця концепція демонструється за допомогою фізичних аналогій та обговорюється з поступовим заглибленням у технічні деталі, що робить одну з найважливіших концепцій криптографії доступною для кожного.

Ця стенограма є доступною копією оригінальної стенограми відео (opens in a new tab), опублікованої WIRED. Її було трохи відредаговано для зручності читання.

Вступ (0:00)

Аміт Сахай: Привіт, мене звати Аміт Сахай, і я професор інформатики в Інженерній школі Самуелі при UCLA. Сьогодні мене попросили пояснити доведення з нульовим розголошенням на п'яти рівнях складності, що поступово зростає.

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

Рівень 1: дитина (0:41)

Аміт Сахай: Який твій улюблений предмет?

Челсі: Я б сказала, математика. Деякі маленькі задачі насправді можуть бути дуже великими та складними. Це як головоломка.

Аміт Сахай: Я люблю математику з тієї ж причини. Сьогодні я розповім тобі про таку річ, як доведення з нульовим розголошенням. У доведенні з нульовим розголошенням беруть участь двоє людей — доводжувач та верифікатор. Я хочу довести тобі, що щось є правдою, але найдивніше те, що я хочу довести тобі це, не пояснюючи жодних причин. Пам'ятаю, коли я вперше почув про це, я подумав: зачекайте, що? Як таке взагалі можливо?

Отже, що ти бачиш на цьому фото?

Челсі: Багато пінгвінів.

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

Челсі: Так.

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

Челсі: Я бачу тупика.

Аміт Сахай: Отже, коли ти дивишся на цю дошку, ми не знаємо, де саме було фото, чи не так? Чи був кут фотографії тут, і в такому разі тупик був би аж на цьому боці? Чи кут фотографії був тут, і тоді тупик був би на іншому боці? Це дуже простий приклад доведення з нульовим розголошенням. Я переконав тебе, що знаю, де знаходиться тупик, але ти не дізналася нічого іншого.

Челсі: Чому ви вивчаєте доведення з нульовим розголошенням?

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

Отже, Челсі, твоїми власними словами, що таке доведення з нульовим розголошенням?

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

Рівень 2: підліток (3:31)

Аміт Сахай: Отже, ти коли-небудь раніше чув термін «доведення з нульовим розголошенням»?

Підліток: Ні, не чув.

Аміт Сахай: Це спосіб для доводжувача переконати верифікатора в тому, що щось є правдою, не розкриваючи нічого про те, чому це правда, що звучить абсолютно дивно. Я хочу довести тобі, що знаю цю комбінацію, не розкриваючи її тобі. А ти міг би написати невелику записку, секрет, якого я точно не знаю. Згорни її і поклади сюди. А потім, якщо я знаю комбінацію, я зможу відкрити замок і сказати тобі, що ти написав.

Гаразд. «Мого собаку звати Даг».

Підліток: Ви дізналися, якою була комбінація?

Аміт Сахай: Ні. Отже, ніде під час нашої взаємодії ти не побачив жодної інформації, якої б ти вже не знав. І все ж я переконав тебе, що знаю комбінацію.

Підліток: Тож яка точна мета доведення з нульовим розголошенням? Це ніби доведення чогось, але без надання достатньої кількості інформації, яка могла б поставити під загрозу те, що ви доводите?

Аміт Сахай: Люди не довіряють одне одному. І якби я міг довести комусь, що зробив щось правильно, не розкриваючи своїх секретів, то ця людина довіряла б мені більше.

Підліток: Як це пов'язано з комп'ютерними технологіями? Це особиста взаємодія?

Аміт Сахай: Припустимо, ти хотів би обмінюватися повідомленнями з кимось, кого ти знаєш. Ви б, напевно, спочатку зустрілися і придумали якийсь секретний код, так? А потім писали б повідомлення одне одному за допомогою цього коду. Але що, якби ти ніколи раніше не зустрічав цю людину? Що, якби ти хотів обмінюватися секретними повідомленнями зі мною, а ми ніколи раніше не бачилися? Як би ми взагалі могли це зробити?

Підліток: Не маю жодного уявлення.

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

Отже, спираючись на те, що ми сьогодні обговорили, твоїми власними словами, що таке доведення з нульовим розголошенням?

Підліток: Це ніби у вас є дуже важливий секрет, про який ви хочете, щоб хтось дізнався, але ви не хочете розповідати їм усе. Ви можете використати доведення з нульовим розголошенням, щоб довести їм цей секрет, але не видати його повністю.

Рівень 3: студент коледжу (6:13)

Аміт Сахай: Що ти вивчаєш?

Студентка: Я студентка першого курсу інформатики в Інженерній школі Вітербі при Університеті Південної Каліфорнії (USC Viterbi). Я цікавлюся всім, що пов'язано з даними, інтернетом, блокчейном та криптовалютою.

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

Студентка: Лише побіжно.

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

Ми підійдемо до цього через концепцію, яка називається 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-му я відвідував курс із криптографії у професора Леонарда Адлемана (Leonard Adleman), літери «A» в RSA. Він доручив мені статтю Гольдвассер (Goldwasser), Мікалі (Micali) та Чарлі Ракоффа (Charlie Rackoff) про доведення з нульовим розголошенням. Тож це дійсно була моя найперша презентація в цій країні — про нульове розголошення.

Аміт Сахай: Це чудово. Це майже гіпнотична концепція.

Шан-Хуа: Також цікаво, як математично сформулювати ці концепції. Наприклад, у нас є дані. Зрештою, з даних, за допомогою інтелектуального аналізу даних, ви можете отримати інформацію. А потім у вас є це слово «знання». Про знання довго сперечалися навіть у філософії. Що таке знання? Але ось дуже захопливий спосіб, у який математики чи інформатики хочуть зафіксувати це знання. Воно не називається «доведенням з нульовою інформацією». Тож яка твоя думка щодо того, чому «знання», а не «інформація» чи «доведення з нульовими даними»? Очевидно, що дані там є, тому це не може бути нульовими даними.

Аміт Сахай: Абсолютно. Я не думаю, що ми досі маємо повністю задовільну відповідь на це запитання. Що було таким прекрасним осяянням, так це ідея про те, що нульове розголошення — це те, що ви вже можете передбачити. Якщо ви вже можете передбачити відповідь, то ви, мабуть, не отримуєте жодних знань від цієї взаємодії. Це осяяння — здатність точно передбачати майбутнє і те, що це є доказом відсутності нових знань — було таким прекрасним, дивовижним осяянням.

Шан-Хуа: Ну, тут немає нульової інформації. Фундаментально, з точки зору обчислень та безпеки, має значення те, скільки знань ви отримуєте, більше, ніж те, скільки інформації ви отримали і скільки даних у вас є. Дані не означають автоматично знання. Але люди не завжди можуть це розрізнити.

Аміт Сахай: Правильно. Наприклад, у медичних дослідженнях — як було б чудово мати ліки і довести, що вони працюють у цій моделі, не розкриваючи структуру сполуки?

Шан-Хуа: Якими, на твою думку, є наступні напрямки в цій сфері?

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

Шан-Хуа: Це правда. Існує неінтерактивна природа. Але в ній є можливість верифікації. У блокчейні також почали впроваджувати більш загальне доведення з нульовим розголошенням у реєстр.

Аміт Сахай: Ми безумовно перебуваємо в тому моменті, коли нульове розголошення буде використовуватися все більше і більше. У просторі нульового розголошення відбувається так багато конференцій та зустрічей, на які нас із тобою не запрошують — тому що вони для людей, які розробляють, людей, які програмують, а не для нас, математиків. І я думаю, що це знак. Це знак того, що наше дитя виросло, і настав час для його розвитку.

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

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

Шан-Хуа: Гадаю, також у квантових обчисленнях вам потрібні ще складніші задачі.

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

Шан-Хуа: Але я впевнений, що вони мотивуватимуть прекрасну математику.

Аміт Сахай: Так, це правда. Одна з чудових речей у реальному світі полягає в тому, що люди в реальному світі мають вимоги. І ці вимоги часто звучать як щось неможливе. І саме тут з'являємося ми — наша робота полягає в тому, щоб робити неможливе можливим.