Twardy predykat

W kryptografii twardym predykatem funkcji jednokierunkowej f jest predykat b ( tzn . _ (x) . Z formalnego punktu widzenia nie ma probabilistycznego algorytmu czasu wielomianowego (PPT) , który oblicza b(x) z f(x) z prawdopodobieństwem znacznie większym niż połowa losowego wyboru x . Innymi słowy, jeśli x jest rysowane równomiernie losowo, to biorąc pod uwagę f(x) , każdy przeciwnik PPT może rozróżnić tylko twardy bit b(x) i jednolicie losowy bit z pomijalną przewagą nad długością x .

W podobny sposób można zdefiniować funkcję twardą . Oznacza to, że jeśli x zostanie wybrane jednostajnie losowo, to przy danym f(x) dowolny algorytm PPT może rozróżnić tylko wartość funkcji twardego rdzenia h(x) i jednakowo losowe bity o długości |h(x)| ze znikomą przewagą nad długością x .

Twardy predykat oddaje „w skoncentrowanym sensie” twardość odwracania f .

Chociaż trudno jest odwrócić funkcję jednokierunkową, nie ma gwarancji co do wykonalności obliczenia częściowej informacji o przedobrazie c z obrazu f(x) . Na przykład, chociaż RSA jest funkcją jednokierunkową, symbol Jacobiego przedobrazu można łatwo obliczyć na podstawie symbolu obrazu.

Oczywiste jest, że jeśli funkcja jeden do jednego ma twardy predykat, to musi być jednokierunkowa. Oded Goldreich i Leonid Levin (1989) pokazali, jak każdą funkcję jednokierunkową można w prosty sposób zmodyfikować, aby uzyskać funkcję jednokierunkową, która ma określony predykat twardy. Niech f będzie funkcją jednokierunkową. Zdefiniuj g(x,r) = (f(x), r) gdzie długość r jest taka sama jak x . Niech x _j oznacza j- ^ty bit x i r _j j - ty ^bit r . Następnie

${\ Displaystyle b (x, r): = \ langle x, r \ rangle = \ bigoplus _ {j} x_ {j} r_ {J}}$

jest twardym rdzeniem predykatu g . Zauważ, że b(x, r) = < x, r > gdzie <·, ·> oznacza standardowy iloczyn wewnętrzny w przestrzeni wektorowej ( Z ₂ ) ⁿ . Ten predykat jest trudny ze względu na problemy obliczeniowe; to znaczy nie jest to trudne do obliczenia, ponieważ g(x, r) jest informacją teoretycznie stratną. Przeciwnie, jeśli istnieje algorytm, który wydajnie oblicza ten predykat, to istnieje inny algorytm, który może skutecznie odwrócić f .

Podobna konstrukcja daje twardą funkcję z bitami wyjściowymi O(log |x|) . Załóżmy, że f jest silną funkcją jednokierunkową. Zdefiniuj g(x, r) = (f(x), r) gdzie | r | = 2| x |. Wybierz funkcję długości l(n) = O(log n) st l(n) ≤ n . Pozwalać

${\ Displaystyle b_ {i} (x, r) = \ bigoplus _ {j} x_ {j} r_ {i + j}.}$

Wtedy h(x, r) := b ₁ (x, r) b ₂ (x, r) ... b _l(|x|) (x, r) jest funkcją hard-core o długości wyjściowej l(| x|) .

Czasami zdarza się, że rzeczywisty bit wejścia x jest twardy. Na przykład każdy pojedynczy bit danych wejściowych do funkcji RSA jest twardym predykatem RSA, a bloki O(log |x|) bitów x są nie do odróżnienia od losowych ciągów bitów w czasie wielomianowym (przy założeniu, że funkcja RSA trudno odwrócić).

Twarde predykaty umożliwiają skonstruowanie generatora pseudolosowego z dowolnej jednokierunkowej permutacji . Jeśli b jest twardym predykatem jednokierunkowej permutacji f , a s jest losowym ziarnem, to

${\ Displaystyle \ {b (f ^ {n} (s)) \} _ {n}}$

jest pseudolosową sekwencją bitów, gdzie f ⁿ oznacza n-tą iterację zastosowania f na s , a b jest generowanym twardym bitem w każdej rundzie n .

Twarde predykaty jednokierunkowych permutacji z pułapką (znane jako predykaty z pułapką ) mogą być używane do konstruowania semantycznie bezpiecznych schematów szyfrowania klucza publicznego.

Zobacz też

• Dekodowanie listy (opisuje dekodowanie listy; rdzeń konstrukcji Goldreicha-Levina twardych predykatów z funkcji jednokierunkowych można postrzegać jako algorytm dekodowania listy kodu Hadamarda ) .

• Oded Goldreich, Podstawy kryptografii, tom 1: podstawowe narzędzia , Cambridge University Press, 2001.