Weak Zero-Knowledge and One-Way Functions

1. Il Problema e il Contesto

La ricerca si colloca nel campo della crittografia teorica, specificamente nell'analisi delle implicazioni della Zero-Knowledge (ZK) sulla costruzione di primitivi crittografici fondamentali, come le Funzioni Unidirezionali (OWF - One-Way Functions).

Storicamente, risultati fondamentali (come quelli di Ostrovsky [Ost91] e Ostrovsky-Wigderson [OW93]) hanno dimostrato che l'esistenza di protocolli ZK per linguaggi difficili (in media o nel caso peggiore) implica l'esistenza di OWF. Tuttavia, questi risultati classici presuppongono che gli errori del protocollo (completamento $\epsilon_c$, correttezza/soundness $\epsilon_s$, e zero-knowledge $\epsilon_z$) siano negligibili.

In pratica, molti protocolli ZK noti e utili (es. per il 3-coloring o l'isomorfismo di grafi) non hanno errori trascurabili nativamente, ma presentano errori costanti o significativi. Questi sono definiti Weak ZK (ZK deboli).
Il problema centrale affrontato dal paper è: Quali sono le implicazioni sulla sicurezza crittografica (esistenza di OWF) se assumiamo l'esistenza di protocolli ZK deboli per linguaggi NP difficili nel caso peggiore?

Un lavoro precedente di Chakraborty et al. [CHK25] aveva mostrato che per i protocolli NIZK (Non-Interactive Zero-Knowledge), se $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$, allora le OWF esistono. Il limite di questo approccio era che non copriva tutti i parametri non banali (ad esempio, non copriva il caso in cui $\epsilon_s$ è grande ma $\epsilon_c + \epsilon_s + \epsilon_z < 1$).

2. Metodologia e Approccio Tecnico

Gli autori sviluppano una nuova tecnica di riduzione che collega l'inversione di funzioni costruite dai simulatori ZK alla capacità di distinguere se un input appartiene a un linguaggio difficile.

A. Costruzione della Funzione Unidirezionale

Il cuore della metodologia è la costruzione di una famiglia di funzioni $f_x$ basata sul simulatore del protocollo ZK.

• Approccio Tradizionale (OW93): Il simulatore genera una stringa di riferimento comune $r$ e una prova $\pi$. La funzione era $f_x(\rho) = r$. L'inversione permetteva di distinguere tra $r$ generati dal simulatore e $r$ casuali.
• Miglioramento degli Autori: Gli autori introducono una funzione che include anche il risultato della verifica:
  $$f_x(\rho) = (r, a)$$
  dove $(r, \pi) \leftarrow \text{Sim}(x; \rho)$ e $a = V(x; r, \pi)$.
  Questo permette di vincolare l'invertitore a trovare un pre-immagine che corrisponda a una prova valida (dove $a=1$).

B. Ottimizzazione dell'Errore

La chiave del miglioramento è evitare di "pagare" due volte l'errore di zero-knowledge ($\epsilon_z$).

• Nel lavoro precedente, la distinzione richiedeva due passaggi di indistinguibilità, portando a condizioni come $\epsilon_s + 2\epsilon_z < 1$ o $\sqrt{\epsilon_s} + \epsilon_z < 1$.
• Con la nuova costruzione, se un invertitore riesce a trovare un pre-immagine per $(r, 1)$, significa che ha trovato un $\rho$ tale che il simulatore produce una prova accettata. Poiché la verifica è parte della funzione, non è necessario un ulteriore controllo esplicito che introdurrebbe un altro errore $\epsilon_z$.
• Questo porta alla condizione ottimale: $\epsilon_c + \epsilon_s + \epsilon_z < 1$.

C. Estensione ai Protocolli Interattivi (Public-Coin)

Per i protocolli interattivi a moneta pubblica (dove le sfide del verificatore sono bit casuali pubblici), gli autori utilizzano un approccio ricorsivo:

1. Definiscono funzioni per ogni round del protocollo.
2. Costruiscono un "prover" fittizio $\tilde{P}$ che utilizza gli invertitori delle funzioni dei round successivi per generare le risposte ottimali nei round precedenti.
3. Analizzano la probabilità di accettazione di questo prover fittizio.
   • Per protocolli a $t$ messaggi: la condizione è $\epsilon_c + \epsilon_s + (t-1)\epsilon_z < 1$.
   • Per protocolli a $k$ round (costanti): la condizione migliora a $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$, ma con una limitazione sulla sicurezza (vedi Risultati).

3. Risultati Chiave

Il paper stabilisce tre teoremi principali, assumendo che esistano linguaggi in NP difficili nel caso peggiore (ovvero $NP \not\subseteq ioP/poly$ o $NP \not\subseteq P/poly$):

1. NIZK (Non-Interactive):
   Se ogni linguaggio in NP ha un protocollo NIZK (o argomento) con errori $(\epsilon_c, \epsilon_s, \epsilon_z)$ tali che $\epsilon_c + \epsilon_s + \epsilon_z < 1$, allora le OWF esistono.

   • Significato: Questo copre tutti i valori non banali possibili per gli errori, migliorando il risultato precedente di [CHK25] che richiedeva $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$. Inoltre, implica che se $\epsilon_c$ è trascurabile, è possibile amplificare il protocollo per avere errori trascurabili su tutti i parametri.

2. ZK Public-Coin a $t$ messaggi:
   Se ogni linguaggio in NP ha un protocollo ZK pubblico a $t$ messaggi con $\epsilon_c + \epsilon_s + (t-1)\epsilon_z < 1$, allora le OWF esistono.

3. ZK Public-Coin a $k$ round (costanti):
   Se ogni linguaggio in NP ha un protocollo ZK pubblico a $k$ round (dove $k$ è una costante) con $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$, allora esistono OWF "infinitely-often" (ioOWF).

   • Nota: In questo caso, la sicurezza è garantita solo per un insieme infinito di lunghezze di input, non per tutte. Questo è un compromesso necessario dovuto alla natura ricorsiva della costruzione che richiede che tutti gli invertitori abbiano successo simultaneamente su una sovrapposizione di lunghezze.

4. Contributi Tecnici Principali

• Generalizzazione dei Parametri: Il risultato per i NIZK è il più generale possibile, mostrando che la somma semplice degli errori (anziché la radice quadrata o combinazioni più complesse) è sufficiente per garantire la durezza.
• Nuova Costruzione di Funzione: L'idea di includere il bit di verifica ($a$) nella funzione unidirezionale $f_x$ è un contributo metodologico significativo che riduce il costo dell'errore di zero-knowledge.
• Analisi Ricorsiva per Protocolli Interattivi: Lo sviluppo di una struttura ricorsiva per gestire protocolli a più round, permettendo di derivare condizioni di errore più strette ($\epsilon_c + \epsilon_s + k\epsilon_z < 1$) rispetto alla semplice estensione lineare.
• Amplificazione: Dimostrano che, sotto le ipotesi di durezza nel caso peggiore, i protocolli deboli possono essere trasformati in protocolli standard con errori trascurabili (per i NIZK).

5. Significato e Implicazioni

Questo lavoro è fondamentale per la teoria della crittografia perché:

1. Rafforza il legame tra ZK e OWF: Conferma che la proprietà di Zero-Knowledge è una fonte potente di durezza computazionale, anche quando i protocolli non sono perfetti (hanno errori costanti).
2. Chiude il gap parametrico: Risolve la questione aperta su quali combinazioni di errori deboli siano sufficienti per garantire l'esistenza di OWF, fornendo una condizione necessaria e sufficiente (la somma degli errori < 1) per i NIZK.
3. Guida per la progettazione: Suggerisce che per costruire sistemi crittografici basati su ZK, non è necessario raggiungere errori trascurabili fin dall'inizio; è sufficiente avere un protocollo "debole" che soddisfi la condizione di somma degli errori, poiché questo implica già l'esistenza di OWF, che possono poi essere usate per costruire protocolli più sicuri.
4. Limiti e Direzioni Future: Il paper identifica che per i protocolli interattivi a più round, ottenere OWF standard (non solo infinitely-often) con parametri deboli richiede nuove tecniche. Inoltre, lascia aperta la questione dei protocolli a moneta privata (private-coin) deboli.

In sintesi, il paper dimostra che la "debolezza" dei protocolli Zero-Knowledge (in termini di errori non trascurabili) non ne mina la potenza fondamentale come generatore di primitivi crittografici, purché la somma degli errori rimanga inferiore a 1.