Sintesi Tecnica: Dalla durezza del caso peggiore di NP alla crittografia quantistica tramite l'offuscamento dell'indistinguibilità quantistica

Definizione del Problema

L'offuscamento dell'indistinguibilità (iO) è un potente primitivo crittografico che, se combinato con le funzioni unidirezionali (OWF), consente la costruzione di una vasta gamma di strumenti avanzati. Tuttavia, l'iO da solo non implica l'esistenza di OWF; richiede un'assunzione aggiuntiva riguardante la durezza di NP. Nel contesto classico, Komargodski et al. [KMN+14] hanno dimostrato che assumendo la durezza del caso peggiore di NP "infinitely-often" ($NP \not\subseteq i.o.BPP$), è possibile costruire OWF dalla iO classica.

Il problema centrale affrontato in questo lavoro è il potere crittografico dell'offuscamento dell'indistinguabilità quantistica (quantum iO). A differenza degli offuscatori classici, gli offuscatori quantistici sono intrinsecamente randomizzati a causa della misurazione, il che significa che non possono essere "derandomizzati" fissando un seme casuale. Di conseguenza, la costruzione classica di OWF da iO [KMN+14], che si basa sulla derandomizzazione, non si estende direttamente al contesto quantistico. Rimane poco chiaro se la quantum iO, combinata con la durezza del caso peggiore di NP nel contesto quantistico ($NP \not\subseteq i.o.BQP$), possa implicare l'esistenza di qualsiasi primitivo crittografico, in particolare quelli che non richiedono OWF (spesso definiti primitivi "Microcrypt").

Metodologia

Gli autori iniziano uno studio sistematico della quantum iO formalizzando varie varianti basate sulla natura computazionale (classica o quantistica) di tre componenti:

1. Algoritmo di Offuscamento ($Obf$)
2. Algoritmo di Valutazione ($Eval$)
3. Codifica Offuscata ($\hat{C}$)

Definiscono la $(X, Y, Z)$-iO dove $X, Y, Z \in \{Q, C\}$, rappresentando Quantistico o Classico per l'offuscatore, l'evaluatore e la codifica, rispettivamente. Il documento si concentra su cinque varianti significative: $(Q, Q, Q)$, $(Q, Q, C)$, $(Q, C, C)$, $(C, Q, C)$ e $(C, C, C)$.

Approccio Tecnico Centrale

La base dei loro risultati è una riduzione dalla durezza del caso peggiore di NP all'esistenza di specifiche distribuzioni crittografiche. La metodologia procede come segue:

1. Riduzione di Valiant-Vazirani: Gli autori sfruttano il teorema di Valiant-Vazirani per ridurre l'assunzione $NP \not\subseteq i.o.BQP$ a $UP \not\subseteq i.o.BQP$ (dove UP è la classe dei problemi con testimoni unici). Ciò consente loro di lavorare con problemi che hanno un testimone unico.
2. Indistinguibilità delle Funzioni Punto rispetto alle Funzioni Zero: Il teorema tecnico centrale (Teorema 4.1) stabilisce che, sotto l'assunzione $NP \not\subseteq i.o.BQP$, l'offuscamento di una funzione punto casuale $P_k$ (che restituisce 1 solo sull'input $k$) è computazionalmente indistinguibile dall'offuscamento di una funzione zero $Z_m$ (che restituisce 0 ovunque), anche quando il distinguitore riceve più campioni generati con la stessa chiave segreta $k$.
   • Schema della prova: Se un distinguitore potesse differenziare $Obf(P_k)$ da $Obf(Z_m)$, si potrebbe costruire un algoritmo per recuperare il testimone unico di un'istanza UP. Ciò è ottenuto costruendo un circuito $V[x, v]$ che differisce dalla funzione zero esattamente su un input ($w \oplus v$). Grazie alla sicurezza della iO (specificamente la sua equivalenza all'offuscamento a singolo input differente in questo contesto), distinguere gli offuscamenti permette di estrarre l'input differente, recuperando così il testimone $w$.
3. Costruzione di Primitivi: Utilizzando l'indistinguibilità di $Obf(P_k)$ e $Obf(Z_m)$, gli autori costruiscono vari schemi di cifratura e altri primitivi. La specifica costruzione dipende dalla variante $(X, Y, Z)$:
   • Per la Crittografia a Chiave Pubblica (PKE), utilizzano $Obf(P_k)$ come chiave pubblica e costruiscono un testo cifrato offuscando un circuito che controlla se l'input corrisponde alla chiave segreta.
   • Per la Crittografia a Chiave Simmetrica (SKE), utilizzano $Obf(P_k)$ e $Obf(Z_m)$ come testi cifrati per i messaggi 1 e 0, rispettivamente.

Contributi Chiave e Risultati

Il documento dimostra che la quantum iO, combinata con $NP \not\subseteq i.o.BQP$, implica una ricca gerarchia di primitivi crittografici. I risultati sono riassunti dalla variante di iO:

• $(Q, Q, Q)$-iO (Obf Quantistico, Eval Quantistico, Codifica Quantistica):

  • Implica la QSKE (Quantum Symmetric Key Encryption) con sicurezza IND-CPA, dove la chiave segreta è classica e il testo cifrato è uno stato quantistico.
  • Implica Generatori di Stato Unidirezionali (OWSG) e coppie EFI.

• $(Q, Q, C)$-iO (Obf Quantistico, Eval Quantistico, Codifica Classica):

  • Implica la QCCC SKE (Quantum-computation Classical-communication SKE) con sicurezza IND-CPA, dove i calcoli locali sono quantistici ma la comunicazione è classica.
  • Implica EV-OWPuzzs (One-Way Puzzles efficientemente verificabili), OWPuzzs, OWSGs, coppie QEFID e coppie EFI.

• $(Q, C, C)$-iO (Obf Quantistico, Eval Classico, Codifica Classica):

  • Implica la QCCC PKE con sicurezza IND-CPA.
  • Implica lo stesso insieme di primitivi della $(Q, Q, C)$-iO (EV-OWPuzzs, OWPuzzs, OWSGs, ecc.).
  • Nota: Poiché l'offuscatore è quantistico, non può essere derandomizzato, quindi le OWF non sono direttamente implicate in questa specifica variante tramite la via standard, ma lo schema di cifratura è costruito direttamente.

• $(C, Q, C)$-iO (Obf Classico, Eval Quantistico, Codifica Classica):

  • Implica la QCCC PKE con sicurezza IND-CPA.
  • Implica (Post-quantum) OWF.
  • Di conseguenza, implica tutti i primitivi Microcrypt implicati dai Pseudorandom Unitaries (PRU).

• $(C, C, C)$-iO (Obf Classico, Eval Classico, Codifica Classica):

  • Implica la PKE con sicurezza IND-CPA e (Post-quantum) OWF.
  • Recupera il risultato classico di [KMN+14] ma con una prova semplificata e requisiti più deboli.

Significato e Rivendicazioni

Gli autori rivendicano diversi contributi significativi:

1. Avviare lo studio della Quantum iO: Questo lavoro è il primo ad analizzare sistematicamente le implicazioni crittografiche della quantum iO, definendo varianti naturali e mappando il loro potere verso specifici primitivi.
2. Collegare la durezza del caso peggiore alla crittografia quantistica: Il documento stabilisce che la durezza "infinitely-often" del caso peggiore di NP è sufficiente per costruire una vasta gamma di primitivi crittografici quantistici (inclusi OWSG e coppie EFI) quando combinata con la quantum iO, anche in assenza di OWF per certe varianti.
3. Semplificazione dei risultati classici: Anche nel contesto classico ($(C, C, C)$-iO), gli autori forniscono una nuova costruzione, certamente più semplice, di OWF da iO imperfetta e durezza di NP del caso peggiore. Il loro approccio evita l' "offuscamento a cascata" (offuscare un circuito già offuscato) richiesto da [KMN+14] e richiede solo l'offuscamento per formule 3CNF anziché per circuiti generali.
4. Risoluzione di problemi aperti: La costruzione di OWF da iO imperfetta per formule 3CNF sotto la durezza del caso peggiore era un problema aperto lasciato da [KMN+14]. Sebbene gli autori notino che questo è stato recentemente risolto da altri lavori [HN24, LMP24] utilizzando tecniche diverse, il loro approccio offre un percorso alternativo e più semplice.

Il documento mantiene un tono modesto, sottolineando che questi risultati sono condizionati all'esistenza della quantum iO e della durezza del caso peggiore di NP, e che i primitivi specifici costruiti dipendono fortemente dalla natura quantistica/classica dei componenti di offuscamento.