SKS 2022 cvicenie tyzden 11

Zhrnutie prednášky

Cvičenie sa venuje Zero Knowledge protokolom (ZKP), v ktorých Peggy (prover) presviedča Viktora (verifier), že pozná diskrétny logaritmus x z hodnoty y pri báze g, bez toho, aby x prezradila. Protokol musí byť úplný (completeness) a odolný voči podvodom (soundness). Triviálny protokol s priamym odoslaním x spĺňa obe vlastnosti, ale nie je zero knowledge. Protokol 2 so zamaskovaním x náhodným k je zero knowledge, no nie je sound, pretože Peggy vie zvoliť s a dopočítať r bez znalosti x. Oprava spočíva v interaktivite: Peggy sa najprv zaviaže hodnotou r, Viktor pošle náhodnú výzvu c a až potom Peggy vypočíta s. Vzniká Schnorrov identifikačný protokol, ktorý je zero knowledge len pri poctivom Viktorovi, patrí medzi sigma protokoly a jeho nevýhodou je interaktivita. Na začiatku lektor oznámil, že skúška bude prezenčná formou pero-papier, a presun konzultácie.

• - Zero Knowledge Proof umožňuje dokázať znalosť tajomstva x bez jeho prezradenia.
• - Požiadavky na protokol: úplnosť (poctivý prover je vždy akceptovaný) a soundness (podvodník uspeje len s malou pravdepodobnosťou).
• - Protokol 2 (maskovanie x pomocou k) nie je sound, lebo Peggy môže zvoliť s a dopočítať r = g^s · y^(-1).
• - Schnorrov identifikačný protokol: záväzok r = g^k, výzva c od Viktora, odpoveď s = k + c·x, overenie g^s = y^c · r.
• - Schnorrov protokol je zero knowledge len pri poctivom Viktorovi, ktorý volí c náhodne.
• - Ide o sigma protokol (záväzok, výzva, odpoveď); jeho nevýhodou je interaktivita, ktorá je v praxi nepraktická.
• - Skúška z predmetu bude prezenčná, písomná formou pero-papier.

Zhrnutie pripravené s pomocou AI z prepisu videa.