💻 computer science

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$ , Generically)

Questo articolo introduce una trasformazione generica che converte i PRF deboli in PRF forti con un overhead di profondità minimo, consentendo la costruzione di PRF computabili in $\mathsf{NC}^1$ da assunzioni standard inclusi LWE, LPN e CDH, risolvendo così problemi aperti di lunga data nella crittografia a bassa profondità.

Autori originali: Youlong Ding, Aayush Jain, Ilan Komargodski

Pubblicato 2026-08-27

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Youlong Ding, Aayush Jain, Ilan Komargodski

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Nel mondo digitale, la sicurezza si affida spesso a un tipo speciale di strumento matematico chiamato funzione pseudocasuale. Immaginate una macchina che prende un codice segreto e un pezzo di dato, poi produce una sequenza di numeri che appare completamente casuale a chiunque stia osservando. Se la macchina funziona correttamente, nessuno può distinguere il suo output da una sequenza veramente casuale, anche se ha visto la macchina operare molte volte prima. Questi strumenti sono le serrature e le chiavi invisibili che proteggono tutto, dalle transazioni bancarie online ai messaggi privati. Per decenni, i ricercatori hanno cercato di costruire queste macchine in modo che siano il più veloci possibile, specificamente facendole lavorare in pochissimi passaggi. Nel linguaggio dell'informatica, questo significa costruirle con un circuito molto superficiale, permettendo al calcolo di avvenire quasi istantaneamente sui moderni processori. Più veloci e semplici sono questi strumenti, più efficientemente possono essere utilizzati in sistemi complessi come il voto sicuro o la condivisione di dati privati.

Per molto tempo, c'è stata una testarda lacuna nella nostra capacità di costruire queste macchine veloci e superficiali. Sapevamo come crearle usando assunzioni matematiche molto forti e complesse, ma quelle richiedevano circuiti profondi e lenti. Al contrario, potevamo costruire circuiti superficiali, ma solo se ci affidavamo ad assunzioni più deboli e meno provate o a strutture matematiche molto specifiche e rigide. Era come avere una chiave che apriva una porta ma era troppo pesante da trasportare, o una chiave che era leggera ma che si adattava solo a una singola e strana serratura. L'obiettivo era trovare un modo per creare una chiave leggera che potesse aprire qualsiasi porta, utilizzando solo le serrature più standard e affidabili disponibili. Questa sfida è rimasta aperta per quasi trent'anni, limitando la nostra capacità di mettere in sicurezza il mondo digitale in modo efficiente.

Un team di ricercatori ha ora colmato questa lacuna con un nuovo metodo generale che trasforma uno strumento più debole e facile da costruire in uno forte e sicuro senza rallentarlo. Il loro lavoro, pubblicato in un articolo intitolato "Pseudorandom Functions in NC1 from LWE/LPN/CDH", dimostra che è possibile costruire queste macchine veloci e superficiali utilizzando tre delle assunzioni più fondamentali e ampiamente affidate della crittografia. I ricercatori hanno ottenuto questo risultato perfezionando un'antica idea chiamata costruzione GGM, che costruisce una funzione complessa percorrendo un albero di piccoli calcoli. Il modo tradizionale di farlo era come camminare lungo un lungo corridoio dove ogni passo richiedeva lo stesso sforzo, rendendo il viaggio totale lungo e lento. Il nuovo metodo cambia la forma del corridoio. Man mano che il processo si addentra nell'albero, la quantità di lavoro richiesto ad ogni passaggio diminuisce geometricamente. I primi passaggi sono pesanti, ma i passaggi successivi diventano sempre più leggeri, così rapidamente che lo sforzo totale rimane ridotto. Questa tecnica di "deformazione" (tapering) permette ai ricercatori di mantenere l'intero processo entro i limiti di un circuito superficiale e veloce.

Per dimostrare che questo nuovo metodo funziona, il team lo ha applicato a tre problemi matematici specifici che sono noti per essere difficili da risolvere. Il primo è il problema "Learning With Errors" (Apprendimento con Errori), che riguarda la ricerca di un modello nascosto in un insieme di dati rumorosi. I tentativi precedenti di costruire macchine veloci da questo problema richiedevano una versione più complessa e specifica della matematica che utilizzava numeri molto grandi. Il nuovo lavoro mostra che la versione standard di questo problema, con numeri molto più piccoli, è sufficiente. Il secondo problema è il "Learning Parity with Noise" (Apprendimento della Parità con Rumore), che riguarda la ricerca di un modello nascosto in un flusso di bit che sono stati invertiti casualmente. I ricercatori hanno dimostrato che il loro metodo funziona con la versione standard di questo problema, eliminando la necessità delle versioni specializzate e strutturate che erano precedentemente richieste. Il terzo problema è l'assunzione "Computational Diffie-Hellman", un pilastro della moderna sicurezza internet utilizzato per scambiare chiavi segrete. Per decenni, l'unico modo noto per costruire macchine veloci da questa assunzione si basava su una versione più forte e restrittiva del problema. La nuova costruzione dimostra che la versione standard è sufficiente.

La significatività di questo lavoro risiede nella sua generalità e nella sua dipendenza da assunzioni standard. Dimostrando che uno strumento debole e superficiale può essere aggiornato a uno forte e sicuro senza aggiungere profondità, i ricercatori hanno sbloccato la capacità di costruire funzioni veloci e sicure partendo dai problemi matematici più basilari e studiati. Questo risolve diverse questioni di lunga data nel campo e fornisce un nuovo, flessibile schema per i futuri sistemi crittografici. I ricercatori non si sono limitati a suggerire che ciò potrebbe essere possibile; hanno fornito una costruzione concreta, passo dopo passo, e una prova rigorosa del fatto che funziona. Hanno dimostrato che la profondità della macchina risultante è essenzialmente la stessa dello strumento di partenza, preservando il vantaggio di velocità pur acquisendo la necessaria sicurezza.

Questo traguardo significa che, per la prima volta, possiamo costruire questi strumenti di sicurezza essenziali utilizzando le fondamenta matematiche più comuni e affidabili, senza sacrificare la velocità. Elimina la necessità di varianti specializzate e complesse di questi problemi che si riteneva fossero necessarie per l'efficienza. Il risultato è una base più robusta e versatile per la sicurezza digitale del futuro, consentendo metodi di cifratura più veloci ed efficienti che possono essere implementati in una vasta gamma di tecnologie. Il lavoro si pone come la prova definitiva che la barriera tra strumenti deboli e veloci e strumenti forti e veloci è stata abbattuta, aprendo la porta a una nuova era di progettazione crittografica efficiente.

Sintesi Tecnica: Funzioni Pseudocasuali in NC1 da LWE/LPN/CDH

1. Enunciato del Problema

La costruzione di Funzioni Pseudocasuali (PRF) con bassa complessità parallela (specificamente all'interno della classe NC1, computabili tramite circuiti di dimensione polinomiale e profondità logaritmica) è stato un problema aperto di lunga data nella crittografia. Sebbene le PRF possano essere costruite genericamente da Generatori di Numeri Pseudocasuali (PRG) tramite la trasformazione di Goldreich-Goldwasser-Micali (GGM), questo metodo è intrinsecamente sequenziale. Anche se il PRG sottostante è computabile in profondità logaritmica, la PRF risultante richiede una profondità $\omega(\log n)$ , collocandola al di fuori di NC1.

Prima di questo lavoro, le PRF computabili in NC1 erano scarse e dipendevano da strutture algebriche altamente specifiche o assunzioni forti:

Naor-Reingold (1997, 2004): Hanno costruito PRF in $TC_0 \subseteq NC1$ partendo dal Decisional Diffie-Hellman (DDH) e dalla fattorizzazione.
Banerjee-Peikert-Rosen (2012): Hanno costruito PRF in $TC_0$ partendo da Ring-LWE, ma richiedevano un rapporto modulo-rumore super-polinomiale.
Ding-Jain-Komargodski (2025): Hanno costruito PRF da varianti strutturate di Learning Parity with Noise (LPN), come SeededLPN o Ring-LPN.

La sfida centrale è ottenere PRF computabili in NC1 da assunzioni standard (LWE con rapporto modulo-rumore polinomiale, LPN standard e Computational Diffie-Hellman) senza fare affidamento su varianti strutturate o parametri super-polinomiali.

2. Metodologia

Il documento introduce un approccio a due fronti: una trasformazione generica che preserva la profondità da Funzioni Pseudocasuali Deboli (WPRF) a PRF forti, e nuove costruzioni di WPRF (o sintetizzatori) a bassa profondità partendo da assunzioni standard.

2.1 Tapering-GGM: Una Trasformazione Generica

Gli autori propongono un'innovativa adattazione della costruzione ad albero GGM, denominata Tapering-GGM, che potenzia una WPRF in una PRF forte preservando la profondità del circuito di valutazione.

Il Meccanismo di Tapering (Riduzione): In un albero GGM standard, la dimensione dello stato rimane costante e la profondità si accumula linearmente con il numero di livelli dell'albero ( $\ell \cdot d_{WPRF}$ ). In Tapering-GGM, la dimensione dello stato si riduce geometricamente ad ogni livello. Se il parametro di sicurezza al livello $i$ è $\lambda^{(i)}$ , gli autori definiscono $\lambda^{(i)} = \lambda^{2^{-i+1}}$ . Di conseguenza, la profondità della chiamata alla WPRF al livello $i$ , denotata $d(\lambda^{(i)})$ , diminuisce geometricamente.
Analisi della Profondità: Se la WPRF di base ha profondità $d(\lambda) = \Theta(\log \lambda)$ , la profondità totale della costruzione Tapering-GGM diventa:
$d_{total} = O(\log \lambda) + \sum_{i=1}^{\ell} d(\lambda^{(i)}) \approx O(\log \lambda) + \sum_{i=1}^{\ell} \log(\lambda^{2^{-i+1}}) = O(\log \lambda)$
Questa decrescita geometrica assicura che la profondità totale rimanga $O(d(\lambda))$ , mantenendo la costruzione all'interno di NC1 se la WPRF di base è in NC1.
Sfide di Sicurezza e Soluzioni:
- Sfida: Man mano che l'albero si approfondisce, il parametro di sicurezza $\lambda^{(i)}$ diventa piccolo (sub-polinomiale), potenzialmente compromettendo la sicurezza computazionale della WPRF sottostante.
- Soluzione 1 (Hashing): L'input viene prima processato tramite una funzione di hash pairwise-indipendente. Ciò assicura che, con alta probabilità, le query dell'avversario siano "frammentate" (mappate su percorsi distinti) entro i primi $O(\log_\Delta q)$ livelli, dove il parametro di sicurezza è ancora polinomiale.
- Soluzione 2 (Uniformità della Chiave): Per i livelli al di sotto del punto di frammentazione, la costruzione si affida alla sicurezza informazionale. Gli autori richiedono che la WPRF sia key-uniform (1-wise independent). Se lo stato al livello di frammentazione è pseudocasuale, la successiva composizione di trasformazioni key-uniform mappa questo stato verso un output perfettamente uniforme, indipendentemente dalla durezza computazionale delle WPRF di livello inferiore.

2.2 Costruzioni di WPRF a Bassa Profondità

Gli autori istanziano il framework Tapering-GGM con nuove costruzioni di WPRF partendo da assunzioni standard:

Da LWE (Learning With Errors):
- Gli autori costruiscono la prima WPRF in NC1 da LWE standard con un rapporto modulo-rumore polinomiale ( $\alpha = n^{-\epsilon}$ ).
- Strumento Tecnico Chiave: Un Campionatore Gaussiano Arrotondato (Rounded Gaussian Sampler) computabile in profondità $O(\text{poly}(\log \log \lambda))$ . Approximano la trasformata di Box-Muller utilizzando approssimazioni polinomiali a bassa profondità per $\ln$ , $\cos$ e l'iterazione di Newton per le radici quadrate.
- Costruzione: Impiegano un paradigma di concatenazione (ispirato a Kim [Kim20]). La costruzione calcola i prodotti interni LWE mascherati livello per livello. I bit di ordine superiore dell'output di un livello campionano deterministicamente la distribuzione dell'errore per il livello successivo. La limitatezza del campionatore dell'errore garantisce la stabilità, permettendo alla prova di sicurezza di procedere tramite ibridi.
Da LPN (Learning Parity with Noise):
- Gli autori sfruttano un recente risultato di Ding, Jain e Komargodski [DJK25] che fornisce WPRF in NC1 da LPN standard (rumore con probabilità inversa polinomiale arbitraria).
- Combinando questo con Tapering-GGM, ottengono le prime PRF in NC1 da LPN standard, eliminando la necessità di varianti strutturate (es. Ring-LPN).
Da CDH (Computational Diffie-Hellman):
- Gli autori osservano che Tapering-GGM richiede in realtà una primitiva più debole di una WPRF: un Sintetizzatore (dove il pool di input è nascosto all'avversario).
- Istanziano la trasformazione utilizzando la costruzione del sintetizzatore di Naor-Reingold [NR95, NR99], che è computabile in NC1 sotto l'assunzione CDH. Ciò produce le prime PRF in NC1 da CDH, migliorando le precedenti costruzioni basate su DDH.

3. Contributi Chiave

Trasformazione Generica che Preserva la Profondità: Una trasformazione black-box che converte qualsiasi WPRF (o sintetizzatore) computabile in profondità $d(\lambda) = \Omega(\log \lambda)$ in una PRF forte computabile in profondità $O(d(\lambda))$ . Questo risolve la barriera generica che impedisce alle PRF in NC1 di derivare da assunzioni standard.
PRF in NC1 da LWE Standard: La prima costruzione di PRF in NC1 da LWE con un rapporto modulo-rumore polinomiale, risolvendo un problema aperto esplicitamente citato nelle note di lezione di Vaikuntanathan. Ciò si basa sulla durezza di GapSVP con fattori di approssimazione polinomiali.
PRF in NC1 da LPN Standard: La prima costruzione di PRF in NC1 dall'assunzione LPN standard, eliminando la necessità di varianti strutturate come Ring-LPN o Sparse LPN.
PRF in NC1 da CDH: La prima costruzione di PRF in NC1 dall'assunzione Computational Diffie-Hellman, migliorando il risultato di 30 anni fa di Naor-Reingold che si basava sul più forte Decisional Diffie-Hellman (DDH).
Campionatore Gaussiano a Bassa Profondità: Un nuovo circuito deterministico per campionare errori gaussiani arrotondati in profondità $O(\text{poly}(\log \log \lambda))$ , che è un componente critico per la WPRF basata su LWE.

4. Risultati

Il documento stabilisce i seguenti risultati concreti:

Teorema: Se esistono WPRF in NC1, allora esistono PRF in NC1.
Corollario (LWE): Assumendo che l'assunzione LWE sia valida per un rapporto rumore-modulo $\alpha = n^{-\epsilon}$ , esistono PRF in NC1.
Corollario (LPN): Assumendo che l'assunzione LPN sia valida per una probabilità di rumore $\mu = n^{-\epsilon}$ , esistono PRF in NC1.
Corollario (CDH): Assumendo che l'assunzione CDH sia valida, esistono PRF in NC1.
Corollario (GapSVP): Assumendo che GapSVP sia difficile da approssimare entro un fattore $\tilde{O}(n^{1+\epsilon})$ , esistono PRF in NC1.

5. Significato

Il lavoro sostiene di risolvere diversi problemi aperti di lunga data nella complessità dei primitivi crittografici. Decoupling (scollegando) la profondità di valutazione della PRF dalla natura sequenziale della trasformazione GGM, gli autori dimostrano che le PRF forti possono essere costruite da una vasta gamma di assunzioni standard senza sacrificare l'efficienza parallela.

Nello specifico, il lavoro:

Rimuove la dipendenza da Ring-LWE e dai parametri super-polinomiali per le PRF in NC1, passando a LWE standard con parametri polinomiali.
Rimuove la dipendenza da varianti strutturate di LPN, passando a LPN standard.
Indebolisce l'assunzione di durezza per le PRF basate su CDH da DDH a CDH.
Fornisce un framework generico (Tapering-GGM) che può potenziare qualsiasi esistente candidato WPRF a bassa profondità (es. da [ABG+14], [AR16]) in una PRF a bassa profondità, a condizione che l'assunzione sottostante sia valida.

Gli autori posizionano questo lavoro come un passo fondamentale per comprendere la complessità parallela della crittografia, con implicazioni per i protocolli di computazione sicura, la teoria dell'apprendimento (tramite le connessioni PRF-versus-learning) e la meta-complessità.