V kryptografii je schéma závazku nebo schéma bitového závazku ( angl. Commitment scheme ) kryptografické primitivum , které vám umožňuje opravit libovolnou vybranou hodnotu (vybraný příkaz, bit informace), udržet ji skrytou pro ostatní s možností později odhalit pevná hodnota [1] . Schémata závazků jsou navržena tak, že strana nemůže po odeslání změnit hodnotu nebo tvrzení, tj. schémata závazků implementují datovou vazbu . Schémata závazků nacházejí uplatnění v řadě kryptografických protokolů , včetně bezpečného hodu mincí , důkazu nulových znalostí, důvěrného výpočetního protokolu a dalších.
Chcete-li si představit, jak schéma funguje, zvažte, zda odesílatel umístí zprávu do schránky se zámkem a schránku předá příjemci. Zpráva je skryta před příjemcem, který nemůže sám otevřít zámek. Od okamžiku, kdy je schránka v držení příjemce, nemůže odesílatel změnit obsah schránky – schránka se jednoduše otevře, pokud se odesílatel později rozhodne předat klíč příjemci.
Interakce dvou stran v závazkovém schématu probíhá ve dvou fázích:
V jednoduchých schématech závazků se fáze přenosu skládá z odeslání jediné zprávy od odesílatele k příjemci. Tato zpráva se nazývá závazek. Je důležité, aby konkrétní zvolená hodnota nemohla být příjemci v této fázi známa (toto se nazývá vlastnost skrytí). Fáze prostého zveřejnění bude sestávat z odeslání jediné zprávy od odesílatele příjemci, po níž bude následovat kontrola závazku, kterou provede příjemce. Hodnota zvolená během fáze přenosu musí být jediná, kterou může odesílatel vypočítat a která je kontrolována během fáze expanze (toto se nazývá vlastnost vazby).
Koncept schémat závazku byl pravděpodobně poprvé formalizován Gillesem Brassardem , Davidem Chaumem a Claudem Crepeauem v roce 1988 [2] jako součást různých protokolů důkazu nulových znalostí třídy NP založených na různých typech schémat závazků [3] . Tento koncept byl použit již dříve, ale bez formálního posouzení. Koncept závazků se objevil v dílech Manuela Blooma [4] a dalších, nebo jako součást, řekněme, Lamportova podpisu původního jednorázového jednobitového podpisového schématu.
Předpokládejme , že Alice a Bob chtějí vyřešit hádku tím, že si hodí mincí . Pokud jsou fyzicky na stejném místě, postup vypadá takto:
Pokud Alice a Bob nejsou na stejném místě, nastává problém při řešení tohoto sporu. Poté, co Alice uhodne a řekne to Bobovi, může lhát o výsledku hodu mincí takovým způsobem, že výsledek je pro něj výhrou. Podobně, pokud Alice neoznámí svůj odhad Bobovi, poté, co Bob hodí mincí a oznámí výsledek, může Alice oznámit, že předpověděla výsledek, který pro ni vyhrál. Alice a Bob mohou v tomto postupu použít schéma závazků, které jim oběma umožňuje důvěřovat výsledku:
Aby Bob zkreslil výsledky ve svůj prospěch, musí prolomit implicitní povinnost. Pokud je schéma závazků dobře sestaveno, pak Bob nemůže zkreslit výsledky. Také Alice nemůže ovlivnit výsledek, pokud nemůže změnit hodnotu, kterou předpovídá před hodem a odevzdáním [4] [5] .
Skutečné uplatnění tohoto problému existuje, když se lidé (často v médiích) rozhodnou a poskytnou odpověď v „zapečetěné obálce“, která se otevře později.
Jedním ze známých konkrétních příkladů je použití schématu závazků v důkazech s nulovými znalostmi . Závazky se v těchto protokolech používají ke dvěma hlavním účelům: zaprvé k tomu, aby umožnily odesílateli účastnit se schémat, kde ověřovatel dostane na výběr, co bude kontrolovat, a odesílatel ukáže pouze to, co odpovídá výběru ověřovatele. Závazková schémata umožňují odesílateli specifikovat všechny informace předem a zveřejnit pouze to, co je potřeba znát později v důkazu [6] . Závazky jsou také používány v důkazech o nulových znalostech ověřovatelem, který často svůj výběr předem specifikuje v závazku. To umožňuje paralelně budovat důkazy s nulovými znalostmi, aniž by došlo k odhalení nadbytečných informací od odesílatele k příjemci [7] .
Dalším důležitým využitím schématu závazků je implementace ověřitelného sdílení tajemství , které je kritickým stavebním kamenem důvěrného výpočetního protokolu . Ve schématu tajného sdílení je zpráva rozdělena na části – „sdílení“ a každá z několika stran obdrží „sdílení“, které musí být skryto všem kromě vlastníka konkrétní části. Tajemství může znovu vytvořit pouze koalice účastníků z původní skupiny a koalice musí zahrnovat alespoň nějaký původně známý počet účastníků. Sdílení tajemství je jádrem mnoha protokolů pro bezpečné výpočty: například pro bezpečné vyhodnocení funkce s určitým sdíleným vstupem, kde se používají tajné sdílené zdroje. Pokud by však útočníci generovali sdílené zdroje, mohlo by dojít k zranitelnosti a správnost těchto zdrojů by bylo nutné ověřit. V ověřitelném schématu sdílení tajemství je sdílení tajemství doprovázeno individuálními závazky sdílení. Závazky neodhalují nic, co by mohlo útočníkům pomoci, ale umožňují každé jednotlivé straně zkontrolovat, zda jsou jejich podíly správné, a vyřadit útočníky [8] .
Závazkové schéma může být buď plně závazné (Alice nemůže po převodu změnit obsah krabice, i když má neomezené výpočetní zdroje), nebo dokonale skryté (Bob nemůže krabici otevřít, dokud Alice nepřenese klíč, i když má neomezené výpočetní zdroje). ), ale ne současně [9] .
V kvantové kryptografii vyvstává zajímavá otázka : existují na kvantové úrovni bezpodmínečně bezpečná schémata závazků s bitovou vazbou, tedy protokoly, které jsou (alespoň asymptoticky) závazné a skryté, i když neexistují žádná omezení na výpočetní zdroje? Doufá se, že bude existovat způsob, jak využít vnitřní vlastnosti kvantové mechaniky , jako například v protokolu distribuce kvantového klíče . [deset]
V roce 1993 byl navržen protokol pro implementaci bitových závazků v rámci kvantové mechaniky a bezpodmínečná bezpečnost tohoto protokolu byla již nějakou dobu obecně akceptována. Tento výsledek se však ukázal jako nesprávný. Nebezpečnost tohoto protokolu, nazývaného protokol BCJL, byla prokázána na podzim roku 1995. V roce 1996 Dominic Myers teoreticky dokázal, že je nemožné zavést bezpodmínečně bezpečné schéma. Jakýkoli takový protokol lze zredukovat na protokol, když je systém po fázi vysílání v jednom ze dvou čistých stavů , v závislosti na bitu, který chce Alice zachytit. Pokud je protokol dokonale skryt, pak Alice dokáže tyto stavy jednotně transformovat do sebe pomocí vlastností Schmidtova rozkladu , čímž účinně potlačuje vazebnou vlastnost [11] .