Dowód bezwiednej wiedzy: Protokół Identyfikacji Schnorra

Trzy kroki: komit, wyzwanie, odpowiedź

Protokół Schnorra identyfikacyjny pozwala dowodnić sprawcowładowi, że zna on sekretną liczbę x – logarytm dyskretny – bez konieczności przekazywania jej, ani też udostępniania sprawcowładowi niczego, co mógłby wykorzystać podszywający się eavesdropper do jej obliczenia. Protokół ten odbywa się w grupie cyklicznej z publicznym generatorem g o dużej liczbie pierwszej q (grupa tego samego rodzaju używana w Diffie-Hellman i DSA), a składa się dokładnie z trzech wiadomości:

rozpoczęcie: klucz publiczny y = g^x mod p (x jest sekretną liczbą sprawcowładowego) 1. komit: sprawcowładowy wybiera losową r, wysyła t = g^r mod p 2. wyzwanie: sprawcowładowi wysyła losowe c 3. odpowiedź: sprawcowładowy wysyła s = r + c*x mod q sprawcowładowi weryfikuje: g^s == t * y^c (mod p) live demo · powtarzane komity / wyzwania / odpowiedzi● LIVE Weryfikacja działa, ponieważ s = r + c*x, zatem g^s = g^r * g^(c*x) = t * (g^x)^c = t * y^c tylko wtedy, gdy sprawcowładowy rzeczywiście użył x odpowiadającego publicznemu kluczowi y. Każdy, kto nie zna x musiałby zgadywać wyzwanie c z góry, aby podszywający się mógł fałszować pasujący t – co jest możliwe jedynie z pomijalną prawdopodobieństwem 1/q, ponieważ c jest wybierane po tym, jak t został już poddany komitowi.

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)

Dlaczego jest to naprawdę zero-wiedzy

Przydatny system dowodów powinien spełniać trzy właściwości: kompletność (uczestnik, który rzeczywiście zna x, zawsze przekonuje zweryfikowanego), solidność (osoba, która nie zna x, może oszukać zweryfikowanego z pomijalnie małą prawdopodobieństwem, ponieważ podszywanie się wymaga zgadywania wyzwania przed złożeniem go) oraz zero-wiedza – transkrypt ujawnia niczego o x poza samym faktem, że uczestnik go zna. Standardowy argument dla trzeciej właściwości to symulator: mając jedynie klucz publiczny y, można wygenerować fałszywy transkrypt (t, c, s), który jest statystycznie niezróżnicowany od rzeczywistego, po prostu wybierając s i c i obliczając t = g^s / y^c w odwrotnej kolejności. Jeśli symulator bez dostępu do sekretu może produkować transkrypty niezróżnicowane od rzeczywistych, to rzeczywisty transkrypt nie może ujawniać informacji o sekrecie.

Podstawowym elementem bezpieczeństwa tego protokołu jest problem logarytmu dyskretnego

Całe bezpieczeństwo protokołu opiera się na problemie logarytmu dyskretnego: przy danym g i y = g^x mod p, znalezienie x uważane jest za obliczeniowo niemożliwe dla dobrze dobranego zbioru, mimo że sprawdzanie danego kandydata x jest trywialne. Jest to ten sam trudny problem leżący u podstaw wymiany kluczy Diffie-Hellmana i podpisów DSA/ECDSA – identyfikacja Schnorra w pewnym sensie stanowi najczystsze możliwe udowodnienie, co daje nam trudność: sposób na udowodnienie posiadania sekretu bez konieczności jego opuszczania maszyny sprawującego dowód, nawet zaszyfrowany.

Od identyfikacji do podpisów: Fiat-Shamir

Interaktywny protokół potrzebuje aktywnego weryfikatora, który losowo wybiera wyzwanie, co jest niewygodne podczas podpisywania dokumentu, który ma być weryfikowalny później przez dowolną osobę bez obecności pierwotnego sprawcy. Transformacja Fiat-Shamir eliminuje interakcję poprzez zastąpienie losowego wyzwania weryfikatora hashem (i wiadomości do podpisania): c = H(t, wiadomość). Ponieważ funkcja skrótu kryptograficznego jest nieprzewidywalna w taki sam sposób jak losowe wyzwanie weryfikatora, ten protokół identyfikacji trzech kroków przekształca się bezpośrednio w schemat podpisu Schnorr – jeden z dwóch algorytmów podpisywania (obok ECDSA) standaryzowanych do użytku w Bitcoinie i Taproot.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Zero-Knowledge Proof i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.