#MT03 – In quale universo computazionale viviamo?
Questo è il terzo di una serie di articoli che ci accompagneranno, durante una breve gita nella “tana del coniglio” matematico, alla scoperta di un argomento che tange – come molti altri – lo studio di #bitcoin: la crittografia.
Tradotto dall’originale di Erica Klarreich – pubblicato il 18 apr 2022
Molti informatici si concentrano sul superamento di problemi computazionali difficili. Ma c’è un’area dell’informatica in cui la “durezza” è un vantaggio: la crittografia, in cui si vogliono ostacoli duri (insormontabili, n.d.t.) tra gli avversari e i segreti.
Purtroppo non sappiamo se la crittografia sicura esista davvero. Nel corso dei millenni, l’uomo ha creato cifrari che sembravano infrangibili, fino a quando non sono stati violati. Oggi, le nostre transazioni su Internet e i nostri segreti di Stato sono protetti da metodi di crittografia che sembrano sicuri, ma che potrebbero fallire in qualsiasi momento.
Per creare un metodo di crittografia veramente sicuro (e permanente), abbiamo bisogno di un problema computazionale abbastanza difficile da creare una barriera insormontabile per gli avversari. Conosciamo molti problemi computazionali che sembrano difficili, ma forse non siamo stati abbastanza intelligenti da risolverli. O forse alcuni di essi sono difficili, ma la loro “durezza” non si presta a una crittografia sicura. Fondamentalmente, i crittografi si chiedono: C’è abbastanza durezza nell’universo per rendere possibile la crittografia?
Nel 1995, Russell Impagliazzo dell’Università della California, San Diego, ha scomposto la questione della durezza in una serie di sotto-domande che gli scienziati informatici potevano affrontare un pezzo alla volta. Per riassumere lo stato delle conoscenze in questo campo, ha descritto cinque mondi possibili – chiamati fantasiosamente Algorithmica, Heuristica, Pessiland, Minicrypt e Cryptomania – con livelli crescenti di durezza e possibilità crittografica. Ognuno di questi potrebbe essere il mondo in cui viviamo.
Algorithmica
In questo mondo, i problemi computazionali più naturali sono tutti facili, il che rende impossibile la crittografia. Qui, l’insieme dei problemi con soluzioni efficienti – un insieme chiamato P – non contiene solo i problemi che abbiamo già capito come risolvere. Include anche tutti i problemi di un altro insieme chiamato NP, che consiste nei problemi per i quali è facile verificare una soluzione proposta se qualcuno ce la consegna.
A prima vista, P e NP sembrano categorie diverse. Per esempio, prendiamo il problema di decidere se le valigie possono contenere tutti gli oggetti che portaqre con noi per un viaggio. Se un amico fa le valigie al posto vostro, è facile verificare se ci ha messo tutto: basta controllare che non ci siano oggetti mancanti. Il problema della preparazione delle valigie è quindi NP. Ma fare le valigie da soli è molto più difficile: potreste dover provare molte soluzioni diverse. Non è chiaro se esista un algoritmo efficiente che risolva questo problema per tutte le possibili combinazioni di oggetti e valigie. In altre parole, non sappiamo se questo problema è in P.
Anche il problema della decrittazione di uno schema di crittografia è in NP. Dopo tutto, se si dispone di un messaggio cifrato e un amico sostiene di averlo decifrato, si può verificare inserendo il suo messaggio decifrato nella macchina di cifratura e vedendo se l’output corrisponde al messaggio cifrato originale. (Naturalmente, per fare questo è necessario possedere una delle macchine di crittografia, ma i crittografi non considerano sicuro uno schema se non è in grado di resistere agli attacchi di un nemico che si impossessi di una delle macchine).
In Algorithmica, P e NP sono lo stesso insieme di problemi. Una prova di questo sarebbe una bonanza algoritmica, poiché significherebbe che esistono algoritmi veloci per cose come l’imballaggio delle valigie e tutti gli altri problemi apparentemente difficili in NP. Ma sarebbe un disastro per i crittografi, poiché uno dei problemi che saremmo in grado di risolvere in modo efficiente è la decrittazione.
La maggior parte degli informatici ritiene che P sia diverso da NP, per la semplice ragione che ci sono così tanti problemi in NP che non siamo riusciti a risolvere in modo efficiente. Ma nessuno è mai stato in grado di dimostrarlo (o smentirlo), anche se la questione “P contro NP” è stata considerata il problema più famoso dell’informatica teorica per cinque decenni. D’altra parte, ha detto Yuval Ishai del Technion di Haifa, in Israele, “a parte il costante fallimento delle persone più intelligenti, non abbiamo prove che sia difficile dimostrare che P non è uguale a NP“.
Heuristica
In questo mondo, ci sono problemi in NP che non sono facili da risolvere, ma ogni problema in NP è facile “in media“, cioè può essere risolto in modo efficiente nella maggior parte dei casi. Per esempio, se siamo in Euristica, esiste un algoritmo efficiente per fare le valigie che ha quasi sempre successo, ma che potrebbe fallire per alcune rare combinazioni di valigie e oggetti da imballare. (Questi algoritmi veloci e di solito vincenti sono comunemente chiamati “euristiche“).
Dal punto di vista della crittografia, non c’è una grande differenza tra Heuristica e Algorithmica. Se si propone uno schema di crittografia in Heuristica, ci sarà un metodo di decifrazione veloce in grado di gestire quasi tutti i messaggi, rendendo lo schema inutile ai fini pratici.
Pessiland
Questo è il peggiore dei mondi possibili. In Pessiland, alcuni problemi di NP sono difficili anche in media. Per questi problemi, qualsiasi algoritmo efficiente fallirà non solo occasionalmente, ma spesso. Tuttavia, questi problemi difficili non sono del tipo utile per nascondere informazioni segrete.
“Non vogliamo assolutamente vivere in Pessilandia“, ha detto Eric Allender della Rutgers University. “Qui abbiamo tutti gli aspetti negativi della complessità [computazionale], ma senza alcun vantaggio come la crittografia“.
Minicrypt
In questo mondo, alcuni problemi NP sono mediamente difficili, e questa durezza è sufficiente per costruire l’elemento fondamentale della crittografia: una “funzione unidirezionale“, cioè una funzione che può essere eseguita in modo efficiente ma non può essere invertita in modo efficiente. I crittografi hanno dimostrato che la crittografia sicura richiede funzioni unidirezionali. E se le abbiamo, otteniamo una serie di vantaggi crittografici, come la crittografia a chiave segreta, le firme digitali e i generatori di numeri pseudorandom.
“L’esistenza di funzioni unidirezionali è, senza dubbio, il problema più importante della crittografia“, ha dichiarato Rafael Pass della Cornell University e della Cornell Tech. “Se non le abbiamo, tutte queste cose possono essere violate“.
Cryptomania
In questo mondo, abbiamo una durezza sufficiente per creare tutto ciò che è presente in Minicrypt, oltre a protocolli crittografici ancora più avanzati, come la crittografia a chiave pubblica (in cui le persone possono inviare messaggi crittografati senza conoscere la chiave segreta).
Eliminazione dei mondi
La maggior parte dei crittografi, ha detto Ishai, ritiene che almeno una parte della crittografia esista, quindi è probabile che viviamo nella criptomania o nella minicriptografia. Ma non si aspettano una prova di ciò a breve. Una prova del genere richiederebbe l’esclusione degli altri tre mondi e l’esclusione della sola Algoritmica richiede già la soluzione del problema “P contro NP“, con cui gli scienziati informatici hanno lottato per decenni.
Recentemente, però, Pass e il suo dottorando Yanyi Liu hanno trovato un nuovo approccio per setacciare questi mondi. Per la prima volta, hanno identificato un problema naturale – chiamato complessità di Kolmogorov legata al tempo, o in breve Kt – il cui livello di difficoltà crea una netta linea di demarcazione tra i mondi che includono la crittografia e quelli che non la includono. Se la Kt è mediamente facile, hanno dimostrato Liu e Pass, allora la crittografia sicura non può esistere, quindi siamo in Algorithmica, Heuristica o Pessiland. Ma se Kt è mediamente difficile, allora possiamo creare funzioni unidirezionali, quindi siamo almeno in Minicrypt e forse in Cryptomania.
Questo nuovo risultato significa che gli informatici possono eliminare Pessiland – il mondo peggiore – se riescono a dimostrare un’altra affermazione: Se Kt è facile in media, allora lo è anche ogni problema in NP. In tal caso, avremo ristretto il campo ai mondi in cui Kt è mediamente difficile (Minicrypt e Cryptomania) e a quelli in cui Kt – e ogni altro problema in NP – è mediamente facile (Algorithmica e Heuristica).
I ricercatori si stanno occupando di Pessiland da tempo, ha dichiarato Ryan Williams del Massachusetts Institute of Technology. “Penso che il consenso generale sia che Pessiland possa essere escluso, ma non so se lo faremo prima o poi“.
I crittografi vorrebbero eliminare anche Heuristica, il che comporterebbe la dimostrazione che se Kt è facile in media, allora ogni problema in NP è facile in tutti i casi (non solo in media). Escludere questi due mondi significherebbe che o viviamo nell’Algorithmica, dove tutto è sempre facile, o abbiamo una durezza sufficiente per la crittografia di base.
I crittografi si riferiscono a questo obiettivo come al Santo Graal del settore. Ishai non si aspetta di vederlo dimostrato nel corso della sua vita, ma anche questo è incerto. “Quando si risolvono problemi difficili, a volte ce ne accorgiamo, ma a volte no“, ha detto. “Sicuramente la nostra migliore possibilità è questa nuova linea di lavoro“.
Articolo originale: Read More
