💻 computer science

Non-Trivial Zero-Knowledge Implies One-Way Functions

Dit artikel bewijst dat, onder de aanname dat $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$ , het bestaan van niet-triviale zero-knowledge argumenten voor $\mathsf{NP}$ (waarbij de som van foutkansen afwijkt van 1) impliceert dat éénrichtingsfuncties bestaan, waarmee een eerder open probleem in de hoge-foutregime wordt opgelost.

Oorspronkelijke auteurs: Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer

Gepubliceerd 2026-02-20

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer

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 Kernboodschap: Een Magische Sleutel uit een Leugen

Stel je voor dat je een geheime sleutel (een One-Way Function) nodig hebt om een digitaal slot te openen. Deze sleutel is zo gemaakt dat het heel makkelijk is om er een slot mee te maken, maar onmogelijk om de sleutel terug te vinden als je alleen het slot ziet. Dit is de basis van moderne beveiliging.

Voorheen dachten wetenschappers dat je om zo'n sleutel te maken, al een heel goed, foutloos bewijs nodig had. Dit bewijs (een Zero-Knowledge Proof) is een manier om iemand te overtuigen dat je een geheim weet (bijvoorbeeld een wachtwoord), zonder het geheim zelf te onthullen.

Deze nieuwe studie zegt echter: "Nee, je hebt geen perfect bewijs nodig. Zelfs een bewijs met veel fouten is genoeg om die magische sleutel te maken, zolang het bewijs maar niet 'triviaal' (dwaas) is."

1. Het Probleem: De "Dwaas" Bewijzen

In de wereld van wiskundige bewijzen zijn er twee uitersten:

Het perfecte bewijs: Je bent 99,999% zeker dat de bewering klopt en dat niemand iets leert. Dit is moeilijk te maken.
Het "dwaas" bewijs: Stel, een bewijs dat 50% van de tijd zegt "Ja, het klopt" en 50% "Nee, het klopt niet", of dat de bewijzer gewoon het geheime wachtwoord hardop roept. Dit is makkelijk te maken, maar nutteloos voor beveiliging.

De vraag was: Wat zit er tussenin? Wat als je een bewijs hebt dat soms fouten maakt (bijvoorbeeld 40% fout), maar toch niet volledig dwaas is?

Als het bewijs te veel fouten maakt (bijvoorbeeld 100% fout of 100% waar), kun je er niets nuttigs mee.
Maar wat als de som van alle fouten (compleetheid, betrouwbaarheid en geheimhouding) minder dan 100% is? Is dat dan genoeg om cryptografische sleutels te maken?

2. De Oplossing: De "Herhalingstruc"

De auteurs (Chakraborty, Hulett, Khurana en Tomer) hebben ontdekt dat je die "moeilijke" sleutel wél kunt maken, zelfs als het bewijs veel fouten maakt, zolang het maar niet triviaal is.

De Analogie van de Gokker:
Stel je hebt een gokker die beweert dat hij een magische munt kan gooien die altijd "Kop" geeft.

Situatie A (Triviaal): De gokker gooit de munt, en hij zegt: "Ik heb 50% kans op Kop en 50% op Zilver." Dit is geen bewijs van magie, het is gewoon een normale munt. Je leert niets.
Situatie B (Niet-triviaal): De gokker zegt: "Ik heb 90% kans op Kop." Maar soms (10% van de tijd) zegt hij "Zilver" terwijl hij eigenlijk Kop had gegooid, of hij liegt over zijn strategie.

De oude methoden faalden hier omdat ze dachten: "Als hij 10% liegt, is het bewijs te zwak."
De nieuwe methode gebruikt herhaling.
Stel je vraagt de gokker niet één keer, maar duizend keer om te gokken.

Als hij echt magisch is (of een sleutel heeft), zal hij bijna altijd "Kop" gooien.
Als hij een leugenaar is die maar wat raadt, zal hij op den duur vastlopen in zijn eigen leugens.

Door de gokker (de bewijzer) duizenden keren te laten spelen met dezelfde regels, kunnen de wetenschappers de "ruis" (de fouten) filteren en de echte "magie" (de eenrichtingsfunctie) eruit halen. Het is alsof je door een wazige foto te nemen en die 1000 keer te herhalen, ineens een kristalheldere foto krijgt.

3. Waarom is dit belangrijk?

Vroeger dachten we: "Om beveiliging te bouwen, heb je eerst perfecte beveiliging nodig." Dit is een beetje als zeggen: "Je kunt pas een auto bouwen als je al een perfect motorblok hebt."

Deze studie zegt: "Nee, je kunt een motorblok bouwen uit een schets met veel krassen, zolang die schets maar niet compleet onzin is."

Dit betekent dat:

Minder eisen: We hoeven niet te wachten tot we perfecte, foutloze protocollen hebben om beveiliging te garanderen.
Sterkere theorie: Het bewijst dat zelfs imperfecte systemen die "iets" van een geheim bewaren, al krachtig genoeg zijn om de basis van cryptografie te vormen.
Amplificatie (Versterking): Als we zo'n imperfect bewijs hebben, kunnen we het "opblazen" tot een perfect bewijs. Het is alsof je een zwakke radio-ontvangst hebt; met de juiste versterker (deze nieuwe wiskunde) kun je er een kristalhelder signaal van maken, zonder dat je een nieuwe zender nodig hebt.

Samenvatting in één zin

Zelfs als een geheim bewijs veel fouten maakt, is het nog steeds waardevol genoeg om de basis te leggen voor onbreekbare digitale sloten, zolang het bewijs maar niet volledig belachelijk is.

De grote les: Perfectie is niet nodig om veiligheid te creëren; zelfs een imperfecte poging is vaak sterk genoeg om de sleutel tot de toekomst te vinden.

Titel: Non-Triviale Zero-Knowledge Impliceert Eén-Weg Functies

Auteurs: Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer
Datum: Februari 2026 (arXiv)

1. Het Probleem

De cryptografische gemeenschap heeft lang gezocht naar de minimale aannames die nodig zijn voor het bestaan van Zero-Knowledge (ZK) bewijssystemen. Een fundamenteel resultaat van Ostrovsky en Wigderson (1991/1993) stelde dat ZK-bewijzen voor NP alleen mogelijk zijn als er één-weg functies (OWF's) bestaan, mits NP gemiddeld moeilijk is. Recentere werken (zoals Hirahara en Nanashima, STOC '24) hebben dit versterkt door te laten zien dat zelfs de worst-case hardheid van NP (specifiek $NP \not\subseteq ioP/poly$ ) voldoende is om OWF's af te leiden uit ZK-bewijzen met verwaarloosbare fouten.

Echter, er bleef een belangrijke kennislacune bestaan: Wat gebeurt er als we ZK-protocollen toestaan met niet-verwaarloosbare (grote) fouten?

Een ZK-systeem wordt "triviaal" als de som van de fouten (completeness $\epsilon_c$ , soundness $\epsilon_s$ , en zero-knowledge $\epsilon_{zk}$ ) gelijk is aan of groter is dan 1. Dergelijke systemen kunnen zonder enige cryptografische aanname worden geconstrueerd.
Als de som van de fouten echter kleiner is dan 1 (een "non-trivial" systeem), is het onduidelijk of dit nog steeds impliceert dat OWF's bestaan.
Bestaande bewijstechnieken zijn afhankelijk van kleine fouten en falen in het regime waar $\epsilon_s + \epsilon_{zk} \approx 1$ . De vraag is: Impliceert het bestaan van een non-triviale ZK-argumentatie (waarbij $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1$ ) het bestaan van één-weg functies?

2. Methodologie en Technieken

De auteurs ontwikkelen nieuwe methoden om de kloof tussen non-triviale fouten en de constructie van OWF's te overbruggen. Ze gebruiken een bewijs door contradictie: ze nemen aan dat OWF's niet bestaan en tonen aan dat dit leidt tot een algoritme dat een taal in $NP$ kan beslissen, wat in strijd is met de aanname dat $NP \not\subseteq ioP/poly$ .

De kern van hun aanpak omvat de volgende stappen:

A. Repetitie en "Goede" vs. "Slechte" CRS (Voor NIZK)

In eerdere werken (zoals [OW93] en [CHK25]) werd gebruikgemaakt van Universal Extrapolation (UE) om de random string van een simulator te "omkeren". Deze technieken faalden bij grote fouten omdat de simulator soms een "slechte" Common Reference String (CRS) kon kiezen waarop het nog steeds een geldig bewijs kon genereren, maar met een lage waarschijnlijkheid.

Nieuwe Inzicht: De auteurs introduceren een repetitie-strategie. In plaats van één keer te proberen, herhaalt het beslissingsalgoritme het proces $p(|x|)$ keer met dezelfde CRS maar nieuwe random strings.
Definitie van "Goede" CRS: Een CRS is "goed" als de simulator met een hoge waarschijnlijkheid (minimaal $1/p(|x|)$ ) een accepterend bewijs kan genereren.
Logica: Als de generator (Gen) een "slechte" CRS kiest, zal de echte Prover (P) altijd accepteren (vanwege perfectie/completeness), maar de Simulator (Sim) zal bijna nooit accepteren. Dit creëert een groot onderscheid dat een onderscheider kan detecteren, tenzij de kans op het kiezen van een slechte CRS verwaarloosbaar is. Door te herhalen, kan het algoritme een accepterend bewijs vinden als de CRS goed is, zelfs als de individuele kans klein is.

B. Generalisatie naar Interactieve ZK (Public Coin)

Voor interactieve protocollen (meerdere rondes) is de uitdaging groter omdat de Verifier (V) niet direct kan voorspellen of een bericht acceptabel is zonder de toekomstige rondes te kennen.

Malicious Prover ( $\tilde{P}$ ): De auteurs definiëren een efficiënte, kwaadaardige Prover-strategie $\tilde{P}$ . Deze strategie gebruikt UE om veel mogelijke volgende berichten te "samplen" en kiest het bericht dat de kans op acceptatie maximaliseert.
Efficiëntie: Omdat het exact berekenen van de acceptatiekans moeilijk is, schat $\tilde{P}$ deze kans door het protocol intern te simuleren (Chernoff-bounds garanderen dat een polynomiaal aantal simulaties voldoende is voor een nauwkeurige schatting).
Public Coin: De analyse vereist dat de Verifier "public coin" is (alle berichten zijn willekeurige strings), zodat $\tilde{P}$ de Verifier kan simuleren zonder interne staat.
Resultaat: Als $NP \not\subseteq ioP/poly$ , dan moet $\tilde{P}$ een taal kunnen beslissen met een significant hogere kans dan een willekeurige aanval, wat impliceert dat OWF's moeten bestaan.

C. Private Coin Protocollen

Voor protocollen met private coins (waarbij de Verifier zijn random bits verbergt) tonen de auteurs aan dat, tenzij er auxiliary-input OWF's bestaan, elk constant-rondig private-coin protocol kan worden omgezet in een public-coin protocol. Hierdoor leiden non-triviale private-coin ZK's tot auxiliary-input OWF's.

3. Belangrijkste Bijdragen en Resultaten

Karakterisering van Non-Triviale ZK:
Het artikel bewijst dat het bestaan van een non-triviale, constant-rondige, public-coin ZK-argumentatie voor NP (waarbij $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1 - 1/poly$ ) het bestaan van één-weg functies (OWF's) impliceert, onder de aanname dat $NP \not\subseteq ioP/poly$ .
Resultaat voor NIZK:
Specifiek voor Non-Interactive Zero-Knowledge (NIZK) wordt bewezen dat non-triviale NIZK's voor NP OWF's impliceren. Dit verbetert eerdere resultaten (zoals [CHK25]) die alleen werkten voor specifieke combinaties van fouten (bijv. $\epsilon_{zk} + \sqrt{\epsilon_s} < 1$ ). De nieuwe methode werkt voor elke non-triviale combinatie.
Resultaat voor Private Coin:
Voor constant-rondige private-coin protocollen wordt bewezen dat ze auxiliary-input OWF's impliceren.
Onvoorwaardelijke Amplificatie:
Een cruciale toepassing is de amplificatie van fouten.
- Als $NP \not\subseteq ioP/poly$ , dan impliceert een non-triviale NIZK het bestaan van OWF's.
- Omdat OWF's voldoende zijn om "standaard" (verwaarloosbare fouten) NIZK's te construeren (via bekende resultaten zoals [BG24, AK25]), betekent dit dat non-triviale NIZK's onvoorwaardelijk kunnen worden geamplificeerd tot standaard NIZK's.
- Dit geldt ook voor interactieve ZK: non-triviale protocollen impliceren het bestaan van 4-rondige standaard ZK-protocollen.

4. Significatie en Impact

Sluiting van een Theoretische Kloof: Het werk sluit een fundamentele kennislacune over de complexiteit van Zero-Knowledge. Het bevestigt dat er geen "zwakke" vorm van ZK bestaat die makkelijker te construeren is dan OWF's, zolang de fouten maar niet triviaal zijn (d.w.z. de som van fouten < 1).
Versterking van Cryptografische Aannames: Het toont aan dat zelfs "zwakke" cryptografische primitieven (ZK met grote fouten) krachtige cryptografische fundamenten (OWF's) vereisen, mits NP hard is in de worst-case.
Praktische Implicaties voor Amplificatie: Voor onderzoekers die werken aan het construeren van ZK-protocollen met grote fouten (wat vaak makkelijker is), biedt dit resultaat een garantie: als je zo'n protocol kunt bouwen, heb je automatisch de middelen (via OWF's) om het te verbeteren tot een volledig veilig, verwaarloosbaar fout-protocol.
Technische Innovatie: De introductie van repetitie-strategieën en de specifieke behandeling van "goede" vs. "slechte" CRS's biedt nieuwe gereedschappen voor toekomstige analyses in de complexiteitstheorie en cryptografie.

Conclusie:
Dit artikel bewijst dat non-triviale Zero-Knowledge argumenten voor NP, ongeacht hoe groot de fouten zijn (zolang ze niet triviaal zijn), fundamenteel afhankelijk zijn van de hardheid van één-weg functies. Dit legt een directe link tussen de complexiteit van ZK-protocollen en de basis van moderne cryptografie, en biedt een pad om zwakke protocollen onvoorwaardelijk te versterken tot standaard protocollen.