💻 computer science

Weak Zero-Knowledge and One-Way Functions

De auteurs tonen aan dat het bestaan van zwakke Zero-Knowledge-protocollen voor alle talen in NP, zelfs met niet-verwaarloosbare fouten, het bestaan van eenrichtingsfuncties impliceert, waarbij de vereiste ongelijkheden voor de foutenpercentages aanzienlijk worden versoepeld ten opzichte van eerdere resultaten.

Oorspronkelijke auteurs: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

Gepubliceerd 2026-02-19

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Magie van de "Zwakke" Magiër: Hoe een imperfecte trui ons veiliger maakt

Stel je voor dat je een magiër hebt die een truc kan uitvoeren: hij bewijst dat hij een geheim kent (bijvoorbeeld de sleutel tot een kist), zonder dat jij ooit het geheim zelf ziet. In de wereld van cryptografie noemen we dit een Zero-Knowledge Protocol (ZK). Het is alsof de magiër zegt: "Ik heb de sleutel, geloof me," en hij bewijst het door de kist te openen, maar jij ziet de sleutel nooit.

Normaal gesproken eisen cryptografen dat deze magiër perfect is:

Hij mag nooit falen als hij de sleutel heeft (Completiteit).
Hij mag nooit liegen als hij de sleutel niet heeft (Klankbaarheid).
Hij mag nooit iets van de sleutel prijsgeven, zelfs niet een klein beetje (Geheimhouding).

Maar in het echte leven zijn magiërs niet perfect. Soms valt een kaart uit hun mouw, soms lukt de truc niet, en soms is de kans dat ze iets prijsgeven heel klein, maar niet nul. Dit noemen de auteurs Wakke Zero-Knowledge (Weak ZK).

De grote vraag in dit artikel is:
Als we alleen maar een zwakke magiër hebben (die soms fouten maakt), kunnen we dan toch nog iets belangrijks bouwen? Namelijk One-Way Functions (Eenrichtingsfuncties).

Wat is een One-Way Function? Denk aan een smoothie. Je kunt fruit, suiker en melk makkelijk in een blender gooien en een smoothie maken (dat is makkelijk). Maar als je de smoothie hebt, is het onmogelijk om hem terug te draaien tot losse appels, banaan en suiker (dat is moeilijk). Deze "onmogelijkheid" is de basis van beveiliging op internet (zoals wachtwoorden en crypto).

De auteurs laten zien dat zelfs als je magiër maar een beetje fouten maakt, je toch die onmogelijke smoothie kunt maken, zolang de fouten maar niet te groot zijn.

De Drie Regels van de Fouten

De auteurs hebben drie scenario's onderzocht, afhankelijk van hoe de magiër (de bewijsvoering) werkt. Ze hebben een formule bedacht om te bepalen of de magiër "sterk" genoeg is om beveiliging te garanderen.

1. De Eenmalige Magie (Niet-Interactief)

Stel, de magiër schrijft één briefje op en geeft het je. Je leest het en oordeelt.

De fouten:
- $\epsilon_c$ : De kans dat hij faalt als hij de sleutel heeft.
- $\epsilon_s$ : De kans dat hij slaagt als hij de sleutel niet heeft (hij liegt).
- $\epsilon_z$ : De kans dat hij iets van de sleutel prijsgeeft.
De ontdekking: Als de som van deze drie fouten minder is dan 1 ( $\epsilon_c + \epsilon_s + \epsilon_z < 1$ ), dan bestaat er een veilige One-Way Function.
Waarom is dit cool? Eerdere onderzoekers dachten dat de formule ingewikkelder moest zijn (zoals $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ ). Deze auteurs zeggen: "Nee, zolang de totale kans op een mislukking of leugen niet 100% is, zijn we veilig." Ze hebben de lat voor de magiër verlaagd, maar de beveiliging blijft staan.

2. De Magie met Worpjes (Publieke Muntjes)

Soms moet de magiër en de kijker met elkaar praten. De kijker gooit een muntje (een willekeurig getal) en de magiër moet daarop reageren. Dit kan meerdere ronden duren.

De ontdekking: Als de magiër $t$ berichten stuurt, dan moet de som van de fouten plus de fouten door de willekeurige muntjes kleiner zijn dan 1.
De formule: $\epsilon_c + \epsilon_s + (t-1) \cdot \epsilon_z < 1$ .
Analogie: Elke keer dat de kijker een nieuwe vraag stelt (een muntje gooit), krijgt de magiër een nieuwe kans om iets te lekken. Hoe meer vragen, hoe strenger de eis dat hij niets mag lekken. Maar zelfs dan, als de totale som onder de 1 blijft, kun je beveiliging bouwen.

3. De Magie met een vaste tijd (Constante Ronden)

Wat als het gesprek maar heel kort duurt? Bijvoorbeeld precies 3 ronden.

De ontdekking: Hier kunnen ze nog een stapje verder gaan. Zelfs als de magiër een beetje meer fouten maakt (zolang de som $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$ is, waarbij $k$ het aantal ronden is), kunnen ze beveiliging maken.
Het kleine nadeel: In dit geval is de beveiliging niet "altijd" perfect, maar "oneindig vaak" goed. Dat betekent dat er misschien soms een jaar is waarin de magiër faalt, maar op de lange termijn is hij onverslaanbaar. Voor de meeste praktische toepassingen is dit al meer dan genoeg.

Hoe werkt de "Truc" eigenlijk? (De Techniek in Simpel Woord)

De auteurs gebruiken een slimme denkfout om hun punt te bewijzen. Ze zeggen: "Stel, er bestaat géén One-Way Function. Dat betekent dat er een super-snelle computer is die elke smoothie weer kan terugdraaien tot fruit."

Als zo'n computer bestaat, kunnen we hem gebruiken om de magiër te ontmaskeren:

We laten de magiër een truc doen.
We gebruiken de "smoothie-terugdraaier" om te proberen het geheim te achterhalen uit de bewijzen.
Als de magiër een zwakke magiër is (met fouten), en de terugdraaier werkt perfect, dan kunnen we de magiër dwingen om een leugen te vertellen die hij niet kan bewijzen, of we kunnen zien of hij de sleutel echt heeft.
Dit leidt tot een tegenstrijdigheid: als de magiër een zwakke magiër is, zou hij de taal (de taal van de wiskunde) moeten kunnen oplossen, wat onmogelijk is als de taal "hard" (moeilijk) is.

De kern van hun verbetering is dat ze de "smoothie-terugdraaier" slim gebruiken. In plaats van de magiër twee keer te testen (wat dubbel zo veel fouten zou geven), testen ze hem op een manier waarbij de fouten elkaar niet optellen, maar elkaar opheffen. Hierdoor kunnen ze accepteren dat de magiër veel meer fouten maakt dan voorheen werd gedacht, en toch nog beveiliging garanderen.

Waarom is dit belangrijk?

Realiteit: In de echte wereld hebben we vaak geen perfecte magiërs. We hebben protocollen die snel zijn, maar misschien niet 100% foutloos. Dit artikel zegt: "Geen paniek! Zolang je binnen de limieten blijft, zijn we veilig."
Fundamentele Beveiliging: Het bewijst dat zelfs imperfecte interacties tussen computers genoeg zijn om de basis van moderne cryptografie (One-Way Functions) te bouwen.
Toekomst: Het opent de deur voor nieuwe, snellere en efficiëntere beveiligingsprotocollen die minder rekenkracht nodig hebben, omdat ze niet hoeven te proberen perfect te zijn, maar alleen "voldoende goed".

Kortom:
De auteurs hebben bewezen dat je niet een perfecte magiër nodig hebt om de wereld veilig te houden. Zolang de magiër maar niet te vaak liegt of te vaak de waarheid prijsgeeft, kun je er nog steeds een onbreekbare slot op zetten. En dat is een grote stap voorwaarts voor de cryptografie.

Technische Samenvatting: Weak Zero-Knowledge and One-Way Functions

1. Probleemstelling

Het artikel onderzoekt de implicaties van het bestaan van zwake Zero-Knowledge (ZK) protocollen voor talen die in het ergste geval (worst-case) moeilijk te berekenen zijn. Traditionele ZK-protocollen vereisen dat de foutenmarges voor volledigheid ( $\epsilon_c$ ), geluid (soundness, $\epsilon_s$ ) en zero-knowledge ( $\epsilon_z$ ) verwaarloosbaar klein (negligible) zijn.

In de praktijk bestaan echter veel nuttige en natuurlijke ZK-protocollen (zoals voor 3-Coloring of Graph Non-isomorphism) waarbij deze fouten constant of aanzienlijk kunnen zijn. De centrale vraag is: Wat impliceert het bestaan van dergelijke "zwakke" protocollen voor de cryptografische hardheid?

Specifiek richten de auteurs zich op de relatie tussen zwakke ZK-protocollen en het bestaan van Eenvoudige Functies (One-Way Functions - OWF). Eerdere resultaten (zoals van Ostrovsky-Wigderson en recentelijk Chakraborty et al.) toonden aan dat ZK met verwaarloosbare fouten OWF impliceert, maar de voorwaarden voor zwakke protocollen waren beperkt tot specifieke combinaties van fouten (bijv. $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ ).

2. Methodologie

De auteurs gebruiken een reductie-techniek waarbij ze aannemen dat er geen OWF bestaan (of dat er geen "auxiliary-input OWF" bestaan) en tonen aan dat dit leidt tot een contradictie met de hardheid van de taal. De kern van hun aanpak is de constructie van een distinguisher (een algoritme dat bepaalt of een invoer tot de taal behoort) die gebruikmaakt van een inverter voor een kandidaat-OWF.

Belangrijke Technieken:

Constructie van Kandidaat-OWF:
In plaats van alleen de output van de simulator te gebruiken, integreren de auteurs de verificatiestap ( $V$ ) direct in de definitie van de kandidaat-functie.
- Oude aanpak (Ostrovsky-Wigderson): $f_x(\rho) = \text{output van } Sim(x; \rho)$ .
- Nieuwe aanpak: $f_x(\rho) = (r, a)$ , waarbij $(r, \pi) \leftarrow Sim(x; \rho)$ en $a = V(x; r, \pi)$ .
  Door de verificatiebit $a$ mee te nemen, hoeft de distinguisher niet expliciet te verifiëren of de gegenereerde transcript correct is; als de inverter een geldige pre-image vindt, impliceert dit automatisch dat de verificatie slaagt. Dit bespaart een extra "kostenpost" van de zero-knowledge fout.
Recursieve Constructie voor Meerdere Rondes:
Voor interactieve protocollen met meerdere rondes (public-coin ZK) gebruiken de auteurs een recursieve aanpak. Ze definiëren een reeks functies $f_1, \dots, f_k$ die afhankelijk zijn van orakels die de volgende functies in de keten inverteren.
- Ze bouwen een "prover-strategie" ( $\tilde{P}$ ) die een inverter gebruikt om de meest waarschijnlijke acceptatiekans te schatten en de beste reactie te kiezen.
- Ze gebruiken concentratie-ongelijkheden (zoals de Hoeffding-bound) om de nauwkeurigheid van deze schattingen te garanderen.
Reductie naar One-Sided Average-Case Hardheid:
De auteurs koppelen de resultaten aan bestaande theorieën (Hirahara-Nanashima, Chakraborty et al.) die aantonen dat auxiliary-input OWF leiden tot "one-sided average-case hard languages". Als een taal hard is in dit gemiddelde geval, maar een zwak ZK-protocol heeft, kan men een OWF construeren.

3. Belangrijkste Bijdragen en Resultaten

Het artikel levert drie hoofdresultaten, afhankelijk van het type protocol en de parameters:

A. Non-Interactive Zero-Knowledge (NIZK)

Stelling: Als alle talen in NP een NIZK-bewijs (of argument) hebben met fouten $\epsilon_c, \epsilon_s, \epsilon_z$ zodanig dat:
$\epsilon_c + \epsilon_s + \epsilon_z < 1$
dan bestaan er One-Way Functions (onder de aanname dat $NP \not\subseteq ioP/poly$ ).

Verbetering: Dit is een strikte verbetering ten opzichte van eerdere werken (zoals Chakraborty et al. 2025) die de voorwaarde $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ vereisten. De nieuwe voorwaarde dekt alle niet-triviale gevallen waar de som van de fouten kleiner is dan 1.
Implicatie: Als NIZK-bewijzen met verwaarloosbare $\epsilon_c$ bestaan, kunnen deze worden versterkt tot protocollen met volledig verwaarloosbare fouten.

B. Meerdere Rondes Public-Coin ZK (Algemeen)

Stelling: Als alle talen in NP een $t$ -berichten public-coin ZK-protocol hebben met:
$\epsilon_c + \epsilon_s + (t-1) \cdot \epsilon_z < 1$
dan bestaan er One-Way Functions.

Hierbij is $t$ het totale aantal berichten in het protocol. De auteurs tonen aan dat de kosten van de zero-knowledge fout lineair toeneemt met het aantal berichten, maar met een factor $(t-1)$ in plaats van $t$ , wat een verbetering is ten opzichte van eerdere schattingen.

C. Constante Rondes Public-Coin ZK

Stelling: Als er een constante $k$ bestaat zodanig dat alle talen in NP een $k$ -rondes public-coin ZK-protocol hebben met:
$\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$
dan bestaan er Infinitely-Often One-Way Functions (ioOWF).

Nuance: Voor constante rondes kunnen de auteurs de voorwaarde nog verder verbeteren tot $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$ . Echter, vanwege de aard van de recursieve constructie (waarbij alle inverteerders tegelijkertijd moeten slagen), kunnen ze in dit geval alleen garanderen dat de OWF "one-way" is voor oneindig veel invoerlengtes, en niet noodzakelijk voor alle grote invoerlengtes.

4. Significatie en Impact

Volledigheid van Parameters: Het artikel sluit de gaten in de literatuur over de hardheid van zwakke ZK-protocollen. Het toont aan dat de voorwaarde $\sum \epsilon < 1$ (met de juiste gewichten) de grens is voor het impliceren van cryptografische hardheid.
Efficiëntie van Bewijzen: Door de verificatiestap in de OWF-constructie te integreren, vermijden de auteurs een extra "straf" voor de zero-knowledge fout. Dit maakt de reductie strakker en toont aan dat zwakke protocollen sterker zijn dan eerder gedacht.
Fundamentele Cryptografie: De resultaten versterken het inzicht dat Zero-Knowledge een fundamentele bouwsteen is voor cryptografie. Zelfs als protocollen niet perfect zijn (hoge foutmarges), impliceert hun bestaan in het ergste geval nog steeds de basis voor veilige cryptografie (OWF), mits de fouten binnen een bepaalde drempel blijven.
Open Vragen: Het artikel identificeert nog open problemen, zoals het uitbreiden van deze resultaten naar private-coin protocollen en het verbeteren van de resultaten voor constante rondes naar standaard OWF in plaats van alleen infinitely-often OWF.

Conclusie:
De auteurs bewijzen dat het bestaan van zwakke Zero-Knowledge protocollen voor NP-talen, zelfs met aanzienlijke foutmarges, voldoende is om het bestaan van One-Way Functions te garanderen, zolang de som van de fouten (gewogen naar het aantal rondes) strikt kleiner is dan 1. Dit generaliseert en verbetert eerdere resultaten aanzienlijk en verduidelijkt de relatie tussen interactieve bewijssystemen en cryptografische hardheid.