Heurystyka Fiata-Shamira

W kryptografii heurystyka Fiata -Shamira to technika pobierania interaktywnego dowodu wiedzy i tworzenia na jego podstawie podpisu cyfrowego . W ten sposób niektóre fakty (na przykład znajomość pewnego tajnego numeru) mogą zostać publicznie udowodnione bez ujawniania informacji leżących u ich podstaw. Technika ta pochodzi od Amosa Fiata i Adi Shamira (1986). Aby metoda działała, oryginalny dowód interaktywny musi mieć właściwość public-coin , tj. losowe monety weryfikatora są upubliczniane w całym protokole dowodu.

Heurystyka została pierwotnie przedstawiona bez dowodu bezpieczeństwa; później Pointcheval i Stern udowodnili swoje bezpieczeństwo przed atakami wybranych wiadomości w modelu losowej wyroczni , to znaczy przy założeniu istnienia losowych wyroczni . Wynik ten został uogólniony na dostępną kwantowo losową wyrocznię (QROM) przez Dona, Fehra, Majenza i Schaffnera, a jednocześnie przez Liu i Zhandry'ego. W przypadku, gdy nie istnieją losowe wyrocznie, Shafi Goldwasser i Yael Tauman Kalai udowodnili, że heurystyka Fiata-Shamira jest niepewna . Heurystyka Fiata-Shamira pokazuje zatem główne zastosowanie losowych wyroczni. Mówiąc bardziej ogólnie, heurystykę Fiata-Shamira można również postrzegać jako przekształcanie interaktywnego dowodu wiedzy monety publicznej w nieinteraktywny dowód wiedzy . Jeśli dowód interaktywny jest używany jako narzędzie identyfikacyjne, wersja nieinteraktywna może być używana bezpośrednio jako podpis cyfrowy, wykorzystując wiadomość jako część danych wejściowych do losowej wyroczni.

Przykład

W przypadku algorytmu określonego poniżej czytelnicy powinni znać grupy multiplikatywne ${\ Displaystyle \ mathbb {Z} _ {q} ^ {*}}$ , gdzie q jest liczbą pierwszą, oraz twierdzenie Eulera o totientie Eulera funkcja φ .

Oto interaktywny dowód znajomości logarytmu $w$ o Schnorra . Wartości publiczne to y $\ Displaystyle y \ w \ mathbb {Z} _ {q} ^ {*}}$ i generator g ${\ Displaystyle \ mathbb {Z} _ {q} ^ {*}}$ , podczas gdy tajną wartością jest logarytm dyskretny y do podstawy g .

$.$ udowodnić Victorowi, $,$ $że$ wie satysfakcjonująca bez
Wybiera losowo , oblicza i wysyła ${v}} v$ $_ {q} ^ {*}$ $} \displaystyle t}$ } do Victora.
Victor wybiera $go$ do
Peggy oblicza ${\ Displaystyle r = v-cx {\ bmod {\ varphi}} (q)}$ $zwraca$ Victorowi .
Sprawdza, czy ${\ Displaystyle t \ równoważnik g ^ {r} y ^ {c}}$ . sol ${\ Displaystyle g ^ {r} y ^ {c} \ równoważnik g ^ {v-cx} g ^ {xc} \$ i ${\ Displaystyle g ^ {\ varphi (q)} \ równoważnik 1}$ .

Heurystyka Fiata-Shamira pozwala zastąpić interaktywny krok 3 nieinteraktywnym losowym dostępem do wyroczni . W praktyce zamiast tego możemy użyć kryptograficznej funkcji skrótu .

$,$ udowodnić $,$ tak $ujawniania$ bez _
Wybiera losowo i oblicza ${Z} _ {q} ^ {*$ $}$ } .
do ${\ Displaystyle c = H (g, y, t)}$ gdzie $kryptograficzną$ funkcją skrótu.
Oblicza ${\ Displaystyle r = v-cx {\ bmod {\ varphi}} (q)}$ . Wynikowym dowodem jest para ${\ displaystyle (t, r)}$ .
$displaystyle t \ równoważnik g ^ {r} y ^ {c}}$ dowodu do obliczenia i sprawdzenia, czy $\$ .

Jeśli użyta poniżej wartość skrótu nie zależy od (publicznej) wartości y , bezpieczeństwo schematu jest osłabione, ponieważ złośliwy dowodzący może wtedy wybrać określoną wartość y , aby produkt cx był znany.

Rozszerzenie tej metody

Tak długo, jak można zbudować stały generator losowy z danymi znanymi obu stronom, każdy interaktywny protokół można przekształcić w nieinteraktywny. ^{[ potrzebne źródło ]}

Zobacz też

Bibliografia _ Szamir, Adi (1987). „Jak się sprawdzić: praktyczne rozwiązania problemów z identyfikacją i podpisem” . Postępy w kryptologii — CRYPTO” 86 . Notatki z wykładów z informatyki. Springer Berlin Heidelberg. 263 : 186–194. doi : 10.1007/3-540-47721-7_12 . ISBN 978-3-540-18047-0 .
^ Pointcheval, Dawid; Stern, Jacques (1996). „Dowody bezpieczeństwa dla schematów podpisów” . Postępy w kryptologii — EUROCRYPT '96 . Notatki z wykładów z informatyki. Springer Berlin Heidelberg. 1070 : 387–398. doi : 10.1007/3-540-68339-9_33 . ISBN 978-3-540-61186-8 .
^ Don, Jelle; Fehr, Serge; Majenz, chrześcijanin; Schaffner, Christian (2019). „Bezpieczeństwo transformacji Fiata-Shamira w kwantowym modelu losowej wyroczni”. Postępy w kryptologii — CRYPTO '19 . Notatki z wykładów z informatyki. Springer Cham. 11693 : 356–383. ar Xiv : 1902.07556 . Bibcode : 2019arXiv190207556D . doi : 10.1007/978-3-030-26951-7_13 . ISBN 978-3-030-26950-0 . S2CID 67769879 .
Bibliografia _ Zhandry, Mark (2019). „Ponowna wizyta w post-kwantowym Fiat-Shamir”. Postępy w kryptologii — CRYPTO '19 . Notatki z wykładów z informatyki. Springer Cham. 11693 : 326–355. doi : 10.1007/978-3-030-26951-7_12 . ISBN 978-3-030-26950-0 . S2CID 75135227 .
Bibliografia _ Kalai, YT (październik 2003). „O (nie) bezpieczeństwie paradygmatu Fiata-Shamira”. 44. doroczne sympozjum IEEE na temat podstaw informatyki, 2003. Materiały. : 102–113. doi : 10.1109/SFCS.2003.1238185 . ISBN 0-7695-2040-5 . S2CID 295289 .
Bibliografia _ Stadler, Markus (1997). „Systemy dowodowe dla ogólnych stwierdzeń dotyczących logarytmów dyskretnych” (PDF) . Wydział Informatyki, ETH Zurich . Zarchiwizowane od oryginału (PDF) w dniu 2020-08-17.
Bibliografia _ Rogaway, Phillip (1995). „Losowe wyrocznie są praktyczne: paradygmat projektowania wydajnych protokołów”. Prasa ACM: 62–73. CiteSeerX 10.1.1.50.3345 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
^ Bernhard, Dawid; Pereira, Olivier; Warinschi, Bogdan. „Jak się nie udowodnić: pułapki heurystyki Fiata-Shamira i zastosowania do Heliosa” (PDF) . W Wang, Xiaoyun; Sako, Kazue (red.). Postępy w kryptologii – ASIACRYPT 2012 . s. 626–643.

[1] Bibliografia _ Szamir, Adi (1987). „Jak się sprawdzić: praktyczne rozwiązania problemów z identyfikacją i podpisem” . Postępy w kryptologii — CRYPTO” 86 . Notatki z wykładów z informatyki. Springer Berlin Heidelberg. 263 : 186–194. doi : 10.1007/3-540-47721-7_12 . ISBN 978-3-540-18047-0 .

[2] Pointcheval, Dawid; Stern, Jacques (1996). „Dowody bezpieczeństwa dla schematów podpisów” . Postępy w kryptologii — EUROCRYPT '96 . Notatki z wykładów z informatyki. Springer Berlin Heidelberg. 1070 : 387–398. doi : 10.1007/3-540-68339-9_33 . ISBN 978-3-540-61186-8 .

[3] Don, Jelle; Fehr, Serge; Majenz, chrześcijanin; Schaffner, Christian (2019). „Bezpieczeństwo transformacji Fiata-Shamira w kwantowym modelu losowej wyroczni”. Postępy w kryptologii — CRYPTO '19 . Notatki z wykładów z informatyki. Springer Cham. 11693 : 356–383. ar Xiv : 1902.07556 . Bibcode : 2019arXiv190207556D . doi : 10.1007/978-3-030-26951-7_13 . ISBN 978-3-030-26950-0 . S2CID 67769879 .

[4] Bibliografia _ Zhandry, Mark (2019). „Ponowna wizyta w post-kwantowym Fiat-Shamir”. Postępy w kryptologii — CRYPTO '19 . Notatki z wykładów z informatyki. Springer Cham. 11693 : 326–355. doi : 10.1007/978-3-030-26951-7_12 . ISBN 978-3-030-26950-0 . S2CID 75135227 .

[5] Bibliografia _ Kalai, YT (październik 2003). „O (nie) bezpieczeństwie paradygmatu Fiata-Shamira”. 44. doroczne sympozjum IEEE na temat podstaw informatyki, 2003. Materiały. : 102–113. doi : 10.1109/SFCS.2003.1238185 . ISBN 0-7695-2040-5 . S2CID 295289 .

[6] Bibliografia _ Stadler, Markus (1997). „Systemy dowodowe dla ogólnych stwierdzeń dotyczących logarytmów dyskretnych” (PDF) . Wydział Informatyki, ETH Zurich . Zarchiwizowane od oryginału (PDF) w dniu 2020-08-17.

[7] Bibliografia _ Rogaway, Phillip (1995). „Losowe wyrocznie są praktyczne: paradygmat projektowania wydajnych protokołów”. Prasa ACM: 62–73. CiteSeerX 10.1.1.50.3345 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )

[8] Bernhard, Dawid; Pereira, Olivier; Warinschi, Bogdan. „Jak się nie udowodnić: pułapki heurystyki Fiata-Shamira i zastosowania do Heliosa” (PDF) . W Wang, Xiaoyun; Sako, Kazue (red.). Postępy w kryptologii – ASIACRYPT 2012 . s. 626–643.