Crypto-IT

Funkcje pseudolosowe to efektywne deterministyczne funkcje, które produkują dane wyjściowe nierozróżnialne od ciągów losowych. Są tworzone na bazie generatorów pseudolosowych, jednak w przeciwieństwie do nich oprócz posiadanego wewnętrznego stanu, przyjmują również dodatkowe dane jako wejście. Dane wejściowe mogą mieć ustaloną i uporządkowaną postać, ale wyjście z funkcji pseudolosowej zawsze powinno sprawiać wrażenie całkowicie losowego ciągu bitów.

Funkcja pseudolosowa, której dane wyjściowe są nierozróżnialne od ciągu losowego, jest nazywana bezpieczną kryptograficznie.

Analogicznie można zdefiniować pseudolosowe permutacje. Generowane przez nie dane wyjściowe są nierozróżnialne od losowych ciągów danych.

Permutacja pseudolosowa, której wyjście jest nierozróżnialne od losowego ciągu jest nazywana bezpieczną kryptograficznie. Można dowieść, że bezpieczna kryptograficznie pseudolosowa permutacja zdefiniowana na wystarczająco dużym zbiorze X jest również bezpieczną kryptograficznie funkcją pseudolosową (jest to tak zwane PRF Switching Lemma).

Mając dany kryptograficznie bezpieczny generator pseudolosowy G, jest możliwe utworzenie kryptograficznie bezpiecznej funkcji pseudolosowej F.

Niech G zwraca dwa razy więcej bitów, niż wynosi wielkość jego stanu wewnętrznego:
    G: K -> K²

Można zdefiniować jednobitową funkcję pseudolosową:
    F: K x {0, 1} -> K
jako:
    F(k, b) = G(k)[b]
gdzie:
    b może być równe 0 lub 1.

Tak określona funkcja F zwraca pierwszą lub drugą połowę danych wyjściowych tworzonych przez dany generator, bazując na otrzymanym jednym bicie wejściowym.

Jeżeli generator G jest kryptograficznie bezpieczny, to funkcja F również jest kryptograficznie bezpieczna.

Następnie, posiadany generator G można rozszerzyć, definiując nowy generator G₁:
    G₁: K -> K⁴
jako:
    G₁(k) = G(G(k)[0]) || G(G(k)[1])

Analogicznie można teraz zdefiniować rozszerzoną pseudolosową funkcję F₁, działającą na podwójnej ilości danych wejściowych:
    F₁: K x {0, 1}² -> K
jako:
    F₁(k, c) = G₁(k)[c]
gdzie:
    c to dwa dowolne bity.

Zaprezentowaną procedurę można powtórzyć dowolną ilość razy otrzymując dowolnie dużą funkcję pseudolosową. Jest to metoda tworzenia funkcji pseudolosowych nazwana od nazwisk jej twórców Konstrukcją Goldreich-Goldwasser-Micali (ang. Goldreich-Goldwasser-Micali Construction).

Można wykazać, że jeżeli generator G jest kryptograficznie bezpieczny, to bazująca na nim funkcja pseudolosowa działająca na danych wejściowych o długości n bitów i zdefiniowana w sposób przedstawiony powyżej, jest również kryptograficznie bezpieczna.