Kryptografia II stopień

W3. Tajność doskonała, OTP i szyfry strumieniowe

OTP

one-time pad. Szyfr z jednorazowym, losowym kluczem długości wiadomości.

Pierwszy pełny schemat: OTP

Cel: ukryć jedną wiadomość o ustalonej długości przed obserwatorem szyfrogramu. Zasób: nadawca i odbiorca mają już ten sam tajny, jednostajny klucz. Sam schemat nie dostarcza sposobu bezpiecznego przekazania tego klucza.

Jak działa jednorazowa maska

Setup ustala długość $\ell=\ell(\lambda)$. Wiadomość, klucz i szyfrogram mają po $\ell$ bitów. KeyGen losuje klucz niezależnie od wiadomości. Nadawca wywołuje Enc z wiadomością i tym kluczem. Odbiorca uruchamia Dec z szyfrogramem i własną kopią tego samego klucza. Na strzałce między nimi znajduje się tylko szyfrogram $c$.

Poprawność: $(m\oplus k)\oplus k=m$. Ograniczenie: OTP nie wykrywa celowej zmiany szyfrogramu. Teraz sprawdzimy jego poufność, a następnie zobaczymy, dlaczego ponowne użycie klucza niszczy tę gwarancję.

Tajność jako równość rozkładów

Niech $M$ oznacza losową wiadomość, a $C$ odpowiadający jej szyfrogram. Małe litery $m,c$ są ich konkretnymi wartościami. W tajności doskonałej obserwacja szyfrogramu nie zmienia rozkładu wiadomości:

dla każdego $c$ o dodatnim prawdopodobieństwie. W one-time pad wiadomość i klucz mają długość $\ell$, klucz jest jednostajny, niezależny od wiadomości i użyty raz. Szyfrowanie to $c=m\oplus k$. Dla ustalonych $m,c$ dokładnie jeden klucz daje ten szyfrogram. Stąd $\Pr[C=c\mid M=m]=2^{-\ell}$ niezależnie od $m$. Również $\Pr[C=c]=2^{-\ell}$, bo uśredniamy tę samą wartość po wszystkich wiadomościach. Podstawiamy do wzoru Bayesa, który zamienia kierunek warunkowania:

Przy dwóch bitach każda ustalona wiadomość może dać dowolny z czterech szyfrogramów. Dla każdego jest dokładnie jeden z czterech kluczy. To mała wersja tego samego argumentu, nie założenie o równomiernym rozkładzie wiadomości.

Jednorazowość jest częścią konstrukcji

Przy ponownym użyciu maski:

Poznanie jednej wiadomości ujawnia drugą. Bez znajomości wiadomości pozostaje ujawniona relacja. Dla szyfru strumieniowego problemem jest powtórzenie pary klucz–nonce, nie samo użycie jednego klucza do poprawnie rozdzielonych strumieni.

Szyfry strumieniowe zastępują długi losowy klucz pseudolosowym strumieniem. ChaCha20 jest przykładem takiego mechanizmu. Sam strumień nie zapewnia integralności. Zmiana bitu szyfrogramu zmienia odpowiedni bit tekstu. Praktyczny kanał potrzebuje uwierzytelniania, np. konstrukcji AEAD.

Poznaliśmy już oba składniki następnego argumentu: definicję PRG w W2 oraz niezależność szyfrogramu OTP od wiadomości. Możemy teraz wyjaśnić, jak założenie o generatorze przenosi się na bezpieczeństwo szyfrowania.

Dlaczego pojawiają się gry numerowane

Mamy już eksperyment określający sukces przeciwnika. Teraz chcemy oszacować jego prawdopodobieństwo. Bezpośredni rachunek bywa trudny, bo jednocześnie występują klucze, hasze, odpowiedzi i warunki akceptacji. Tworzymy więc kolejne wersje tego samego eksperymentu, zmieniając po jednym elemencie.

$G_0$ oznacza wersję wyjściową. $G_1$ to wersja po pierwszej zmianie, a nie nowy typ algorytmu lub nowa grupa algebraiczna. Przeciwnik próbuje osiągnąć ten sam cel. Dla każdej zmiany pytamy: czy jego widok ma ten sam rozkład, czy odróżnienie wymagałoby złamania założenia, czy też różnica zachodzi tylko po rzadkim zdarzeniu?

Jeśli w ostatniej grze szyfrogram jest zupełnie niezależny od ukrytego bitu, zgadywanie daje $1/2$. Jeżeli umiemy ograniczyć wszystkie różnice między sąsiednimi grami, wracamy do początkowego systemu. Nie wystarczy nazwać kolejnych etapów grami. Każda strzałka wymaga uzasadnienia.

Redukcja jest algorytmem wykorzystującym atak

Przyjmujemy hipotetyczny skuteczny atak $\mathcal A$ na konstrukcję. Budujemy program $\mathcal B$, który dostaje trudne zadanie, uruchamia $\mathcal A$, przygotowuje mu widok i wykorzystuje jego odpowiedź do rozwiązania tego zadania. Jeśli przygotowany widok jest właściwy i koszt nie jest zbyt duży, skuteczność $\mathcal A$ przeczyłaby naszemu założeniu.

To kierunek od ataku do rozwiązania trudnego problemu. Redukcja nie musi znać sekretów uczciwej implementacji. Musi umieć zastąpić ich użycie przy generowaniu widoku. Gdy w rzekomym dowodzie do symulacji podpisu potrzebujemy nieznanego klucza z wyzwania, konstrukcja redukcji jest niekompletna.

Poniższy przykład z generatorem ma tylko dwie gry, żeby ten mechanizm był widoczny bez rozbudowanej aparatury.

Pierwszy kompletny dowód obliczeniowy

Rozważmy jednorazowe szyfrowanie $c=m\oplus\mathsf{PRG}(k)$. W grze $G_0$ maska pochodzi z generatora. W $G_1$ zastępujemy ją niezależnym $U_\ell$. W drugiej grze szyfrogram jest jednostajny i niezależny od $b$.

Redukcja $\mathcal B$ otrzymuje ciąg $z$, będący wyjściem generatora albo ciągiem losowym. Uruchamia $\mathcal A$, odbiera parę wiadomości, losuje $b$ i zwraca $m_b\oplus z$. Zwraca 1 dokładnie wtedy, gdy $\mathcal A$ zgadnie $b$. Nie zna zalążka i go nie potrzebuje. Jej różnica prawdopodobieństw wyjścia 1 jest dokładnie przewagą zgadywania:

To dowód dla jednej wiadomości. Wielokrotne użycie tej samej maski nie jest objęte twierdzeniem.

Dlaczego to nie tajność doskonała? Generator ma najwyżej $2^n$ możliwych wyjść, a ciąg losowy długości $\ell$ ma ich $2^\ell$. Nieograniczony przeciwnik może wypisać cały obraz generatora i sprawdzać przynależność. Bezpieczeństwo obliczeniowe mówi, że takiego rozróżniania nie da się wykonać wydajnie przy przyjętym parametrze. Nie mówi, że rozkłady są identyczne.

Wiele wiadomości: redukcja do PRF

Korzystamy z rodziny $F_k$ i idealnej funkcji $R$ z W2. Wszystkie maski mają tę samą długość co szyfrowane wiadomości.

Dla wiadomości długości $\ell$ wybieramy losowy identyfikator $r$ i wysyłamy $(r,m\oplus F_k(r))$. Zastępujemy $F_k$ przez $R$. Dopóki argumenty nie powtarzają się, każda maska jest niezależna. Przy $t$ losowych identyfikatorach:

Różnicę między grami ogranicza przewaga PRF, a pozostały błąd kolizja. Konserwatywną granicą jest suma tych dwóch wielkości. Przy wymuszonej unikalności identyfikatorów kolizja znika, ale trzeba zachować unikalność także po awarii i restarcie.

Nie dowodzimy tu, że AES jest PRF. Dowodzimy bezpieczeństwa konstrukcji przy wskazanym założeniu o prymitywie. Ścieżkę PRG → hybrydy → PRF → IND-CPA stosują też materiały MIT.

Dwa narzędzia do dalszych dowodów

Hybryda jest pośrednią wersją eksperymentu. Jeśli każdy sąsiedni krok zmienia szansę sukcesu najwyżej o określoną wartość, całkowitą zmianę ograniczamy sumą tych wartości. To nierówność trójkąta, a nie nowe założenie o szyfrze. Pełny zapis podaje pogłębienie A.

Sprzężenie losowań (coupling) pozwala porównać dwa eksperymenty we wspólnym doświadczeniu. Każdy z osobna musi zachować swój prawidłowy rozkład. Przykład: jeden eksperyment losuje identyfikatory z powtórzeniami, drugi bez powtórzeń. Korzystają z tej samej propozycji losowej, dopóki jest nowa. Gdy propozycja się powtórzy, pierwszy ją zachowuje, a drugi losuje jednostajnie spośród nieużytych. Każdy ma właściwy rozkład, a historie są identyczne do pierwszego powtórzenia.

W tym wspólnym doświadczeniu różnica wyników wymaga kolizji, więc jej prawdopodobieństwo ogranicza różnicę szans sukcesu. To narzędzie analizy, nie dodatkowy interfejs przeciwnika ani wiedza symulatora. Takiego porównania użyjemy później przy FDH i UC. Metoda gier Shoupa, oryginał. Pełne wyjaśnienie po polsku z animacją i rachunkiem.

FDH

Full Domain Hash. Haszowanie o pełnej dziedzinie wyników.

UC

Universal Composability. Uniwersalna kompozycyjność, czyli formalna analiza bezpieczeństwa przy składaniu protokołów.

Pytanie kontrolne: test częstości bitów bada jedną własność rozkładu. Dlaczego nie wyklucza algorytmu odzyskującego stan generatora?

Powiązania: C1: tajność doskonała, C3: generatory i redukcje, L2: ataki na losowość.

W3a. Metoda gier: kompletny dowód krok po kroku

Cel: przejść od zdania „ten atak nie powinien działać” do twierdzenia, w którym wiadomo, od czego zależy szansa jego powodzenia. Potrzebne są eksperymenty z rozdziału o modelach, funkcja pseudolosowa z W2 i jednorazowa maska z W3. Nie potrzebujemy jeszcze grup ani krzywych eliptycznych.

Punktem odniesienia jest Victor Shoup, Sequences of Games: A Tool for Taming Complexity in Security Proofs, §1.1. Tytuł można oddać jako „Ciągi gier: narzędzie porządkowania złożonych dowodów bezpieczeństwa”. Chodzi o złożoność rozumowania, nie o pomiar czasu działania. Poniżej rozwijamy własny przykład szyfrowania z W3, z pełnym rachunkiem i obliczeniami do prześledzenia.

1. Gra nie jest pojedynczym przebiegiem

Gra jest opisem całego doświadczenia losowego. Określa losowanie klucza, interfejs przeciwnika, odpowiedzi na pytania i warunek wygranej. Jeden uruchomiony przykład jest tylko jednym możliwym wynikiem tego doświadczenia. Prawdopodobieństwo liczymy po wszystkich losowaniach, w tym po losowości przeciwnika.

Ustalmy jednego przeciwnika $\mathcal A$. Numer $i$ oznacza wersję eksperymentu $G_i$, a $S_i$ zdarzenie jego sukcesu. Zapisujemy $p_i=\Pr[S_i]$. W tym rozdziale sukces zawsze oznacza $b'=b$, czyli odgadnięcie ukrytego bitu. Zmieniamy obsługę eksperymentu, a nie cel ani program przeciwnika. Jego następne pytania mogą jednak zmienić się po otrzymaniu innych odpowiedzi.

Challenger prowadzi grę zgodnie z jej regułami. Redukcja jest innym programem, który próbuje odtworzyć tę obsługę, korzystając z otrzymanego trudnego zadania. Autor dowodu porównuje rozkłady. Nie wolno przenosić jego wiedzy, np. znajomości obu porównywanych światów, do interfejsu redukcji lub przeciwnika.

2. Każda zmiana musi mieć osobne uzasadnienie

W terminologii Shoupa występują trzy rodzaje przejścia. Bridging step to równoważne przepisanie doświadczenia. Indistinguishability transition korzysta z nierozróżnialności. Failure-event transition ogranicza różnicę przez zdarzenie, poza którym porównanie działa identycznie. Oryginał, §1.1.

Możliwy jest również bezpośredni argument statystyczny o odległości rozkładów. Nie wymaga on ograniczenia czasu przeciwnika. Założenie obliczeniowe jest czymś innym: dwa rozkłady mogą być różne, lecz nie pozwalać na wydajne odróżnianie.

3. Z czego składa się lemat o różnicy

Sprzężenie to wspólne losowanie dwóch eksperymentów, które zachowuje właściwy rozkład każdego z nich osobno. Nie wymaga ich niezależności. Właśnie zależność pozwala powiedzieć, że w konkretnym wspólnym losowaniu zachowują się tak samo aż do wskazanego zdarzenia.

Niech $\mathrm{Bad}$ będzie zdarzeniem w tej wspólnej przestrzeni. Zakładamy, że poza nim sukces w jednej grze zachodzi dokładnie wtedy, gdy zachodzi w drugiej. Lemat o różnicy Shoupa daje wtedy ograniczenie przez $\Pr[\mathrm{Bad}]$. Difference Lemma, lemat 1.

Odtwórzmy rachunek, aby zrozumieć, dlaczego nie pojawia się dodatkowy czynnik 2. Rozdzielamy sukces na część wewnątrz i poza $\mathrm{Bad}$:

Pierwsza część jest taka sama w obu grach i znika przy odejmowaniu. Pozostaje:

Obie odejmowane liczby należą do przedziału od zera do $\Pr[\mathrm{Bad}]$. Ich odległość nie przekracza długości tego przedziału. Bad nie oznacza jeszcze udanego ataku. Oznacza miejsce, w którym kończy się nasza gwarancja zgodności dwóch światów. Także po nim wyniki mogą przypadkiem pozostać równe.

Nie wystarczy napisać „zakładamy, że Bad nie wystąpi”. Warunkowanie usuwa część przebiegów i może zmienić rozkład. Nie wystarczy też nadać zmiennym w dwóch niezależnych uruchomieniach te same nazwy. Trzeba zbudować ich wspólne losowanie i sprawdzić oba rozkłady.

4. Twierdzenie, które teraz udowodnimy

Rozważamy rodzinę funkcji $F_k:\{0,1\}^n\to\{0,1\}^{\ell}$. Klucz $k$ jest tajny. Wiadomość $m$ ma dokładnie $\ell$ bitów, a identyfikator $r$ ma $n$ bitów. Każde szyfrowanie losuje go niezależnie i jednostajnie. Reguły są następujące:

Powtórzenie identyfikatora jest dopuszczone przez algorytm, choć może zaszkodzić bezpieczeństwu. Identyfikator nie jest drugim tajnym kluczem. Jest przesyłany jawnie wraz z szyfrogramem. Poprawność wynika z dwukrotnego XOR tej samej maski. Nie wynika z niej poufność.

Model. Przeciwnik otrzymuje jedno wyzwanie dla wybranych $m_0,m_1$ i może pytać o szyfrowanie przed nim oraz po nim. Wszystkie teksty mają długość $\ell$. Nie ma wyroczni deszyfrującej, odczytu klucza ani możliwości ustawiania $r$. To eksperyment IND-CPA z jednym wyzwaniem. Łączna liczba szyfrowań, wraz z wyzwaniem, nie przekracza $t\le 2^n$.

Twierdzenie. Dla każdego takiego przeciwnika istnieje redukcja $\mathcal B$ wykonująca najwyżej $t$ zapytań do swojej wyroczni, dla której:

Jest to konserwatywna granica, nie równość opisująca najlepszy atak. Teraz uzasadnimy każdy jej składnik. Pełny łańcuch pozostaje widoczny na rysunku.

5. Pierwsza strzałka: redukcja zastępuje funkcję

W $G_0$ działa rzeczywiste $F_k$. W $G_1$ używamy jednej losowej funkcji $R$ o tej samej dziedzinie i zbiorze wyników. Dla nowego argumentu losujemy jej wartość. Dla powtórzonego zwracamy wartość zapamiętaną. To nie jest nowa maska przy każdym pytaniu.

Redukcja $\mathcal B$ dostaje wyrocznię $O$. Nie wie, czy jest to $F_k$ dla losowego klucza, czy $R$. Nie dostaje klucza, kodu wybranej funkcji ani jej całej tabeli. Otrzymuje tylko odpowiedzi na własne pytania.

1. Uruchamia $\mathcal A$ i samodzielnie obsługuje jego pytania o szyfrowanie. Losuje $r$, pyta o $O(r)$ i oddaje $(r,m\oplus O(r))$.
2. Po otrzymaniu $m_0,m_1$ losuje ukryty bit $b$ i tak samo szyfruje $m_b$. Obsługuje również dalsze pytania.
3. Odbiera $b'$ i zwraca 1 dokładnie wtedy, gdy $b'=b$. Potrafi to sprawdzić, bo to ona wylosowała $b$.

Gdy $O=F_k$, widok jest dokładnie widokiem $G_0$. Gdy $O=R$, widok jest dokładnie widokiem $G_1$. W obu przypadkach obejmuje również adaptacyjnie wybrane pytania. Dlatego, w konwencji różnicy prawdopodobieństw:

Nie zgadujemy pozycji wyzwania. Redukcja zastępuje cały interfejs funkcji i obsługuje wszystkie szyfrowania. Nie ma więc dodatkowego mnożenia przewagi PRF przez $t$. Jej czas to czas $\mathcal A$ oraz obsługa najwyżej $t$ szyfrowań i komunikatów. Gdy operację wyroczni liczymy jako jedno zapytanie, narzut bitowy poza nią wynosi $O(t\cdot(n+\ell))$. W rzeczywistym pomiarze trzeba doliczyć koszt wykonania samej funkcji.

6. Druga strzałka: porównujemy losowania identyfikatorów

W $G_1$ identyfikatory losujemy z powtórzeniami. W $G_2$ wybieramy je jednostajnie spośród dotąd nieużytych. To inny algorytm obsługi gry, a nie przemilczany warunek narzucony na $G_1$.

Zbudujmy sprzężenie. W obu światach wykorzystujemy te same losowe bity przeciwnika i ten sam ukryty bit. Przed pierwszą rozbieżnością wybory wiadomości są więc takie same. Niech $U$ oznacza zbiór identyfikatorów użytych w $G_2$, a $N=2^n$.

1. Losujemy wspólną propozycję $r$ jednostajnie z $N$ możliwości. Gra $G_1$ zawsze ją przyjmuje.
2. Jeżeli $r\notin U$, gra $G_2$ również ją przyjmuje. W przeciwnym razie losuje zamiennik jednostajnie z $N-|U|$ wolnych identyfikatorów.
3. Przed pierwszą rozbieżnością wspólny nowy identyfikator dostaje wspólną świeżą maskę. Po rozbieżności każda gra nadal przestrzega własnej tabeli i rozkładu. Pytania przeciwnika nie muszą już być jednakowe.

Dlaczego drugi świat naprawdę losuje jednostajnie bez powtórzeń? Jeśli wykorzystano $j$ identyfikatorów, każdy ustalony wolny identyfikator $v$ zostanie przyjęty bezpośrednio z prawdopodobieństwem $1/N$. Może też zostać zamiennikiem po trafieniu jednej z $j$ zajętych pozycji. Łącznie:

Zatem obie strony zachowują wymagane rozkłady. Poza zdarzeniem pierwszego powtórzenia propozycji historie i wyniki są identyczne. To jest hipoteza lematu o różnicy, a nie tylko podobieństwo rysunków.

Poniżej $i$ jest numerem szyfrowania, $r$ przyjętym identyfikatorem, $m$ wiadomością, $z$ maską, a $c=m\oplus z$ częścią szyfrogramu. Wiersze są historią szyfrowań, nie osobnymi wpisami funkcji. Jeśli w $G_1$ identyfikator wraca, odczytujemy istniejący wpis $R(r)$.

W demonstracji porównujemy cztery zwykłe szyfrowania wybranych wiadomości. Małe wartości to czterobitowe bloki, a identyfikatory należą do zbioru od 0 do 7. Jest to jawnie dobrany zapis możliwego przebiegu, nie losowanie bezpiecznego klucza. Tabele pokazujemy studentowi, nie przeciwnikowi. Przykład ilustruje sprzężenie i ponowne użycie maski, a nie mierzy przewagi PRF.

7. Skąd bierze się granica urodzinowa

W $G_1$ mamy niezależne propozycje $r_1,\ldots,r_t$ z $N$ wartości. Przy wcześniejszym zakończeniu eksperymentu możemy dolosować niewykorzystane propozycje tylko na potrzeby analizy. Nie zmieniają widoku przeciwnika i dają górną granicę dla liczby co najwyżej $t$ szyfrowań.

Dla ustalonej pary $i<j$ szansa $r_i=r_j$ wynosi $1/N$. Par jest $t\cdot(t-1)/2$. Oszacowanie sumą (union bound) mówi, że prawdopodobieństwo co najmniej jednego zdarzenia nie przekracza sumy ich prawdopodobieństw. Nie wymaga niezależności tych zdarzeń. Tutaj kolizje poszczególnych par nie są rozłączne.

Dla dokładnie $t$ propozycji możemy również policzyć wynik bez oszacowania. Pierwsza nie powoduje kolizji. Druga unika jednej zajętej wartości. Trzecia unika dwóch, pod warunkiem że wcześniej kolizji nie było. Stąd:

Iloczyn wynika z kolejnych prawdopodobieństw warunkowych. Nie zakładamy niezależności zdarzeń „dotąd nie było kolizji”. Dla $N=8$ i $t=4$ mamy $1-(8\cdot7\cdot6\cdot5)/8^4=151/256$. Granica sumą to $6/8=3/4$. Większa liczba jest ograniczeniem, nie błędem w dokładnym rachunku.

8. Ostatnia strzałka: maski stają się niezależne

W $G_2$ nigdy nie pytamy $R$ o ten sam identyfikator dwa razy. Wartość losowej funkcji na nowym argumencie jest jednostajna i niezależna od wcześniejszych odpowiedzi. Możemy więc usunąć tabelę i przy każdym szyfrowaniu losować nową maskę $z\in\{0,1\}^{\ell}$. Tak otrzymujemy $G_3$. Nadal losujemy identyfikatory bez powtórzeń. Nie zmieniamy dwóch reguł naraz.

To przejście ma koszt zero. Sprawdźmy je także dla adaptacyjnego przeciwnika. Dla każdego możliwego dotychczasowego widoku następne pytanie ma tę samą regułę wyboru po obu stronach. W obu światach odpowiedź używa świeżej maski o tym samym rozkładzie. Indukcja po pytaniach daje identyczny rozkład całego widoku.

W wyzwaniu $c=m_b\oplus z$ mamy dla każdego ustalonego $m_b$ i każdego $c$ dokładnie jedną maskę, która daje ten wynik. Zatem $c$ jest jednostajne. Pozostałe szyfrowania korzystają z innych, niezależnych masek i nie ujawniają bitu. Dotyczy to również pytań po wyzwaniu, wybieranych na podstawie dotychczasowych szyfrogramów. W $G_3$ cały widok jest niezależny od $b$, więc $p_3=1/2$.

9. Składamy dowód i kontrolujemy stałe

Dodajemy i odejmujemy prawdopodobieństwa gier pośrednich, a następnie korzystamy z nierówności trójkąta:

Po wstawieniu granicy z punktu 7 dostajemy twierdzenie. Możemy użyć dokładnego iloczynu zamiast granicy sumą. Wynik wolno dodatkowo ograniczyć przez $1/2$, ponieważ tyle maksymalnie wynosi przyjęta przewaga zgadywania.

Czynnik 2 zależy od definicji przewagi. Tutaj przewagą jest odległość szansy trafienia od $1/2$. Jeśli inne źródło definiuje ją jako $|2\cdot\Pr[S_0]-1|$, trzeba pomnożyć prawą stronę przez 2. Sama zmiana nazw nie zmienia matematyki, ale pominięcie normalizacji zmienia twierdzenie.

Liczba gier też jest parametrem. Dla $h$ kroków ogólny rachunek daje $|p_0-p_h|\le\sum_{i=0}^{h-1}|p_i-p_{i+1}|$. Stała liczba zaniedbywalnych składników daje zaniedbywalną sumę. Przy rosnącym $h(\lambda)$ trzeba podać wspólne ograniczenie składników i wzrost liczby kroków. Wielomian razy funkcja zaniedbywalna pozostaje zaniedbywalny. Wykładnicza liczba kroków nie daje tej gwarancji.

Jeżeli zastępujemy wiele osobnych obiektów i redukcja losuje pozycję zastąpienia, strata rzędu $h$ może być uzasadniona. Nie przenosimy jej automatycznie do naszego przykładu z jedną wyrocznią. Przy losowaniu pozycji analizujemy różnice ze znakami i teleskopowanie, nie średnią wartości bezwzględnych, która może opisywać inny algorytm.

10. Kiedy argument przestaje działać

• Przeciwnik ustawia identyfikator. Może wymusić powtórzenie i odzyskać maskę z szyfrowania zera. Losowa granica urodzinowa nie opisuje takiego modelu.
• Pojawia się deszyfrowanie. Konstrukcja nie uwierzytelnia danych. Zmiana $c$ na $c\oplus\Delta$ zmienia tekst na $m\oplus\Delta$. Twierdzenie CPA nie obejmuje modelu CCA.
• Redukcja potrzebuje nieznanego klucza. W naszym dowodzie tego uniknęliśmy przez interfejs $O(r)$. W innym schemacie odpowiedź „symulujemy” wymaga osobnego algorytmu.
• Przerwanie znika z rachunku. Jeśli symulator po kolizji przerywa, trzeba zdefiniować wynik takiego przebiegu i ograniczyć jego wpływ. Nie wolno po prostu analizować tylko udanych symulacji.
• Bad liczymy w wygodniejszej, ale innej grze. Trzeba uzasadnić przeniesienie oszacowania, np. osobną redukcją lub dodatkowym sprzężeniem. W naszym przykładzie liczymy kolizje niezależnych propozycji w $G_1$.
• Pomiar zastępuje kwantyfikator. Test kilku przeciwników nie daje granicy dla każdego dozwolonego algorytmu. Numeryczny kalkulator sprawdza rachunek prawdopodobieństwa, nie założenie PRF.

11. Jak używać tej metody w dalszej części kursu

RSA-FDH

Rivest–Shamir–Adleman with Full Domain Hash. Podpis RSA z haszowaniem do pełnej dziedziny wyników.

Ćwiczenie z rozwiązaniem. Dla trzech szyfrowań z czterech identyfikatorów policz kolizję i granicę sumą. Czy ich równość jest wymagana? Następnie wskaż koszt każdej z trzech strzałek naszego dowodu.

Dalszy rachunek: C3, redukcje i suma strat oraz L2, ponowne użycie losowości. W źródle: Shoup, pełny tekst. Dodatkowe tło do eksperymentów i szyfrowania z funkcją pseudolosową: Boneh–Shoup, A Graduate Course in Applied Cryptography, rozdziały 2, 4 i 5.