Intuicja ZKP: jaskinia Ali Baby

Dowód z wiedzą zerową (ZKP) pozwala dowodzącemu przekonać weryfikatora, że zna sekret (lub że dane twierdzenie jest prawdziwe), bez ujawniania samego sekretu. Ma trzy właściwości: zupełność, wiarygodność i wiedzę zerową.

Jeśli dowodzący zna sekret, zawsze może przekonać weryfikatora. Uczciwy dowodzący postępujący zgodnie z protokołem odniesie sukces z prawdopodobieństwem 1 (lub prawdopodobieństwem przytłaczająco bliskim 1). Weryfikator nie odrzuci poprawnego dowodu.

Osoba próbująca oszukiwać (która nie zna sekretu) nie może przekonać weryfikatora, z wyjątkiem sytuacji o pomijalnym prawdopodobieństwie. Każda runda interakcji zmniejsza prawdopodobieństwo oszustwa — po k rundach prawdopodobieństwo sukcesu oszusta wynosi najwyżej 2^{-k}.

Weryfikator nie dowiaduje się niczego poza tym, że dane twierdzenie jest prawdziwe. Formalnie: istnieje symulator, który bez znajomości sekretu tworzy transkrypt nieodróżnialny od rzeczywistej interakcji dowodzącego z weryfikatorem. Weryfikator nie uzyskuje żadnej dodatkowej wiedzy.

Jaskinia ma okrężny korytarz z magicznymi drzwiami pośrodku. Dowodząca (Alicja) twierdzi, że zna hasło. Weryfikator (Bob) czeka na zewnątrz. Alicja wchodzi i wybiera lewą albo prawą stronę. Bob woła, z której strony ma wyjść. Jeśli Alicja zna hasło, zawsze wychodzi właściwą stroną. Prawdopodobieństwo oszustwa w każdej rundzie wynosi 1/2.

Po 20 rundach oszust odnosi sukces z prawdopodobieństwem 2^{-20} ≈ 1 na milion. Alicja (która zna hasło) odnosi sukces za każdym razem. Bob nigdy nie poznaje hasła — widzi tylko, że Alicja wychodzi wskazaną stroną. To właśnie jest wiedza zerowa.

Interaktywne ZKP wymagają wymiany komunikatów między dowodzącym a weryfikatorem. Nieinteraktywne ZKP (NIZK) używają transformacji Fiat-Shamira: losowe wyzwanie weryfikatora zastępuje się haszem zobowiązania (hash = losowa wyrocznia). Powstaje pojedynczy ciąg dowodu, który każdy może zweryfikować.

ZKP jest dowodem znajomości (PoK), jeśli strategia dowodzącego oznacza, że mógłby on wyodrębnić sekret. Jest to silniejsza własność niż samo dowiedzenie prawdziwości twierdzenia. Podpisy ECDSA i Schnorra są nieinteraktywnymi dowodami znajomości klucza prywatnego.

Uwierzytelnianie za pomocą hasła bez przesyłania hasła. Weryfikacja wieku bez ujawniania daty urodzenia. Dowody zakresu (wynagrodzenie mieści się w określonym zakresie) bez ujawniania wynagrodzenia. Blockchain: dowód znajomości prawidłowej transakcji bez ujawniania transakcji.

Perfekcyjna wiedza zerowa: wynik symulatora jest identyczny z rzeczywistym transkryptem. Statystyczna wiedza zerowa: transkrypty są nierozróżnialne poza pomijalnym prawdopodobieństwem. Obliczeniowa wiedza zerowa: transkrypty są nierozróżnialne dla weryfikatorów działających w czasie wielomianowym. Słabsze gwarancje oznaczają wydajniejsze dowody.

Jaskinia jest protokołem składającym się z 3 etapów: zobowiązanie → wyzwanie → odpowiedź. Formalnie nazywa się to protokołem Sigma. Większość praktycznych ZKP (Schnorr, Pedersen, Fiat-Shamir) to protokoły Sigma lub ich kompozycje. Nazwa pochodzi od kształtu Σ diagramu przepływu komunikatów.

ZKP pozwalają udowodnić znajomość sekretu bez jego ujawniania. Trzy właściwości to: zupełność, solidność i wiedza zerowa. Jaskinia Ali Baby ilustruje interaktywny ZKP. Dalej: protokoły Sigma i identyfikacja Schnorra.