Kryptografia II stopień

Pogłębienie B. Rewinding i forking lemma

Dwa dowody, jedna idea algebraiczna. W identyfikacji ekstraktor sam wysyła drugie wyzwanie po odtworzeniu stanu dowodzącego. W podpisie wyzwanie jest odpowiedzią hasza. Redukcja musi więc ponownie uruchomić fałszerza ze zmienioną wyrocznią i doprowadzić do drugiego fałszerstwa dotyczącego tego samego zobowiązania. To dodatkowe wymaganie ma mierzalny koszt.

Najpierw ustalimy funkcjonalność i model, potem zbudujemy algorytm redukcji. Każdą stratę prawdopodobieństwa policzymy oddzielnie. Symbol $\bot$ oznacza niepowodzenie, $\Pr[E]$ prawdopodobieństwo zdarzenia $E$, a $\mathbb E[Z]$ wartość oczekiwaną zmiennej $Z$, czyli średnią ważoną prawdopodobieństwami jej wyników. Wszystkie eksperymenty są klasyczne. Nie obejmują kwantowych zapytań do wyroczni. Przeciwnicy mają jawny limit czasu, wielomianowy względem parametru bezpieczeństwa.

Identyfikacja Schnorra: pełny dowód z cofaniem przebiegu

1. Co dokładnie ma zapewniać schemat?

Publiczna grupa $G=\langle g\rangle$ ma pierwszy rząd $q$. Jej działanie zapisujemy multiplikatywnie. Sekret to $a\in\mathbb Z_q$, a klucz publiczny to $A=g^a$. Parametry $pp$ obejmują grupę, generator, rząd i jednoznaczne kodowania. Skalary dodajemy i mnożymy modulo $q$. Odbiorca sprawdza typy, przynależność do grupy i zakresy skalarów przed użyciem równania.

Schemat to krotka $\Pi_{\mathrm{ID}}=(\mathsf{Setup},\mathsf{KeyGen},P,V)$. Dwa ostatnie algorytmy są interaktywne. Ich kroki i stan prywatny są zdefiniowane w formalnym opisie Schnorra. Przypomnijmy interfejsy potrzebne w dowodzie:

Poprawność. Uczciwy dowodzący zawsze przechodzi test, ponieważ

Cel bezpieczeństwa. Przeciwnik ma przekonać uczciwego weryfikatora bez znajomości $a$. Nie definiujemy porażki jako samego braku dostępu do algorytmu Respond. Przeciwnik może wykonywać dowolne obliczenia. Wygraną jest rzeczywista akceptacja jego odpowiedzi.

Rozważamy podszywanie po pasywnym treningu. Przeciwnik otrzymuje $pp,A$ i może żądać wielomianowo wielu niezależnych transkryptów uczciwych sesji. Liczbę żądań i moment zakończenia treningu może dobierać adaptacyjnie. W końcowej sesji sam wysyła $X$, otrzymuje świeże jednostajne $c$ i odpowiada $s$. Nie ma wtedy dostępu do żywego uczciwego dowodzącego. Nie dostaje nonce ani klucza prywatnego. Nie zakładamy bezpieczeństwa wobec przekazywania wyzwania równolegle prawdziwemu użytkownikowi.

2. Symulator transkryptów nie potrzebuje sekretu

Symulator $\mathsf{Sim}(pp,A)$ losuje niezależnie $c,s\overset{\$}{\leftarrow}\mathbb Z_q$, oblicza $X=g^s\cdot A^{-c}$ i zwraca $(X,c,s)$. Weryfikacja akceptuje. Ważniejsze jest jednak to, że rozkład całej trójki jest identyczny z uczciwym przebiegiem, a nie jedynie to, że równanie się zgadza.

Uczciwy przebieg wybiera $(u,c)$ z prawdopodobieństwem $1/q^2$. Dla ustalonego klucza odwzorowanie

jest bijekcją na $\mathbb Z_q^2$. Jego odwrotność to $u=s-a\cdot c$. Każdy dopuszczalny transkrypt ma więc w obu doświadczeniach prawdopodobieństwo $1/q^2$. To doskonała wiedza zerowa wobec uczciwego weryfikatora, czyli perfect honest-verifier zero knowledge. Symulator wybiera wyzwanie. Ten argument nie daje mu możliwości narzucania wyzwań złośliwemu weryfikatorowi w aktywnych sesjach.

Redukcja otrzymuje instancję problemu logarytmu dyskretnego $(pp,A)$ i odpowiada na każde żądanie treningowe nowym wynikiem Sim. Nie zna $a$, ale nie traci na symulacji żadnego prawdopodobieństwa. Przez indukcję po adaptacyjnych żądaniach cały widok przeciwnika ma właściwy rozkład.

3. Dwa transkrypty wydobywają ten sam sekret

Niech $P^*$ oznacza program podszywającego się przeciwnika. Ekstraktor uruchamia go z ustaloną taśmą losową, symuluje trening i zapamiętuje stan $v$ po wysłaniu $X$, przed otrzymaniem $c$. Taśma zawiera również bity, które program wykorzysta dopiero później. Po jej ustaleniu odpowiedź programu na konkretne wyzwanie jest deterministyczna. Przekroczenie limitu czasu lub brak odpowiedzi oznacza odrzucenie.

Ekstraktor $\mathsf{ExtractID}^{P^*}(pp,A)$ wykonuje następujące czynności:

1. Uruchamia trening i pierwszą część końcowej sesji. Jeśli nie uzyska poprawnego $X$, zwraca $\bot$.
2. Zapamiętuje $v$. Losuje $c\overset{\$}{\leftarrow}\mathbb Z_q$, otrzymuje $s$ i sprawdza Check. Przy odrzuceniu zwraca $\bot$.
3. Przywraca ten sam stan i taśmę. Losuje niezależnie $c'\overset{\$}{\leftarrow}\mathbb Z_q$ i otrzymuje $s'$. Sprawdza Check i $c'\ne c$. Inaczej zwraca $\bot$.
4. Oblicza $\widehat a=(s-s')\cdot(c-c')^{-1}\pmod q$. Sprawdza $g^{\widehat a}=A$ i zwraca $\widehat a$.

Z dwóch akceptacji wynika kolejno

Ostatni krok jest legalny, bo $q$ jest pierwsze, a $c-c'$ nie jest zerem w $\mathbb Z_q$. W szczególności nie wystarczą dwa dowolne poprawne przebiegi. Muszą mieć ten sam klucz i to samo zobowiązanie oraz różne wyzwania. Ta własność nazywa się special soundness, czyli ekstrakcją świadka z dwóch akceptujących transkryptów o wspólnym pierwszym komunikacie.

Przykład liczbowy. W małej grupie $G=\langle2\rangle\subset\mathbb Z_{47}^*$ rzędu $23$ weźmy $a=7$, więc $A=34$. Dla $u=9$ mamy $X=42$. Wyzwania $c=4$ i $c'=12$ dają odpowiedzi $s=14$ i $s'=1$. Oba testy akceptują, a ekstraktor otrzymuje

Mała grupa służy sprawdzeniu rachunku, nie bezpieczeństwu. Cofanie jest uprawnieniem redukcji uruchamiającej kod przeciwnika. Nie zakładamy, że zewnętrzny napastnik może cofać uczciwe urządzenie. Jeżeli urządzenie rzeczywiście powtórzy nonce w dwóch sesjach, ten sam rachunek staje się atakiem na jego sekret.

4. Dokładne prawdopodobieństwo ekstrakcji

Dla ustalonego stanu $v$ niech $k_v$ oznacza liczbę wyzwań, na które $P^*$ odpowiada poprawnie. Wtedy $p_v=k_v/q$ jest warunkowym prawdopodobieństwem akceptacji. Gdy program nie dotarł do poprawnego zobowiązania, przyjmujemy $k_v=0$. Dwa niezależne wyzwania tworzą $q^2$ jednakowo prawdopodobnych par. Dokładnie $k_v\cdot(k_v-1)$ par daje dwie akceptacje z różnymi wyzwaniami. Zatem

Niech $\epsilon=\mathbb E[p_v]$ będzie prawdopodobieństwem podszycia. Uśredniamy po treningu i losowości przeciwnika. Nieujemność wariancji daje $\mathbb E[p_v^2]\ge(\mathbb E[p_v])^2$, stąd pełny rachunek:

Twierdzenie ID. Jeśli istnieje przeciwnik odnoszący sukces $\epsilon$ w opisanym modelu pasywnym, istnieje redukcja do logarytmu dyskretnego o sukcesie co najmniej $\max\{0,\epsilon\cdot(\epsilon-1/q)\}$. Potrzebuje najwyżej dwóch wykonań przeciwnika, dokładnej symulacji treningu oraz ekstrakcji. Gdy $q$ rośnie wykładniczo z parametrem bezpieczeństwa, nieznikomy sukces podszycia daje nieznikomy sukces rozwiązania logarytmu dyskretnego. To sprzeczne z założeniem jego trudności.

Dlaczego nie możemy usunąć $1/q$? Bez sekretu można przygotować odpowiedź na jedno przewidziane wyzwanie $c_0$. Wybieramy $s_0$, ustalamy $X=g^{s_0}\cdot A^{-c_0}$ i odpowiadamy tylko, gdy $c=c_0$. Dla niezerowego klucza daje to sukces $1/q$, ale nie dwa różne akceptujące wyzwania. Liczba $1/q$ to knowledge error, czyli próg błędu wiedzy. Nie oznacza prawdopodobieństwa wycieku klucza.

Jeżeli dolna granica sukcesu jednej niezależnej próby na ustalonym kluczu wynosi $b>0$, to po $r$ próbach prawdopodobieństwo niepowodzenia jest najwyżej $(1-b)^r\le e^{-r\cdot b}$. Oczekiwana liczba prób do sukcesu jest najwyżej $1/b$. Nie wolno wyprowadzać takiej granicy oczekiwanego czasu dla każdego klucza wyłącznie ze średniego sukcesu po losowych kluczach. Rachunek jednej próby pozostaje poprawny również po uśrednieniu po kluczu, z ponownym użyciem nieujemnej wariancji.

Podpis Schnorra: pełna redukcja niepodrabialności

1. Krotka algorytmów i granice twierdzenia

Schemat podpisu to $\Pi_{\mathrm{Sig}}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Sign},\mathsf{Verify})$. Setup ustala $pp=(G,q,g,\operatorname{enc})$ oraz dziedzinę wyroczni skalarnej $\mathcal H:\{0,1\}^*\to\mathbb Z_q$. Funkcja enc jest jednoznaczna. Stały znacznik domeny $\mathtt{Schnorr}$ oddziela ten schemat od innych zastosowań hasza.

Poprawność wynika z tego samego równania co w identyfikacji. Diagram uczciwego podpisywania znajduje się przy definicji schematu. Teraz badamy, czy przeciwnik może uzyskać akceptację dla nowej wiadomości.

Eksperyment EUF-CMA, czyli existential unforgeability under chosen-message attack, bada egzystencjalną niepodrabialność przy adaptacyjnie wybieranych wiadomościach. Przeciwnik $\mathcal A$ otrzymuje $pp,A$. Ma najwyżej $Q_H\ge1$ zapytań do Hash i $Q_S$ żądań Sign. Prowadzimy zbiór $M_S$ wiadomości przekazanych do Sign. Wygrywa, gdy zwróci $(m^*,X^*,s^*)$ takie, że $m^*\notin M_S$ i Verify zwraca 1. Nowy podpis wcześniej podpisanej wiadomości nie jest wygraną tego eksperymentu.

Najpierw ustalamy $A\ne1_G$. Nie zmieniamy po cichu wcześniejszego KeyGen. Przy losowaniu $a$ z całego ciała zdarzenie $A=1_G$ ma prawdopodobieństwo $1/q$. W takim kluczu $a=0$ jest jawne i każdy może podpisywać. Jeśli $\epsilon_{\mathrm{all}}$ jest sukcesem dla całego KeyGen, a $\epsilon$ sukcesem warunkowym dla $A\ne1_G$, to

Dalsze twierdzenie dotyczy tego niezerowego profilu. Przy KeyGen losującym od początku z $\mathbb Z_q^*$ powyższej korekty nie potrzeba. Zerowy klucz nie psuje algebraicznej ekstrakcji w identyfikacji, bo jego logarytm wynosi po prostu zero. Ma jednak znaczenie dla poniższego oszacowania zgadywania hasza.

2. Redukcja dostaje trudny klucz i symuluje podpisującego

Redukcja $\mathcal B$ otrzymuje instancję DL, czyli discrete logarithm, problemu logarytmu dyskretnego $(pp,A)$, bez $a$. Przekazuje $A$ przeciwnikowi. Utrzymuje jedną początkowo pustą tabelę $T$ wejść hasza, wartości i ich pochodzenia. Zbiór zapisanych wejść oznaczamy przez $\operatorname{dom}T$. Pochodzenie jest informacją wewnętrzną redukcji. Przeciwnik go nie widzi.

Symulator nie nadpisuje wcześniejszego hasza, nawet jeżeli jego wylosowane $c$ przypadkiem zgadza się z wpisem. Przerwanie jest świadomym uproszczeniem redukcji. Nie jest zachowaniem uczciwego podpisującego. Wpis programowany przez SimSign nie zużywa pozycji taśmy $h_1,\ldots,h_{Q_H}$. Późniejszy odczyt tego wpisu przez Hash też jej nie zużywa.

3. Dlaczego symulacja wygląda jak prawdziwe podpisy?

Gdy $t$ jest świeże, prawdziwy Sign wybiera jednostajne $(u,c)$ i oblicza $s=u+a\cdot c$. SimSign wybiera jednostajne $(s,c)$. Bijekcja z dowodu identyfikacji daje identyczny rozkład $(X,c,s)$. Redukcja nie musi znać $u$ ani $a$, aby wytworzyć ten rozkład.

Pozostaje konflikt z wcześniejszą tabelą. Przy $j$-tym żądaniu podpisu jest w niej najwyżej $Q_H+j-1$ wpisów. Dla ustalonego $c$ skalar $s-a\cdot c$ jest jednostajny, więc $X$ jest jednostajne na $G$. Każdy wcześniejszy wpis dotyczący tego samego $A,m$ wyklucza najwyżej jedno z $q$ zobowiązań. Warunkowe prawdopodobieństwo pierwszego konfliktu jest najwyżej $(Q_H+j-1)/q$. Sumujemy po żądaniach:

Nie zakładamy niezależności konfliktów. To nierówność sumy prawdopodobieństw. Sprzęgamy oba eksperymenty tak, aby do pierwszego konfliktu dawały te same transkrypty. Ich wyniki mogą się różnić tylko po konflikcie. Sukces symulowanego przeciwnika jest zatem co najmniej $\epsilon-\delta_S$. Jest to przykład argumentu „identyczne do bad” w metodzie gier.

4. Wybierz sukces, którego hasz można rozwinąć ponownie

Jeżeli przeciwnik nie zapytał Hash o $t^*=\operatorname{enc}(\mathtt{Schnorr},A,X^*,m^*)$, to tego wpisu nie mogła też utworzyć Sign. Wiadomość $m^*$ jest świeża. Weryfikacja losuje wtedy nowy, niezależny skalar. Dla ustalonych $A\ne1_G,X^*,s^*$ równanie akceptacji dopuszcza dokładnie jedno $c$, ponieważ $A$ ma rząd $q$. Sukces bez wcześniejszego pytania ma więc prawdopodobieństwo najwyżej $1/q$.

Niech $\eta$ oznacza rzeczywisty sukces po symulacji, ograniczony do fałszerstw z takim wcześniejszym pytaniem. Dostajemy

Procedura $\mathsf{Run}(pp,A,\rho,h_1,\ldots,h_{Q_H})$ odtwarza cały ten eksperyment. $\rho$ zawiera taśmę przeciwnika i prywatne losowania SimSign. Przy odpowiednim sukcesie Run zwraca $(I,m^*,X^*,s^*)$, gdzie $I$ jest indeksem pierwszego zapytania Hash tworzącego wpis $t^*$. Inaczej zwraca $(0,\bot)$. Jeżeli wpisu brakuje, Run odrzuca wynik bez dodatkowego losowania hasza. Ta klasa sukcesów została już odjęta w oszacowaniu $\epsilon_0$. Brakujące odpowiedzi do długości $Q_H$ dopełniamy niewykorzystanymi niezależnymi skalarami.

5. Rozwidlenie musi odtworzyć stan, nie tylko zmienić c

Algorytm $\mathsf{Fork}$ wykonuje dokładnie następujący eksperyment:

1. Losuje $\rho$ i niezależne $h_1,\ldots,h_{Q_H}\overset{\$}{\leftarrow}\mathbb Z_q$. Wywołuje Run. Jeśli $I=0$, zwraca $\bot$.
2. Zachowuje $\rho$ oraz $h_1,\ldots,h_{I-1}$. Losuje niezależny sufiks $h'_I,\ldots,h'_{Q_H}$.
3. Uruchamia Run od początku z tymi danymi. Dostaje $(I',m',X',s')$ albo porażkę. Każdy wpis tabeli powstaje ponownie podczas wykonania. Wpisów z pierwszego sufiksu nie kopiuje.
4. Wymaga $I'=I\ne0$ i $h'_I\ne h_I$. Obie gałęzie muszą spełniać warunki poprawności i świeżości. Inaczej zwraca $\bot$.
5. Zwraca $\widehat a=(s^*-s')\cdot(h_I-h'_I)^{-1}\pmod q$, po sprawdzeniu $g^{\widehat a}=A$.

Dlaczego wiadomość i zobowiązanie są te same? Do chwili wysłania pytania numer $I$ program widzi identyczny klucz, losowość, odpowiedzi i symulowane podpisy. Jest deterministyczny po ustaleniu tych danych. Wysyła więc identyczne $t^*$. Jednoznaczność enc ustala te same $A,X^*,m^*$. Jeżeli drugie fałszerstwo wskazuje również indeks $I$, dotyczy właśnie tego wejścia. Nie jest potrzebne założenie, że reszta obu wykonań pozostanie identyczna.

Czego nie wolno dopowiedzieć? Druga gałąź może przestać odnosić sukces, przerwać symulację podpisu albo oprzeć fałszerstwo na innym pytaniu. Nie wolno przyjąć, że zmiana jednego wyzwania automatycznie zachowuje sukces. Tę trudność rozwiązuje poniższy rachunek.

Lemat o rozwidleniu: dowód, nie tylko gotowy wzór

Udowodnimy wersję o dwóch wykonaniach. To współczesna postać z Bellarego–Nevena, Lemma 1, wyrażająca precyzyjnie ideę Pointchevala–Sterna. Historyczny harmonogram z ich oryginalnymi stałymi wyprowadzimy osobno. W tej części $Q$ jest liczbą pozycji odpowiedzi, a $h$ rozmiarem alfabetu wyzwań. Dla naszego Schnorra $Q=Q_H$ i $h=q$.

1. Warunkowanie po wspólnym prefiksie

Dla pozycji $i$ niech $v$ obejmuje publiczne wejście, całą taśmę $\rho$ i odpowiedzi $h_1,\ldots,h_{i-1}$. Definiujemy

Prawdopodobieństwo $p_i(v)$ dotyczy dolosowania całego sufiksu od $i$. Jeśli program w tym prefiksie nie może odnieść sukcesu z indeksem $i$, wartość wynosi zero. Sumowanie po wszystkich prefiksach nadal jest poprawne. Zdarzenia wskazania różnych indeksów są rozłączne, dlatego $\sum_{i=1}^Q\mu_i=\eta$.

2. Policz dwa sukcesy o wspólnym indeksie

Przy ustalonym $v$ pierwszy i drugi sufiks są niezależne. Dwa sukcesy z indeksem $i$ mają prawdopodobieństwo $p_i(v)^2$. Nie twierdzimy, że sukcesy są niezależne bez warunkowania. Wspólny prefiks właśnie je wiąże. Zatem

Nieujemna wariancja daje $\mathbb E[Z^2]\ge(\mathbb E[Z])^2$. Nierówność Cauchy'ego–Schwarza daje $(\sum_i\mu_i)^2\le Q\cdot\sum_i\mu_i^2$. Stosując je kolejno, otrzymujemy

3. Usuń pary z równym wyzwaniem

Po dowolnym pierwszym sukcesie nowe $h'_I$ jest jednostajne i niezależne od całego pierwszego wykonania. Powtórzy $h_I$ z prawdopodobieństwem $1/h$. Zdarzenie „pierwszy sukces i równe wyzwania” ma więc prawdopodobieństwo $\eta/h$. Jego usunięcie może zabrać najwyżej tyle par sukcesów. Ostatecznie

To kończy dowód lematu. Kwadrat pochodzi z dwóch sufiksów. Dzielenie przez $Q$ pochodzi z rozdzielenia sukcesów między indeksy. Odjęcie $\eta/h$ usuwa równe wyzwania. Nie mnożymy wyniku ponownie przez $1/Q$. Indeks odczytujemy z pierwszego fałszerstwa, a cena zgodności indeksów została już policzona.

4. Wstaw wszystkie straty i zakończ redukcję Schnorra

Dwa sukcesy lematu mają to samo $X^*,m^*$ i różne $c,c'$. Algebraiczna ekstrakcja z identyfikacji daje więc dokładnie $a$. Pełne twierdzenie przyjmuje postać

Podstawienie dolnego oszacowania jest legalne. Funkcja $f(x)=\max\{0,x^2/Q_H-x/q\}$ jest zerowa dla $0\le x\le Q_H/q$, a następnie rosnąca. Dla nieznikomego $\epsilon$, wielomianowych budżetów i wykładniczo dużego $q$ otrzymujemy nieznikomy sukces DL. To dowodzi EUF-CMA w zadeklarowanym klasycznym modelu wyroczni losowej, ROM, czyli random oracle model, pod założeniem trudności DL.

Koszt. Oznaczmy przez $T_{\mathrm{run}}$ ograniczenie czasu całego Run, łącznie z symulacją. Jeśli samo wykonanie kodu przeciwnika kosztuje najwyżej $T_{\mathcal A}$, to można przyjąć

$T_{\mathrm{exp}}$ ogranicza potęgowanie w $G$, a $T_{\mathrm{mul}}$ iloczyn grupowy. $T_{\mathrm{enc}}$ obejmuje kodowanie wejścia podpisu, $T_{\mathrm{tab}}$ wszystkie operacje tabel, losowania i księgowanie, a $T_{\mathrm{test}}$ końcowe sprawdzenie fałszerstwa. Odpowiednie koszty uwzględniają długości wiadomości. Redukcja zużywa najwyżej $2T_{\mathrm{run}}+T_{\mathrm{extract}}$. Ekstrakcja obejmuje odejmowania i odwrotność w $\mathbb Z_q$ oraz jedno potęgowanie kontrolne. Nie ma pairingu.

Granica nie obejmuje wycieku nonce, resetowania uczciwego podpisującego ani pairingowych modyfikacji protokołu. Zamiana idealnej wyroczni na konkretny hash jest etapem instancjacji, nie twierdzeniem, że każda funkcja skrótu dziedziczy ten dowód.

Poniższy kalkulator używa ogólnego alfabetu $h=2^k$ i podanego już sukcesu $\epsilon_0$ po odjęciu strat symulacji. Nie oblicza $\delta_S$ za użytkownika. W dokładnym rachunku dla naszego skalarnego hasza alfabet ma rozmiar $h=q$, a nie dowolnie zaokrągloną potęgę dwójki.

Pointcheval–Stern: skąd biorą się wszystkie stałe?

Powyższy dowód daje ograniczony czas jednej próby. Teraz prześledzimy historyczny harmonogram wielu prób z §3.1 pracy Security Arguments for Digital Signatures and Blind Signatures. To inny algorytm, więc jego stałej $84480$ nie wstawiamy do poprzedniej granicy prawdopodobieństwa.

Ustalamy publiczne wejście i maszynę atakującą bez wyroczni podpisującej. Jej sukces wynosi $\epsilon$, liczba pytań jest najwyżej $Q\ge1$, a czas jednego wykonania najwyżej $T$. Alfabet odpowiedzi ma $h$ elementów. Oryginał posługuje się $h=2^k$. Dla kursowego Schnorra stosujemy $h=q$. Potrzebujemy założenia, że sukces bez istotnego pytania ma prawdopodobieństwo najwyżej $1/h$. Dla $A\ne1_G$ i skalarnych wyzwań wynika ono z równania weryfikacji.

Przekład oznaczeń. Pointcheval i Stern zapisują klucz publiczny jako $y=g^{-x}$ i sprawdzają $r=g^s\cdot y^e$. Nasze oznaczenia to $a=x$, $A=y^{-1}$, $X=r$ i $c=e$. Wtedy ten sam test przyjmuje postać $g^s=X\cdot A^c$. Rachunek poniżej dotyczy jawnie podanego alfabetu wyzwań. Nie zakładamy, że redukowanie dowolnego ciągu bitów modulo $q$ zawsze daje jednostajny skalar.

1. Próg 7 i klasy sukcesów

Zakładamy $\epsilon\ge7Q/h$. Niech $S$ będzie zdarzeniem sukcesu z zadanym istotnym pytaniem, a $S_i$ sukcesu z indeksem $i$. Oznaczmy $\nu=\Pr[S]$. Wtedy

Klasa jest ciężka, jeśli $\Pr[S_i\mid S]\ge1/(2Q)$. Lekkich klas jest najwyżej $Q$, więc ich łączna masa warunkowa jest najwyżej $1/2$. Co najmniej połowa sukcesów trafia do ciężkich klas. Każda ciężka klasa ma bezwarunkową masę co najmniej $\nu/(2Q)$.

2. Splitting lemma: dobry prefiks istnieje z policzalną częstością

W ciężkiej klasie nazwijmy prefiks dobrym, gdy $p_i(v)\ge\nu/(4Q)$. Symbol $\mathbf1_E$ oznacza wskaźnik zdarzenia. Ma wartość 1, gdy $E$ zachodzi, a 0 w przeciwnym przypadku. Masa sukcesów tej klasy pochodzących ze złych prefiksów wynosi

Cała klasa ma masę co najmniej $\nu/(2Q)$, więc najwyżej połowa jej sukcesów pochodzi ze złych prefiksów. Po znalezieniu sukcesu prawdopodobieństwo jednoczesnego trafienia ciężkiej klasy i dobrego prefiksu jest co najmniej $(1/2)\cdot(1/2)=1/4$. Jest to konkretne zastosowanie splitting lemma, czyli lematu o podziale przestrzeni wykonań na dobre prefiksy i ich kontynuacje. Nie wymaga niezależności dwóch tych zdarzeń. Drugie oszacowanie jest warunkowe w każdej ciężkiej klasie.

Z dobrego prefiksu prawdopodobieństwo użytecznej drugiej gałęzi jest co najmniej

3. Znane epsilon: 2, 14, 16 oraz 1/9

Wykonujemy do $\lceil2/\epsilon\rceil$ niezależnych prób znalezienia pierwszego sukcesu. Szansa znalezienia go jest co najmniej $1-e^{-2\nu/\epsilon}\ge1-e^{-12/7}>4/5$. Pierwszy znaleziony sukces ma rozkład wykonania warunkowany przez $S$, więc z prawdopodobieństwem co najmniej $1/4$ daje dobry prefiks.

Z tego prefiksu wykonujemy do $\lceil14Q/\epsilon\rceil$ niezależnych kontynuacji. Użyteczna druga gałąź pojawi się z prawdopodobieństwem co najmniej $1-e^{-1}>3/5$. Cały eksperyment odnosi sukces z prawdopodobieństwem większym niż

Planowana liczba wykonań spełnia

To pochodzenie stałych z Lemma 2. Autorzy zapisują budżet bez jawnego narzutu zaokrągleń. Dla rzeczywistej całkowitej liczby wywołań zachowujemy powyższe dwa sufity. Nie nazywamy $16Q/\epsilon$ dokładną liczbą uruchomień programu.

4. Nieznane epsilon: harmonogram adaptacyjny

Redukcja nie zna $\epsilon$ ani $\nu$. W etapie $j=0,1,\ldots$ wykonuje nowe niezależne próby do pierwszego sukcesu w $S$. Niech $N_j$ będzie ich liczbą. Następnie wykonuje najwyżej $\lfloor140N_j\cdot\alpha^j\rfloor$ kontynuacji uzyskanego prefiksu, gdzie $\alpha=8/7$. Zatrzymuje się po użytecznym rozwidleniu. Inaczej przechodzi do następnego etapu. Używamy podłogi, aby budżet był całkowity i nie przekraczał wskazanej wartości.

$N_j$ ma rozkład geometryczny o średniej $1/\nu$. Czas oczekiwania i uzyskany pierwszy sukces są niezależne. Dla dowolnego podzbioru $E\subseteq S$ zachodzi bowiem

Ponadto $\Pr[N_j<1/(5\nu)]\le1/5$. Wystarczy zsumować prawdopodobieństwa sukcesu w mniej niż $1/(5\nu)$ pierwszych próbach. Zatem $\Pr[N_j\ge1/(5\nu)]\ge4/5\ge3/4$. Ostatnie, słabsze oszacowanie zachowujemy, aby odtworzyć stałe autorów.

Niech $\ell=\lceil\log_\alpha Q\rceil$. Dla $j\ge\ell$ i $N_j\ge1/(5\nu)$ liczba kontynuacji jest większa niż $28Q/\nu-1$. Prawdopodobieństwo użytecznej kontynuacji dobrego prefiksu jest co najmniej $\nu/(12Q)$, ponieważ

Iloczyn liczby kontynuacji i dolnej granicy sukcesu jest większy niż

Uwzględniliśmy więc również podłogę w budżecie. Prawdopodobieństwo znalezienia drugiej gałęzi jest większe niż $1-e^{-2}>6/7$. Od etapu $\ell$ szansa sukcesu etapu jest co najmniej $(1/4)\cdot(3/4)\cdot(6/7)=9/56>1/7$. Przyjmujemy zachowawczo $\gamma=6/7$ jako górną granicę porażki etapu.

5. Oczekiwany koszt i liczba 84480

Niech $R_j$ oznacza zdarzenie dotarcia do etapu $j$. Dla $j<\ell$ używamy granicy $\Pr[R_j]\le1$, a dla $j\ge\ell$ granicy $\Pr[R_j]\le\gamma^{j-\ell}$. Koszt rozpoczętego etapu to najwyżej $N_j+140N_j\cdot\alpha^j\le141N_j\cdot\alpha^j$. Jego świeże próby są niezależne od wcześniejszych etapów. Dlatego dla łącznej liczby wykonań $N$:

Nie warunkujemy średniej $N_j$ przez przyszły moment zakończenia całego algorytmu. Takie warunkowanie mogłoby zmienić rozkład czasu oczekiwania. Sumujemy koszt tylko z prawdopodobieństwem rozpoczęcia etapu.

Aby uzyskać historyczną stałą, osłabiamy oszacowanie, zastępując $\alpha^j$ większą wartością $\alpha^{j+1}/(\alpha-1)$. Używamy też $141/\nu\le(141\cdot7/6)/\epsilon<165/\epsilon$. Rozdzielenie sumy na etapy przed $\ell$ i po nim daje

Pierwszy składnik pochodzi z ograniczenia skończonej sumy geometrycznej. Drugi pochodzi z ogona $\sum_{t\ge0}(\alpha\cdot\gamma)^t$. Teraz każde podstawienie jest jawne:

Otrzymujemy

Jeżeli $T$ obejmuje koszt pojedynczego wykonania z obsługą wyroczni i kontrolą sukcesu, czas uzyskania rozwidlenia ma wartość oczekiwaną najwyżej $84480\cdot Q\cdot T/\epsilon$. Dla redukcji do DL dodajemy jednorazowy koszt ekstrakcji. Harmonogram kończy się z prawdopodobieństwem 1, bo jego ogon maleje geometrycznie. To luźna granica z konkretnego harmonogramu, a nie dolna granica pracy atakującego ani pomiar wydajności podpisu.

Zastosowanie do naszej symulacji podpisów. Run jest jednym programem probabilistycznym. Symulator Sign stanowi jego część, a nie dodatkową zewnętrzną wyrocznię. Dla ustalonego klucza jego sukces wynosi $\eta$, z dolnym oszacowaniem $\epsilon_0$. Każdy sukces Run ma istotny indeks. Jeżeli dla tego klucza $\epsilon_0\ge7Q_H/q$, ten sam rachunek etapów daje

Do mianownika nie wolno wstawić sukcesu przed odjęciem strat symulacji. Nie wolno też zamienić warunku dla ustalonego klucza na samą średnią po kluczach. Bez takich dodatkowych warunków używamy wcześniejszego twierdzenia o ograniczonym czasie i sukcesie jednej próby.

Co wnosi sposób dowodzenia Herranza–Sáeza?

W podpisie pierścieniowym istotne może być $n$ różnych pytań. Herranz i Sáez grupują sukcesy według uporządkowanego wzorca ich indeksów, a rozwidlenie wykonują przy najpóźniejszym z nich. Liczba możliwych wzorców wynosi

Ten wybór zachowuje wcześniejsze zobowiązania i odpowiedzi, a zmienia jedno wyzwanie potrzebne ekstrakcji. W zwykłym Schnorrze $n=1$ i $V_{Q,1}=Q$. Dokładnie to zrobiliśmy: wskazaliśmy istotny indeks, zachowaliśmy jego prefiks, sprawdziliśmy zgodność obu sukcesów i dopiero potem odjęliśmy równania. Nie dodajemy sztucznego czynnika $1/n$ do dowodu dla jednego klucza.

W Theorem 1 pracy Herranza–Sáeza historyczny koszt ma postać $84480\cdot V_{Q,n}\cdot T/\epsilon$. W ich Theorem 2, dla konkretnej symulacji chosen-message, straty zostawiają co najmniej $7\epsilon/12$. Zastąpienie $\epsilon$ tą wartością daje $84480\cdot12/7=144822{,}857\ldots$, więc zaokrąglona w górę stała wynosi $144823$. Pełny rachunek pierścieniowy wyjaśnia oddzielnie warunki i straty tamtej symulacji. Nie przenosimy $7/12$ do naszego SimSign. Jego rzeczywisty koszt prawdopodobieństwa to policzone wyżej $\delta_S$.

Co student powinien umieć sprawdzić samodzielnie?

1. Wskazać instancję trudnego problemu i dane, których redukcja nie zna.
2. Wykazać zgodność rozkładu odpowiedzi symulatora, nie tylko ich poprawność.
3. Określić stan cofnięcia oraz losowość zachowaną i losowaną ponownie.
4. Uzasadnić, że z dwóch sukcesów powstają zgodne równania z niezerowym mianownikiem.
5. Przypisać każdej stracie prawdopodobieństwa konkretne zdarzenie.
6. Odróżnić bezpieczeństwo identyfikacji w modelu pasywnym, EUF-CMA podpisu w ROM i koszt oczekiwany historycznego harmonogramu.

References

• C.-P. Schnorr, Efficient Signature Generation by Smart Cards, Journal of Cryptology 4, 1991. Publikacja.
• D. Pointcheval, J. Stern, Security Arguments for Digital Signatures and Blind Signatures, Journal of Cryptology 13, 2000, s. 361–396. Pełna wersja pracy Security Proofs for Signature Schemes z EUROCRYPT 1996. §2.3: splitting lemma. §3.1: Lemma 2 i Theorem 1 z rachunkiem stałych. Tekst autorów.
• J. Herranz, G. Sáez, Forking Lemmas in the Ring Signatures' Scenario, 2003. §3: wzorce indeksów i oba warianty lematu. IACR ePrint 2003/067.
• M. Bellare, G. Neven, Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma, ACM CCS 2006. §3, Lemma 1: dwukrotne wykonanie i granica $\eta^2/Q-\eta/h$. Tekst autorów.

Herranz–Sáez: pełny dowód anonimowości transkryptu

Punktem wyjścia jest rzeczywisty algorytm podpisywania, nie sam rysunek podobnych podpisów. Ustalamy pierścień $L$, wiadomość $m$ i całą funkcję $\mathcal H$. W tym dowodzie hasz nie musi być wyrocznią losową. Porównujemy tylko rozkłady wywołane uczciwą losowością podpisujących.

Eksperyment. Przeciwnik wskazuje dwóch użytkowników w pierścieniu $j_0,j_1$. Eksperyment losuje bit $b\overset{\$}{\leftarrow}\{0,1\}$ i zwraca $\operatorname{Sign}_{j_b}(m)$. Przeciwnik zgaduje $b$. Nie dostaje faktycznie użytej taśmy losowej ani danych z kanałów bocznych. Pokażemy, że rozkład publicznego podpisu nie zależy od $b$, nawet przy nieograniczonych obliczeniach.

Krok 1. Ustal dowolny możliwy publiczny wynik

Niech $\sigma=(R_1,\ldots,R_n,z)$ będzie podpisem akceptowanym w zadeklarowanym profilu, z różnymi $R_i\ne1_G$. Jest

możliwych uporządkowanych wektorów zobowiązań. Dla każdego takiego wektora wszystkie hasze są ustalone. Równanie weryfikacji wyznacza dokładnie jeden $z\in\mathbb Z_q$, ponieważ $z\mapsto g^z$ jest bijekcją. To stwierdzenie o jednoznaczności, nie algorytm obliczania DL.

Krok 2. Policz pozostałe n − 1 pozycji

Dla podpisującego $j$ każda pozycja poza $j$ jest losowana bez zwracania spośród niezerowych skalarów. Potęgowanie przenosi ten rozkład bijektywnie na niejednostkowe punkty. Prawdopodobieństwo dokładnie ustalonych $R_i$ dla $i\ne j$ wynosi

Dla $n=1$ iloczyn pusty wynosi jeden. Nie ma wtedy anonimowości między różnymi osobami, ale rachunek nadal opisuje poprawnie algorytm.

Krok 3. Uwzględnij odrzucenia, zamiast udawać losowanie bez ograniczeń

Po ustaleniu innych pozycji wyrażenie $\prod_{i\ne j}A_i^{-c_i}$ jest stałe. Odwzorowanie $u\mapsto R_j$ jest bijekcją z $\mathbb Z_q$ na $G$. Każda próba daje więc jednostajny punkt. Odrzucamy dokładnie $n$ punktów: element neutralny oraz $n-1$ wcześniejszych zobowiązań.

Dla dowolnego dozwolonego $R_j$ prawdopodobieństwo otrzymania go po dowolnej liczbie odrzuceń to

Nie jest to $1/q$. Średnia liczba prób wynosi $q/(q-n)$. Potrzebujemy $n<q$. W rzeczywistych parametrach pierścień jest nieporównanie mniejszy od rzędu grupy.

Krok 4. Połącz prawdopodobieństwa i przejdź do gry

Odpowiedź $z$ jest już jednoznaczna. Nie pojawia się dodatkowy czynnik losowania odpowiedzi. Dla każdego użytkownika $j$ w pierścieniu:

Wartość jest taka sama dla wszystkich $j$. Podpisy poza tym nośnikiem mają prawdopodobieństwo zero dla każdego podpisującego. Rozkłady są zatem identyczne punkt po punkcie. Dla dowolnej strategii zgadywania $\Pr[\hat b=b]=1/2$, a przewaga $|\Pr[\hat b=b]-1/2|$ wynosi zero.

Jeśli przeciwnik zna długoterminowe sekrety, może matematycznie odtworzyć możliwe losowości dla każdego kandydata. Nie dowie się jednak z samego podpisu, która została użyta. Ujawnienie faktycznej losowości jest innym modelem. Wiele niezależnych podpisów zachowuje równość rozkładów przez kolejne warunkowanie na już widzianych podpisach. Nierównomierne nonce lub dodatkowe logi mogą ten argument unieważnić.

To rozwinięcie rachunku z Herranz–Sáez, §4.3. W szczególności zachowuje odrzucanie powtórzonych zobowiązań. Nie dodaje do prawdziwego podpisującego zakazu kolizji wartości hasza, który występuje tylko w pomocniczym historycznym symulatorze. Źródło.

Herranz–Sáez: pełna ścieżka redukcji niepodrabialności

Cel gry. Ustalamy pierścień $n$ różnych uczciwie wygenerowanych kluczy. Przeciwnik nie zna żadnego sekretu, ale zadaje $Q_H\ge n$ zapytań do Hash i najwyżej $W$ żądań Sign. Może wskazać użytkownika, który podpisze. Wygrywa, jeśli podpisze wiadomość niepodpisaną wcześniej przez żadnego użytkownika w tym pierścieniu. W tym modelu nie ma Corrupt ani rejestracji własnych kluczy.

Poniżej podajemy kompletny wariant dydaktyczny redukcji, z jawną obsługą tabeli i własnym oszacowaniem strat. Zachowuje konstrukcję oraz ekstrakcję z oryginału. Nie jest przepisaniem stałej czasowej Theorem 3. Historyczne twierdzenie i jego dodatkowe warunkowania zestawiamy osobno, aby nie łączyć niezgodnych rachunków.

Krok 1. Jedna instancja DL we wszystkich kluczach

Redukcja dostaje $A=g^a\ne1_G$. Losuje różne niezerowe $\alpha_1,\ldots,\alpha_n$ i publikuje

Mnożenie przez niezerowe $a$ jest permutacją $\mathbb Z_q^*$. Dlatego wektor kluczy ma rozkład uczciwych różnych kluczy. Redukcja zna $\alpha_i$, ale nie zna żadnego sekretu $a_i=\alpha_i\cdot a$. W ten sposób każda późniejsza wyekstrahowana gałąź będzie użyteczna. Nie zgadujemy dodatkowo indeksu podpisującego.

Krok 2. Hash i Sign współdzielą tabelę

Hash odczytuje istniejący wpis $T[m,R]$ albo losuje jednostajny $c\overset{\$}{\leftarrow}\mathbb Z_q$ i zapisuje go. Zwykłe kolizje wartości hasza są dozwolone. Różne wejścia mogą otrzymać ten sam skalar.

Na żądanie podpisu przez użytkownika $j$:

1. Wylosuj inne $n-1$ zobowiązań dokładnie jak prawdziwy podpisujący. Dla każdego odczytaj albo utwórz $c_i=T[m,R_i]$ przez Hash.
2. Wylosuj niezależnie $c_j,z\overset{\$}{\leftarrow}\mathbb Z_q$ i wyznacz

3. Przy $R_j=1_G$ lub powtórzeniu innego zobowiązania losuj ponownie $z$, pozostawiając pozostałe dane i $c_j$ bez zmian.
4. Jeśli $(m,R_j)$ ma już wpis w tabeli, przerwij redukcję. W przeciwnym razie zapisz $T[m,R_j]=c_j$ i zwróć podpis.

W żadnym kroku nie wykorzystaliśmy sekretu. Weryfikacja zgadza się przez konstrukcję $R_j$.

Krok 3. Uzasadnij rozkład, a nie tylko poprawne równanie

Ustalmy wcześniejszy widok, inne zobowiązania i ich hasze. W rzeczywistym podpisie zaakceptowane $R_j$ jest jednostajne na $q-n$ dozwolonych punktach. Jeśli wejście jest świeże, jego hasz $c_j$ jest niezależnym jednostajnym skalarem.

W symulatorze dla każdego ustalonego $c_j$ odwzorowanie $z\mapsto R_j$ jest bijekcją na $G$. Po odrzuceniach każdy dozwolony punkt ma prawdopodobieństwo $1/(q-n)$, niezależnie od $c_j$. Zatem para $(R_j,c_j)$ w obu eksperymentach ma dla świeżego wejścia prawdopodobieństwo $1/((q-n)\cdot q)$. Odpowiedź $z$ jest jednoznacznie ustalona przez tę parę i pozostałe dane. Zgadza się cały transkrypt i tabela, nie tylko pojedynczy element.

Łączymy wykonania tak, aby były identyczne aż do trafienia zapisanego wejścia przez domykające zobowiązanie. Przy $t$-tym podpisie tabela przed programowaniem ma najwyżej $Q_H+n\cdot(t-1)+(n-1)$ wpisów. Jeden wcześniejszy wpis tej wiadomości wyklucza najwyżej jeden dozwolony punkt. Dlatego wystarcza jawna granica

To oszacowanie jest konserwatywne, bo liczy także wpisy innych wiadomości. Nie zakłada niezależności kolizji. Nie dopisujemy tu błędu za powtórzone wartości $c_i$, bo nasz symulator dopuszcza je tak samo jak prawdziwa wyrocznia.

Losowanie z odrzucaniem ma oczekiwaną liczbę prób $q/(q-n)$. Przy wymaganym sztywnym limicie $K$ prób na domknięcie trzeba dodać do granicy błędu najwyżej $W\cdot(n/q)^K$. Wtedy również czas symulatora ma jawny limit. Losowanie różnych pozostałych skalarów można realizować bez zwracania, bez odrzucania całego podpisu.

Krok 4. Zidentyfikuj zapytania sfałszowanego podpisu

Świeżość wiadomości oznacza, że żaden z jej wpisów nie został zaprogramowany przez Sign. Jeżeli przeciwnik pominął któryś hasz, weryfikacja wymaga trafienia niezależnej odpowiedzi. Ponieważ odpowiadający jej $A_i$ ma rząd $q$, najwyżej jedna wartość nieznanego wyzwania dopełnia równanie przy ustaleniu pozostałych. Można zastosować konserwatywną sumę $n/q$ dla brakujących pozycji.

Po usunięciu konfliktów symulacji i takich trafień prawdopodobieństwo użytecznej pierwszej gałęzi $\eta$ spełnia

W naszym symulatorze zwykłych świeżych losowań Hash jest najwyżej $Q=Q_H+W\cdot(n-1)$. Drugi składnik liczy hasze innych gałęzi, tworzone wewnątrz Sign. Programowane $c_j$ należą do prywatnej taśmy symulatora. Nie pomijamy tych dwóch rodzajów losowości przy odtwarzaniu.

Krok 5. Fork pierścienia: zachowaj cały wzorzec

Dla poprawnego fałszerstwa zapamiętujemy uporządkowany wektor $(\ell_1,\ldots,\ell_n)$ indeksów pierwszych losowań Hash dla $(m,R_i)$. Są różne, bo zobowiązania są różne. Możliwych wzorców jest co najwyżej

Dla $Q=10,n=3$ jest ich $720$, nie $10$ ani $120$. Pozycja wektora jest związana z konkretnym kluczem. Nie można zastąpić uporządkowanego wektora zbiorem indeksów.

Rozwidlamy przy $b=\max_i\ell_i$. Odtwarzamy ten sam stan, taśmę przeciwnika i symulatora oraz odpowiedzi sprzed $b$. Od $b$ dolosowujemy nowy sufiks. Sukces drugiej gałęzi wymaga tego samego wektora indeksów i innej odpowiedzi na pytanie $b$.

Wszystkie istotne pytania powstały najpóźniej w chwili $b$, a każde zostało wysłane przed otrzymaniem własnej odpowiedzi. Wspólny prefiks i to samo ostatnie pytanie ustalają więc wiadomość oraz wszystkie $R_i$. Tylko jedno istotne wyzwanie się zmienia. Pozostałe odpowiedzi spoza podpisu mogą zmienić się w sufiksie.