Função pseudo-aleatória

Uma função pseudo-aleatória (ou PRF para função pseudo-aleatória ) é uma função cujo conjunto de saídas possíveis não é efetivamente distinguível das saídas de uma função aleatória. Esta noção não deve ser confundida com a do gerador de números pseudo-aleatórios (PRNG). Uma função que é um PRNG garante apenas que uma de suas saídas, considerada sozinha, apareça aleatória se sua entrada tiver sido escolhida aleatoriamente. Por outro lado, uma função pseudo-aleatória garante isso para todas as suas saídas , independentemente do método de escolha da entrada.

Na criptografia, esse tipo de função é extremamente importante: ela serve como um bloco de construção básico para o projeto de primitivas criptográficas , em particular para algoritmos de criptografia .

Definição

Formalmente, uma função pseudo-aleatória é uma função , onde representa o espaço das chaves, representa o domínio da função e sua imagem . ${\ displaystyle {\ mathcal {F}}: {\ mathcal {K}} \ times {\ mathcal {X}} \ to {\ mathcal {Y}}}$ ${\ displaystyle {\ mathcal {K}}}$ ${\ mathcal {X}}$ ${\ mathcal {Y}}$

A definição de segurança associada é dada pelo fato de que qualquer polinômio adversário é incapaz de distinguir entre a saída da saída de uma função aleatória no mesmo domínio, condicionado à escolha da chave . ${\ displaystyle {\ mathcal {F}} (k, \ cdot)}$ ${\ displaystyle k \ in {\ mathcal {K}}}$

Construção

A existência de funções unilaterais é suficiente para construir funções pseudo-aleatórias. Na verdade, é possível construir um gerador pseudo-aleatório ( PRG ) a partir de funções unilaterais, e é possível construir uma função pseudo-aleatória a partir de um gerador pseudo-aleatório.

Formulários

Criptografia semanticamente segura

A existência de uma função pseudo-aleatória torna possível projetar um esquema de criptografia simétrica semanticamente seguro pela seguinte construção. Intuitivamente, consiste em usar a saída da função pseudo-aleatória como uma saída uniforme para usá-la como máscara descartável . A vantagem está no fato de que a chave aqui não é mais tão longa quanto a mensagem, mas vai depender da chave usada e do tamanho do aleatório (que depende da entrada da função pseudo-aleatória ). ${\ mathcal {F}}$ ${\ mathcal {F}}$

Geração de chave : uma chave é gerada aleatoriamente no espaço de chave do PRF. ${\ displaystyle k \ gets _ {\ $} {\ mathcal {K}}}$
Criptografar : para criptografar uma mensagem com a chave , a mensagem criptografada é calculada da seguinte maneira: m{\ displaystyle m} $m$ k{\ displaystyle k} $k$
- Desenhe um perigo . ${\ displaystyle r \ gets _ {\ $} {\ mathcal {X}}}$
- Reenvie a mensagem criptografada:, onde é o bit a bit exclusivo ou . ${\ displaystyle C = (r, F (k, r) \ oplus m)}$ $\ oplus$
Decrypt : Para decifrar uma mensagem com a chave é calculado: . ${\ displaystyle C = (c_ {1}, c_ {2})}$ $k$ ${\ displaystyle m '= F (k, c_ {1}) \ oplus c_ {2}}$

A correção é verificada pelo fato de ser involutiva . $\ oplus$

A segurança é obtida pela redução do tempo polinomial da segurança da criptografia pseudo-aleatória. Em outras palavras, se um oponente foi capaz de distinguir entre o esquema apresentado acima e uma sequência aleatória, então alguém poderia usá-lo diretamente para distinguir entre uma mensagem construída usando uma função pseudo-aleatória e uma função verdadeiramente aleatória, caso em que o a cifra seria distribuída uniformemente sobre o espaço da cifra (o exclusivo ou de uma constante (aqui uma mensagem) por uma função uniforme é distribuída como uma função uniforme). ${\ displaystyle (c_ {1}, c_ {2})}$

Bibliografia

[Katz and Lindell 2014] (en) Jonathan Katz e Yehuda Lindell, Introdução à Criptografia Moderna, 2ª Edição , Boca Raton, Chapman e Hall ,2014, 583 p. ( ISBN 978-1-4665-7026-9 , leia online ) , "Capítulo 3.6.1 Funções pseudo-aleatórias"
[Håstad et al. 1999] (en) Johan Håstad, Russell Impagliazzo, Leonid A. Levin e Michael Luby, " A pseudo-gerador aleatório de qualquer função unilateral " , SIAM Journal of Computing ,1999( DOI 10.1137 / S0097539793244708 )