Amplifying Randomized Encodings & Applications

Nel vasto panorama della crittografia moderna, esiste una tensione fondamentale tra sicurezza ed efficienza. Vogliamo sistemi che siano incredibilmente difficili da violare, ma abbastanza semplici da poter essere eseguiti su dispositivi di uso comune. Per raggiungere questo obiettivo, i crittografi si affidano spesso alle "funzioni unidirezionali", operazioni matematiche che sono facili da eseguire in una direzione ma quasi impossibili da invertire senza una chiave segreta. L'esistenza di queste funzioni è il fondamento della privacy digitale, eppure per decenni i matematici hanno lottato per dimostrare che esse esistano basandosi sui problemi più difficili della computer science. Inveve di fare affidamento su assunzioni specifiche e potenzialmente fragili, i ricercatori hanno a lungo cercato di dimostrare che le funzioni unidirezionali debbano esistere semplicemente perché certe ampie classi di problemi sono intrinsecamente difficili da risolvere. Tra queste classi di problemi difficili figurano quelli che coinvolgono le "prove a conoscenza zero" (zero-knowledge proofs), un metodo con cui una parte può convincere un'altra di conoscere un segreto senza rivelare alcun dettaglio sul segreto stesso. La domanda è rimasta: se questi problemi a conoscenza zero sono difficili da risolvere nello scenario peggiore (worst-case), ciò garantisce l'esistenza delle funzioni unidirezionali necessarie per la crittografia sicura?

Un team di ricercatori ha ora compiuto un passo significativo verso la risposta a questa domanda, sviluppando un nuovo modo per amplificare l'affidabilità delle "codifiche randomizzate". Immaginate una codifica randomizzata come un modo per tradurre un problema complesso in una versione più semplice e rimescolata. L'obiettivo è creare una traduzione che non riveli nulla del problema originale oltre alla risposta finale, pur essendo molto più facile da computare rispetto all'originale. I ricercatori si sono concentrati su un tipo specifico di queste traduzioni in cui la garanzia di sicurezza vale solo per le risposte "sì", uno scenario noto come codifica a lato singolo (one-sided encoding). Hanno scoperto che anche se queste codifiche sono inizialmente imperfette — ovvero, potrebbero far trapelare una piccola quantità di informazioni o occasionalmente fornire la risposta errata — possono essere sistematicamente migliorate. Applicando una nuova tecnica basata sul concetto di "riduzioni lossy" (lossy reductions), che misura quanta informazione viene scartata durante una trasformazione, il team ha dimostrato che queste codifiche difettose possono essere amplificate finché gli errori e le perdite di informazioni non diventano trascurabili, ovvero effettivamente nulli.

Questo processo di amplificazione è la chiave per sbloccare connessioni più profonde nella computer science. I ricercatori hanno dimostrato che se un problema può essere codificato con un livello anche modesto di privacy e correttezza, può essere trasformato in una versione virtualmente perfetta. Hanno applicato questa scoperta alla classe di problemi nota come NISZK, che tratta le prove a conoscenza zero non interattive. Per anni, è stato un problema aperto se la proprietà di conoscenza zero di queste prove potesse essere rafforzata da una garanzia debole, di ordine inverso-polinomiale, a una garanzia forte, trascurabile. Il team ha dimostrato che può esserlo, risolvendo un problema che rimaneva senza risposta dalla fine degli anni '90. Ciò significa che qualsiasi problema con una prova a conoscenza zero debole può essere convertito in uno con una garanzia a conoscenza zero virtualmente perfetta, a condizione che il problema sottostante sia sufficientemente difficile.

Le implicazioni di questo lavoro si estendono direttamente all'esistenza delle funzioni unidirezionali. I ricercatori hanno dimostionato che se le versioni worst-case di questi problemi a conoscenza zero sono effettivamente difficili da risolvere, allora le funzioni unidirezionali devono esistere, a condizione che possa essere stabilita una specifica procedura di rimozione degli errori per le codifiche a lato singolo. Essi hanno ottenuto questo dimostrando che la capacità di rimuovere gli errori dalle codifiche a lato singolo è sufficiente a colmare il divario tra la difficoltà di questi problemi specifici e la creazione di strumenti crittografici sicuri. Sebbene l'articolo stabilisca che tale rimozione degli errori sarebbe sufficiente, esso lascia esplicitamente aperta la questione della costruzione di un algoritmo di rimozione degli errori come oggetto di ricerche future. Inoltre, hanno esplorato il regno quantistico, mostrando che principi simili si applicano alle codifiche quantistiche, il che implica a sua volta l'esistenza di "generatori di stati unidirezionali", un equivalente quantistico delle funzioni unidirezionali. Ciò suggerisce che la difficoltà fondamentale di questi problemi è abbastanza robusta da supportare sia la crittografia classica che quella quantistica.

Lo studio ha affrontato anche la natura dell' "oscuramento indistinguibile" (indistinguishability obfuscation), uno strumento crittografico potente che nasconde il funzionamento interno di un programma informatico preservandone la funzione. Ricerche precedenti avevano dimostrato che l'oscuramento implica funzioni unidirezionali solo sotto condizioni molto rigide, in cui il programma è o perfettamente nascosto o presenta un errore molto basso. Il nuovo lavoro dimostra che anche se l'oscuramento è debole e imperfetto — lasciando trapelare una quantità significativa di informazioni e commettendo errori frequenti — esso implica comunque l'esistenza di funzioni unidirezionali, a patto che una struttura teorica fondamentale della computer science, nota come Gerarchia Polinomiale, non collassi. Questa scoperta amplia significativamente le condizioni sotto le quali possiamo essere certi che una crittografia sicura sia possibile, suggerendo che la barriera per costruirla sia più bassa e più robusta di quanto precedentemente pensato.

Stabilendo queste connessioni, i ricercatori hanno fornito una mappa più chiara delle fondamenta teoriche della crittografia. Hanno dimostrato che la difficoltà di risolvere certe ampie classi di problemi non è solo una curiosità matematica astratta, ma una fonte diretta della sicurezza necessaria per il nostro mondo digitale. Il loro lavoro conferma che se possiamo fidarci del fatto che questi problemi complessi siano difficili da risolvere nei casi peggiori, e se la questione aperta della rimozione degli errori per le codifiche a lato singolo viene risolta, possiamo fare affidamento sull'esistenza delle funzioni unidirezionali che proteggono i nostri dati. I risultati non si limitano a suggerire una possibilità; offrono una prova rigorosa che il percorso dai problemi difficili alla crittografia sicura è aperto, a condizione del successo del raffinamento delle tecniche di codifica per eliminare gli errori. Ciò avvicina la comunità teorica a una comprensione definitiva del perché la crittografia funzioni e di cosa sia realmente necessario per costruirla.