Come rifornire il serbatoio della crittografia
COMPUTING SCIENCES |

Come rifornire il serbatoio della crittografia

ALON ROSEN HA VINTO UN ERC ADVANCED GRANT PER PORRE UNA NUOVA BASE A METODI CRITTOGRAFICI AVANZATI, SUPERANDO IL PROBLEMA DELLA SCARSITA' DI PROBLEMI DIFFICILI

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

di Fabio Todesco
Bocconi Knowledge newsletter

News

  • Le novita' del regolamento HTA a livello europeo

    L'Health Technology Assessment diventa centralizzato ed armonizzato in tutti i 27 paesi membri dell'Unione europea  

  • Utopia e utopie tra scienza, filosofia e letteratura

    La sesta edizione di ScienzaNuova affronta le varie interpretazioni di un tema sempre attuale  

Seminari

  Agosto 2022  
Lun Mar Mer Gio Ven Sab Dom
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

Seminari

  • ELLIS@Milan Artificial Intelligence workshop

    GABOR LUGOSI - Department of Economics, Pompeu Fabra University
    RICARDO BAEZA-YATES - Khoury College of Computer Sciences Northeastern University
    NOAM NISAN - School of Computer Science and Engineering, Hebrew University of Jerusalem
    MICHAL VALKO - Institut national de recherche en sciences et technologies du numérique

    AS02 DEUTSCHE BANK - Roentgen building

  • tbd

    ANDREW KING - Questrom School of Business

    Meeting room 4E4SR03 (Roentgen) 4