Os acidentes não são aleatórios: quem são as famílias das funções pseudo-aleatórias (PRFs)

Em 1984, Goldreich, Goldwasser e Micali formalizaram o conceito de funções pseudo-aleatórias e propuseram uma implementação de PRF baseada em um gerador pseudo-aleatório (PRG) com duplicação de comprimento. Desde então, as funções pseudo-aleatórias provaram ser uma abstração extremamente importante que encontrou aplicações em vários campos, como autenticação de mensagens e prova de teoremas. Neste artigo vou explicar:





  • O que são funções aleatórias (RF)





  • O que são funções pseudo-aleatórias (PRF)





  • Quem são essas suas famílias?





  • PRF vs. PRG





  • O que as cifras de bloco têm a ver com isso?





Aleatoriedade

Já pelo nome fica claro que uma função pseudo-aleatória é algo que "se parece" com uma função aleatória. Bem, o que é uma função aleatória no nosso caso? Para começar, limitaremos nosso escopo de consideração às funções que exibem uma sequência de zeros e uns com o comprimento de numa sequência de zeros e uns do mesmo comprimento n, isto é





\ underbrace {1110 ... 0010} _ {n} \ rightarrow \ underbrace {0100 ... 0011} _ {n} \ Leftrightarrow \ {0,1 \} ^ n \ rightarrow \ {0,1 \} ^ n

De um modo geral, isso pode ser evitado e podemos considerar o mapeamento de strings de um comprimento para strings de outro comprimento, mas neste caso é preciso prestar atenção às diferenças de dimensões. A seguir, apresentamos o conjunto de todas as funções que realizam o mapeamento \ {0,1 \} ^ n \ rightarrow \ {0,1 \} ^ ne o denotam \ text {Func} _n.





Considere a cardinalidade deste conjunto. É óbvio isso | {\ text {Func} _n} |  = 2 ^ {n2 ^ n}.





-
\ text {Strings distintas totais de comprimento} n \ espaço - \ espaço 2 ^ n. \ text {Para armazenar} 2 ^ n \ text {linhas que você precisa} n2 ^ n \ text {bits.}\ text {Estes} n2 ^ {n} \ text {bits e definirá o mapeamento desejado} 2 ^ n \ text {linhas.}\ text {E haverá um total de tais mapeamentos} 2 ^ {n2 ^ n}.





. – \ text {Func} _n. , 2 ^ n - 2 ^ n. ,





P (f (x) = y_0) = 2 ^ {- n}

f\ text {Func} _n, y_0 – .





, – - , . , .





, :





P (f (x) \ in \ {\ forall y: primeiro \ bit de espaço = 1 \}) = \ frac {1} {2}

, :





P (f (x) \ in \ {\ forall y: último \ bit de espaço = 1 \}) = \ frac {1} {2}

n :





P (f (x) \ in \ {\ forall y: número \ espaço zeros = número \ espaço uns \}) = \ frac {1} {2 ^ n} \ begin {pmatrix} n \\ n / 2 \ end {pmatrix}

\ begin {pmatrix} n \\ n / 2 \ end {pmatrix}n n / 2 ( n / 2 n ).





. , , 20 . :





P (A_i (f (x)) = 1)

, , \ varejpsilon:





| P (A_i (f (x)) = 1) -P (A_i (F (x)) = 1) |  <\ varepsilon

f (x) – , F (x) – , .





. -, , , ? , . .





F(t, \ varepsilon)-, UMA , t





| P (A (f (x)) = 1) -P (A (F (x)) = 1) |  <\ varepsilon

, , , , . , , , F_k :





F_k (x) = F (k, x), , \ {0,1 \} ^ m \ times \ {0,1 \} ^ n \ rightarrow \ {0,1 \} ^ l, F_k . k .





m = l = n.





, k .





\ {0,1 \} ^ n \ rightarrow \ {0,1 \} ^ n \ text {Func} _n. , F_k \ text {Func} _n.





, , , :





F_k , k D F_k f \ in \ text {Func} _n.





, , . , - . , . , . , - x_0 y_0, , , x_0, y_1 \ neq y_0. , , - , . , . . , , F_k, , k ( ).





PRF vs. PRG

PRG – . , . , PRG – PRF, PRF – PRG. , PRG, . , PRG (), n (seed) m> n. , PRG , PRF , . .





G (k) = F_k (0 ... 0) | F_k (0 ... 1)

| – , PRG PRF. , . , PRF , PRG.





PRF F_k , . , , F_k k. F ^ {- 1} (y) .





, . , : , n, F_k, k , , () .





, , AES.





. , .





P.S. . , . , c:





P.P.S. – .





Como construir funções aleatórias - tyk





Funções pseudo- aleatórias: três décadas depois - tyk





Introdução à Criptografia Moderna - tyk





Funções pseudo - aleatórias e cifras de bloco - tyk












All Articles