Protokoły Sigma i identyfikacja Schnorra

Protokół Sigma składa się z 3 komunikatów: (1) Zobowiązanie: dowodzący wysyła zobowiązanie do losowej wartości. (2) Wyzwanie: weryfikator wysyła losowe wyzwanie. (3) Odpowiedź: dowodzący wysyła odpowiedź obliczoną na podstawie wyzwania i sekretu. Weryfikator akceptuje dowód albo go odrzuca.

Dowodzący zna sekret x (klucz prywatny); klucz publiczny = g^x mod p (lub punkt X = x*G na krzywej eliptycznej). Celem jest udowodnienie znajomości x bez jego ujawniania. Jest to dowód znajomości logarytmu dyskretnego.

(1) Dowodzący wybiera losowe r i wysyła zobowiązanie R = r*G. (2) Weryfikator wysyła wyzwanie c (losową liczbę całkowitą). (3) Dowodzący wysyła odpowiedź s = r + c*x. (4) Weryfikator sprawdza, czy s*G == R + c*X. Jeśli tak, akceptuje dowód. Dowodzący zna x; odpowiedź s można obliczyć wyłącznie znając x.

Zupełność: uczciwy dowodzący zawsze spełnia s*G = r*G + c*x*G = R + c*X. Solidność: dwa transkrypty z tym samym R, ale różnymi wyzwaniami c i c', dają s i s', z których można odzyskać x = (s-s')/(c-c') — oszust nie może więc utworzyć dwóch poprawnych odpowiedzi dla tego samego R.

Symulator (nieznający x): wybiera losowe s i c, a następnie ustawia R = s*G - c*X. (R, c, s) ma rozkład poprawnego transkryptu. Weryfikator nie może odróżnić rzeczywistych transkryptów od symulowanych — protokół Schnorra zapewnia wiedzę zerową względem uczciwego weryfikatora.

Aby uczynić protokół Schnorra nieinteraktywnym, należy zastąpić wyzwanie weryfikatora wartością c = Hash(R || message). Dowodzący sam oblicza c i wysyła odpowiedź. W rezultacie powstaje dwuelementowy dowód (R, s), który każdy może zweryfikować. Jest to schemat podpisu Schnorra.

Sign(x, m): r ← losowe; R = r*G; c = Hash(R||m); s = r + c*x. Podpis = (R, s). Verify: s*G == R + Hash(R||m)*X. Kompaktowe (64 bajty dla P-256), możliwe do weryfikacji wsadowej i uzasadnione bezpieczeństwem w ROM. Zastosowane w Bitcoin Taproot (BIP-340).

C = r*G + v*H, gdzie H jest drugim niezależnym generatorem. Zobowiązanie do wartości v z użyciem losowości r. Wiążące: nie można otworzyć zobowiązania dla innej wartości v (logarytm dyskretny). Ukrywające: C ma rozkład jednostajny. Stosowane w opartych na Schnorrze dowodach zakresu i w Bulletproofs.

Jednoczesne udowodnienie znajomości x1 AND x2: należy uruchomić dwa protokoły Schnorra z tym samym wyzwaniem (współdzielić wyzwanie za pomocą Fiat-Shamir). Weryfikator akceptuje dowód tylko wtedy, gdy oba poddowody są poprawne. Umożliwia to udowadnianie wielu twierdzeń w ramach jednej interakcji.

Udowodnienie znajomości x1 OR x2 bez ujawniania, którego sekretu dotyczy dowód: należy użyć symulatora dla jednej gałęzi, aby obliczyć fałszywy transkrypt, a następnie podzielić wyzwanie między obie gałęzie. Weryfikator widzi dwa wiarygodnie wyglądające transkrypty, których suma daje rzeczywiste wyzwanie. Nazywa się to „podpisami pierścieniowymi”.

Identyfikacja Schnorra: elektroniczne paszporty (protokół PACE). Podpisy Schnorra: Bitcoin Taproot, Monero (RingCT używa dowodów OR Schnorra), Signal Protocol (uzgadnianie kluczy X3DH). Zobowiązania Pedersena: Confidential Transactions, Bulletproofs, szyfrowanie notatek Sapling w Zcash.

Co weryfikator sprawdza w ostatnim kroku protokołu identyfikacji Schnorra?

Protokoły Sigma: zobowiązanie–wyzwanie–odpowiedź. Schnorr pozwala udowodnić znajomość logarytmu dyskretnego. Fiat-Shamir czyni protokół nieinteraktywnym (podpis Schnorra). Dalej: zk-SNARK, czyli zwarte nieinteraktywne dowody.