Permutacja pseudolosowa

W kryptografii permutacja pseudolosowa (PRP) to funkcja, której nie można odróżnić od permutacji losowej (to znaczy permutacji wybranej losowo z jednakowym prawdopodobieństwem z rodziny wszystkich permutacji w dziedzinie funkcji) przy praktycznym wysiłku.

Definicja

Niech F będzie odwzorowaniem ${\ Displaystyle \ lewo \ {0,1 \ prawo \} ^ {n} \ razy \ lewo \ {0,1 \ w prawo\}^{s}\rightarrow \left\{0,1\right\}^{n}}$ . F jest PRP wtedy i tylko wtedy, gdy

${\ Displaystyle K \ w \ lewo \ {0,1 \ prawo \} ^ {s}}$ ∈ fa $\ Displaystyle F_ {K}}$ jest bijekcją od $gdzie$ $_$ K _ ${\ Displaystyle F_ {K} (x) = F (x, K)}$ .
Dla $.$ „ $_ {K} (x)}$ dla dowolnego ${\ Displaystyle x \ in \ lewo \ {0,1 \ prawo \} ^ {n}}$ ,.
wyróżników wielomianowych w czasie ${\ displaystyle D}$ : ${\ Displaystyle \ lewo | Pr \ lewo (D ^ {F_ {K}} (1 ^ {n}) = 1 \ prawo) -Pr \ lewo (D ^ {f_ {n}} (1 ^ {n}) = 1 \ prawej) \ prawej | <\ varepsilon (s)}$ , gdzie ${\ Displaystyle K \ in \ lewo \ {0,1 \ prawej \} ^ {s}}$ jest wybierane równomiernie w $wybierany jednostajnie losowo$ i jest zbioru permutacji n -bitowych łańcuchów.

Rodzina permutacji pseudolosowych to zbiór permutacji pseudolosowych, w których za pomocą klucza można wybrać określoną permutację.

Model szyfrów blokowych

Wyidealizowana abstrakcja (kluczowego) szyfru blokowego jest prawdziwie losową permutacją odwzorowań między tekstem jawnym a tekstem zaszyfrowanym. Jeśli istnieje algorytm rozróżniający, który osiąga znaczną przewagę przy mniejszym wysiłku niż określony przez parametr bezpieczeństwa szyfru blokowego (zwykle oznacza to, że wymagany wysiłek powinien być mniej więcej taki sam, jak przeszukiwanie przestrzeni klucza szyfru metodą siłową), wówczas szyfr jest uważany za złamany przynajmniej w sensie certyfikacyjnym, nawet jeśli taka przerwa nie prowadzi od razu do praktycznego zabezpieczenia awaria.

Oczekuje się, że nowoczesne szyfry będą miały super pseudolosowość. Oznacza to, że szyfr powinien być nie do odróżnienia od losowo wybranej permutacji w tej samej przestrzeni wiadomości, nawet jeśli przeciwnik ma dostęp do czarnej skrzynki do kierunku do przodu i do tyłu szyfru.

Połączenia z funkcją pseudolosową

Michael Luby i Charles Rackoff wykazali, że „silną” permutację pseudolosową można zbudować z funkcji pseudolosowej przy użyciu konstrukcji Luby-Rackoff , która jest zbudowana przy użyciu szyfru Feistela .

Pojęcia pokrewne

Nieprzewidywalna permutacja

Nieprzewidywalna permutacja ( UP ) F _k jest permutacją , której wartości nie można przewidzieć za pomocą szybkiego losowego algorytmu . Nieprzewidywalne permutacje mogą być używane jako prymityw kryptograficzny , element konstrukcyjny systemów kryptograficznych o bardziej złożonych właściwościach.

Przeciwnikiem nieprzewidywalnej permutacji jest algorytm, który ma dostęp do wyroczni zarówno dla operacji permutacji do przodu, jak i odwrotnych . Przeciwnik otrzymuje wyzwanie wejściowe k i jest proszony o przewidzenie wartości F _k . Dozwolone jest wykonanie serii zapytań do wyroczni, aby pomóc jej w dokonaniu tej prognozy, ale nie wolno pytać o wartość k .

Losowy algorytm generowania permutacji generuje nieprzewidywalną permutację , jeśli jego wyjściami są permutacje na zbiorze elementów (opisanych przez długość- n ciągów binarnych), których przeciwnik nie może przewidzieć z dokładnością znacznie lepszą niż losowość przez przeciwnika, który tworzy wielomian (w n ) liczba zapytań do wyroczni przed rundą wyzwania, których czas wykonania jest wielomianowy w n i których prawdopodobieństwo błędu jest mniejsze niż 1/2 dla wszystkich instancji. Oznacza to, że nie można tego przewidzieć w klasie złożoności PP , relatywizowane przez wyrocznię dla permutacji.

Właściwości nieprzewidywalnych permutacji

Można wykazać, że funkcja Fk nie jest kodem uwierzytelniania bezpiecznej wiadomości (MAC), jeśli spełnia tylko wymóg nieprzewidywalności _. Można również pokazać, że nie można zbudować wydajnego MAC o zmiennej długości wejściowej z szyfru blokowego, który jest modelowany jako UP z n bitów. Wykazano, że wyjście okrągłej konstrukcji Feistela a k = n / ω (log λ ) z nieprzewidywalnymi funkcjami okrągłymi może przepuszczać wszystkie pośrednie wartości okrągłe. Nawet w przypadku realistycznych funkcji nieprzewidywalnych (UF) niektóre częściowe informacje o zaokrąglonych wartościach pośrednich mogą wyciekać przez dane wyjściowe. Później wykazano, że jeśli zastosuje się superlogarytmiczną liczbę rund w konstrukcji Feistela, to wynikowa konstrukcja UP jest bezpieczna, nawet jeśli przeciwnik otrzyma wszystkie pośrednie wartości rund wraz z wynikiem permutacji.

Istnieje również udowodnione w tym względzie twierdzenie, które mówi, że jeśli istnieje skuteczny przeciwnik UP A _π , który ma niebagatelną przewagę ε _π w grze nieprzewidywalności przeciwko konstrukcji UP ψ _{U, k} i który tworzy liczbę wielomianową zapytania do pretendenta, to istnieje również przeciwnik UF A _f , który ma istotną przewagę w grze nieprzewidywalności przeciwko UF próbkowanemu z rodziny UF F . Na tej podstawie można wykazać, że maksymalna przewaga przeciwnika UP A _π jest ε _π = O ( ε _{fa .} ( qk ) ⁶ ). Tutaj ε _f oznacza maksymalną przewagę przeciwnika UF działającego w czasie O( t + ( qk ) ⁵ ) nad UF próbkowanym z F , gdzie t to czas działania przeciwnika PRP A _ψ , a q to liczba wykonanych zapytań przez to.

Ponadto schemat podpisu, który spełnia właściwość nieprzewidywalności i niekoniecznie pseudolosowości, jest zasadniczo weryfikowalną nieprzewidywalną funkcją (VUF). Weryfikowalna nieprzewidywalna funkcja jest definiowana analogicznie do weryfikowalnej funkcji pseudolosowej (VRF), ale pseudolosowość jest zastępowana słabszą nieprzewidywalnością. Weryfikowalne nieprzewidywalne permutacje to analogi permutacji VUF lub nieprzewidywalne analogi VRP. VRP jest również VUP, a VUP można faktycznie zbudować, budując VRP za pomocą konstrukcji Feistela zastosowanej do VRF. Ale nie jest to uważane za przydatne, ponieważ VUF wydają się być znacznie łatwiejsze do zbudowania niż VRF.

Aplikacje

DES

K x X → X ∀ X={0,1} ⁶⁴ , K={0,1} ⁵⁶

AES-128

K x X → X ∀ k=X={0,1} ¹²⁸

Zobacz też

Szyfr blokowy (rodziny permutacji pseudolosowych działające na blokach bitów o stałym rozmiarze)
Szyfrowanie z zachowaniem formatu (rodziny permutacji pseudolosowych działające na dowolnych skończonych zbiorach)