Ciphertext-Policy ABE for $\mathsf{NC}^1$ Circuits with Constant-Size Ciphertexts from Succinct LWE

Titolo

CP-ABE per Circuiti NC1 con Cifrari a Dimensione Costante da LWE Succinto

1. Il Problema

L'obiettivo della ricerca è costruire uno schema di Ciphertext-Policy Attribute-Based Encryption (CP-ABE) basato su reticoli (lattice-based) che supporti politiche di accesso rappresentate da circuiti nella classe di complessità NC1.
Le sfide principali affrontate sono:

• Dimensione del Cifrario: Negli schemi CP-ABE esistenti basati su LWE (Learning With Errors), la dimensione del cifrario spesso scala con la dimensione del circuito o la lunghezza degli input, rendendo inefficiente l'uso per politiche complesse.
• Assunzioni di Sicurezza: Molti schemi precedenti si basano su assunzioni non standard o complesse (come "evasive LWE" o "tensor LWE"). L'obiettivo è utilizzare assunzioni più deboli e standard, pur mantenendo l'efficienza.
• Ottimalità dei Parametri: Si cerca di raggiungere cifrari di dimensione costante ($O(1)$) rispetto alla profondità del circuito, indipendentemente dal numero di utenti o dalla complessità della politica, mantenendo la sicurezza nel modello standard.

2. Metodologia

Gli autori propongono una costruzione che combina diverse tecniche avanzate della crittografia basata su reticoli:

• Assunzione LWE Succinto ($\ell$-succinct LWE): La sicurezza si basa sull'assunzione di LWE succinto introdotta da Wee (CRYPTO 2024). Questa assunzione permette di gestire istanze di LWE con parametri compatti, dove la matrice pubblica è piccola rispetto alla dimensione dell'input.
• Schema LSSS (Linear Secret Sharing Scheme): Utilizzano una trasformazione da circuiti booleani a schemi di condivisione segreta lineare (LSSS) non monotoni (basata su [DKW21]), permettendo di rappresentare politiche NC1 come matrici con coefficienti in $\{-1, 0, 1\}$.
• Matrice di Impegno (Matrix Commitment): Per comprimere la dimensione del cifrario, adottano uno schema di impegno per matrici (da [Wee25]). Invece di includere nel cifrario una componente per ogni riga della matrice di accesso (che crescerebbe con la dimensione del circuito), commettono l'intera matrice in un singolo elemento di dimensione costante.
• Generazione di Trappole (Trapdoor Generation): Una parte cruciale della dimostrazione di sicurezza è la capacità del challenger di generare chiavi segrete per insiemi di attributi non autorizzati senza rivelare informazioni sulle istanze LWE sottostanti. Questo viene ottenuto sfruttando la trappola $T$ fornita nell'assunzione LWE succinto per generare nuove trappole per matrici derivate, permettendo di simulare le risposte alle query senza usare la trappola master originale.
• Tecnica del "Smudging" (Noise Smudging): Viene utilizzata per garantire che le distribuzioni dei segreti e dei cifrari siano statisticamente indistinguibili quando si passa da un gioco ibrido all'altro nella prova di sicurezza, mascherando piccoli errori o perturbazioni.

3. Contributi Chiave

1. Cifrari a Dimensione Costante: Hanno costruito un primo schema CP-ABE per circuiti NC1 in cui la dimensione del cifrario è $O(1)$ (indipendente dalla dimensione $s$, dalla profondità $d$ e dalla lunghezza dell'input $\ell$ del circuito), nascondendo solo fattori polinomiali nel parametro di sicurezza $\lambda$.
2. Parametri Ottimali:
   • Dimensione della chiave pubblica: $O(s)$ (dove $s$ è la dimensione del circuito), ma con la possibilità di comprimere la parte uniforme tramite generatori pseudo-casuali per ottenere $O(1)$.
   • Dimensione della chiave segreta: $O(\ell)$ (lunghezza dell'input), che può essere ridotta a $O(1)$ se l'utente possiede un numero costante di attributi.
3. Sicurezza nel Modello Standard: La sicurezza è dimostrata in modo selettivo (selectively secure) nel modello standard sotto l'assunzione di poly($\lambda$)-succinct LWE, un'assunzione più debole e standard rispetto a quelle utilizzate in lavori precedenti (come evasive LWE).
4. Broadcast Encryption Ottimale: Come applicazione diretta, ottengono uno schema di Broadcast Encryption per $N$ utenti con dimensione del cifrario indipendente da $\log N$, raggiungendo l'ottimalità asintotica.

4. Risultati

I parametri dello schema proposto sono i seguenti (dove $\lambda$ è il parametro di sicurezza):

• **Dimensione della Chiave Pubblica ($|pk|$):**$O(s)$, dove $s$ è la dimensione del circuito. Tuttavia, poiché la maggior parte dei parametri è campionata uniformemente, può essere compressa a $O(1)$ usando un generatore pseudo-casuale.
• **Dimensione del Cifrario ($|ct|$):**$O(1)$, indipendente da $s$, $d$ e $\ell$. Questo è asintoticamente ottimale.
• **Dimensione della Chiave Segreta ($|sk|$):**$O(\ell)$, dipendente dal numero di attributi associati all'utente.
• Sicurezza: Selettivamente sicura contro collusioni illimitate (unbounded collusions) sotto l'assunzione LWE succinto con rapporto segnale-rumore sub-esponenziale.

Nel caso specifico di Broadcast Encryption per $N$ utenti:

• $|pk| = \text{poly}(\lambda)$ (dopo compressione).
• $|sk| = \text{poly}(\lambda, \log N)$.
• $|ct| = \text{poly}(\lambda)$, indipendente da $N$ e $\log N$.

5. Significato e Impatto

Questo lavoro rappresenta un passo significativo verso l'efficienza pratica della crittografia basata su reticoli per l'accesso granulare ai dati:

• Efficienza Scalabile: La dimensione costante del cifrario risolve un collo di bottiglia fondamentale negli schemi CP-ABE basati su LWE, rendendo fattibile l'uso di politiche di accesso complesse (circuiti NC1) senza penalizzare la larghezza di banda o lo storage.
• Robustezza Quantistica: Essendo basato su LWE, lo schema è resistente agli attacchi quantistici, a differenza di molte soluzioni basate su gruppi bilineari.
• Assunzioni più Deboli: L'uso dell'assunzione "succinct LWE" invece di assunzioni più forti o non standard (come tensor LWE o evasive LWE) rende la costruzione più credibile e vicina alla pratica reale.
• Applicazione al Broadcast Encryption: Fornisce la prima costruzione di Broadcast Encryption con cifrari di dimensione costante (indipendente dal numero di utenti) basata su assunzioni LWE standard, superando i limiti precedenti dove la dimensione del cifrario dipendeva da $\log N$.

In sintesi, gli autori hanno dimostrato che è possibile ottenere un controllo di accesso fine-granulare con cifrari di dimensione costante utilizzando solo assunzioni di reticolo standard, ponendo le basi per sistemi di crittografia post-quantistica più scalabili ed efficienti.