Rozwidlony lemat

Lemat rozwidlenia jest jednym z wielu powiązanych lematów w badaniach kryptograficznych . Lemat stwierdza, że ​​jeśli przeciwnik (zwykle probabilistyczna maszyna Turinga ), na danych wejściowych pobranych z pewnego rozkładu , daje wynik, który ma pewną właściwość z nie pomijalnym prawdopodobieństwem , to z nie pomijalnym prawdopodobieństwem, jeśli przeciwnik jest ponownie uruchamiany na nowe wejścia, ale z tą samą losową taśmą, jego drugie wyjście również będzie miało tę właściwość.

Koncepcja ta została po raz pierwszy zastosowana przez Davida Pointchevala i Jacquesa Sterna w „Dowodach bezpieczeństwa dla schematów podpisów”, opublikowanych w materiałach Eurocrypt 1996. W ich artykule lemat forking jest określony w kategoriach przeciwnika, który atakuje schemat podpisu cyfrowego utworzony w losowy model wyroczni . Pokazują one, że jeśli przeciwnik może sfałszować podpis z nie do pominięcia prawdopodobieństwem, to istnieje nie do pominięcia prawdopodobieństwo, że ten sam przeciwnik z tą samą przypadkową taśmą może stworzyć drugie fałszerstwo w ataku z inną losową wyrocznią. Lemat rozwidlenia został później uogólniony przez Mihira Bellare'a i Gregory'ego Nevena. Forking lemat został wykorzystany i dalej uogólniony, aby udowodnić bezpieczeństwo różnych schematów podpisów cyfrowych i innych konstrukcji kryptograficznych opartych na losowych wyroczniach.

Stwierdzenie lematu

Uogólniona wersja lematu jest przedstawiona w następujący sposób. Niech A będzie algorytmem probabilistycznym z danymi wejściowymi ( x , h ₁ , ..., h _q ; r ), który daje na wyjściu parę ( J , y ), gdzie r odnosi się do losowej taśmy A (to znaczy losowych wyborów zrobi). Załóżmy dalej, że IG jest rozkładem prawdopodobieństwa, z którego rysuje się x , a H jest zbiorem o rozmiarze h , z którego każda z wartości h _i jest rysowana zgodnie z rozkładem jednostajnym . Niech acc będzie prawdopodobieństwem, że przy danych wejściowych rozłożonych zgodnie z opisem, J przez A jest większe lub równe 1.

Możemy wtedy zdefiniować „algorytm rozwidlenia” F _{A , który na wejściu} x postępuje w następujący sposób :

1. Wybierz losową taśmę r dla A .
2. Wybierz h ₁ , ..., h _q równomiernie z H .
3. Uruchom A na wejściu ( x , h ₁ , ..., h _q ; r ), aby wyprodukować ( J , y ).
4. Jeśli J = 0, to zwróć (0, 0, 0).
5. Wybierz h' _J , ..., h' _q równomiernie z H .
6. Uruchom A na wejściu ( x , h ₁ , ..., h _{J −1} , h ' _J , ..., h ' _q ; r ) w celu wytworzenia ( J ', y ').
7. Jeśli J' = J i h _J ≠ h' _J to zwróć (1, y , y '), w przeciwnym razie zwróć (0, 0, 0).

Niech frk będzie prawdopodobieństwem, że F _A wygeneruje potrójną liczbę zaczynającą się od 1, mając dane wejściowe x wybrane losowo z IG . Następnie

${\ Displaystyle {\ tekst {frk}} \ geq {\ tekst {acc}} \ cdot \ lewo ({\ Frac {\ tekst {acc}}} {q}} - {\ Frac {1} {h}} \ Prawidłowy).}$

Intuicja

Chodzi o to, aby myśleć o A jako uruchomionym dwa razy w powiązanych wykonaniach, w których proces „ rozwidla się ” w pewnym momencie, kiedy zbadano część, ale nie wszystkie dane wejściowe. W wersji alternatywnej pozostałe wejścia są regenerowane, ale generowane są w normalny sposób. Punkt, w którym proces rozwidla się, może być czymś, o czym chcemy zdecydować dopiero później, prawdopodobnie na podstawie zachowania A za pierwszym razem: dlatego instrukcja lematu wybiera punkt rozgałęzienia ( J ) na podstawie danych wyjściowych A . Wymóg, że h _J ≠ h' _J jest technicznym wymogiem wielu zastosowań lematu. (Zauważ, że ponieważ zarówno h _J, jak i h' _J są wybierane losowo z H , to jeśli h jest duże, jak to zwykle bywa, prawdopodobieństwo, że te dwie wartości nie będą różne, jest bardzo małe.)

Przykład

Na przykład niech A będzie algorytmem łamania schematu podpisu cyfrowego w losowym modelu wyroczni . Wtedy x byłoby parametrami publicznymi (w tym kluczem publicznym), które A atakuje, a h _i byłoby wyjściem losowej wyroczni na jej i- tym odrębnym wejściu. Lemat rozwidlenia jest przydatny, gdy przy dwóch różnych losowych sygnaturach tej samej wiadomości byłoby możliwe rozwiązanie jakiegoś podstawowego trudnego problemu. Jednak przeciwnik, który sfałszuje raz, rodzi przeciwnika, który sfałszuje dwukrotnie tę samą wiadomość z niemałym prawdopodobieństwem dzięki lematowi rozwidlenia. Kiedy A próbuje sfałszować wiadomość m , uważamy, że wynikiem A jest ( J , y ), gdzie y jest fałszerstwem, a J jest takie, że m było J -tym unikalnym zapytaniem skierowanym do losowej wyroczni (można założyć, że że A zapyta m w pewnym momencie, jeśli A ma odnieść sukces z dużym prawdopodobieństwem). (Jeśli A wyprowadza nieprawidłowe fałszerstwo, uważamy, że wynik to (0, y ).)

Zgodnie z lematem rozwidlenia prawdopodobieństwo ( frk ) uzyskania dwóch dobrych fałszerstw y i y' w tej samej wiadomości, ale z różnymi losowymi wynikami wyroczni (to znaczy z h _J ≠ h' _J ) jest nie do pominięcia, gdy acc jest również nie -nieistotny. To pozwala nam udowodnić, że jeśli leżący u podstaw trudny problem jest rzeczywiście trudny, to żaden przeciwnik nie może sfałszować podpisów.

To jest istota dowodu podanego przez Pointchevala i Sterna dla zmodyfikowanego schematu podpisu ElGamala przeciwko adaptacyjnemu przeciwnikowi.

Znane problemy z zastosowaniem lematu rozwidlenia

Redukcja zapewniona przez lemat o rozwidleniu nie jest ścisła. Pointcheval i Stern zaproponowali argumenty bezpieczeństwa dla podpisów cyfrowych i podpisu w ciemno za pomocą lematu rozwidlenia. Claus P. Schnorr przeprowadził atak na ślepe schematy podpisów Schnorra, z więcej niż $zbadany$ . Atak w czasie wielomianowym dla $egzekucji$ został pokazany w 2020 roku przez Benhamoudę, Lepointa, Raykovą Schnorr zasugerował również ulepszenia do zabezpieczania schematów ślepych podpisów opartych na problemie logarytmu dyskretnego .