Доказ з Нульової Інформації: Протокол Ідентифікації Шеннора

Три ходи: комміт, виклик, відповідь

Протокол ідентифікації Шнорра дозволяє перевіряючому переконатися, що перевізник знає секретне число x — логарифм відрізка — без передачі x або будь-чого, що може використати шкідливець для його обчислення. Він працює в циклічній групі з публічним генератором g великого простого порядку q (та сама група, що використовується в Diffie-Hellman і DSA), і складається з трьох повідомлень:

налаштування: публічний ключ y = g^x mod p (x є секретом перевізника) 1. комміт: перевізник обирає випадкове r, відправляє t = g^r mod p 2. виклик: перевіряючий надсилає випадковий c 3. відповідь: перевізник відправляє s = r + c*x mod q перевіряючий перевіряє: g^s == t * y^c (mod p) жива демонстрація · повторні раунди комміт / виклик / відповідь● ЖИВА Перевірка працює тому, що s = r + c*x, отже g^s = g^r * g^(c*x) = t * (g^x)^c = t * y^c точно тоді, коли перевізник справді використовував x, який відповідає публічному ключу y. Будь-хто, хто не знає x, повинен буде вгадувати виклик c заздалегідь, щоб підробити відповідне t — що вони можуть зробити лише з незначним шансом 1/q, оскільки c обирається після того, як t вже було підтверджено.

setup:      public key  y = g^x mod p        (x is the prover's secret)

1. commit:   prover picks random r, sends   t = g^r mod p
2. challenge: verifier sends a random        c
3. response:  prover sends                   s = r + c*x mod q

verifier checks:   g^s  ==  t * y^c  (mod p)

Чому це справді нульові знання

Корисна система доказів має три властивості: повнота (чесний доведене, яке дійсно знає x, завжди переконує перевіреного), міцність (доведене, яке не знає x, може обдурити перевіреного лише з незначною ймовірністю, оскільки вгадування виклику перед підтвердженням є результатом випадковості) та нульове знання — транскрипт нічого не розкриває про x, окрім того факту, що доведене його знає. Стандартний аргумент для третьої властивості полягає в симуляторі: маючи лише публічний ключ y, ви можете створити фальшивий транскрипт (t, c, s), який статистично не відрізняється від реального, просто вибравши s і c спочатку та обчисливши t = g^s / y^c назад. Якщо симулятор без доступу до секрету може генерувати транскрипти, які статистично не відрізняються від реальних, то реальний транскрипт також не розкриває інформації про секрет.

Заснована на проблемі розрахунку дискретного логарифму

Цілісна безпека протоколу спирається на проблему розрахунку дискретного логарифму: за заданих g та y = g^x mod p, знайти x вважається обчислювально неможливою для добре обраної групи, хоча перевірка кандидата x є тривіальною. Це така ж складна проблема, що лежить в основі обміну ключами Diffie-Hellman та підписів DSA/ECDSA — ідентифікація Шеннора, у певному сенсі, є найчистішим можливим демонстрацією того, що ви отримуєте за цю твердження про складність: спосіб довести володіння секретом без необхідності покидання машини перевідача, навіть якщо він не зашифрований.

Від ідентифікації до підписів: Fiat-Shamir

Інтерактивний протокол потребує живого перевірявача, який обирає справді випадкове випробування, що незручно для підписання документу, який потрібно перевірити будь-ким пізніше без початкового довідника. Трансформація Fiat-Shamir усуває взаємодію шляхом заміни випадкового випробування перевірявача хешем коміту (і повідомлення, що підписується): c = H(t, message). Оскільки криптографічна хешна функція непередбачувана так само, як і випадковий перевірявач, це робить триступеневий протокол ідентифікації безпосередньо в схему підписів Шнорра – одну з двох схем підписання (поряд із ECDSA), стандартизованих для використання в Bitcoin та Taproot.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Zero-Knowledge Proof і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.