Schemat identyfikacji Feige – Fiat – Shamir

W kryptografii schemat identyfikacji Feige -Fiat-Shamir jest rodzajem równoległego dowodu z wiedzą zerową, opracowanego przez Uriela Feige , Amosa Fiata i Adi Shamira w 1988 roku. udowodnić innej stronie, Weryfikatorowi, że posiadają tajne informacje bez ujawniania Weryfikatorowi, czym są te tajne informacje. Schemat identyfikacji Feige-Fiat-Shamir wykorzystuje jednak arytmetykę modułową i równoległy proces weryfikacji, który ogranicza liczbę komunikacji między Prover i Verifier.

Organizować coś

Zgodnie z ogólną konwencją , wezwij weryfikatora Peggy i weryfikatora Victora.

Wybierz dwie duże liczby pierwsze p i q i oblicz iloczyn n = pq . Twórz tajne liczby ${\ Displaystyle s_ {1}, \ cdots, s_ {k}}$ względnie pierwsze do n . Oblicz ${\ Displaystyle v_ {i} \ równoważnik s_ {i} ^ {2} {\ pmod {n}}}$ . $w$ i Victor otrzymują, $gdy$ i $.$ utrzymywane tajemnicy Następnie Peggy otrzymuje liczby ${\ displaystyle s_ {i}}$ . To są jej tajne numery logowania. Victor otrzymuje numery $,$ kiedy chce się przedstawić Victorowi. Victor nie jest w $stanie$ odzyskać liczb Peggy'ego $gdy$ z trudności w określeniu modułowego pierwiastka kwadratowego, faktoryzacja modułu jest nieznana.

Procedura

1. ${\ Displaystyle s \ cdot x \ równoważnik r ^ {2} {\ pmod {n}}}$ wybiera losową liczbę całkowitą ${$ losowy znak ${\ Displaystyle s \ in \ {-1,1 \}}$ i oblicza . Peggy wysyła $Victora$ .
2. $\ Displaystyle a_ {i}}$ wybiera liczby $się$ { equals 0 or 1. Victor sends these numbers to Peggy.
3. Peggy oblicza ${\ Displaystyle y \ równoważnik rs_ {1} ^ {a_ {1}} s_ {2} ^ {a_ {2}} \cdots s_{k}^{a_{k}}{\pmod {n}}}$ . Peggy wysyła ten numer do Victora.
4. Victor sprawdza, czy ${\ Displaystyle y ^ {2} {\ pmod {n}} \ równoważnik \ pm \, xv_{1}^{a_{1}}v_{2}^{a_{2}}\cdots v_{k}^{a_{k}}{\pmod {n}}} i$ że ${ \displaystyle x\neq 0.}$

Ta procedura jest powtarzana z różnymi $i$ aż jest przekonany, że Peggy rzeczywiście posiada modułowe pierwiastki kwadratowe ( ) $z$$r}$ displaystyle jego liczby. ${\ displaystyle v_ {i}}$

Bezpieczeństwo

W ramach procedury Peggy nie przekazuje Victorowi żadnych użytecznych informacji. Po prostu udowadnia Victorowi, że ma tajne liczby, nie ujawniając, jakie to liczby. Każdy, kto przechwyciłby komunikację między Peggy i Victorem, dowiedziałby się tylko tych samych informacji. Podsłuchujący nie dowiedziałby się niczego przydatnego o tajnych numerach Peggy.

$wie,$ że Eve przechwyciła liczby Victora, $są liczby$ jakie . Jeśli Ewa chce spróbować przekonać Victora $,$ że ​​jest Peggy, musiałaby poprawnie odgadnąć, jakie będą liczby Następnie wybiera losowo $,$$\ Displaystyle x \ równoważnik y ^ {2} v_ { 1} ^ {-a_ {1}} v_ {2} ^ {-a_ {2}} \ cdots v_ {k} ^ {-a_ {k}} {\ pmod {n}}} i wysyła x$ x { $Displaystyle x}$ do Wiktora. Kiedy Victor wysyła $po$ prostu $zwraca$ . Victor jest zadowolony i dochodzi do wniosku, że Ewa ma tajne numery. Jednak prawdopodobieństwo, że Ewa poprawnie odgadnie, jaki będzie Victor, $do$ 2 $\ displaystyle 2 ^ {k}}$ . Powtarzając procedurę $,$ prawdopodobieństwo spada do 1 w ${\ displaystyle 2 ^ {kt}}$ . Dla $displaystyle k = 5}$$\$ prawdopodobieństwo pomyślnego udawania Peggy jest mniejsze niż 1 na 1

•   Feige, Uriel; Fiat, Amos; Szamir, Adi (1988). „Dowody tożsamości o zerowej wiedzy” . Dziennik kryptologii . 1 (2): 77–94. doi : 10.1007/BF02351717 . S2CID 2950602 .
•   Trappe, Wade; Waszyngton, Lawrence C. (2003). Wprowadzenie do kryptografii z teorią kodowania . Upper Saddle River: Prentice-Hall. s. 231 –233. ISBN 0-13-061814-4 .
• Wong, Chung Kei; Lam, Simon S (sierpień 1999). „Podpisy cyfrowe dla przepływów i multiemisji” (PDF) . Transakcje IEEE/ACM w sieci . 7 (4). (eFFS, rozszerzony schemat Feige – Fiat – Shamir)