Non-Trivial Zero-Knowledge Implies One-Way Functions

1. Il Problema e il Contesto

La ricerca si colloca nel campo della crittografia teorica e della complessità computazionale, focalizzandosi sulla relazione fondamentale tra le Dimostrazioni a Conoscenza Zero (ZK) e le Funzioni a Una Via (OWF).

• Sfondo Storico: Risultati classici (Ostrovsky-Wigderson, 1993) hanno stabilito che l'esistenza di ZK per problemi NP implica l'esistenza di OWF, ma solo assumendo che gli errori di completezza, correttezza e zero-knowledge siano negligibili.
• Progressi Recenti: Hirahara e Nanashima (STOC 2024) hanno mostrato che, assumendo la durezza nel caso peggiore di NP ($NP \not\subseteq ioP/poly$), anche ZK con errori trascurabili implicano OWF.
• Il Gap Aperto: Cosa succede se permettiamo errori non trascurabili (ma comunque "non banali")? È noto che protocolli con errori tali che la somma di completezza ($\epsilon_c$), correttezza ($\epsilon_s$) e zero-knowledge ($\epsilon_{zk}$) sia $\ge 1$ sono banali e non richiedono assunzioni crittografiche. Tuttavia, il caso in cui la somma sia strettamente minore di 1 (ma non trascurabile) rimaneva un'area inesplorata.
• Domanda Chiave: L'esistenza di protocolli ZK "non banali" (dove $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1 - 1/poly(n)$) implica l'esistenza di OWF?

2. Metodologia e Tecniche

Gli autori sviluppano nuove tecniche per superare i limiti delle riduzioni precedenti, che fallivano quando gli errori erano grandi.

A. Superamento delle Barriere Precedenti

Le tecniche di [OW93] e [CHK25] si basavano su un'analisi di ibridi che richiedeva condizioni strette sugli errori (es. $\epsilon_s + 2\epsilon_{zk} < 1$ o $\epsilon_{zk} + 2\sqrt{\epsilon_s} < 1$). Gli autori dimostrano che queste tecniche non possono essere semplicemente affinate per coprire il caso generale non banale, fornendo un controesempio specifico in cui l'analista fallisce.

B. La Tecnica della Ripetizione (Repetition)

Per il caso Non-Interattivo (NIZK), gli autori introducono un algoritmo di decisione che utilizza la Universal Extrapolation (UE) (possibile se le OWF non esistono) per campionare molte prove simulate.

• Idea Chiave: Invece di accettare se una prova simulata è accettata, l'algoritmo ripete il processo molte volte ($p(n)$ volte) con lo stesso CRS (Common Reference String) ma con nuova aleatorietà.
• Logica: Se il CRS è "cattivo" (il simulatore non riesce quasi mai a produrre prove accettate), la probabilità che il simulatore lo generi è limitata dall'errore di zero-knowledge. Se il CRS è "buono", la ripetizione garantisce che l'algoritmo trovi una prova accettante con alta probabilità. Questo permette di distinguere tra input in $L$ e fuori da $L$ purché $\epsilon_s + \epsilon_{zk} < 1$.

C. Generalizzazione al Caso Interattivo

Estendere la tecnica al caso interattivo è più complesso perché il verificatore non è necessariamente "public-coin" (i suoi messaggi non sono solo casualità pubblica) e lo stato interno conta.

• Prover Malizioso ($\tilde{P}$): Gli autori definiscono un prover malizioso che, dato un trascritto parziale, usa l'UE per campionare molti possibili prossimi messaggi dal simulatore.
• Stima della Probabilità: $\tilde{P}$ stima quale messaggio massimizza la probabilità di accettazione futura simulando l'interazione "nella propria testa" (possibile solo se il protocollo è public-coin o tramite trasformazioni specifiche).
• Gestione degli Errori: Invece di richiedere che $\tilde{P}$ scelga il messaggio ottimale, si dimostra che scegliere un messaggio tra i "migliori" (top $\delta$) è sufficiente. L'analisi mostra che la perdita di probabilità di accettazione è controllata e non si accumula linearmente con il numero di round $k$, a differenza delle tecniche precedenti.

D. Dal Private-Coin al Public-Coin

Per i protocolli a monete private, gli autori dimostrano che, a meno che non esistano OWF con input ausiliario, è possibile convertire qualsiasi protocollo a round costante in uno public-coin. Questo porta alla costruzione di OWF con input ausiliario nel caso generale.

3. Risultati Principali

Il paper stabilisce caratterizzazioni complete della complessità nel caso peggiore per ZK non banali:

1. Teorema Principale (NIZK): Se $NP \not\subseteq ioP/poly$ e esistono argomenti NIZK non banali per NP, allora esistono Funzioni a Una Via (OWF).

   • Questo migliora i risultati precedenti [CHK25] che richiedevano condizioni più stringenti sugli errori (es. $\epsilon_{zk} + \sqrt{\epsilon_s} < 1$).

2. Teorema Principale (Interattivo): Se $NP \not\subseteq ioP/poly$ e esistono argomenti ZK pubblici, a monete pubbliche e a round costante non banali per NP, allora esistono OWF con input ausiliario.

   • Se si assume l'assenza di OWF con input ausiliario, allora ogni protocollo private-coin a round costante può essere convertito in public-coin.

3. Amplificazione degli Errori:

   • NIZK: I risultati implicano che, sotto l'assunzione di durezza nel caso peggiore di NP, qualsiasi NIZK non banale può essere amplificato in un NIZK standard con errori trascurabili, senza bisogno di assunzioni crittografiche aggiuntive (come la crittografia a chiave pubblica).
   • Interattivo: Analogamente, l'esistenza di ZK non banali implica l'esistenza di OWF, che a loro volta implicano l'esistenza di protocolli ZK interattivi a 4 round con errori trascurabili (risultato di [BJY97]).

4. Contributi Chiave

• Caratterizzazione Completa: Chiudono il gap teorico mostrando che la soglia per la non-banalità ($\sum \epsilon < 1$) è esattamente il punto in cui la struttura ZK diventa sufficiente per costruire OWF, indipendentemente dalla grandezza degli errori (purché non banali).
• Nuova Tecnica di Analisi: L'uso della ripetizione per "isolare" i CRS buoni dai cattivi nel caso NIZK e l'uso di prover maliziosi che campionano e stimano probabilità nel caso interattivo rappresentano un avanzamento metodologico significativo.
• Riduzione delle Assunzioni: Eliminano la necessità di assunzioni crittografiche forti (come PKE) per l'amplificazione dei protocolli ZK non banali, basandosi solo sulla durezza nel caso peggiore di NP.

5. Significato e Implicazioni

Questo lavoro ha un impatto profondo sulla comprensione della complessità della crittografia:

• Robustezza delle OWF: Dimostra che le OWF sono una conseguenza inevitabile di qualsiasi schema ZK che non sia "triviale" (cioè che non permetta di accettare tutto o niente con probabilità 1).
• Limiti dei Protocolli Deboli: Suggerisce che non è possibile costruire protocolli ZK "deboli" (con errori grandi) che siano utili per scopi pratici senza implicitamente costruire le basi della crittografia moderna (OWF).
• Semplificazione delle Assunzioni: Fornisce una via per ottenere protocolli ZK standard (con errori trascurabili) partendo da protocolli molto più facili da costruire (con errori grandi), riducendo il carico delle assunzioni di sicurezza necessarie.

In sintesi, il paper stabilisce che la "non-banalità" è la proprietà critica che separa i protocolli ZK banali da quelli che implicano la fondazione della crittografia moderna, indipendentemente dalla precisione degli errori.