20463 Str079
154 4 Kio ck publicme
kroki 1-3 w dowodzie o zerowej wiedzy znajomości Inga rytmu dyskretnego?
2. Przypuśćmy, że w dowodzie o zerowej wiedzy znajomości logarytmu dyskretnego Stefan nic zna wartości N.
(a) Wyjaśnij, dlaczego protokół opisany w tekście nie jest całkowicie dowodem „zerowej wiedzy”.
(b) W jaki sposób może Urszula zmniejszyć ilość otrzymywanych przez Stefana informacji dotyczących wielkości liczby NI
3. Przypuśćmy, że Urszula nic zna liczby N, a więc w kroku 1 wybiera losową liczbę c z jakiegoś innego przedziału (np. e < Bt gdzie B jest ograniczeniem górnym możliwych wartości N)% a w kroku 3 wysyła po prostu liczbę x -ł- e, a nic jej resztę z dzielenia przez N. Wyjaśnij, dlaczego nie jest to dowód o zerowej wiedzy. Dlaczego ta procedura przeprowadzona przez Cezarego nie jest poprawną symulacją?
4. Wyjaśnij, w jaki sposób podany w tekście dowód o zerowej wiedzy znajomości logarytmu dyskretnego może być użyty do elektronicznego potwierdzania tożsamości. (Oznacza to, że Urszula ma przekonać Stefana, że rzeczywiście jest Urszulą.)
5. Wyjaśnij, dlaczego umiejętność wyciągania pierwiastków kwadratowych modulo n = pq jest w zasadzie równoważna znajomości rozkładu liczby n na czynniki.
6. Czy ten sam klucz (/?l5 P2) dla przekazów nierozróżnialnych może być użyty przez wiele różnych osób, które chcą przekazać Stefanowi dowód o zerowej wiedzy tego, że wszystkie one niezależnie od siebie znają ten sam rozkład na czynniki? Załóż, że każda osoba może podsłuchiwać transmisję innych osób.
7. Wykorzystując przekazy nierozróżnialnc, skonstruuj nieinterakcyjny dowód o zerowej wiedzy znajomości logarytmu dyskretnego. (Załóż, że rząd N grupy jest każdemu znany.)
8. Ostatnio zaproponowano następujący schemat protokołu o zerowej wiedzy, za pomocą którego Urszula może wykazać Stefanowi, że zna dzielniki p i q liczby n, o której wiadomo, że jest iloczynem dwóch liczb pierwszych przystających do 3 modulo 4. Znajdź zasadniczy błąd w tym schemacie.
Krok 1. Stefan, który zna liczbę n, ale nie zna jej czynników p i q, wybiera losowo liczbę całkowitą x. Oblicza następnie resztę z dzielenia przez n - oznaczmy ją przez y - i wysyła Urszuli tę resztę.
Krok 2. Kiedy Urszula otrzyma y, oblicza pierwiastek kwadratowy modulo n (co jest łatwe, gdyż zna ona rozkład liczby n na czynniki, por. ćwiczenie 5 powyżej). Spośród czterech możliwych pierwiastków wybiera ten jedyny, który jest resztą kwadratową modulo p i modulo q. Musi on być resztą z dzielenia x2 przez n. Wtedy wysyła ona ten pierwiastek Stefanowi.
Krok 3. Stefan sprawdza, że liczba, którą otrzymał od Urszuli jest rzeczywiście resztą z dzielenia x2 przez n. Jest wtedy przekonany o tym, że potrafi ona wyciągać pierwiastki kwadratowe modulo n, co byłoby niemożliwe, gdyby nie znała rozkładu n na czynniki.
9. Znajdź wadę następującej procedury dla dowodu o zerowej wiedzy znajomości rozkładu na czynniki. Załóżmy, że liczba n jest iloczynem dwóch liczb pierwszych p i q. Załóżmy, że obdarzone zaufaniem „Centrum” dostarcza nieograniczony ciąg losowo wybranych kwadratów modulo n, tak jak w tekście: yv yz, .... Dla każdej kolejnej liczby y, Urszula znajduje jeden z jej pierwiastków kwadratowych x, i wysyła go Stefanowi, który sprawdza, że x] & y (mod ń).
Bibliografia
1. Bcllarc M.f Micali S.: Non-interaclive oblivious transfer and applieatfons. Adamus in Cryjh tology - Crypto '89, Springer-Verlag, s. 547-557.
2. Bcn-Or M., Goldrcich O., Goldwasser S., Histad Kilian i., Mieaii S., Rogaway P: Everyt-hing provable is provable m zero-knowledge. Adamus in Cryptology - Crypto 88, Springer--Verlag 1990, s. 37-56.
3. Blum M., Feldman P., Micali S.: Non-interaclive zero-knowledge proofs and their appiica-tions. Proc. 20th ACM Symp. Theory of Computing, 1988.
4. Chaum D., Everlse J.-Mvan de Graaf J., Pcralla R.: Demcnstraiing possession of a discrcle logarilhm witbout rcvealing ii, Adamus in Cryptology - Crypto 86, Springer- Verlag 1987, s. 200-212.
5. Garey M.R., Johnson D.J.: Computers and Intractabilily: A Guide 10 the Theory of NP-Comp-leteness. W. H. Frecman 1979.
6. Goldwasser S., Micali S., RackofT C.: The knowledge compleriiy of interaclive proof systems. SIAM J. Computing, 1989,18, s. 186-208.
7. Kilian J.: Foundrag cryplography on oblivious transfer. Proc. 20th ACM Symp. Theory of Computing, 1988, s. 20-31
8. Rabin M.: How to exchange secrets by oblivious transfer. Technical Report TR-81, Aiken Compulational Laboratory, Harvard Universily 1981.
9. Shamir A.: The research for provably secure idenliiication schemes. Proc. Intern. Cong. Maik, 1986, s. 1488-1495.
Wyszukiwarka
Podobne podstrony:
154 WSPÓŁPRACA Z JEDNOSTKAMI PUBLICZNYMI • przygotowywanie, w oparciu o analizę
stawiają politykom dziennikarze w programach publicystycznych, dowodząc, że ich wiedza na temat prze
skanowanie0008 3 154 ancMuawMw Jfrtf podejmowaniu decyzji o tym. kto powinien, kio sU nie powinien t
stawiają politykom dziennikarze w programach publicystycznych, dowodząc, że ich wiedza na temat prze
Informator Urzędu Zamówień Publicznych nr 6/2014> Uwzględnienie skargi Prezesa UZP na wyrok KIO 1
35 Administracja publiczna. Wojskowość KONFERENCJA NAUKOWA "AUTOMATYZACJA DOWODZENIA" NT.
Zasad ta określona jest w art. 7 „w toku postępowania organy administracji publicznej podejmuję wsze
zasada prawdy obiektywnej również wynika z art.7 organy administracji publicznej podejmują wszelkie
stawiają politykom dziennikarze w programach publicystycznych, dowodząc, że ich wiedza na temat prze
stawiają politykom dziennikarze w programach publicystycznych, dowodząc, że ich wiedza na temat prze
stawiają politykom dziennikarze w programach publicystycznych, dowodząc, że ich wiedza na temat prze
więcej podobnych podstron