A Practical Protocol for Quantum Oblivious Transfer from One-Way Functions

Riepilogo Tecnico: Un Protocollo Pratico per il Trasferimento Obliquo Quantistico da Funzioni Unidirezionali

1. Enunciato del Problema

Il Trasferimento Obliquo Quantistico (QOT) è una primitiva fondamentale per la costruzione del Calcolo Multi-Partecipante (MPC) nell'ambito quantistico. Sebbene lavori precedenti [6, 7] abbiano dimostrato che il QOT può essere costruito a partire da Funzioni Unidirezionali (OWF) e risorse quantistiche, tali protocolli hanno incontrato ostacoli significativi per la realizzazione sperimentale. I problemi principali identificati sono stati:

• Fragilità: I protocolli esistenti erano intolleranti agli errori sperimentali (ad esempio, inversioni di bit durante la distribuzione degli stati).
• Complessità di Implementazione: La dipendenza da Prove a Conoscenza Zero che non facevano uso in scatola nera delle OWF rendeva non banale l'integrazione con funzioni hash post-quantistiche pratiche (come SHA).
• Inefficienza: La struttura iterativa dei protocolli precedenti richiedeva un numero impraticabile di stati quantistici (ad esempio, $\sim 10^{13}$ stati BB84 per esecuzione), risultando in tempi di trasmissione dell'ordine di mesi.

Gli autori mirano a fornire un protocollo QOT tollerante al rumore ed efficiente, basato su OWF nel modello piano, che sia fattibile per le attuali configurazioni sperimentali.

2. Metodologia e Approccio Tecnico

La soluzione proposta costruisce un protocollo QOT sicuro per simulazione introducendo una nuova primitiva crittografica: uno schema di Impegno di Bit Equivoco ed Estraibile Rilassato (ERE).

Innovazioni Centrali:

• Estraibilità Rilassata: Gli autori osservano che l'estraibilità completa non è strettamente necessaria per dimostrare la sicurezza del QOT. Introducono l'"estraibilità rilassata", dove un simulatore può estrarre il messaggio impegnato per una grande frazione di impegni, mentre una frazione trascurabile può rimanere non estraibile. Questo rilassamento consente una struttura di protocollo più efficiente.
• Tolleranza al Rumore tramite Correzione d'Errore: A differenza dei lavori precedenti che assumevano dispositivi privi di rumore, questo protocollo incorpora codici di correzione d'errore lineari (nello specifico, codici basati su sindrome come LDPC). Il mittente trasmette le sindromi dei valori codificati, permettendo al destinatario (o a un simulatore) di correggere gli errori ed estrarre i semi corretti anche in presenza di rumore.
• Distillazione Efficiente dei Semi: Il protocollo utilizza tecniche di amplificazione della privacy (Lemma della Funzione Hash di Scarto) sugli stati BB84 per distillare semi casuali. Questi semi fungono da chiavi per impegni equivoci. La struttura raggruppa questi semi in famiglie per consentire impegni paralleli, evitando il sovraccarico quadratico trovato nei compilatori precedenti.
• Struttura dell'Impegno: Lo schema ERE-Commitment combina:
  1. EqCommitment: Un compilatore che trasforma un impegno statisticamente vincolante standard in uno equivoco. Gli autori modificano il compilatore originale [7] riducendo il numero di ripetizioni sequenziali da $\lambda$ a una singola istanza, scambiando la vincolatura completa per una "vincolatura rilassata".
  2. ERE-Commitment: Un protocollo di livello superiore che utilizza lo schema EqCommitment. Prevede che il mittente invii stati BB84, il destinatario impegni le scelte di base e gli esiti utilizzando lo schema ERE-Commitment, e una fase di sfida in cui un sottoinsieme viene aperto per la verifica. Gli stati rimanenti sono utilizzati per generare semi per la cifratura del messaggio finale.

Flusso del Protocollo (Protocollo 1):

1. Trasmissione Quantistica: Alice invia $2\lambda_{OT}$ stati BB84 a Bob.
2. Impegno: Bob misura e si impegna sulle sue scelte di base e sugli esiti utilizzando lo schema ERE-Commitment.
3. Sfida: Alice sfida un sottoinsieme casuale $T$ degli impegni. Bob li apre per verificare la coerenza con gli stati inviati da Alice (tenendo conto dell'errore sperimentale $\alpha$).
4. Generazione della Chiave: Alice invia le informazioni di base per l'insieme non sfidato $\bar{T}$. Bob partiziona $\bar{T}$ negli insiemi $I_0$ e $I_1$ in base alla corrispondenza delle basi.
5. Cifratura: Alice invia le sindromi di correzione d'errore e cifra i suoi messaggi $m_0, m_1$ utilizzando semi derivati dagli stati non sfidati e un Generatore Pseudo-Casuale (PRG).
6. Decifratura: Bob corregge i propri errori utilizzando le sindromi e decifra il messaggio corrispondente al suo bit di scelta $b$.

3. Contributi Chiave

• Nuova Primitiva: La definizione e la costruzione di uno schema di Impegno di Bit Equivoco ed Estraibile Rilassato (ERE) basato su OWF.
• QOT Tollerante al Rumore: Un protocollo QOT che gestisce esplicitamente gli errori sperimentali (inversioni di bit ed eventi multi-fotone) tramite correzione d'errore basata su sindromi, una caratteristica assente nelle costruzioni teoriche precedenti.
• Miglioramento dell'Efficienza: Ottimizzando la struttura dell'impegno e utilizzando la correzione d'errore, il protocollo riduce il numero richiesto di stati BB84 da $\sim 10^{13}$ (in [7]) a $\sim 10^7$.
• Distillazione Multi-OT: Il protocollo consente la distillazione di più chiavi OT ($n_{OT}$) da una singola esecuzione del protocollo, aspetto cruciale per un'implementazione efficiente dell'MPC.
• Quadro Analitico: Il documento fornisce espressioni analitiche per valutare le risorse quantistiche richieste rispetto ai parametri di sicurezza target (distanza di traccia $\Delta$), tenendo conto dei tassi di errore fisici ($\alpha$) e della fuoriuscita di informazioni ($\vartheta$).

4. Risultati e Prestazioni

Gli autori forniscono un benchmark delle prestazioni (Tabella 1) confrontando il loro protocollo con [7] e [21] per una distanza di traccia target $\Delta \le 10^{-15}$:

• Riduzione delle Risorse: Il numero richiesto di stati BB84 ($N_{BB84}$) è ridotto a circa $1,43 \times 10^6$ (ideale) fino a $3,33 \times 10^7$ (scenario realistico rumoroso), rispetto a $2,27 \times 10^{13}$ per il protocollo in [7].
• Efficienza Temporale: Questa riduzione si traduce in un tempo di acquisizione ($T_{acq}$) di secondi (ad esempio, da 1,43s a 43,6s assumendo una frequenza di 1 MHz), mentre il lavoro precedente [7] richiederebbe circa 8,6 mesi.
• Sicurezza: Il protocollo è dimostrato sicuro per simulazione contro parti maliziose nel modello piano, basandosi esclusivamente sull'esistenza di funzioni unidirezionali post-quantistiche.

5. Significato e Affermazioni

Il documento afferma che questo lavoro colma il divario tra la crittografia quantistica teorica e l'implementazione pratica. Rimuovendo la necessità di dispositivi privi di rumore e riducendo drasticamente il sovraccarico delle risorse quantistiche, gli autori affermano che il loro protocollo rende fattibile la realizzazione sperimentale del QOT (e, di conseguenza, dell'MPC quantistico) con la tecnologia attuale.

Gli autori sottolineano che la loro costruzione raggiunge costi BB84 comparabili ai protocolli basati sul Modello dell'Oracolo Casuale (ROM) [21], ma opera sotto assunzioni computazionali strettamente più deboli (modello piano con OWF piuttosto che ROM). Affermano esplicitamente che il loro obiettivo è un'"implementazione pratica" e non sostengono di eguagliare l'efficienza classica degli impegni basati sul ROM, bensì di fornire un percorso percorribile per l'OT sicuro quantistico nel mondo reale. Il lavoro evidenzia inoltre che la proprietà di estraibilità rilassata è sufficiente per la sicurezza, un'insight tecnico che consente i guadagni di efficienza senza compromettere le garanzie di sicurezza basate sulla simulazione richieste per l'MPC.