Kryptografický důkaz může skrýt tajemství tím, že ztíží prokázání nepřítomnosti simulátoru

Trik není v tom, dokázat, že tajemství je skryté

Začněme nejjednodušší podobou nulové znalosti.

Alice chce Boba přesvědčit, že Sudoku hádanka má řešení. Pokud pošle řešení, Bob je přesvědčen, ale hádanka je zničená. To, co chce, je ještě podivnější – důkaz, že řešení existuje, aniž by ho odhalila.

To je příslib důkazu s nulovou znalostí. Dokazovatelka (Alice) přesvědčí ověřovatele (Boba), že tvrzení je pravdivé, aniž odhalí cokoli nad rámec jeho pravdivosti.

Problém je, že tento příslib něco stojí. Běžný matematický důkaz má dvě pohodlné vlastnosti. Je jedinou zprávou: sepíšete jej, předáte a odejdete. A je dokonale spolehlivý: nepravdivé tvrzení nemá žádný platný důkaz. Klasické výsledky o nemožnosti říkají, že nulová znalost se musí vzdát obou vlastností — a nejen jejich kombinace; každá je nedostupná i samostatně.

Za prvé, důkaz s nulovou znalostí vyžaduje komunikaci. Pokud Alice pošle jedinou zprávu bez předem připraveného důvěryhodného nastavení, záruka nulové znalosti se zhroutí — bez ohledu na to, jak velkou spolehlivost jsme ochotni obětovat.

Za druhé, důkaz s nulovou znalostí potřebuje malou toleranci chyby. Požadavek dokonalé spolehlivosti nenápadně ničí i interakci: ověřovatel, kterého nelze oklamat bez ohledu na jeho náhodné volby, je může stejně dobře stanovit předem. Jakmile je předvídatelný, Alice dokáže na vše odpovědět jedinou zprávou — tedy právě v případě, který už selhal.

Práce Rahula Ilanga hledá cestu kolem této dvojité zdi. Nepředstírá, že zeď neexistuje, ani nevytváří klasickou nulovou znalost v nemožných podmínkách. Postup je jemnější: oslabit význam slov „nic neodhaluje“, ale způsobem, který zachová bezpečnostní vlastnosti, jež kryptografové skutečně dokážou testovat.

Výsledek se nazývá efektivní nulová znalost.

Starý test: simulátor existuje

Klasický způsob formalizace nulové znalosti využívá fiktivního pomocníka zvaného simulátor.

Myšlenka je tato: představte si Jane, která nezná Alicino tajemství. Pokud Jane dokáže sama vytvořit důkazy, které vypadají přesně jako důkazy, které by Bob dostal od Alice, pak Aliceiny důkazy Bobovi nic nového nepřinesly. Jane už dokázala napodobit jeho zkušenost bez Alicina tajemství.

Takže klasická nulová znalost vyžaduje skutečný simulátor. Musí existovat efektivní algoritmus, který dokáže vytvořit zdánlivě pravé důkazy, aniž by znal tajemství — svědka, jak se říká v žargonu; pro Sudoku je svědkem jednoduše vyplněná mřížka.

Tato definice je silná, ale právě zde se projeví starý výsledek o nemožnosti. Intuice je následující. Skutečně neinteraktivní důkaz je jen řetězec. Jakmile Bob tento řetězec má, může jej ukázat někomu jinému: získal schopnost dokázat tvrzení ostatním, což už zní jako víc než „nic“. Klasické věty tuto intuici zpřesňují do výše uvedených výsledků o nemožnosti.

Rozdíl na příkladu mega-Sudoku

Tady je záměrně zjednodušený způsob, jak ten rozdíl vnímat.

Pro vážnější část analogie nepoužívejme běžné sudoku 9 × 9. Je příliš malé a příliš konečné: počítač je může jednoduše vyřešit nebo dokázat, že řešení nemá. Místo toho si představme rodinu hádanek MegaSudoku(n). Zobecněme obvyklé pravidlo: zvolme velikost bloku n, položme N = n² a vytvořme mřížku N × N, rozdělenou na bloky n × n a používající N symbolů. Běžné sudoku je jen malý případ n = 3, N = 9: mřížka 9 × 9, bloky 3 × 3 a devět symbolů. Příběh složitosti důkazů začíná až tehdy, když n může růst a mřížka může obsahovat další gadgety, díky nimž se chová jako formule SAT převlečená za sudoku. Formule SAT je pouze seznam logických omezení: lze proměnným přiřadit hodnoty pravda či nepravda tak, aby byla splněna všechna omezení?

Svědka si lze stále snadno představit. Alice zná úplné platné vyplnění mega-Sudoku. Bob chce být přesvědčen, že takové vyplnění existuje, ale Alice je nechce prozradit. Když je pošle celé, Bob je přesvědčen, ale tajemství je pryč.

V klasické verzi s nulovou znalostí Alice a Bob interagují. Jeden starý mentální model používá zakryté destičky. Alice schová vyřešenou mřížku, před každým kolem tajně přejmenuje symboly a nechá Boba prohlédnout si jedno náhodně vybrané lokální omezení: řádek, sloupec, blok nebo gadget. Pokud odkryté buňky ukazují různé symboly, Bob získává jistotu. Pak se vše znovu zakryje a symboly se znovu přejmenují. (Je tu jedna zvláštnost: zadané hodnoty hádanky potřebují další trik, protože přejmenování symbolů skryje i je. Poznámka níže vysvětluje, jak klasické protokoly tento problém řeší; pro další výklad tento zjednodušený obraz stačí.)

To není protokol z této práce. Je to mentální model pro klasickou nulovou znalost:

• Alice a Bob si vyměňují zprávy.
• Bob vybírá náhodné kontroly.
• Alice odhaluje pouze lokální konzistenci, nikoli celé řešení.
• Důkaz soukromí funguje tak, že ukazuje, že Bobův pohled mohl být generován i bez Aliceina tajného řešení.

Klasická nulová znalost je tedy založena na pozitivním faktu:

Simulátor opravdu existuje.

Teď odstraňte ty pohodlné části. Alice pošle jeden řetězec tvořící důkaz a odejde. Neexistuje žádné důvěryhodné počáteční nastavení, žádný předem připravený sdílený náhodný řetězec a Bob nikdy nesmí přijmout nepravdivé tvrzení. To je prostředí, které klasická nulová znalost nemůže přežít.

Před vlastní myšlenkou potřebujeme ještě jednu postavu. Zvolme soubor pravidel: formální důkazový systém v logickém smyslu — pevnou sadu axiomů a mechanických pravidel pro kontrolu zapsaných matematických důkazů. Kanonickým příkladem je ZFC, standardní axiomatický systém matematiky. Vše další se vztahuje k předem zvolenému systému; volba je libovolná a konstrukce funguje pro každý pevně zvolený systém včetně ZFC.

(Terminologická poznámka převzatá z práce: „důkazový systém“ zde vždy znamená tento soubor pravidel — formální systém kontrolující matematické důkazy — nikdy zprávy, které posílá Alice. Mechanismy Alice a Boba se nazývají „dokazovatel a ověřovatel“.)

Gödelovská verze zachovává příběh mega-Sudoku, ale mění důkaz.

Vyberme druhý systém omezení stejné zobrazené velikosti a nazvěme jej D. Pro účely příběhu jsou S a D dvě hádanky MegaSudoku(n) ve stejném formátu. V zákulisí mohl D vzniknout jako obtížná logická formule jiné velikosti; je-li třeba, lze ji doplnit neškodnými fiktivními omezeními, aby se vešla do stejné mřížky. D je vytvořeno z logické formule, která je ve skutečnosti nesplnitelná: neexistuje přiřazení hodnot, jež by učinilo všechna její omezení pravdivými, stejně jako rozbitá hádanka nemá žádné legální úplné vyplnění. Jednoduchým příkladem by byla formule vyžadující zároveň „X je pravda“ a „X je nepravda“. D tedy nemá platné vyplnění.

Ale D nesmí být rozbitá hádanka, jejíž rozbitost lze snadno odhalit. Uvedený jednoduchý příklad nevyhovuje: každý důkazový systém vyvrátí „X a ne-X“ v jediné větě. D musí být nepravdivé způsobem, který zvolený důkazový systém nedokáže potvrdit krátkým argumentem. Kdyby důkazový systém dokázal D vyvrátit krátkým důkazem, následující příběh by se zhroutil: alternativní cesta k důkazům bez Alicina tajemství by mohla být formálně vyloučena, a s ní i záruka soukromí. D se proto vybírá z rodiny, kterou pevně zvolený důkazový systém nedokáže efektivně vyvrátit: v tomto systému neexistuje krátký důkaz, že D nemá řešení.

Alicin jednozprávový důkaz je pak o výroku buď–anebo:

buď má skutečný mega-Sudoku S řešení, nebo návnada D má řešení.

To je logické spojení. D není generováno nějakým magickým způsobem, který by činil S pravdivým. Důkaz netvrdí “D nemá řešení, tedy S má řešení.” Dokazuje disjunkci S nebo D. Dokonalá spolehlivost říká, že falešná disjunkce nemůže mít platný důkaz. Protože D je ve skutečnosti nepravdivé — nemá řešení — jediný způsob, jak může být disjunkce pravdivá, je, aby S byla pravdivá. Pokud je důkaz přijat, musí mít S řešení. Falešná formule nemůže falešné S učinit pravdivým.

Pro část připomínající nulovou znalost se však ptejme, co by se stalo, kdyby D mělo řešení. Toto řešení nepravdivé formule by sloužilo jako alternativní svědek. Umožnilo by někomu vytvářet důkazy bez znalosti skutečného Alicina řešení mega-Sudoku — tedy fungovat jako simulátor. Ve skutečnosti D řešení nemá, takže tato simulační cesta je uzavřena. Podstatné je, že důkazový systém nedokáže efektivně dokázat, že je uzavřena.

D tedy plní dvě úlohy. Pro spolehlivost je D nepravdivé, takže platný důkaz „S nebo D“ vynucuje pravdivost S. Pro efektivní nulovou znalost je D obtížné vyvrátit, takže důkazový systém nemůže rychle vyloučit alternativní cestu, která by simulaci umožnila.

Takže bezpečnostní test už není:

Můžeme dokázat, že simulátor skutečně existuje?

Stává se to:

Dokáže váš důkazový systém efektivně dokázat, že simulátor nemůže existovat?

Pokud je odpověď ne, vyplývá z toho něco překvapivě silného: každá bezpečnostní záruka, kterou (a) lze pozorovat spuštěním testu a (b) prokazatelně vyplývá — v tomto důkazovém systému — z existence simulátoru, skutečně platí. Úspěšný útok proti kterékoli z nich by sám o sobě znamenal chybějící krátké vyvrácení, a takové krátké vyvrácení neexistuje. To je ta “efektivní” část efektivní nulové znalosti.

Takže kontrast ve třídě je následující:

Klasická nulová znalost: důkazy jsou bezpečné, protože existuje simulátor.

Gödelovská efektivní nulová znalost: důkazy jsou považovány za bezpečné pro pozorovatelné bezpečnostní testy, protože důkazový systém nedokáže efektivně dokázat, že simulátor nemůže existovat.

Druhé tvrzení je slabší. Je to také důvod, proč si práce může zachovat tři rysy, které klasickou verzi zlomily: jednu zprávu, žádné počáteční nastavení a dokonalou spolehlivost.

Nový test: nelze dokázat, že simulátor chybí

Ilangovo oslabení mění otázku.

Klasická nulová znalost se ptá:

Existuje nějaký simulátor?

Efektivní nulová znalost se ptá na něco slabšího:

Dokáže váš zvolený důkazový systém efektivně dokázat, že žádný simulátor neexistuje?

Zní to jako technický úskok, ale je to základní myšlenka. Konstrukce žije v podivném stavu: simulátor ve skutečnosti neexistuje — práce to výslovně uvádí — ale důkazový systém, který jste zvolili, nemůže efektivně dokázat, že neexistuje. I kdyby každý špatný důsledek, na kterém vám záleží, vyžadoval takové vyvrácení, systém se vůči těmto důsledkům stále chová jako systém s nulovou znalostí.

Tady přichází na scénu Gödel. Ne jako ozdoba ani ve smyslu „Gödel zabezpečuje kryptografii“. Souvislost vede přes teorii důkazů. Důkazový systém se nazývá optimální, pokud je v přesném smyslu nejlepší možný: kdykoli libovolný systém dokáže příslušnou formuli vyvrátit krátkým důkazem, dokáže to i optimální důkazový systém, přičemž jeho důkaz je nanejvýš polynomiálně delší. Krajíček a Pudlák v roce 1989 vyslovili domněnku, že žádný optimální důkazový systém neexistuje: ať zvolíme jakýkoli systém, jiný systém dokáže určitou rodinu pravdivých tvrzení prokazovat mnohem stručněji. Jde o jednu z ústředních otevřených domněnek teorie složitosti důkazů a o konečný protějšek Gödelovy věty o neúplnosti z teorie složitosti: některá pravdivá tvrzení nemají ve zvoleném systému krátký důkaz — nikoli proto, že by byla z principu nedokazatelná, ale proto, že každý pevně zvolený důkazový systém ponechává některé stručně formulované pravdy bez krátkých důkazů.

Práce tuto domněnku předpokládá v mírně silnější podobě „nekonečně často“, která je při kryptografickém využití domněnek standardní. Věta Krajíčka a Pudláka pak dává konkrétní výsledek: pro každý důkazový systém existuje posloupnost skutečně nesplnitelných formulí, které tento systém nedokáže vyvrátit krátkými důkazy — a především je dokáže efektivní algoritmus generovat. Poslední vlastnost, uniformita, mění tvrzení o existenci ve skutečný algoritmus, který Alice může spustit: její formule D vznikají systematicky, nikoli z ničeho.

Kryptografický tah spočívá v tom, že tento nedostatek důkazové síly je využit.

Co konstrukce dělá

Zde je konstrukce práce zbavená podrobností.

Zvolte důkazový systém — například ZFC. Za předpokladu z teorie složitosti důkazů existuje efektivně generovatelná posloupnost formulí, které jsou ve skutečnosti nesplnitelné, ale zvolený systém nemá žádný krátký důkaz jejich nesplnitelnosti.

Nyní vytvořte jednozprávový důkaz této formy:

buď je reálné tvrzení splnitelné, nebo je tato speciální tvrdá formule splnitelná.

Speciální obtížná formule není splnitelná. Pokud je tedy základní důkazový mechanismus dokonale spolehlivý, přijetí zprávy stále znamená, že skutečné tvrzení je pravdivé. Tím se zachová dokonalá spolehlivost.

Ale pro bezpečnost typu nulové znalosti si představte, že by speciální tvrdý vzorec byl splnitelný. Pak by jeho svědek mohl být použit k simulaci důkazů bez znalosti skutečného svědka. Vzorec není ve skutečnosti splnitelný — ale důkazový systém to nedokáže efektivně dokázat. Takže nemůže efektivně dokázat, že simulátor nemůže existovat.

To je klíčový bod. Systém neskrývá tajemství vytvořením klasického simulátoru. Pro širokou třídu pozorovatelných bezpečnostních testů je chrání neschopnost důkazového systému potvrdit, že simulátor chybí.

Co práce tvrdí

Hlavní věta přichází ve vrstvách. Hlavní výsledek je tento:

Za standardního kryptografického předpokladu — existence neinteraktivních důkazů s nerozlišitelnými svědky, dobře prozkoumaných objektů odvozených z několika zavedených souborů předpokladů — a za domněnky z teorie složitosti důkazů, že neexistuje žádný (nekonečně často) optimální důkazový systém, práce pro každý zvolený důkazový systém konstruuje dvojici jednozprávového dokazovatele a ověřovatele pro NP/SAT, která nemá žádné počáteční nastavení, je dokonale spolehlivá a vůči tomuto systému má efektivní nulovou znalost. (NP/SAT je standardní „nejtěžší společný jmenovatel“ problémů podobných hádankám; mega-Sudoku je jedním z jeho převleků.)

Pro širší tvrzení o zachování falzifikovatelných bezpečnostních vlastností práce přidává další standardní předpoklad, derandomizační domněnku P = BPP (přibližně: náhodnost algoritmům nedává žádnou podstatnou dodatečnou moc).

Přeloženo z jazyka vět:

• Důkaz tvoří jediná zpráva.
• Neexistuje žádné důvěryhodné počáteční nastavení.
• Nepravdivá tvrzení nelze prokázat.
• Dokazovatel nemá klasickou nulovou znalost — neexistuje pro něj simulátor.
• Lze však dosáhnout každého falzifikovatelného bezpečnostního důsledku klasické nulové znalosti definovaného hrou.

„Falzifikovatelné“ je důležité. Znamená to, že bezpečnostní selhání lze otestovat spuštěním protivníka ve hře. Mnoho kryptografických bezpečnostních definic má tuto podobu: dokáže útočník rozlišit dva šifrové texty, obrátit funkci, získat svědka nebo vyhrát určitý experiment? Věta poskytuje dokazovatele pro každou falzifikovatelnou vlastnost, jednu po druhé. Jeden dokazovatel, který by měl všechny falzifikovatelné vlastnosti současně, je pravděpodobně nemožný — starý útok na znovupoužitelnost („Bob může ukázat důkaz ostatním“) je sám falzifikovatelnou vlastností a právě ta zde skutečně neplatí. Práce navrhuje, že jeden dokazovatel by mohl věrohodně pokrýt všechny přirozené falzifikovatelné vlastnosti — ty, které se skutečně vyskytují v kryptografické praxi — tato část je však podmíněným tvrzením založeným na neformálním pojmu „přirozenosti“ a na explicitní domněnce. Záruka míří na pozorovatelná selhání, nikoli na všechny filozofické či simulační významy skrývání.

Jeden konkrétní důsledek stojí za zmínku: konstrukce přináší první neinteraktivní důkazy skrývající svědka s uniformním dokazovatelem — „důkaz řešitelnosti hádanky vám nepomůže najít její řešení“, bez interakce a bez počátečního nastavení — skromně znějící objekt, který konstrukci odolával desítky let.

Co práce neříká

Tato část udržuje text poctivý.

Neříká, že staré věty o nemožnosti byly špatné. Konstrukce se jim vyhýbá změnou definice.

Nedává běžnou klasickou nulovou znalost bez interakce, bez počátečního nastavení a s dokonalou spolehlivostí. Práce výslovně uvádí, že zkonstruovaný dokazovatel nemá simulátor.

To neznamená, že důkaz nelze znovu použít. Důkaz tvořený jedinou zprávou lze stále ukázat někomu jinému; práce nezachovává vlastnosti, jako je popiratelnost. (Neinteraktivní nulová znalost s důvěryhodným počátečním nastavením má stejné omezení.)

Neznamená to, že jde o praktický protokol připravený k nasazení. Práce patří k teorii složitosti a základům kryptografie. Výsledek závisí na hlavních předpokladech teorie složitosti důkazů a kryptografie a konstrukce ukazuje, co je možné v principu.

To z „Gödla“ nedělá magický bezpečnostní primitiv. Souvislost s Gödlem vede přes důkazové systémy, optimální důkazové systémy a konečné obdoby neúplnosti. Užitečná intuice nezní „neúplnost chrání vaše heslo“. Zní takto: pokud důkazový systém nedokáže efektivně dokázat, že simulátor nemůže existovat, lze na úrovni bezpečnostních definic zablokovat útoky, které by takový důkaz vyžadovaly.

Proč je to vlastně zajímavé

Kryptografie často proměňuje obtížnost v bezpečnost. Rozklad na prvočinitele je obtížný, a proto jsou užitečné předpoklady ve stylu RSA. Mřížkové problémy jsou obtížné, a proto je užitečná mřížková kryptografie. Zde je obtížnost nezvyklejší: nikoli „je těžké vypočítat tajemství“, ale „je těžké dokázat, že určitý důkazový objekt nemůže existovat“.

Proto tato práce působí neobvykle. S axiomy a důkazovými systémy zachází téměř jako s kryptografickými zdroji. Obvyklá nemožnost říká, že existuje napětí mezi spolehlivostí a simulací. Ilango se snaží umístit napětí za důkazově-teoretickou oponu: simulátor chybí, ale formální systém tuto absenci nedokáže efektivně odhalit.

Překvapením nemá být, že by tento přístup měl nahradit dnešní systémy s nulovou znalostí. Pravděpodobně je nenahradí, alespoň ne přímo. Překvapivé je, že omezení matematické logiky lze využít konstruktivně: nejen jako zeď, ale také jako určitý druh krytí.

Jak silné jsou důkazy?

Jde o teoretickou práci, takže „důkazy“ zde znamenají něco jiného než v biologii nebo astronomii. Otázkou není, zda byl experiment zopakován, ale zda tvrzení podporují definice, předpoklady a řetězec formálních důkazů.

Důkazní řetězec je formální a práce své předpoklady výslovně uvádí. Nejde o nahodilé volby. Neinteraktivní důkazy s nerozlišitelnými svědky jsou standardními objekty kryptografie a vycházejí z několika zavedených souborů předpokladů. Domněnka o neexistenci optimálního důkazového systému je ústřední domněnkou teorie složitosti důkazů. P = BPP je standardní derandomizační domněnka použitá pouze pro širší větu o falzifikovatelných vlastnostech.

Práce také tvrdí, že předpoklady jsou odpovídající cenou, nikoli svévolnou konstrukcí: dokazuje obrácené tvrzení, že jsou v podstatě nezbytné — pokud takové konstrukce vůbec existují, musí existovat neinteraktivní důkazy s nerozlišitelnými svědky, a (při standardních jednocestných funkcích) nemůže existovat žádný optimální důkazový systém. A předpoklady jsou „win-win“: vyvrácení kterékoli z nich by samo o sobě bylo průlomovým objevem v teorii složitosti důkazů, kryptografii nebo teorii složitosti.

Protože je výsledek podmíněný, je podmíněná i míra jistoty. Pokud tyto předpoklady selžou, interpretace věty se změní. A i kdyby platily, zárukou není úplná klasická nulová znalost; jde o oslabenou verzi založenou na teorii důkazů.

Správné hodnocení tedy zní: vysoká jistota, že práce stanovuje koherentní podmíněný výsledek; střední jistota, že její předpoklady popisují kryptografický svět, ve kterém skutečně žijeme; a nízká jistota ohledně jakéhokoli bezprostředního praktického důsledku.

Proč je to důležité

Práce otevírá cestu, která měla být uzavřena.

Klasická teorie říká: plné nulové znalosti nelze dosáhnout jedinou zprávou bez počátečního nastavení a zároveň jí nelze dát dokonalou spolehlivost. Ilangova práce říká: požadujeme-li důsledky nulové znalosti, které lze testovat v bezpečnostních hrách, a necháme-li definici bezpečnosti záviset na tom, co důkazový systém může či nemůže efektivně vyvrátit, lze obnovit mnoho užitečných vlastností — s jedinou zprávou, bez počátečního nastavení a s dokonalou spolehlivostí.

Nejde o drobnou úpravu definice. Je to jiný způsob uvažování o kryptografických zárukách. Místo abychom se ptali pouze na to, co existuje, ptáme se, co může náš důkazový systém vyloučit. Místo abychom neprokazatelnost považovali za filozofickou nepříjemnost, využijeme ji jako součást konstrukce.

Praktický svět se možná zítra nezmění, ale konceptuální mapa ano. Nyní máme formální smysl, v němž tvrzení „nikdo nedokáže efektivně prokázat, že tajemství uniklo“ může být dostatečně silné k obnovení mnoha herních ochran, které jsme očekávali od tvrzení „tajemství neuniklo“.

Proto Gödel patří do názvu.

Čisté shrnutí

Důkazy s nulovou znalostí umožňují dokazovateli přesvědčit ověřovatele, že tvrzení je pravdivé, aniž odhalí svědka. Klasické výsledky o nemožnosti říkají, že nulovou znalost nelze vměstnat do jediné zprávy bez počátečního nastavení a nelze jí dát dokonalou spolehlivost. Práce Rahula Ilanga tyto výsledky nevyvrací. Definuje slabší pojem, efektivní nulovou znalost: místo požadavku, aby simulátor skutečně existoval, vyžaduje, aby zvolený formální soubor pravidel — například ZFC — nedokázal efektivně dokázat, že žádný simulátor neexistuje. Za zásadních předpokladů kryptografie (neinteraktivní důkazy s nerozlišitelnými svědky) a teorie složitosti důkazů (neexistence optimálního důkazového systému) práce konstruuje jednozprávové dokazovatele pro NP/SAT bez počátečního nastavení a s dokonalou spolehlivostí, kteří postupně dosahují jednotlivých falzifikovatelných herních důsledků nulové znalosti. Jediný dokazovatel pokrývající všechny takové „přirozené“ vlastnosti je dalším, částečně spekulativním rozšířením — a pokrytí doslova všech falzifikovatelných vlastností je pravděpodobně nemožné, protože důkazy zůstávají znovupoužitelné. Výsledek je teoretický a podmíněný, nikoli hotový primitiv, ale ukazuje nový způsob využití důkazově-teoretické neprokazatelnosti jako kryptografického zdroje.

Kontrola bez nesmyslů

Co práce ukazuje: Za uvedených předpokladů lze vytvořit jednozprávové dokazovatele a ověřovatele pro NP/SAT bez počátečního nastavení, kteří jsou dokonale spolehliví, mají efektivní nulovou znalost vzhledem k libovolnému zvolenému důkazovému systému a dosahují každého falzifikovatelného herního důsledku klasické nulové znalosti.

Co je pravděpodobné, ale není bezpodmínečně dokázáno: Že platí potřebné předpoklady složitosti důkazu a kryptografie. Jsou to vážné, dobře prozkoumané předpoklady — a práce ukazuje, že jsou v podstatě nezbytné i dostačující — ale stále jen předpoklady.

Co neukazuje: Klasická nulová znalost bez interakce, bez počátečního nastavení a s dokonalou spolehlivostí; praktický systém připravený k nasazení; popíratelnost nebo nemožnost opětovného použití důkazů; nebo že Gödelova věta o neúplnosti sama o sobě zajišťuje kryptografii.

Hlavní omezení: Záruka je oslabením nulové znalosti; nejširší verze závisí na několika předpokladech; tvrzení o jediném univerzálním dokazovateli zůstávají částečně spekulativní; a výsledek je především fundamentální.

Jakou důvěru by měl mít běžný čtenář? Vysokou v to, že jde při přijetí definic o důležitý podmíněný teoretický výsledek. Střední v to, že předpoklady zachycují realitu. Nízkou ohledně okamžitého praktického nasazení. Bezpečné poučení zní: práce neporušuje výsledky o nemožnosti nulové znalosti; nachází nový důkazově-teoretický způsob, jak obejít ty jejich části, které jsou důležité pro mnoho bezpečnostních her.