Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits

1. Il Problema e il Contesto

Il lavoro si concentra sulla complessità comunicativa nei protocolli crittografici a due parti (Alice e Bob) che devono calcolare funzioni su input privati senza rivelarli. In particolare, il paper affronta il problema della Valutazione Ostile Non Interattiva del Tensor (NI-OTE).

• Scenario: Alice possiede un vettore lungo $x \in \mathbb{Z}_q^m$, Bob possiede un vettore segreto più piccolo $y \in \mathbb{Z}_q^\ell$.
• Obiettivo: Dopo una singola round di messaggi simultanei, le due parti devono ottenere una condivisione segreta additiva del prodotto tensoriale $x \otimes y$, ovvero $\alpha + \beta = x \otimes y$, preservando la privacy di $y$ (e in alcune varianti anche di $x$).
• Sfida: Intuitivamente, ci si aspetterebbe che i messaggi debbano essere proporzionali alla dimensione degli input. L'obiettivo è costruire protocolli succinti, dove la dimensione dei messaggi è indipendente (o logaritmica) rispetto alla dimensione di $x$, pur mantenendo la sicurezza basata su assunzioni standard come LWE (Learning With Errors).

2. Metodologia e Costruzioni Chiave

Gli autori sviluppano una serie di strumenti tecnici che si fondono per raggiungere i risultati finali.

A. Valutazione Ostile del Tensor (NI-OTE) Succinta

La costruzione principale è un protocollo NI-OTE che riduce la complessità comunicativa.

1. NI-OTE "Half-Succinct": Viene prima costruita una versione in cui solo il messaggio di Alice (l'hasher) è succinto (indipendente da $|x|$), mentre quello di Bob dipende da $|x|$. La costruzione si basa su:
   • Una matrice pubblica $A$ e una matrice $B$ (pseudocasuale tramite LWE).
   • Alice calcola un hash $d = A \cdot x$.
   • Bob calcola un encoding $C$ che nasconde $y$ usando un segreto $s$ e rumore LWE.
   • La somma dei risultati locali ($C^\top x$ e $-s^\top d$) rivela $x \otimes y$ più un piccolo errore.
2. Bootstrapping a "Fully-Succinct": Per rendere succinto anche il messaggio di Bob, gli autori utilizzano una strategia ricorsiva. Invece di inviare l'intero vettore $x$, Alice lo suddivide in blocchi e invia solo gli hash di questi blocchi. Bob invia un encoding che può essere valutato contro tutti gli hash.
   • Innovazione Critica: Per evitare che la dimensione del segreto di Bob esploda durante la ricorsione, gli autori sostituiscono il segreto casuale con uno pseudocasuale generato tramite LWE (usando matrici binarie $B_i$). Questo permette di mantenere la dimensione del segreto costante ($s$) mentre si riduce la dimensione dell'input di Alice a livello logaritmico.

B. Codifiche di Reticolo Adattive (Adaptive Lattice Encodings)

Un ingrediente tecnico fondamentale è una nuova variante delle codifiche di reticolo (basate su BGG+14) che supporta la sicurezza adattiva.

• Problema delle codifiche BGG+: Sono sicure solo in modo selettivo (l'input $x$ deve essere scelto prima di vedere i parametri pubblici). Se $x$ è scelto adattivamente dopo aver visto la chiave pubblica, esistono attacchi per recuperare il segreto.
• Soluzione: Gli autori introducono codifiche con due chiavi: una chiave di cifratura $s$ e una chiave di autenticazione $r$. La codifica è della forma $c = s^\top A + r^\top(x \otimes G) + e$.
• Proprietà: Queste codifiche sono sicure contro attacchi adattivi sotto LWE standard. Inoltre, permettono operazioni omomorfe (somma e moltiplicazione) tra codifiche che condividono chiavi correlate (es. la chiave di autenticazione della prima è la chiave di cifratura della seconda).
• Compressione: Viene presentata una procedura per comprimere queste codifiche adattive utilizzando il protocollo NI-OTE, riducendo la dimensione da lineare a logaritmica rispetto all'input.

C. Hashing con Trappola Inverso (Reverse Trapdoor Hashing - TDH)

Sfruttando il NI-OTE e le codifiche adattive, gli autori costruiscono uno schema di Reverse TDH.

• Differenza dal TDH classico: Nel TDH classico, Alice ha la funzione $f$ e Bob l'input $x$. Nel Reverse TDH, Alice ha $f$ (e ne invia un hash) e Bob ha $x$ (e ne invia un encoding).
• Vantaggio: Questo permette di ottenere schemi dove la dimensione della chiave di encoding dipende solo dalla descrizione della funzione $f$ e non dalla dimensione dell'input $x$, raggiungendo una comunicazione ottimale.

3. Risultati Principali e Contributi

Il paper presenta diversi risultati teorici e pratici, tutti basati sull'assunzione standard di LWE (senza bisogno di assunzioni più forti come LWE adattivo o circolarità):

1. NI-OTE Succinta Ottimale:

   • Un protocollo NI-OTE con complessità comunicativa $\ell \cdot \text{poly}(\lambda) + \text{poly}(\lambda, \log m)$.
   • La dimensione della CRS (Common Reference String) è $\text{poly}(\lambda, \log m)$.
   • Questo è il primo protocollo OTE con tali parametri basato su LWE standard.

2. Reverse Trapdoor Hashing per Tutte le Funzioni:

   • Costruzione di un TDH per funzioni di profondità $D$ con dimensione della chiave di encoding $|f| \cdot \text{poly}(\lambda, D)$.
   • Supporta anche programmi RAM.
   • Migliora i lavori precedenti che supportavano solo funzioni lineari o richiedevano assunzioni più forti.

3. Condivisione Segreta Omomorfa Succinta (HSS):

   • Un protocollo HSS pubblico per tutte le funzioni, con complessità comunicativa logaritmica nell'input lungo di Alice.
   • Supera i lavori precedenti (es. [ARS24]) che supportavano solo circuiti NC1 e avevano complessità polinomiale sub-lineare ma non logaritmica.

4. Laconic Function Evaluation (LFE) Adattiva a Tasso 1:

   • Risultato di punta: Il primo schema LFE che è simultaneamente:
     • Adattivamente sicuro: L'attaccante può scegliere l'input dopo aver visto i parametri pubblici (risolvendo un problema aperto di [QWW18]).
     • A Tasso 1 (Rate-1): La dimensione dell'encoding è $m + \ell + D \cdot \text{poly}(\lambda)$, ovvero lineare nell'input più un fattore additivo.
   • Questo risultato è ottenuto basandosi solo su LWE standard, migliorando lavori concorrenti che richiedevano varianti di LWE più deboli o complessi.

5. Controesempio all'Assunzione LWE Adattiva:

   • Gli autori mostrano che l'assunzione "Adaptive LWE" proposta in [QWW18] è falsa in impostazioni di parametri ottimistici (dove la dimensione dell'input può essere arbitrariamente più grande della dimensione della matrice pubblica). Forniscono un attacco concreto che recupera il segreto, sottolineando la necessità di costruire primitive basate su LWE standard.

4. Significato e Impatto

Questo lavoro rappresenta un avanzamento significativo nella crittografia basata su reticoli (Lattice-based cryptography):

• Risoluzione di Problemi Aperti: Risolve il problema della sicurezza adattiva per l'LFE e la costruzione di TDH per funzioni generali, problemi che erano aperti o risolti solo con assunzioni non standard.
• Ottimalità dei Parametri: Raggiunge limiti di comunicazione ottimali (tasso 1 e complessità logaritmica) basandosi sull'assunzione di sicurezza più standard e robusta (LWE), evitando il "costo" di assunzioni più forti o di parametri esagerati.
• Nuovi Strumenti Tecnici: L'introduzione delle codifiche di reticolo adattive e del protocollo NI-OTE è di per sé un contributo indipendente che probabilmente troverà applicazioni future in altri contesti crittografici (es. crittografia omomorfa, generazione di correlazioni pseudocasuali).
• Applicazioni Pratiche: Le tecniche abilitano schemi di trasferimento obliquo (OT) più efficienti, crittografia "spooky" e generatori di correlazione, rendendo queste primitive più pratiche per scenari reali dove la larghezza di banda è limitata.

In sintesi, il paper dimostra che è possibile ottenere primitive crittografiche altamente efficienti e adattivamente sicure utilizzando solo l'assunzione LWE standard, superando le limitazioni dei lavori precedenti e fornendo nuovi strumenti fondamentali per la teoria della crittografia.