Hidden Fields Equations

Le Hidden Fields Equations (HFE), in italiano funzioni a campi nascosti, altrimenti note come funzioni botola (trapdoor functions in inglese), sono un sistema crittografico a chiave pubblica presentato per la prima volta all'Eurocrypt, nel 1996, dal francese Jacques Patarin, il quale lo elaborò seguendo le idee preesistenti nel sistema di Matsumoto e Imai. Tale sistema è basato sull'utilizzo di polinomi in campi finiti $\mathbb {F} _{q}$ dotati di diversa dimensione, in modo tale da mascherare la relazione tra chiave pubblica e chiave privata. La famiglia di sistemi crittografici HFE si basa sulla difficoltà nel trovare le soluzioni di un sistema a equazioni quadratiche multivariate (chiamato anche Problema MQ). Le HFE hanno trovato un campo applicativo anche nella costruzione di schemi per la firma digitale, come ad esempio Quartz and Sflash.^[1]

Basi matematiche

Una delle nozioni principali da assimilare per comprendere in che modo le HFE funzionino è capire che per due estensioni di campo $\mathbb {F} _{q^{n}}$ e $\mathbb {F} _{q^{m}}$ , entrambe contenute nel campo base $\mathbb {F} _{q}$ , una delle due estensioni può interpretare un sistema a $m$ polinomi multivariati in $n$ variabili, contenuto in $\mathbb {F} _{q}$ e rappresentato dalla funzione $\mathbb {F} _{q^{n}}\to \mathbb {F} _{q^{m}}$ , utilizzando una base adatta di $\mathbb {F} _{q^{n}}$ su $\mathbb {F} _{q}$ . Nella quasi totalità delle applicazioni i polinomi sono quadratici, ovvero di grado 2.^[2] Partiamo dalla tipologia più semplice di polinomi, chiamati monomi, e verrà mostrato in che modo questi conducono ai sistemi quadratici di equazioni.

Sia $\mathbb {F} _{q}$ un campo finito, dove $q$ è una potenza di 2, e sia $K$ un'estensione di campo. Sia $\beta _{1},...,\beta _{n}$ una base di $K$ come spazio vettoriale di $\mathbb {F} _{q}$ . Sia $0<h<q^{n}$ tale che $h=q^{\theta }+1$ sia verificato per distinti valori di $\theta$ e il massimo comune divisore (MCD) sia $(h,q^{n}-1)=1$ e si prenda un elemento casuale $u\in \mathbb {F} _{q^{n}}$ . Si rappresenti $u$ rispetto alla base come $u=(u_{1},...,u_{n})$ . Si definisca $v\in \mathbb {F} _{q^{n}}$ attraverso

v=u^{q^{\theta }}u\ \ \ \ (1)

La condizione del MCD è equivalente al richiedere che la funzione $u\to u^{h}$ su $K$ sia in corrispondenza uno a uno e che la sua inversa sia la funzione $u\to u^{h'}$ , dove $h'$ rappresenta l'inverso moltiplicativo di $h\ {\bmod {q}}^{n}-1$ . Si scelgano due trasformazioni affini riservate, ovvero due matrici $n\times n$ invertibili, come $S=\{S_{ij}\}$ e $T=\{T_{ij}\}$ con le voci appartenenti a $\mathbb {F} _{q}$ e due vettori $c=(c_{1},...,c_{n})$ e $d=(d_{1},...,d_{n})$ di dimensione $n$ su $\mathbb {F} _{q}$ e si definiscano $x$ e $y$ attraverso:

u=Sx+c\ \ \ \ v=Ty+d\ \ \ \ (2)

Sia $A^{(k)}={a_{ij}^{(k)}}$ una matrice di trasformazioni lineari nella base $\beta _{1},...,\beta _{n}$ in modo che

\beta _{i}^{q^{k}}=\sum _{j=1}^{n}a_{ij}^{k}\beta _{j},\ \ a_{ij}^{k}\in \mathbb {F} _{q}

per $1\leq i,k\leq n$ . Si scrivano tutti gli elementi della basi in relazione alle basi stesse, ovvero:

\beta _{i}\beta _{j}=\sum _{l=1}^{n}m_{ijl}\beta _{l},\ \ m_{ijl}\in \mathbb {F} _{q}

per ogni $1\leq i,j\leq n$ . Il sistema di $n$ equazioni che è esplicito in $v_{i}$ e quadratico in $u_{j}$ può essere ottenuto dall'espansione della (1) e uguagliando a zero i coefficienti di $\beta _{i}$ . Usando le relazioni affini nella (2) per rimpiazzare $u_{j},v_{i}$ con $x_{k},y_{l}$ , il sistema di $n$ equazioni è lineare in $y_{l}$ e di secondo grado in $x_{k}$ . Applicando l'algebra lineare il sistema darà $n$ equazioni esplicite, una per ogni $y_{l}$ sotto forma di polinomi di secondo grado in $x_{k}$ .^[3]

Crittosistemi multivariati

L'idea di base della famiglia HFE, ciò che consente l'utilizzo di sistemi multivariati, è la costruzione della chiave privata a partire da un polinomio $P$ in una sconosciuta incognita $x$ e all'interno di un qualche campo finito $\mathbb {F} _{q^{n}}$ (normalmente il valore utilizzato è $q=2$ ). Questo polinomio può essere facilmente invertito in $\mathbb {F} _{q^{n}}$ , ovvero è fattibile trovare le soluzioni all'equazione $P(x)=y$ , ovviamente è condizione necessaria che tali soluzioni esistano. La trasformazione privata o decriptazione e/o la firma digitale sono basate su questa inversione. Come spiegato sopra $P$ può essere identificato con un sistema a $n$ equazioni $(p_{1},...,p_{n})$ a patto di utilizzare una base prestabilita. Per costruire il crittosistema il polinomio deve essere trasformato in modo tale che le informazioni pubbliche nascondano la struttura originale, evitando così delle possibili inversioni. Questo viene fatto visualizzando il campo finito $\mathbb {F} _{q^{n}}$ come uno spazio vettoriale in $\mathbb {F} _{q}$ e scegliendo due trasformazioni affini lineari $S$ e $T$ . La terzina $(S,P,T)$ costituisce la chiave privata. Il polinomio privato $P$ è definito in $\mathbb {F} _{q}$ .^[1]^[4] La chiave pubblica è $(p_{1},...,p_{n})$ . Qui sotto si vede il diagramma per l'MQ-trapdoor $(S,P,T)$ nelle HFE

{\text{input}}x\to x=(x_{1},...,x_{n}){\overset {{\text{secret}}:S}{\to }}x'{\overset {{\text{secret}}:P}{\to }}y'{\overset {{\text{secret}}:T}{\to }}{\text{output}}y

Polinomi HFE

Il polinomio privato $P$ con grado $d$ in $\mathbb {F} _{q^{n}}$ è un elemento di $\mathbb {F} _{q^{n}}[x]$ . Se i termini del polinomio $P$ hanno al massimo termini quadratici in $\mathbb {F} _{q}$ , allora questo manterrà le dimensioni del polinomio pubblico ridotte.^[1] Nel caso in cui $P$ sia costituito da monomi nella forma $x^{q^{s_{i}}+q^{t_{i}}}$ , ossia con una doppia potenza di $q$ come esponente, sia ha la forma base delle HFE, e quindi $P$ è scelto come:

P(x)=\sum c_{i}x^{q^{s_{i}}+q^{t_{i}}}

Il grado $d$ del polinomio è anche conosciuto come parametro sicurezza e maggiore è il valore maggiore sarà la sicurezza dal momento che il risultante set di equazioni quadratiche assomiglia, all'aumentare di $d$ , ad un set di equazioni scelto casualmente. Senza contare che un valore maggiore di $d$ rallenta significativamente la decriptazione. Questo dipende dal fatto che $P$ è un polinomio con grado di valore massimo uguale a $d$ , ciò comporta che l'inverso di $P$ , ossia $P^{-1}$ , può essere computato in $d^{2}(\ln d)^{O(1)}n^{2}\mathbb {F} _{q}$ operazioni.

Crittografia e decrittografia

La chiave pubblica è data dagli $n$ polinomi multivariati $(p_{1},...,p_{n})$ in $\mathbb {F} _{q}$ . È quindi necessario trasferire il messaggio $M$ da $\mathbb {F} _{q^{n}}\to \mathbb {F} _{q}^{n}$ per poterlo criptare, ossia si assume che $M$ sia un vettore $(x_{1},...,x_{n})\in \mathbb {F} _{q}^{n}$ . Per criptare il messaggio $M$ si valutano tutti i $p_{i}$ in $(x_{1},...,x_{n})$ . Il testo cifrato risulta quindi $(p_{1}(x_{1},...,x_{n}),p_{2}(x_{1},...,x_{n}),...,p_{n}(x_{1},...,x_{n}))\in \mathbb {F} _{q}^{n}$ .

Per comprendere meglio la decriptazione la si esprima in termini di $S,T,P$ . Si noti che questi non sono disponibili al mittente. Valutando i $p_{i}$ del messaggio viene in primo luogo applicata $S$ , che porta $x'$ come risultato. A questo punto $x'$ viene trasformato da $\mathbb {F} {q^{n}}\to \mathbb {F} _{q^{n}}$ in modo da poter applicare il polinomio privato $P$ che appartiene a $\mathbb {F} _{q^{n}}$ dando come risultato $y'\in \mathbb {F} _{q^{n}}$ . Di nuovo, $y'$ viene trasferito al vettore $(y_{1}',...,y_{n}')$ . Come ultimo passo viene applicata la trasformazione $T$ e l'output finale $y\in \mathbb {F} _{q^{n}}$ risulta prodotto da $(y_{1},...,y_{n})\in \mathbb {F} _{q}^{n}$ .

Per decriptare $y$ i procedimenti sopra citati vengono eseguiti in ordine inverso. Ma questo è possibile solo se la chiave privata $(S,P,T)$ è conosciuta. Il passo cruciale della decifrazione non è l'inversione di $S$ e $T$ , piuttosto il calcolo della soluzione di $P(x')=y'$ . Dal momento che $P$ non è necessariamente una biiezione, possono essere trovate più di una soluzione a questa inversione (esistono al più d soluzioni distinte $X'=(x_{1}',...,x_{d}')\in \mathbb {F} _{q^{n}}$ dal momento che $P$ è un polinomio di grado $d$ ). La ridondanza denotata $r$ è aggiunta durante il primo passaggio al messaggio $M$ in modo da poter selezionare il giusto $M$ dal set di soluzioni $X'$ .^[1]^[3]^[5] Il diagramma riportato sotto mostra lo schema base delle HFE per la criptazione

M{\overset {+r}{\to }}x{\overset {{\text{secret}}:S}{\to }}x'{\overset {{\text{secret}}:P}{\to }}y'{\overset {{\text{secret}}:T}{\to }}y

Variazioni delle HFE

Le Hidden Fields Equations hanno quattro variazioni di base, chiamate +, -, f e v ed è possibile combinarle tra di loro in diversi modi. I principi base che le differenziano sono i seguenti:

01. Il simbolo + indica che viene effettuato un mix lineare tra le equazioni pubbliche e alcune equazioni casuali.

02. Il simbolo - è dovuto ad Adi Shamir e il suo scopo è quello di rimuovere la ridondanza

r

dalle equazioni pubbliche.

03. Il simbolo f indica che alcune variabili d'ingresso

f

sono state fissate.

04. Il simbolo v più che indicare un qualche cambiamento definisce una struttura, talvolta notevolmente complessa, tale che l'inversa della funzione può essere calcolata solo se determinate variabili

v

, chiamate variabili aceto, sono state precedentemente fissate.

Le operazioni riportate sopra concorrono a preservare in una certa misura la cosiddetta solvibilità botola (trapdoor solvability in inglese) della funzione. Per chiarire questo aspetto basta sapere che una funzione botola è una funzione facilmente computabile in una direzione, ma difficile da calcolare nella direzione opposta (ossia trovare l'inversa) se non si conoscono determinate informazioni.

Le HFE- e le HFEv sono molto utili, e di conseguenza molto usate, nella creazione di schemi per la firma digitale dal momento che prevengono i rallentamenti nella generazione delle chiavi e garantiscono inoltre una maggiore sicurezza generale delle HFE. Per quanto riguarda la criptazione sia l'HFE- che l'HFEv portano ad un processo di decifratura sensibilmente più lento grazie alle loro peculiarità implementative. Entrambe hanno inoltre avuto un ruolo fondamentale nella creazione di Quartz.

L'HFE+ invece, sempre nell'ambito della criptazione, porta ad una situazione, in linea teorica, ottimale dal momento che il processo di decifrazione richiede la stessa quantità di tempo, anche se le chiavi pubbliche hanno più equazioni che variabili.^[1]^[2]

Attacchi alle HFE

Esistono due famosi attacchi che sono stati portati di recente alle HFE:

01. L'attacco Shamir-Kipnis: recuperare la chiave privata

Il punto chiave di questo attacco è quello di recuperare la chiave privata sotto forma di polinomi univariati all'interno dell'estensione di campo $\mathbb {F} _{q^{n}}$ . Questa tipologia di attacco funziona esclusivamente se portato a delle HFE di base, mentre fallisce contro qualsiasi loro variazione.

02. L'attacco Faugere: Basi di Gröbner

L'idea dell'attacco di Faugere è quella di usare gli algoritmi veloci per calcolare una Base di Gröbner del sistema di equazioni polinomiali. Faugere, nel 2002, riuscì a violare le HFE in 96 ore. Dal 2003 Faugere e Joux lavorano insieme sulla sicurezza delle HFE.^[1]

Note

^ ^a ^b ^c ^d ^e ^f Christopher Wolf and Bart Preneel, Asymmetric Cryptography: Hidden Field Equations(EN)
^ ^a ^b Nicolas T. Courtois On Multivariate Signature-only public key cryptosystems(EN)
^ ^a ^b Ilia Toli Hidden Polynomial Cryptosystems(EN)
^ Jean Charles Faugere and Antoine Joux, Algebraic Cryptanalysis of Hidden Field Equations (HFE) Cryptosystems Using Grobner Bases Archiviato l'11 novembre 2008 in Internet Archive.(EN)
^ Jacques Patarin, Hidden Field Equations (HFE) and Isomorphic Polynomial (IP): two new families of asymmetric algorithm(EN)

Bibliografia

Nicolas T. Courtouis, Magnus Daum and Patrick Felke, On the Security of HFE, HFEv- and Quartz(EN)

Collegamenti esterni

Nicolas Courtois HFE page, su minrank.org.

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

[autogenerated2-1] ^ ^a ^b ^c ^d ^e ^f Christopher Wolf and Bart Preneel, Asymmetric Cryptography: Hidden Field Equations(EN)

[autogenerated1-2] Nicolas T. Courtois On Multivariate Signature-only public key cryptosystems(EN)

[autogenerated4-3] Ilia Toli Hidden Polynomial Cryptosystems(EN)

[autogenerated3-4] Jean Charles Faugere and Antoine Joux, Algebraic Cryptanalysis of Hidden Field Equations (HFE) Cryptosystems Using Grobner Bases Archiviato l'11 novembre 2008 in Internet Archive.(EN)

[5] Jacques Patarin, Hidden Field Equations (HFE) and Isomorphic Polynomial (IP): two new families of asymmetric algorithm(EN)

[1]

[2]

[3]

[4]

[5]