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.

Definizione formale

Si consideri una famiglia di funzioni $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 $k\in \{0,1\}^{n}$, si ha una funzione $F_{k}:\{0,1\}^{l(n)}\to \{0,1\}^{l(n)}$), dove $l(\cdot ):\mathbb {N} \to \mathbb {N}$. Per semplicità si può assumere $l(n)=n$.

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

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

Alcune varianti

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 $F_{k}$, ma con qualche limitazione.

Funzione pseudocasuale debole

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

Funzione pseudocasuale non adattiva

L'attaccante può interrogare l'oracolo per $F_{k}$ una sola volta, passando un numero arbitrario di stringhe $x_{i}$. L'oracolo restituisce $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.

Funzione pseudocasuale sequenziale

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

Permutazione pseudocasuale

Una funzione $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. La costruzione, che prende il nome degli autori, si basa sulla rete di Feistel.

Costruzioni teoriche

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

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.

Costruzione GGM

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

$$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 $n$ invocazioni in sequenza del PRG sottostante. Un'alternativa è stata fornita da Naor e Reingold nel 1997: la loro costruzione, tuttavia, si basa sui sintetizzatori pseudocasuali, un oggetto crittografico apparentemente più difficile da istanziare rispetto a un PRG.

Costruzione nel modello del Random Oracle

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

$$F_{k}(x):={\texttt {RO}}(k||x)$$

Applicazioni

Cifrari simmetrici

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

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

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

Un'alternativa

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

Codici autenticatori di messaggio (MAC)

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:

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

Derivazione di una chiave

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

Bibliografia

• 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.