Kryptografia II stopień

W1. Od szyfru do definicji bezpieczeństwa

Pytanie: co dokładnie ma pozostać tajne i przed kim? Tekst jawny to wiadomość przed zaszyfrowaniem, a szyfrogram to wynik szyfrowania. Zaczniemy od szyfrów historycznych. Pokażą nam, że zmiana wyglądu tekstu nie musi ukrywać jego struktury. Bezpieczeństwo nie powinno zależeć od ukrywania opisu algorytmu. Zakładamy, że przeciwnik zna ten opis, ale nie zna tajnego klucza.

Historyczna droga prowadzi od ukrywania samego sposobu szyfrowania do publicznego opisu algorytmu i precyzyjnego modelu przeciwnika. Szyfry podstawieniowe i przestawieniowe uczą rozpoznawania struktury. Analiza Shannona oddziela tajność informacyjną od ograniczeń obliczeniowych. Kryptografia z kluczem publicznym rozdziela prawo do szyfrowania lub sprawdzania od prawa do odszyfrowania lub podpisania. Każdy z tych kroków zmienia pytanie, które zadajemy o system.

Podstawianie, przestawianie i informacja, która pozostaje

Szyfr monoalfabetyczny. Klucz określa jedną tabelę zamiany liter. Jeżeli według tej tabeli literze A odpowiada Q, każde wystąpienie A w tekście jawnym zastępujemy literą Q w szyfrogramie, niezależnie od pozycji. Dopóki używamy tego samego klucza, przyporządkowanie się nie zmienia. Nie chodzi więc o pozostawienie litery bez zmiany, tylko o konsekwentne stosowanie tej samej tabeli.

W rozpatrywanym prostym podstawieniu różnym literom wejściowym odpowiadają różne litery wynikowe. Dzięki temu odbiorca znający tabelę może odwrócić każdą zamianę. Definicja dopuszcza też przyporządkowanie niektórej litery jej samej, np. B do B. Stałość tabeli nie oznacza jednak, że wszystkie litery pozostają bez zmiany.

Przykład: jeśli tabela zawiera zamiany A → Q i L → M, tekst ALA daje szyfrogram QMQ. Oba wystąpienia A przeszły w Q. Czytelnik szyfrogramu nadal widzi, że pierwsza i trzecia litera tekstu jawnego były jednakowe. Sama obserwacja tego powtórzenia nie mówi mu jeszcze, jakie to były litery. Liczba wystąpień danej litery przechodzi na jej zamiennik, np. liczba liter A staje się liczbą liter Q. Powtarzający się fragment tekstu jawnego daje powtarzający się fragment szyfrogramu.

Szyfr przestawieniowy. Nie zastępuje liter innymi literami, lecz zmienia ich kolejność zgodnie z kluczem. Na przykład przestawienie ALA w AAL pozostawia dwie litery A i jedną L. Zachowane są więc same znaki i liczba wystąpień każdego z nich, ale niekoniecznie ich sąsiedztwo. To inny rodzaj zachowanej informacji niż przy podstawianiu. Handbook of Applied Cryptography, §7.3.1–7.3.2.

Duża liczba możliwych kluczy sama nie wystarcza do zapewnienia bezpieczeństwa. Dla prostego podstawienia alfabetu 26-literowego istnieje $26!$ tabel zamiany. Przeciwnik nie musi jednak sprawdzać ich wszystkich. Może wykorzystywać częstości liter, typowe połączenia liter i prawdopodobne słowa. Są to wskazówki, a nie pewne odpowiedzi, szczególnie przy krótkim tekście. Nie możemy też zakładać, że przeciwnik nie zna formatu, nagłówka lub części treści wiadomości.

Szyfr polialfabetyczny. Korzysta z więcej niż jednej tabeli podstawień. Wybór tabeli może zależeć od pozycji litery w wiadomości. Ta sama litera tekstu jawnego może więc dawać różne litery szyfrogramu na różnych pozycjach. Jeśli kolejność tabel powtarza się z krótkim okresem, można zebrać pozycje korzystające z tej samej tabeli i analizować je osobno. Za chwilę zobaczymy to w szyfrze Vigenère’a. Samo wrażenie, że szyfrogram wygląda losowo, nie jest zatem dowodem bezpieczeństwa.

Vigenère: gdzie dokładnie działa klucz

W popularnym wariancie szyfru Vigenère’a zapisujemy litery jako liczby od $A=0$ do $Z=25$. Klucz to słowo długości $t\ge1$, powtarzane pod wiadomością. Numerujemy pozycje od zera. Liczba $m_i$ oznacza literę tekstu jawnego na pozycji $i$, a $c_i$ literę szyfrogramu na tej pozycji. Wartość $k_j$ oznacza literę klucza na pozycji $j$. Dla kolejnej pozycji wiadomości wybieramy $j=i\bmod t$, czyli wracamy do początku klucza po wykorzystaniu jego ostatniej litery. Szyfrowanie i odszyfrowanie mają postać:

Litera klucza określa przesunięcie w alfabecie. Dla litery wiadomości A i litery klucza K liczymy $(0+10)\bmod26=10$, czyli otrzymujemy K. Po przekroczeniu Z wracamy do A, co zapewnia działanie modulo 26. Zmiana jednej litery klucza zmienia przesunięcie na wszystkich pozycjach wiadomości, na których używamy tej litery klucza. Dwa przebiegi poniżej szyfrują tę samą wiadomość, ale różnymi kluczami.

Słabość: okres rozbija problem na prostsze części. Numerujemy pozycje od zera, jak we wzorze. Przy kluczu długości trzy pozycje 0, 3, 6, … korzystają z jednego przesunięcia, pozycje 1, 4, 7, … z drugiego, a pozycje 2, 5, 8, … z trzeciego. Przy dostatecznie długim tekście można analizować częstości w tych grupach. Odległości między powtarzającymi się fragmentami szyfrogramu pomagają proponować okres w metodzie Kasiskiego, ale pojedyncze powtórzenie może być przypadkowe. Krótki przykład ilustruje zależność, nie gwarantuje odzyskania klucza analizą częstości.

Gdy znamy fragment tekstu jawnego, obliczamy odpowiadający mu fragment klucza przez $k_j=(c_i-m_i)\bmod26$. Przy wybranym tekście AAAA… dostajemy bezpośrednio powtarzany klucz. To różne możliwości przeciwnika. Ich uporządkowanie za chwilę stanie się podstawą modelu bezpieczeństwa. Handbook of Applied Cryptography, §7.3.3 i §7.3.5.

Enigma: stan maszyny zmienia podstawienie

Enigma jest elektromechaniczną maszyną szyfrującą. Operator naciska klawisz z literą wiadomości, a maszyna zapala lampkę z literą szyfrogramu. Na przykład naciśnięcie A może zapalić B. O tym, która lampka się zapali, decydują połączenia elektryczne i aktualne nastawy maszyny. Klawisz służy do wprowadzania litery. Klucz kryptograficzny to uzgodniony zestaw nastaw, a nie naciskany klawisz.

Rozpatrujemy wojskową Enigmę z trzema ruchomymi wirnikami. W naszym przykładzie są to wirniki I, II i III, umieszczone w tej kolejności od lewej, oraz nieruchomy reflektor B. Oznaczenie B określa tutaj typ reflektora, nie literę wyniku. Inne wersje Enigmy mogły mieć inną budowę.

Najpierw części maszyny

• Klawiatura ma klawisze literowe. Naciśnięcie klawisza uruchamia mechanizm kroku wirników, a następnie zamyka obwód elektryczny odpowiadający wybranej literze.
• Łącznica wtyczkowa to panel gniazd oznaczonych literami. Kabel wpięty między A i Z zamienia te dwie litery: wejście A prowadzi dalej jako Z, a wejście Z jako A. Litera bez kabla przechodzi bez zmiany. Łącznica nie obraca się. Te same połączenia działają także na drodze powrotnej.
• Wirnik to obracany krążek z 26 stykami elektrycznymi po każdej stronie. Wewnątrz przewody łączą każdy styk jednej strony z jednym stykiem drugiej strony. Każdy typ wirnika realizuje własne przestawienie styków. Okablowanie jest ustalone, ale obrót całego krążka zmienia to, które styki spotykają się ze stykami sąsiednich części.
• Okienko i pierścień literowy pozwalają określić nastawy wirnika. Przez okienko w pokrywie widać jedną literę z pierścienia otaczającego wirnik. Sam pierścień można przestawić względem rdzenia z przewodami. Dlatego wskazanie okienka i nastawa pierścienia są dwiema osobnymi informacjami. W przykładach używamy liter A–Z, również gdy historyczna maszyna oznaczała pozycje liczbami 01–26.
• Reflektor łączy styki parami i kieruje sygnał z powrotem przez te same trzy wirniki. Nie jest lampą ani czwartym ruchomym wirnikiem.
• Panel lampek pokazuje wynik. Świeci litera, do której doprowadziła droga elektryczna. W tej maszynie wynik odczytuje i zapisuje operator, zamiast otrzymać wydruk.

Między łącznicą a prawym wirnikiem jest jeszcze nieruchoma tarcza wejściowa ETW. Doprowadza przewody do zestawu wirników. W wybranym wariancie zachowuje oznaczenia liter, więc w obliczeniach nie dodaje osobnej zamiany. Zasilanie zapewnia bateria. Budowa Enigmy I w Crypto Museum, A. Ray Miller, budowa i nastawy maszyny, s. 4–5.

ETW

Eintrittswalze. Niemiecka nazwa tarczy wejściowej Enigmy. Po angielsku entry wheel lub entry disc. Nie jest to skrót angielski.

Jeden klawisz, jedna droga do lampki

Na poniższym schemacie zachowujemy kolejność części: reflektor jest po lewej, a wirnik III po prawej. Początek drogi jest jednak po prawej stronie rysunku, przy klawiaturze. Górna droga prowadzi do reflektora, a dolna wraca do lampki. Pokazujemy tylko połączenia wykorzystane przy jednym naciśnięciu, nie wszystkie przewody maszyny.

1. Przed naciśnięciem okienka pokazują AAA. Używamy pierścieni AAA i łącznicy bez kabli. Każda z trzech liter opisuje kolejny wirnik, od lewej strony maszyny.
2. Naciskamy A. Najpierw następuje ruch mechaniczny. Prawy wirnik III przesuwa się o jedną pozycję, więc okienka pokazują AAB. W tym kroku wirniki I i II pozostają nieruchome.
3. Dopiero po kroku płynie sygnał. Łącznica i ETW przekazują A bez zmiany. Wirnik III przekształca A w C, wirnik II przekształca C w D, a wirnik I przekształca D w F.
4. Reflektor zawraca drogę. W reflektorze B styk F jest połączony ze stykiem S. Sygnał wraca przez wirnik I jako S, przez II jako E, a przez III jako B. Przejście przez ETW i łącznicę bez kabli pozostawia B.
5. Zapala się lampka B. Podczas tej drogi w obie strony wirniki już się nie obracają. Operator odczytuje wynik. Następne naciśnięcie ponownie rozpocznie się od kroku mechanizmu.

Litery wewnątrz rysunku są oznaczeniami torów elektrycznych. Maszyna nie wyświetla pośrednich C, D ani F. Widoczna jest dopiero lampka wyniku. Ruch i przepływ to dwa etapy jednego naciśnięcia, a nie obrót wirnika przy każdym przejściu sygnału. Droga sygnału i kolejność działania, okablowanie wirników i reflektora.

Gdzie jest klucz i co zmienia obrót

Nie dodajemy tu litery klucza do litery wiadomości jak w Vigenèrze. Operator przygotowuje maszynę według uzgodnionej konfiguracji. Te nastawy wybierają drogę elektryczną, a mechanizm zmienia ją podczas pisania.

Okienko i pierścień to nie to samo. Obrót całego wirnika zmienia literę widoczną w okienku. Przestawienie pierścienia zmienia jego ustawienie względem rdzenia. Po takiej zmianie można ponownie ustawić tę samą literę w okienku, ale przewody będą już dopasowane inaczej. W naszej demonstracji typ reflektora pozostaje stały. Odbiorca musi użyć zgodnej maszyny i odtworzyć nastawy do danej wiadomości, nie tylko trzy litery okienek.

Przy nastawach z rysunku dwa kolejne naciśnięcia A dają różne wyniki. Nie zmieniamy kabla ani okablowania wirników. Zmienia się ich położenie:

To przykład, nie reguła zakazująca powtórzenia wyniku w całej wiadomości. Inne położenie wybiera inne podstawienie całego alfabetu, ale dla niektórych liter wyniki mogą się powtarzać. W pięcioliterowym przebiegu poniżej AAAAA daje BDZGO.

Przepływ rozłożony na pojedyncze operacje

Teraz te same trzy wirniki przedstawiamy jako kolejne kroki drogi sygnału. Oznaczenie „powrót” nie dodaje nowej części. To ponowne przejście przez wcześniej poznany wirnik, w przeciwnym kierunku. Przebieg A zachowuje nastawy ze schematu trzywirnikowej maszyny. Przebieg B służy do porównania po zmianie jednej nastawy. Okienka i pierścienie nadal zapisujemy od lewej, w kolejności I, II, III.

MIT

Massachusetts Institute of Technology. Massachusettski Instytut Technologiczny, uczelnia w USA.

Dlaczego czasem porusza się więcej wirników

Zapadka to mechaniczny element, który przy naciśnięciu klawisza popycha wirnik o jeden krok. Wycięcie na pierścieniu pozwala w określonym położeniu zaangażować mechanizm przesuwający również sąsiedni wirnik. Prawy wirnik wykonuje krok zawsze. To, czy poruszą się pozostałe, zależy od położeń wycięć przed naciśnięciem.

Dla wirników I, II, III z pierścieniami AAA można to prześledzić od nastawy ADU:

Środkowy wirnik przeszedł kolejno z D do E, a zaraz potem z E do F. To podwójny krok, czyli dwa kroki podczas dwóch kolejnych naciśnięć, nie dwa kroki w jednym naciśnięciu. Dlatego Enigma nie zachowuje się dokładnie jak licznik, który przenosi pozycję dopiero po pełnym obrocie sąsiada. Wycięcie jest związane z pierścieniem literowym. Zmiana nastawy pierścienia nie zmienia litery okienka, przy której następuje przeniesienie, ale zmienia dopasowanie przewodów. D. Hamer, analiza mechanizmu podwójnego kroku.

Dopiero teraz zapis matematyczny

Przy nieruchomych wirnikach droga do reflektora jest permutacją, czyli odwracalnym przyporządkowaniem 26 liter. Oznaczmy ją przez $P$. W $P$ uwzględniamy łącznicę, ETW i trzy wirniki na drodze do reflektora. Reflektor oznaczymy przez $U$. Droga powrotna odwraca wcześniejsze połączenia, więc opisuje ją $P^{-1}$. Całe podstawienie $E$ ma postać:

Czytamy złożenie od prawej: najpierw $P$, potem $U$, na końcu $P^{-1}$. Reflektor łączy różne styki parami. Jego dwukrotne zastosowanie zwraca literę wejściową, a pojedyncze nigdy nie pozostawia jej bez zmiany. Stąd:

dla każdej litery $a$ i tego samego, ustalonego położenia wirników. Nie chodzi o dwa kolejne naciśnięcia, bo pomiędzy nimi następuje obrót. Aby odszyfrować całą wiadomość, odbiorca odtwarza nastawy początkowe i wpisuje szyfrogram. Maszyna przechodzi wtedy przez tę samą kolejność położeń. W naszym przykładzie po powrocie do AAA wpisanie BDZGO daje AAAAA.

Ograniczenie konstrukcji: brak szyfrowania litery na nią samą eliminuje pewne dopasowania przy zgadywaniu fragmentu wiadomości. Sam nie wystarcza do odzyskania klucza. Przewidywalny tekst i błędy procedur mogą jednak dostarczyć dalszych wskazówek. Liczba możliwych nastaw nie jest więc samodzielnym dowodem bezpieczeństwa.

Od szyfrowania do celów bezpieczeństwa

Trzy cele nie są zamienne. Poufność chroni treść. Integralność pozwala wykrywać nieuprawnioną zmianę. Uwierzytelnianie wiąże działanie z odpowiednią stroną lub kluczem. Szyfrowanie bez integralności może pozwalać na kontrolowaną modyfikację. Poprawny podpis nie ukrywa treści. Kanał z uzgodnionym kluczem nie musi jeszcze wiedzieć, kto jest partnerem.

Rozróżniamy generowanie klucza $\mathsf{Gen}$, szyfrowanie $\mathsf{Enc}$ i deszyfrowanie $\mathsf{Dec}$. Dla klucza $k$ i wiadomości $m$ wymagamy poprawności:

Prawdopodobieństwo obejmuje losowość algorytmów. Jeżeli konstrukcja dopuszcza mały błąd poprawności, trzeba podać jego granicę. Poprawność nie mówi, czy podsłuchujący potrafi odzyskać wiadomość.

Bezpieczeństwo jako eksperyment

Przeciwnik $\mathcal A$ otrzymuje określony widok i ma wygrać określone zadanie. W eksperymencie nierozróżnialności wybiera dwie dozwolone wiadomości $m_0,m_1$ jednakowej długości. Challenger $\mathsf{Ch}$ generuje tajny klucz $k$, losuje równomiernie bit $b$ i przekazuje przeciwnikowi szyfrogram $c^\star$ wiadomości $m_b$. Przeciwnik odpowiada bitem $b'$, czyli swoją oceną, którą wiadomość zaszyfrowano. Równa długość usuwa trywialne rozróżnianie przez rozmiar.

Na rysunku rozdzielamy wiedzę obu stron. Czytelnik widzi zapis losowania bitu po prawej, ale przeciwnik nie otrzymuje jego wartości. Widzi tylko dane przekazane strzałkami i własny stan. Szyfrogram $c^\star$ nazywamy wyzwaniem tego eksperymentu. Nie jest to wyzwanie z protokołu identyfikacji. Rysunek pokazuje podstawowy wariant z jednym szyfrogramem. Za chwilę rozszerzymy dostęp przeciwnika do dodatkowych usług. Boneh–Shoup, eksperyment 2.4.

W tym kursie przewaga zgadywania to:

Dwie wersje eksperymentu oznaczymy przez $G_0,G_1$, a zdarzenia sukcesu w nich przez $S_0,S_1$. Indeksy numerują eksperymenty, nie grupy algebraiczne. Różnica $|\Pr[S_0]-\Pr[S_1]|$ mówi, jak bardzo zmieniła się szansa sukcesu. To inna konwencja niż przewaga zgadywania. Przy przejściu między typowymi definicjami może pojawić się czynnik 2. Każde twierdzenie podaje swoją konwencję. Pełne wyjaśnienie zawiera rozdział o metodzie gier.

Zaniedbywalna oznacza tu więcej niż „mała w jednym pomiarze”. Funkcja $\nu(\lambda)$ jest zaniedbywalna, jeżeli dla każdego dodatniego wielomianu $p$ od pewnego $\lambda$ zachodzi $\nu(\lambda)<1/p(\lambda)$. Przykładem jest $2^{-\lambda}$. Funkcja $1/\lambda$ nie jest zaniedbywalna, choć dąży do zera.

Od podsłuchu do aktywnego przeciwnika

Najpierw oddzielmy dwie osie. Cel mówi, co przeciwnik ma osiągnąć, np. rozpoznać zaszyfrowaną wiadomość. Model dostępu mówi, jakie dane i usługi może wykorzystać. COA, KPA, CPA i CCA opisują możliwości ataku. Sam skrót nie ustala jeszcze formalnego zdarzenia wygranej. Angielskie rozwinięcia i polskie znaczenia są zebrane w słowniku modeli ataku.

Przy zgodnych ograniczeniach zasobów kolejne uprawnienia obejmują poprzednie. Usługa deszyfrująca w modelu zwraca tekst lub odrzucenie, oznaczane $\bot$. W rzeczywistym ataku wystarcza czasem informacja pośrednia, np. rozróżnialny błąd odbiorcy. Nie utożsamiamy jednak każdego komunikatu błędu z pełną wyrocznią deszyfrującą. Goldwasser–Bellare, modele ataków na szyfrowanie.

Ta sama gra IND, coraz szerszy dostęp

Teraz ustalamy jeden cel: odgadnąć bit wyboru między dwiema wiadomościami tej samej długości. Zmieniamy tylko uprawnienia. Wyzwanie to szyfrogram $c^\star\leftarrow\mathsf{Enc}_k(m_b)$ otrzymany w tej grze, nie wyzwanie z protokołu identyfikacji.

IND oznacza nierozróżnialność. W CCA1 dostęp do deszyfrowania kończy się przed wyzwaniem. W CCA2 napastnik może reagować na otrzymane wyzwanie i odpowiedzi na kolejne dozwolone zapytania. Nie wolno pytać o deszyfrowanie samego $c^\star$, bo wtedy gra natychmiast ujawniłaby $m_b$. Wolno natomiast pytać o zmieniony szyfrogram. To właśnie taki dostęp musi przetrwać konstrukcja odporna na CCA2. Bellare, Desai, Pointcheval, Rogaway, Relations among Notions of Security for Public-Key Encryption Schemes.

Zapytania przed wyzwaniem mogą zależeć od wcześniejszych odpowiedzi również w CCA1. Różnica między CCA1 i CCA2 dotyczy dostępu do deszyfrowania po wyzwaniu, a nie zakazu reagowania na wcześniejsze odpowiedzi.

Dlaczego silniejszy model daje mocniejszą gwarancję

Dla tej samej rodziny schematów, zgodnych reguł wyzwania i odpowiednio rozliczonych zasobów zachodzi:

Strzałki gwarancji biegną przeciwnie do rozszerzania uprawnień. Przeciwnik słabszego modelu jest szczególnym przypadkiem przeciwnika silniejszego: po prostu nie korzysta z części usług. Jeśli schemat wytrzymuje wszystkich dozwolonych przeciwników silniejszego modelu, wytrzymuje również tę podklasę. W drugą stronę taki argument nie działa.

Szyfrowanie publiczne jest szczególne. Mając klucz publiczny, napastnik sam szyfruje wybrane teksty. Dlatego dodatkowa wyrocznia szyfrująca nie daje mu nowej możliwości. Rozróżnienie EAV–CPA zyskuje znaczenie przede wszystkim dla szyfrowania symetrycznego. Trzeba też pilnować, czy definicja dotyczy jednej wiadomości, wielu wiadomości lub schematu ze stanem. Nie zamieniamy między sobą tych definicji bez argumentu.

Konkretny skok możliwości: jednorazowa maska bitowa ukrywa jeden bit. Jeśli jednak tę samą maskę wykorzystamy ponownie i pozwolimy przeciwnikowi zaszyfrować zero, pozna maskę. Nie łamie to twierdzenia o jednorazowej masce. Łamie warunek jej jednorazowości. W W3 policzymy to dokładnie. Z kolei klasyczny ElGamal może spełniać IND-CPA przy założeniu DDH, lecz pozwala modyfikować szyfrogram. Dostęp CCA2 zamienia tę modyfikację w odzyskanie wiadomości, co pokazujemy rachunkiem i demonstracją w W10a.

DDH

Decisional Diffie–Hellman. Decyzyjny problem Diffiego–Hellmana.

Silniejszy model nie naprawia algorytmu. Ujawnia dodatkowe wymaganie. Odpowiedzią może być konstrukcja z uwierzytelnianiem szyfrogramów i dowodem, a nie zwiększenie samej długości klucza. W W4 poznamy AEAD. Standardowa poufność IND-CCA nie oznacza automatycznie uwierzytelnienia nadawcy, ochrony metadanych, odporności na wycieki z urządzenia ani bezpieczeństwa po utracie tajnego klucza. To osobne cele i rozszerzenia modelu. Boneh–Shoup, rozdziały 2, 5, 9 i 12.

IND-CCA

indistinguishability under chosen-ciphertext attack. Nierozróżnialność przy ataku z wybranym szyfrogramem. Zakres dostępu ustala definicja.

Przykład. Deterministyczne szyfrowanie tej samej wiadomości daje ten sam szyfrogram. Przy dostępie do szyfrowania przeciwnik może zapamiętać szyfrogram $m_0$ i porównać go z wyzwaniem. Długi klucz nie usuwa tego problemu.

Powiązania: C1. Literatura: Goldwasser–Bellare, Handbook of Applied Cryptography.

W2. Generatory i funkcje pseudolosowe

Pytanie: czym zastąpić długi losowy ciąg, gdy mamy tylko krótki sekret? Najpierw zdefiniujemy generator i rodzinę funkcji. W W3 poznamy szyfrowanie z prawdziwie losową maską. Dopiero wtedy porównamy je z maską z generatora i przeprowadzimy pierwszą redukcję.

Niech $U_n$ oznacza jednostajny ciąg $n$ bitów. Generator pseudolosowy $\mathsf{PRG}:\{0,1\}^n\to\{0,1\}^{\ell}$, gdzie $\ell>n$, rozwija krótki zalążek. Wymagamy, aby wydajny algorytm nie odróżniał $\mathsf{PRG}(U_n)$ od $U_\ell$ z niezaniedbywalną przewagą.

Wiele wiadomości i PRF

Rodzina $F_k:\{0,1\}^n\to\{0,1\}^{\ell}$ jest funkcją pseudolosową (PRF), jeżeli dostęp do jej wartości jest nierozróżnialny od dostępu do jednej losowej funkcji $R$ o tych samych dziedzinach. Powtórzenie argumentu daje tę samą odpowiedź także u $R$.

PRG rozwija jeden tajny zalążek. PRF obsługuje wiele wybranych argumentów pod jednym tajnym kluczem. Dla PRG porównujemy dwa rozkłady ciągów. Dla PRF porównujemy dwa interfejsy odpowiadające na zapytania. Funkcja $R$ pamięta odpowiedzi tak jak poznana wyrocznia losowa, ale w tym eksperymencie zastępuje funkcję z kluczem. Nie udostępniamy osobno jej pełnej tabeli.

PRG

pseudorandom generator. Generator pseudolosowy.

Bezpieczeństwo tych prymitywów jest założeniem o zachowaniu wobec wszystkich wydajnych rozróżniaczy. Test częstości bitów sprawdza tylko jeden rodzaj odchylenia. Nie wystarcza do ustanowienia tego założenia.

Powiązania: C3, pogłębienie: gry symetryczne.