La crittografia oltre le criptovalute

ALON ROSEN, NUOVO PROFESSORE DELLA BOCCONI, STUDIA L'INTERAZIONE TRA COMPLESSITA' COMPUTAZIONALE E CRITTOGRAFIA, TEMI SU CUI HA RICEVUTO UN ERC ADVANCED GRANT

Ultimamente, il prefisso “cripto” (o “critto”) è stato per lo più associato alle criptovalute, ma mentre queste ultime sono apparse solo pochi anni fa, la crittografia ha migliaia di anni di storia. Infatti, la necessità di nascondere informazioni preziose dalle intrusioni di terzi ha accompagnato l'umanità fin dall'antichità. Le civiltà antiche ricorrevano a semplici cifrari a sostituzione, come il cifrario Atbash, originariamente usato per l'alfabeto ebraico, o il cifrario di Cesare, impiegato nell'antica Roma. Più recentemente, dispositivi meccanici ed elettromeccanici, come la famosa macchina Enigma, hanno svolto un ruolo importante nella seconda guerra mondiale, come racconta anche il film “The Imitation Game”, basato sulla biografia di Alan Turing, famoso matematico, crittografo e pioniere dell'informatica.
 

Non è un caso che, dopo la seconda guerra mondiale, l'evoluzione della crittografia sia andata di pari passo con lo sviluppo dell'informatica e con lo studio della complessità computazionale. Crittografia e complessità computazionale sono anche i principali campi di interesse di Alon Rosen, da poco entrato nel Dipartimento di Scienze delle Decisioni della Bocconi come full professor. Rosen si è anche aggiudicato un “ERC Advanced Grant” per un progetto incentrato su questi temi, in particolare sullo studio di nuove misure di difficoltà computazionale.
 
“La complessità computazionale è cruciale per la crittografia”, spiega Rosen, “e i problemi computazionalmente difficili sono stati uno degli elementi costitutivi della crittografia per decenni. Un esempio è la fattorizzazione in numeri primi, cioè il problema di scomporre un numero nell'unico insieme di numeri primi (più piccoli) che moltiplicati tra loro restituiscono il numero di partenza (un numero primo è un numero naturale maggiore di 1 - per esempio 2, 3, ecc. - che è divisibile solo per 1 e per se stesso). La crittografia sfrutta la seguente asimmetria computazionale: è facile e veloce moltiplicare tra loro due numeri primi molto grandi, ottenendo così un semiprimo ancora più grande, ma è molto difficile scomporre un semiprimo molto grande che sia il prodotto di due primi distinti ma approssimativamente della stessa dimensione. Per ‘difficile’ intendiamo un problema che richiede molte risorse computazionali e molto tempo - anche anni - rendendo questo compito possibile in linea di principio ma irrealizzabile in pratica. Ecco perché questi due numeri primi così difficili da trovare possono essere usati come chiave per decifrare un codice”.
 
“La fattorizzazione in numeri primi è solo un esempio di un problema difficile che può essere sfruttato in crittografia. I crittografi sono sempre alla ricerca di nuovi problemi difficili, ma la definizione di ‘problema difficile’ è di per sé non banale. Le definizioni tradizionali classificano un problema come difficile se richiede un tempo di calcolo che cresce esponenzialmente con la dimensione dell'input (nell'esempio della fattorizzazione in primi, la dimensione dell'input è il numero di cifre del numero da scomporre). Tuttavia, questa definizione può essere troppo restrittiva, e una crescita polinomiale di grado elevato può essere sufficiente per scopi crittografici”.
 
Quest’idea può aprire nuove strade per la crittografia, che non solo ha una lunga storia ma anche un ruolo cruciale nel presente. Infatti, la cifratura end-to-end utilizzata nelle e-mail e nella messaggistica istantanea, le firme digitali, i pagamenti elettronici e le stesse criptovalute si basano tutti sulla buona, vecchia crittografia – che però è sempre in continua evoluzione.
 
Per saperne di più
 
Ball, M., Rosen, A., Sabin, M., Vasudevan, P. N. “Average-case fine-grained hardness.” In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (2017). DOI: https://doi.org/10.1145/3055399.3055466.
 

di Sirio Legramanti