Уявіть, що у вас є якісь корисні знання — можливо, секретний рецепт або ключ до шифру. Чи можете ви довести другові, що володієте цими знаннями, нічого про це не розкриваючи? Комп’ютерні вчені довели понад 30 років тому, що ви можете, якщо використаєте те, що називається доказом нульового знання.
Для простого розуміння цієї ідеї припустімо, що ви хочете показати своєму другові, що знаєте, як пройти через лабіринт, не розголошуючи жодних подробиць про шлях. Ви можете просто подолати лабіринт протягом певного часу, поки вашому другу було заборонено спостерігати. (Обмеження часу необхідне, тому що за достатньо часу будь-хто зрештою зможе знайти вихід шляхом проб і помилок.) Ваш друг знав би, що ви можете це зробити, але він не знав би, як.
Докази з нульовим знанням корисні криптографам, які працюють із секретною інформацією, а також дослідникам обчислювальної складності, які мають справу з класифікацією складності різних проблем. «Багато сучасних криптографій покладаються на припущення про складність — на припущення, що певні проблеми важко вирішити, тому між двома світами завжди існували певні зв’язки», — сказав Клод Крепо, фахівець з інформатики в Університеті Макгілла. «Але [ці] докази створили цілий світ зв’язків».
Докази з нульовим знанням належать до категорії, відомої як інтерактивні докази, тому, щоб дізнатися, як працюють перші, це допоможе зрозуміти друге. Спочатку описаний у статті 1985 року комп’ютерників Шафі Голдвассер, Сільвіо Мікалі та Чарльза Ракоффа, інтерактивні докази працюють як опитування: через серію повідомлень одна сторона (доказник) намагається переконати іншу (верифікатор), що певне твердження є істинним. Інтерактивний доказ повинен задовольняти дві властивості. По-перше, правдиве твердження завжди врешті-решт переконає чесного верифікатора. По-друге, якщо дане твердження є хибним, жоден доказувач — навіть той, хто вдає, що володіє певними знаннями — не зможе переконати перевіряючого, за винятком мізерно малої ймовірності.
Інтерактивні докази мають імовірнісний характер. Підтверджувач може відповісти на одне або два запитання правильно просто завдяки щасливому випадку, тому потрібна досить велика кількість викликів, усі з яких перевіряючий повинен виконати правильно, щоб перевіряючий став упевненим, що перевіряючий справді знає, що твердження правдиве.
Ця ідея взаємодії виникла, коли Мікалі та Голдвассер — тодішні аспіранти Каліфорнійського університету в Берклі — ламали голову над логістикою гри в покер через мережу. Як усі гравці можуть перевірити, що коли один із них отримує картку з віртуальної колоди, результат є випадковим? Інтерактивні докази можуть лідирувати. Але тоді, як гравці можуть перевірити, що весь протокол — повний набір правил — було дотримано правильно, не розкриваючи руку кожного гравця?
Щоб досягти цієї мети, Мікалі та Голдвассер додали третю властивість до двох, необхідних для інтерактивного доказу: доказ не повинен розкривати нічого про самі знання, лише правдивість твердження. «Існує поняття про проходження протоколу, наприкінці якого ви вважаєте, що [гравці в покер] не знають нічого більше, ніж вони повинні знати», — сказав Голдвассер.
Розглянемо класичний приклад. Аліса хоче довести Бобу, що певний граф G — унікальна сукупність вершин (точок), з’єднаних ребрами (лініями) — має «Гамільтонів цикл». Це означає, що графік має шлях, який відвідує кожну точку рівно один раз і закінчується в тій самій точці, з якої він почався. Аліса могла б зробити це, просто показавши Бобу шлях, який це робить, але, звісно, тоді він теж знав би шлях.
Ось як Аліса може переконати Боба, що вона знає про існування такого шляху, не показуючи йому це. Спочатку вона малює новий графік, H, це не схоже G але схожий у вирішальному сенсі: він має однакову кількість вершин, з’єднаних однаковими способами. (Якщо G дійсно має гамільтонів цикл, ця подібність означає H також буде.) Потім, закривши кожен край усередині H за допомогою малярської стрічки вона замикає H у коробці та віддає коробку Бобу. Це не дозволяє йому бачити це безпосередньо, але також заважає їй змінити це. Тоді Боб робить вибір: або він може попросити Алісу показати це H дійсно схожий на G, або він може попросити її показати йому гамільтонів цикл у H. За умови, що обидва запити повинні бути легкими для Аліси H дійсно досить схожий на G, і що вона справді знає шлях.
Звичайно, навіть якщо Аліса не знає гамільтонів цикл у G, вона може спробувати обдурити Боба, малюючи графіки, які не схожі на G, або надсилаючи графіки, шлях до яких вона не знає. Але після того, як вони зіграли кілька раундів, шанс того, що Аліса щоразу обманює Боба, стає надзвичайно малим. Якщо вона зробить все правильно, зрештою Боб переконається, що Аліса знає гамільтонів цикл у графі G, хоча Боб ніколи цього не бачив.
Після початкової статті, яка вперше описувала такі докази, Мікалі та двоє математиків — Одед Голдрайх і Аві Вігдерсон — виявили несподіваний наслідок із далекосяжними наслідками. Це пов’язано з основною категорією проблем приблизно однакової складності, відомих як NP. Ці проблеми важко вирішити, але їх рішення легко перевірити. Троє дослідників знайшов це, якщо дійсно надійне шифрування можливо, то розв’язок кожної проблеми в NP також може бути доведено за допомогою доказу з нульовим знанням. Це дослідження допомогло дослідникам зачати варіанти доказів з нульовим знанням, які навіть не вимагають надійного шифрування; вони відомі як інтерактивні докази з кількома доказами.
А в 1988 році Мікалі та ін показав якщо перевіряльник і верифікатор спільно використовують короткий рядок випадкових бітів, взаємодія не потрібна. Теоретично це означало, що докази з нульовим знанням не повинні бути інтерактивними, що означало б, що постійне спілкування між двома сторонами не потрібне. Це зробило б їх набагато кориснішими для дослідників, але такі докази набули популярності лише на початку 21 століття.
«Наприкінці 2000-х ми почали спостерігати еволюцію ефективних методів побудови доказів із нульовим знанням», — сказав Метью Д. Грін, криптограф в університеті Джона Гопкінса. «Ми дійшли до того моменту, коли зрозуміли: «Зачекайте секундочку, насправді може бути спосіб застосувати це на практиці».»
Тепер перевіряльник може надіслати одне повідомлення верифікатору, не потребуючи доступу обох до мережі, а дослідники можуть створити дуже короткий доказ, який можна швидко перевірити навіть для дуже складних проблем. Це призвело до кількох практичних застосувань, таких як можливість швидко перевірити блокчейн після транзакції криптовалюти, приховуючи деталі транзакції. А в 2016 році група фіз показав як докази нульового знання можуть допомогти в ядерному роззброєнні: не розкриваючи жодного секрету про дизайн своєї ядерної боєголовки, країна тепер може довести ядерним інспекторам, чи є боєголовка активною чи неактивною.
Нещодавно прогрес у квантових обчисленнях змусив Крепо провести стрес-тест минулих досліджень, щоб переконатися, що протоколи з нульовим знанням все ще життєздатні. У 2021 році допоміг демонструвати що інтерактивні докази з декількома доказами зберігають свою таємницю, навіть якщо задіяні квантові комп’ютери, але досягнення того самого рівня безпеки робить протокол набагато повільнішим. За його словами, відкриття було гарною новиною, але з розвитком технологій виникнуть нові проблеми.
«Кожен тип обчислень, які ми можемо робити в майбутньому, включатиме квантові комп’ютери», — сказав Крепо. «Як хороші криптографи-параноїки, коли ми оцінюємо безпеку системи, ми хочемо переконатися, що наша система безпечна».
Примітка редактора: Шафі Голдвассер отримав фінансування від фонду Саймонса, який також фінансує це редакційно незалежне видання. Рішення про фінансування Simons Foundation не впливають на наше висвітлення.
