Funzione pseudocasuale

In crittografia, una famiglia di funzioni pseudocasuali, o più semplicemente una famiglia PRF (dall'inglese pseudorandom function family), è un insieme di funzioni calcolabili in modo efficiente, tali che nessun algoritmo efficiente possa distinguere (se non con vantaggio trascurabile) tra una funzione scelta casualmente dalla famiglia PRF e una vera funzione casuale. Le funzioni pseudocasuali sono strumenti vitali nella costruzione di molte primitive crittografiche, in particolare i cifrari sicuri; in questo caso si fa spesso riferimento a una particolare sottoclasse delle funzioni pseudocasuali, ovvero le permutazioni pseudocasuali (spesso abbreviate in PRP).

Nelle applicazioni pratiche, i cifrari a blocchi vengono utilizzati nella maggior parte dei casi in cui è necessaria una funzione o una permutazione pseudocasuale; in generale, essi non costituiscono una famiglia di funzioni pseudocasuali, poiché i cifrari a blocchi come AES sono definiti solo per un numero limitato di dimensioni di input e chiave^[1].

Si consideri una famiglia di funzioni ${\displaystyle F:\{0,1\}^{n}\times \{0,1\}^{l(n)}\to \{0,1\}^{l(n)},}$dove il primo input è la chiave (una volta fissata la chiave ${\displaystyle k\in \{0,1\}^{n}}$, si ha una funzione ${\displaystyle F_{k}:\{0,1\}^{l(n)}\to \{0,1\}^{l(n)}}$), dove ${\displaystyle l(\cdot ):\mathbb {N} \to \mathbb {N} }$. Per semplicità si può assumere ${\displaystyle l(n)=n}$.

Una tale famiglia di funzioni è pseudocasuale se sono soddisfatte le seguenti condizioni:

• Per ogni scelta di ${\displaystyle k}$ e ${\displaystyle x}$, esiste sempre un algoritmo efficiente (in tempo polinomiale) per calcolare ${\displaystyle F_{k}(x)}$.
• Sia ${\displaystyle R_{n}}$ la distribuzione uniforme sull'insieme di tutte le funzioni che mappano stringhe di ${\displaystyle n}$ bit in stringhe di ${\displaystyle n}$ bit. Si richiede che ${\displaystyle F_{k}}$ e ${\displaystyle R_{n}}$ siano indistinguibili dal punto di vista computazionale, dove con ${\displaystyle n}$ si indica il parametro di sicurezza. Cioè, per qualsiasi avversario che può interrogare l'oracolo di una funzione campionata da ${\displaystyle F_{k}}$ o ${\displaystyle R_{n}}$, il vantaggio che può distinguere quale tipo di oracolo gli viene dato è trascurabile^[2].

In alcuni contesti è preferibile considerare definizioni più deboli di pseudocasualità; in particolare, si possono definire alcune varianti nelle quali l'attaccante ha accesso a un oracolo per ${\displaystyle F_{k}}$, ma con qualche limitazione.

L'attaccante ha accesso a un oracolo per ${\displaystyle F_{k}}$ che campiona una stringa ${\displaystyle x}$ in modo uniforme e restituisce la coppia ${\displaystyle (x,F_{k}(x))}$. A differenza della definizione originale, quindi, l'attaccante non ha il controllo sulle stringhe di input.

L'attaccante può interrogare l'oracolo per ${\displaystyle F_{k}}$ una sola volta, passando un numero arbitrario di stringhe ${\displaystyle x_{i}}$. L'oracolo restituisce ${\displaystyle F_{k}(x_{i}),\forall i}$. In questo caso, dunque, la scelta delle stringhe di input deve essere effettuata prima di vedere una qualunque stringa di output.

L'attaccante accede all'oracolo che alla sua ${\displaystyle i}$-esima invocazione restituisce ${\displaystyle F_{k}(i)}$.

Una funzione ${\displaystyle f}$ è una permutazione pseudocasuale se:

• è una funzione pseudocasuale
• è biettiva

Nel 1988 Luby e Rackoff hanno dimostrato che è possibile costruire permutazioni pseudocasuali "forti" a partire da funzioni pseudocasuali^[3]. La costruzione, che prende il nome degli autori, si basa sulla rete di Feistel.

È stato dimostrato che le funzioni pseudocasuali esistono se e solo se esistono le funzioni unidirezionali (one-way)^[4].

Una famiglia di funzioni pseudocasuali può essere costruita da qualsiasi generatore pseudocasuale (o PRG), usando, ad esempio, la costruzione GGM, che prende il nome da Goldreich, Goldwasser e Micali^[5].

Dato un generatore pseudocasuale ${\displaystyle G:\{0,1\}^{n}\to \{0,1\}^{2n}}$, è possibile creare una PRF ${\displaystyle F_{k}:\{0,1\}^{n}\to \{0,1\}^{n}}$. In particolare, siano ${\displaystyle G_{0}(\cdot )}$ e ${\displaystyle G_{1}(\cdot )}$ rispettivamente la metà sinistra e la metà destra dell'output di ${\displaystyle G(\cdot )}$. Data una chiave ${\displaystyle k}$ scelta uniformemente nell'insieme ${\displaystyle \{0,1\}^{n}}$ e un input ${\displaystyle x=(x_{1},\dots x_{n})}$ di ${\displaystyle n}$ bit, si ha che$${\displaystyle F_{k}(x):=G_{x_{n}}(\dots (G_{x_{2}}(G_{x_{1}}(k))\dots )}$$è una PRF.

Si noti che tale costruzione non è efficiente poiché richiede ${\displaystyle n}$ invocazioni in sequenza del PRG sottostante. Un'alternativa è stata fornita da Naor e Reingold^[6] nel 1997: la loro costruzione, tuttavia, si basa sui sintetizzatori pseudocasuali, un oggetto crittografico apparentemente più difficile da istanziare rispetto a un PRG.

Nel modello dell'oracolo casuale, assumendo quindi l'esistenza di un oracolo ${\displaystyle {\texttt {RO}}(\cdot )}$, è possibile definire una PRF nel seguente modo:$${\displaystyle F_{k}(x):={\texttt {RO}}(k||x)}$$

Si può dimostrare^[7] che una PRF è sufficiente per costruire un cifrario simmetrico ${\displaystyle \Pi }$ che sia CPA-sicuro. Sia ${\displaystyle F(\cdot ):\{0,1\}^{n}\to \{0,1\}^{n}}$ una PRF (eventualmente debole), allora ${\displaystyle \Pi =({\texttt {KGen}},{\texttt {Enc}},{\texttt {Dec}})}$ con:

• ${\displaystyle k\leftarrow {\texttt {KGen}}(1^{n})}$ campiona una chiave ${\displaystyle k}$ di ${\displaystyle n}$ bit in modo uniforme
• ${\displaystyle {\texttt {Enc}}_{k}(m)=(r,F_{k}(r\oplus m)),r\in \{0,1\}^{n}}$genera un crittotesto ${\displaystyle c}$, campionando in modo uniforme una stringa ${\displaystyle r}$ di ${\displaystyle n}$ bit
• ${\displaystyle {\texttt {Dec}}_{k}(c)={\texttt {Dec}}_{k}(c_{1},c_{2})=F_{k}(c_{1})\oplus c_{2}}$ recupera il messaggio ${\displaystyle m}$

La dimostrazione che il precedente schema sia CPA-sicuro si basa su una riduzione alla sicurezza di ${\displaystyle F}$: se, infatti, esistesse un attaccante efficiente in grado di rompere ${\displaystyle \Pi }$ in un gioco CPA, allora si potrebbe anche distinguere con un algoritmo efficiente ${\displaystyle F}$ da una funzione veramente casuale.

La costruzione proposta presenta un crittotesto di lunghezza doppia rispetto all'input. Si può fare a meno di inviare ${\displaystyle c_{1}}$ se si adotta una modalità contatore: viene campionata una e una sola volta una stringa ${\displaystyle r}$ di ${\displaystyle n}$ bit in modo uniforme. Quando si vuole cifrare un messaggio si incrementa il contatore ${\displaystyle r}$ da passare all'algoritmo ${\displaystyle {\texttt {Enc}}}$. Tale soluzione richiede che le due controparti mantengano uno stato (il valore di ${\displaystyle r}$) per poter funzionare in modo corretto.

Una delle applicazioni più naturali e immediate delle funzioni pseudocasuali è la costruzione dei codici autenticatori di messaggio (o semplicemente MAC). La seguente costruzione è dovuta a Goldreich, Goldwasser e Micali^[8]:

• ${\displaystyle s\leftarrow {\texttt {Gen}}(1^{n})}$ campiona una chiave segreta ${\displaystyle s}$ di ${\displaystyle n}$ bit in modo uniforme. Tale chiave è condivisa tra chi manda il messaggio (Alice) e chi lo riceve (Bob)
• ${\displaystyle {\texttt {Tag}}_{s}(m)=F_{s}(m)}$ genera l'autenticatore ${\displaystyle \phi }$
• ${\displaystyle {\texttt {Vrfy}}_{s}(m,\phi )}$ verifica che ${\displaystyle \phi }$ sia uguale a ${\displaystyle {\texttt {Tag}}_{s}(m)}$

Un metodo molto semplice ed efficiente per generare chiavi crittografiche ${\displaystyle k_{i}}$ consiste nel passare l'indice i alla funzione pseudocasuale, dopo aver generato una chiave ${\displaystyle s}$: quindi, ${\displaystyle k_{i}=F_{s}(i)}$. Tale sistema si dimostra sicuro finché la chiave ${\displaystyle s}$ rimane privata e non viene compromessa.

• Daniele Venturi, Crittografia nel Paese delle Meraviglie, collana UNITEXT, Springer Milan, 2012, DOI:10.1007/978-88-470-2481-6, ISBN 978-88-470-2480-9. URL consultato il 16 gennaio 2020.
• (EN) Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge, Cambridge University Press, 2001, ISBN 978-0-511-54689-1.
• (EN) Jonathan Katz, Introduction to modern cryptography, Chapman & Hall/CRC, 2008, ISBN 978-1-58488-551-1, OCLC 137325053. URL consultato il 16 gennaio 2020.

Portale Crittografia: accedi alle voci di Teknopedia che trattano di crittografia