Come rifornire il serbatoio della crittografia

La crittografia a chiave pubblica rischia di finire il carburante e potrebbe aver bisogno di una fonte di energia alternativa. Alon Rosen, professore ordinario al Dipartimento di Computing Sciences della Bocconi, ha ottenuto un ERC Advanced Grant da 2,49 milioni di euro per cercare di trovare questa nuova fonte.

Il carburante utilizzato dalla crittografia sono i problemi computazionalmente difficili, cioè problemi ardui e che richiedono molto tempo. Un crittografo cerca problemi così difficili da non poter essere risolti, in media, in un tempo ragionevole, senza un suggerimento sotto forma di una chiave, cioè una certa informazione (di solito una stringa di bit) che, se elaborata attraverso un algoritmo crittografico, può codificare o decodificare dati.

La crittografia si basa sull'asimmetria computazionale. Ha bisogno di problemi con una direzione facile (il problema che il "buono", cioè il crittografo, deve risolvere) e una difficile (il problema che dovrebbe risolvere il "cattivo" per decifrare le informazioni).

Nella crittografia a chiave pubblica, in particolare, la parte che cripta usa una chiave conosciuta pubblicamente per criptare le sue informazioni, mentre la parte che decripta usa una chiave segreta e diversa. La sua controparte è la crittografia a chiave privata, in cui entrambe le parti usano la stessa chiave segreta. La crittografia a chiave pubblica è estremamente utile in molte applicazioni, ma ha due aspetti negativi: è un processo molto lento e trovare problemi difficili per essa è molto più difficile che trovare problemi difficili per la crittografia a chiave privata.

"Il tipo di difficoltà computazionale di cui abbiamo bisogno per la crittografia a chiave pubblica è difficile da trovare", dice Rosen, "e in 45 anni abbiamo trovato solo una manciata di candidati".

Un caso classico di questo tipo di asimmetria computazionale strutturata è la fattorizzazione in numeri primi, cioè il problema di scomporre un numero nell'unico insieme di numeri primi (più piccoli) che moltiplicati insieme restituiscono quel numero. Moltiplicare due numeri primi è facile, anche quando i numeri sono molto grandi, mentre tornare a due numeri primi partendo dal loro prodotto è molto più difficile.

Il progetto ERC di Rosen (FGC - Fine-Grained Cryptography) mira a trovare nuovi problemi difficili per la crittografia a chiave pubblica e a renderla più veloce.

Tradizionalmente, la crittografia si è basata su problemi per i quali esiste un divario di complessità esponenziale tra la direzione facile e quella difficile, dove la complessità può essere considerata una misura della potenza computazionale necessaria per risolvere un problema.

Infografica di Weiwei Chen
Consideriamo una stringa di 128 bit come chiave e usiamo 128 come parametro. Un divario di complessità esponenziale significa che mentre il buono deve affrontare, per esempio, una complessità pari a 128 elevato alla potenza di due (=16.384), il cattivo affronta una complessità pari a due elevato alla potenza di 128 (un numero vicino a quello di tutte le particelle nel mondo) - il che rende molto improbabile craccare il codice.

Rosen sta esplorando una nuova strada, in cui il divario di complessità non è esponenziale, ma "solo" polinomiale. Seguendo l'esempio precedente, vuole trovare problemi in cui, se la complessità affrontata dal buono è 128 elevato alla potenza di due, anche il cattivo affronta 128 elevato ad una potenza. Se la potenza è sufficientemente alta, il codice è sicuro come con uno scarto di complessità esponenziale: 128 elevato alla potenza di 20, per esempio, è approssimativamente uguale a 2 elevato alla potenza di 140 e quindi paragonabile al caso dello scarto esponenziale.

"Esistono già alcuni sospetti", dice Rosen, "problemi di cui possiamo supporre abbiano una direzione difficile. Per quanto possa sembrare controintuitivo, la cosa difficile per noi è mostrare che esiste anche una direzione facile".