OWSG Strutturati: La Nuova Frontiera per gli Impegni Quantistici Sicuri

Ciao a tutti, appassionati di scienza e tecnologia! Oggi ci tufferemo in un argomento che sta facendo tremare le fondamenta della crittografia moderna: i generatori di stati quantistici unidirezionali, o per gli amici, gli OWSG (One-Way Quantum State Generators). Pensateli come la versione quantistica delle classiche funzioni unidirezionali (OWF), quei mattoncini fondamentali su cui si basa gran parte della sicurezza informatica che usiamo ogni giorno. Ma qui c’è una svolta affascinante: invece di generare una semplice stringa di bit, gli OWSG producono uno stato quantistico.

Ma cosa sono esattamente questi OWSG?

Immaginate una macchina magica: le date in input una stringa classica (una sequenza di 0 e 1) e lei vi restituisce uno stato quantistico, magari puro come un singolo fotone polarizzato in un certo modo, o più complesso, come uno stato misto. La “magia” sta nella proprietà unidirezionale: è facile generare lo stato quantistico partendo dalla stringa, ma è computazionalmente impossibile (o quasi) fare il percorso inverso, cioè risalire alla stringa originale anche avendo a disposizione molte copie dello stato quantistico generato. È un po’ come rompere un uovo: facile farlo, impossibile ricomporlo perfettamente.

Questa idea, introdotta e poi generalizzata da Morimae e Yamakawa, ha aperto scenari incredibili. Si è scoperto che gli OWSG sono legati a doppio filo con altre primitive crittografiche quantistiche, come le firme digitali quantistiche o persino il denaro quantistico. Ma una delle domande più scottanti è: possiamo usare gli OWSG per costruire impegni quantistici (quantum commitments)?

L’importanza cruciale degli Impegni Quantistici

Gli impegni sono protocolli crittografici fondamentali, un po’ come mettere un messaggio in una cassaforte sigillata. Funzionano in due fasi:

• Commit (Impegno): Una parte (il committer) si impegna su un messaggio segreto, inviando delle informazioni all’altra parte (il receiver).
• Reveal (Rivelazione): In un secondo momento, il committer rivela il messaggio e dimostra che era proprio quello a cui si era impegnato inizialmente.

Le proprietà chiave sono due:

• Hiding (Occultamento): Il receiver non può scoprire il messaggio prima della fase di rivelazione.
• Binding (Vincolo): Il committer non può cambiare idea e rivelare un messaggio diverso da quello a cui si era impegnato.

Nel mondo classico, sappiamo che gli impegni esistono se e solo se esistono le funzioni unidirezionali (OWF). Ma nel regno quantistico, le cose si fanno più interessanti. Sappiamo già che si possono costruire impegni quantistici (addirittura non interattivi!) partendo da OWF post-quantistiche, cosa impossibile classicamente. E lavori recenti hanno mostrato che si possono ottenere anche da generatori di stati pseudocasuali (PRS), che sembrano essere un’assunzione più debole delle OWF post-quantistiche.

La domanda naturale diventa: e gli OWSG? Possono darci gli impegni quantistici, magari partendo da assunzioni ancora più basilari o con costruzioni più semplici? È qui che entra in gioco la nostra ricerca.

I Nostri Contributi: OWSG Strutturati al Lavoro

Nel nostro lavoro, abbiamo esplorato proprio questo legame, concentrandoci su OWSG con strutture particolari. Ecco i risultati principali che abbiamo ottenuto:

1. Impegni Quantistici da OWSG “Un Po’ Iniettivi”

Abbiamo dimostrato come costruire schemi di impegno quantistico (nello specifico, le cosiddette coppie EFI – Efficiently samplable, statistically Far but computationally Indistinguishable pairs of distributions, che sono equivalenti agli impegni canonici) partendo da OWSG che hanno una proprietà chiamata “somewhat injectivity” (un po’ di iniettività). Cosa significa? In parole povere, una funzione (o un generatore di stati) è iniettiva se a input diversi corrispondono sempre output diversi. Un OWSG “somewhat injective” non è perfettamente iniettivo su tutto il dominio, ma lo è su una frazione significativa (non trascurabile) di esso. Abbiamo mostrato che questa proprietà, anche se più debole dell’iniettività totale, è sufficiente per garantire il “binding” statistico (cioè, nemmeno un committer con potenza di calcolo illimitata può barare), mentre l’hiding computazionale deriva dalla proprietà di unidirezionalità dell’OWSG.

Ma come si ottengono questi OWSG “somewhat injective”? Abbiamo dimostrato che possono essere derivati da un’altra classe di OWSG, quelli “almost regular” (quasi regolari). Un OWSG è quasi regolare se, grosso modo, il numero di input che mappano vicino a un certo output è prevedibile e non varia troppo. Usando tecniche basate su funzioni hash universali, siamo riusciti a “trasformare” un OWSG quasi regolare in uno “somewhat injective”, aprendo la strada alla costruzione di impegni.

2. L’Equivalenza tra Coppie EFI e Predicati Hard-Core

Ci siamo poi concentrati su una variante particolare di OWSG: quelli segretamente verificabili ed estremamente statisticamente invertibili (SV-eSI-OWSG). Questi OWSG producono stati quantistici che sono molto distanti tra loro (la loro distanza di traccia è quasi massima). Abbiamo stabilito un’equivalenza affascinante: l’esistenza di coppie EFI è necessaria e sufficiente per l’esistenza di un predicato hard-core sicuro contro attacchi a singola copia per questi SV-eSI-OWSG. Un predicato hard-core è, intuitivamente, un’informazione sull’input dell’OWSG che è difficile da calcolare conoscendo solo l’output. Questa equivalenza rafforza la connessione tra queste primitive fondamentali e conferma l’importanza degli SV-eSI-OWSG (che sono equivalenti ai più generali SV-SI-OWSG).

3. Una Costruzione Semplice basata sull’Assunzione LPN

Infine, abbiamo proposto un modo nuovo e semplice per costruire coppie EFI basandoci su un’assunzione crittografica ben studiata: la versione decisionale del problema Learning Parity with Noise (LPN). L’assunzione LPN afferma, in sostanza, che è difficile distinguere un sistema di equazioni lineari “rumorose” da uno completamente casuale. Sfruttando questa assunzione (nella sua versione quantistica), abbiamo costruito un generatore di coppie EFI che offre una maggiore flessibilità nella scelta dei parametri (come il tasso di rumore e la dimensione del problema) rispetto alle costruzioni classiche di impegni basate su LPN. Questo è importante perché permette di adattare meglio lo schema alle esigenze di sicurezza specifiche, potenzialmente usando parametri per cui l’assunzione LPN è considerata più robusta. La costruzione è elegante e sfrutta la capacità dei computer quantistici di creare sovrapposizioni di stati “rumorosi”.

Approfondiamo le Tecniche

Vediamo un po’ più nel dettaglio come funzionano queste idee.

Dall’Iniettività (parziale) agli Impegni: L’idea di base si ispira a una costruzione classica: se hai una permutazione unidirezionale P (che è iniettiva per definizione), puoi impegnarti su un bit ‘b’ inviando (P(x), + b, r), dove x è una stringa casuale, r un’altra stringa casuale e è il prodotto scalare modulo 2. L’hiding viene dal teorema di Goldreich-Levin (è difficile indovinare conoscendo P(x)), e il binding dall’iniettività di P. Noi abbiamo adattato questa idea al mondo quantistico e alle coppie EFI. Invece di inviare un singolo valore, generiamo una sovrapposizione quantistica. L’indistinguibilità computazionale tra lo stato per b=0 e quello per b=1 (che garantisce l’hiding) deriva ancora dalla difficoltà di calcolare il predicato hard-core (versione quantistica del teorema di Goldreich-Levin). La “farness” statistica (la distanza tra i due stati, che garantisce il binding) deriva proprio dalla proprietà di “somewhat injectivity”: poiché una frazione non trascurabile degli output è unica, i due stati globali per b=0 e b=1 risultano distinguibili per un algoritmo con potenza illimitata.

Ottenere l’Iniettività (parziale) dalla Quasi Regolarità: La sfida è: come rendere una funzione (o un OWSG) “un po’ iniettiva” senza partire da una già iniettiva (che è un’assunzione forte)? L’idea è usare le funzioni hash. Consideriamo la costruzione f'(x,h) = (f(x), h, h(x)), dove h è una funzione hash scelta da una famiglia 2-wise independent. Se f è quasi regolare, possiamo scegliere la dimensione dell’output ‘e’ della funzione hash in modo tale che, con alta probabilità, l’output combinato (f(x), h, h(x)) abbia una sola preimmagine (x,h), garantendo l’iniettività locale. Allo stesso tempo, scegliendo ‘e’ non troppo grande, si preserva l’unidirezionalità grazie al “Leftover Hash Lemma” (anche nella sua versione quantistica). È un delicato gioco di equilibri!

L’Equivalenza con i Predicati Hard-Core: Per gli SV-eSI-OWSG, la cui caratteristica è che gli stati output ρ_x e ρ_x’ sono estremamente distanti per x ≠ x’, l’esistenza di un predicato hard-core P(x) sicuro a singola copia si lega strettamente alle coppie EFI. Se abbiamo il predicato, possiamo costruire le coppie EFI generando stati misti del tipo E_x [ρ_x ⊗ |P(x) ⊕ b⟩⟨P(x) ⊕ b|]. L’indistinguibilità viene dalla sicurezza del predicato, la farness dalla grande distanza tra gli stati ρ_x originali. Viceversa, se abbiamo le coppie EFI, possiamo costruire SV-eSI-OWSG e il loro predicato hard-core, chiudendo il cerchio dell’equivalenza.

La Costruzione LPN: Qui sfruttiamo il fatto che, data l’assunzione LPN decisionale, è difficile distinguere (A, Ax ⊕ e) da (A, r), dove A è una matrice casuale, x un segreto, e un vettore di rumore e r un vettore casuale. Possiamo generare le coppie EFI in modo molto diretto: lo stato ρ_0 sarà una sovrapposizione di |A⟩⟨A| ⊗ |Ax ⊕ e⟩⟨Ax ⊕ e|, mentre ρ_1 sarà una sovrapposizione di |A⟩⟨A| ⊗ |r⟩⟨r|. L’indistinguibilità è garantita dall’assunzione LPN. La farness deriva dal fatto che, finché l’assunzione LPN non è banale (cioè, la distribuzione LPN è statisticamente distinguibile da quella casuale), i due stati misti ρ_0 e ρ_1 avranno una distanza di traccia non trascurabile.

Conclusioni e Prospettive Future

Il nostro viaggio nel mondo degli OWSG strutturati ci ha permesso di fare luce sulla loro potenza e versatilità. Abbiamo dimostrato che possono effettivamente servire come base per costruire impegni quantistici sicuri, stabilito connessioni profonde con altre primitive come i predicati hard-core e proposto costruzioni pratiche basate su assunzioni standard come LPN, offrendo anche maggiore flessibilità.

Questi risultati non solo ampliano la nostra comprensione teorica della crittografia quantistica, ma aprono anche nuove strade per applicazioni pratiche. Tuttavia, la ricerca non si ferma qui. Una delle grandi sfide aperte rimane quella di costruire generatori di stati pseudocasuali (PRS) o funzioni pseudocasuali quantistiche (PRF) partendo dagli OWSG. Riuscire a sfruttare l’unidirezionalità degli OWSG per ottenere la pseudocasualità richiesta da queste primitive più avanzate sarebbe un passo avanti enorme per il campo. È un problema affascinante che merita sicuramente ulteriori sforzi di ricerca. Il futuro della sicurezza quantistica si costruisce anche così, un passo alla volta, esplorando le intricate proprietà di questi affascinanti oggetti quantistici!

Fonte: Springer