Sintesi Tecnica: Funzioni a Indipendenza Limitata Veloci e i Loro Duali

Definizione del Problema

Il documento affronta la sfida di costruire primitive crittografiche che imitino le proprietà statistiche delle funzioni casuali e dei codici lineari casuali mantenendo un overhead computazionale costante. Nello specifico, gli autori ricercano implementazioni "veloci" — definite come computabili tramite circuiti aritmetici di dimensione lineare (dimensione $O(n)$) — che soddisfino:

1. Indipendenza Limitata: Funzioni di hash che siano $t$-indipendenti per ogni $t$ costante.
2. Codici Duali Veloci: Famiglie di codici lineari in cui sia il codice che il suo duale ammettono una codifica sistematica veloce e raggiungono distanze vicine al limite di Gilbert-Varshamov (GV).
3. Proprietà di tipo Casuale più Forti: Estendere oltre la semplice distanza a proprietà come la decodificabilità in lista, garantendo che i codici si comportino come codici lineari casuali anche sotto vincoli locali (similarità locale).

Lavori precedenti, come [IKOS08] e [DI14], hanno stabilito funzioni di hash a indipendenza pairwise veloci e codici veloci che si avvicinano al limite GV, ma spesso con limitazioni riguardanti il parametro di indipendenza $t$, il campo di operazione o la capacità di ottimizzare simultaneamente il codice e il suo duale. Una recente costruzione di [BR26] ha migliorato i codici duali veloci, ma era limitata ai campi binari, richiedeva un tasso fisso di 1/2, presentava una probabilità di fallimento non trascurabile e mancava di codifica sistematica.

Metodologia

Gli autori si basano sulla "costruzione IKOS" (Ishai, Kushilevitz, Ostrovsky, Sahai) e sulla "costruzione DI" (Druk, Ishai), generalizzandole a parametri di indipendenza più elevati.

1. Generalizzazione delle Funzioni di Hash

La costruzione principale per le funzioni di hash segue una pipeline a tre fasi:

1. Codifica Esterna (Outer Encoding): Applicare un codice lineare veloce con grande distanza su un alfabeto grande (ma costante) all'input.
2. Hashing Interno (Inner Hashing): Applicare funzioni di hash a dimensione costante e $t$-indipendenti a ogni coordinata del vettore codificato.
3. Estrazione (Extraction): Applicare la trasposta di una matrice generatrice di un buon codice (che funge da estrattore) al risultato.

Per ottenere l'indipendenza $t$-wise, gli autori sostituiscono le funzioni di hash a indipendenza pairwise a dimensione costante nel passaggio interno con funzioni di hash a dimensione costante e $t$-indipendenti. Dimostrano che se il codice esterno ha una distanza sufficientemente grande (specificamente $> 1 - 1/t^2$), la distinzione di $t$ input è preservata attraverso una frazione sufficiente di coordinate, permettendo alle funzioni di hash interne di produrre output uniformi e indipendenti che lo step finale di estrazione preserva.

2. Famiglie di Output Lineari Uniformi (LUOF)

Per costruire i codici, gli autori utilizzano il concetto di una Famiglia di Output Lineari Uniformi (LUfica LUOF). Una matrice casuale $A$ è una LUOF se, per ogni input non nullo $x$, l'output $xA$ è distribuito uniformemente.

• Fast LUOF: Gli autori generalizzano la costruzione di [DI14] per creare una fast $t$-LUOF. Una matrice $A$ è una $t$-LUOF se, per ogni insieme di $t$ input linearmente indipendenti $x_1, \dots, x_t$, gli output $x_1A, \dots, x_tA$ sono uniformi e stocasticamente indipendenti.
• Costruzione: Simile alla costruzione della funzione di hash, questa prevede un codice esterno, uno strato di matrici casuali a dimensione costante (che fungono da funzione "interna") e uno step di estrazione. Gli autori dimostrano che se il codice esterno ha una distanza sufficiente, le matrici casuali interne mappano input linearmente indipendenti in output uniformi e indipendenti.

3. Costruzione di Codici Duali Veloci

Utilizzando una matrice $t$-LUOF $A \in \mathbb{F}_q^{k \times r}$, gli autori definiscono un codice $C$ con la mappa di codifica sistematica $x \mapsto (x, xA)$.

• Dualità: Il codice duale $C^\perp$ è generato dalla mappa $y \mapsto (-yA^\top, y)$.
• Principio di Trasposizione: Citando il principio di trasposizione (Lemma 3.4), sostengono che se il calcolo di $xA$ è veloce (dimensione lineare), allora anche il calcolo di $yA^\top$ è veloce.
• Indipendenza del Duale: Un contributo tecnico cruciale è dimostrare che se $A$ è una $t$-LUOF, allora anche $A^\top$ è una $t$-LUOF (Lemma 3.9). Ciò si basa sul Lemma XOR di Vazirani e assicura che il codice duale erediti le forti proprietà di casualità del codice primale.

Contributi Chiave e Risultati

1. Funzioni di Hash $t$-Wise Indipendenti Veloci

• Risultato: Per ogni costante $t$, gli autori costruiscono una famiglia di funzioni di hash $t$-wise indipendenti computabili da circuiti di dimensione lineare.
• Ottimizzazione: Per il campo binario ($q=2$), il grado algebrico è ottimizzato a $\log_2 t$. Questo è quasi ottimale, poiché gradi inferiori non riuscirebbero a supportare l'indipendenza $t$-wise.
• Efficienza: La dimensione del circuito è $O(k+r)$, dove $k$ è la lunghezza dell'input e $r$ è la lunghezza dell'output. La costante nascosta dipende da $t$ (circa $\Theta(t^7)$), ma rimane costante per un $t$ fissato.

2. Codici Veloci con Duali Veloci (Limite GV)

• Risultato: Gli autori costruiscono una famiglia di codici $C$ e dei loro duali $C^\perp$ su qualsiasi campo finito $\mathbb{F}_q$ con tasso arbitrario $R \in (0, 1)$.
• Proprietà:
  • Sia $C$ che $C^\perp$ ammettono una codifica sistematica veloce (dimensione lineare).
  • Entrambi raggiungono distanze $\varepsilon$-vicine al limite di Gilbert-Varshamov con probabilità $1 - 2q^{-\varepsilon n}$.
  • La costruzione ha una probabilità di fallimento trascurabile (a differenza di [BR26]).
  • Supporta un circuito universale di dimensione lineare per la codifica.

3. Codici con Decodifica in Lista Veloci con Duali Veloci

• Risultato: Utilizzando la proprietà $t$-LUOF, gli autori estendono la costruzione a codici che sono $t$-localmente simili a codici lineari casuali.
• Decodifica in Lista: Dimostrano che per ogni costante $t$, i codici costruiti (e i loro duali) sono $(\rho, L)$-decodificabili in lista fino alla capacità di decodifica in lista, con dimensione della lista $L = O(1/\varepsilon)$.
• Novità: Questa è la prima costruzione (per quanto ne sappiano gli autori) che raggiunge simultaneamente codifica veloce, codifica del duale veloce e decodifica in lista ottimale sia per il codice che per il suo duale.

Significato e Applicazioni Crittografiche

Il documento dimostra che queste costruzioni fungono da potenti blocchi costruttivi per la crittografia, particolarmente in scenari che richiedono alta efficienza e forti garanzie di sicurezza.

1. Multiparty Computation (MPC) Perfettamente Sicura

Gli autori presentano i primi protocolli non banali per la MPC perfettamente sicura dove la complessità del circuito scala linearmente con il numero di parti ($O(n)$).

• Contesto: I protocolli precedenti che utilizzano codici algebrici (come i codici di Reed-Solomon) spesso incorrevano in un overhead quasi-lineare.
• Applicazione: Utilizzando i codici duali veloci, costruiscono un protocollo di Oblivious Linear Evaluation (OLE) e lo estendono a funzioni generiche di dimensione costante. Il protocollo raggiunge una soglia di sicurezza $t = (1/2 - \varepsilon)n$ contro avversari passivi.

2. Prodotti Matrice-Vettore Cifrati (EMVP)

Nel contesto della crittografia basata sulla complessità, gli autori applicano i loro codici duali veloci ai prodotti matrice-vettore cifrati.

• Miglioramento: La loro costruzione supera le limitazioni dell'approccio [BR26] (che era limitato a $\mathbb{F}_2$ e aveva una probabilità di fallimento non trascurabile).
• Beneficio: Ciò consente protocolli EMVP in cui sia la codifica della matrice che la codifica della query hanno una complessità di circuito asintoticamente ottimale.

3. Sostituti Conservativi per i Codici Lineari Casuali

La costruzione $t$-LUOF fornisce un sostituto "conservativo" per i codici lineari casuali in applicazioni che si affidano alla durezza dell'algebra rumorosa (ad esempio, Learning Parity with Noise - LPN).

• Vantaggio: Mentre le costruzioni precedenti si affidavano solo alla distanza minima (similarità 1-locale), la $t$-LUOF garantisce la similarità $t$-locale, assicurando proprietà combinatorie più forti come la decodificabilità in lista. Ciò offre un'assunzione di sicurezza più robusta contro attacchi che potrebbero sfruttare strutture locali.

4. Hashing MPC-Friendly

Le funzioni di hash $t$-wise indipendenti veloci con basso grado algebrico sono direttamente applicabili a protocolli MPC in cui sia la dimensione del circuito che il grado algebrico impattano la complessità di comunicazione e di round. La costruzione ottimizza entrambi simultaneamente.

Conclusione

Il documento riesce a generalizzare le precedenti costruzioni a dimensione lineare per supportare parametri di indipendenza più elevati e proprietà di tipo casuale più forti. Introducendo le $t$-LUOF veloci e dimostrando le loro proprietà di dualità, gli autori forniscono un framework unificato per costruire codici e funzioni di hash che siano simultaneamente veloci, sistematici e statisticamente robusti. Questi risultati abilitano nuovi protocolli crittografici con complessità asintotica ottimale, particolarmente nella MPC a informazione teorica e nel calcolo cifrato.