I kryptografi er en forpligtelsesordning eller en bit-forpligtelsesordning ( eng. Commitment scheme ) en kryptografisk primitiv , der giver dig mulighed for at rette en hvilken som helst valgt værdi (valgt udsagn, en smule information), holde den skjult for andre, med mulighed for senere at afsløre den faste værdi [1] . Forpligtelsesskemaer er designet på en sådan måde, at en part ikke kan ændre værdien eller påstanden efter indsendelse, dvs. forpligtelsesskemaer implementerer databinding . Forpligtelsesordninger finder anvendelse i en række kryptografiske protokoller , herunder sikker møntkast , nul-vidensbevis, fortrolig beregningsprotokol og andre.
For at forestille dig, hvordan ordningen fungerer, kan du overveje, at en afsender placerer en besked i en boks med hængelås og sender boksen videre til modtageren. Beskeden er skjult for modtageren, som ikke selv kan åbne låsen. Fra det øjeblik beskedboksen er i modtagerens besiddelse, kan indholdet af kassen ikke ændres af afsenderen – boksen åbnes blot, hvis afsenderen senere beslutter sig for at give nøglen til modtageren.
Samspillet mellem to parter i forpligtelsesordningen sker i to faser:
I simple tilsagnsordninger består transmissionsfasen af at sende en enkelt besked fra afsender til modtager. Dette budskab kaldes en forpligtelse. Det er vigtigt, at den valgte værdi ikke kan kendes af modtageren i denne fase (dette kaldes en skjult egenskab). Den simple afsløringsfase vil bestå i at sende en enkelt besked fra afsenderen til modtageren, efterfulgt af et engagementstjek udført af modtageren. Den værdi, der vælges under transmissionsfasen, skal være den eneste, som afsenderen kan beregne, og som kontrolleres under udvidelsesfasen (dette kaldes bindingsegenskaben).
Begrebet forpligtelsesordninger blev måske først formaliseret af Gilles Brassard , David Chaum og Claude Crepeau i 1988 [2] som en del af forskellige NP-klasse nul-viden bevis protokoller baseret på forskellige typer forpligtelsesordninger [3] . Konceptet har været brugt før, men uden formel overvejelse. Begrebet forpligtelser dukkede op i Manuel Blooms [4] og andres værker, eller som en del af f.eks. Lamport -signaturen af det originale engangs-en-bit signaturskema.
Antag, at Alice og Bob ønsker at løse et skænderi ved at kaste en mønt . Hvis de fysisk er på samme sted, går proceduren således:
Hvis Alice og Bob ikke er på samme sted, er der et problem med at løse denne tvist. Efter at Alice har lavet et gæt og fortalt det til Bob, kan han lyve om resultatet af møntkastet på en sådan måde, at resultatet er en sejr for ham. På samme måde, hvis Alice ikke annoncerer sit gæt til Bob, efter at Bob har vendt mønten og annonceret resultatet, kan Alice rapportere, at hun forudsagde det resultat, der var sejr for hende. Alice og Bob kan bruge en forpligtelsesordning i denne procedure, som giver dem begge mulighed for at stole på resultatet:
For at Bob kan fordreje resultaterne til hans fordel, må han bryde den underforståede forpligtelse. Hvis tilsagnsordningen er godt konstrueret, så kan Bob ikke skævvride resultaterne. Alice kan heller ikke påvirke resultatet, hvis hun ikke kan ændre den værdi, hun forudsiger før kastet og begår [4] [5] .
Den virkelige anvendelse af dette problem eksisterer, når folk (ofte i medierne) træffer en beslutning og giver et svar i en "lukket kuvert", der åbnes på et senere tidspunkt.
Et velkendt specifikt eksempel er brugen af tilsagnsordningen i nulvidensbeviser . Forpligtelser bruges i disse protokoller til to hovedformål: For det første at give afsenderen mulighed for at deltage i ordninger, hvor verifikatoren får mulighed for at vælge, hvad der skal kontrolleres, og afsenderen vil kun vise, hvad der matcher verifikatorens valg. Forpligtelsesordninger giver afsenderen mulighed for at specificere alle oplysninger på forhånd og kun oplyse, hvad der skal vides senere i beviset [6] . Tilsagn bruges også i beviser med nulviden af verifikatoren, som ofte angiver sit valg på forhånd i forpligtelsen. Dette gør det muligt at bygge nul-viden beviser parallelt uden at afsløre overflødig information fra afsender til modtager [7] .
En anden vigtig anvendelse af forpligtelsesordningen er implementeringen af verificerbar hemmelig deling , som er en kritisk byggesten i den fortrolige computerprotokol . I en hemmelig-delingsordning er beskeden opdelt i dele - "aktier", og hver af de flere parter modtager "andele", der skal skjules for alle undtagen ejeren af en bestemt del. Hemmeligheden kan kun genskabes af en koalition af deltagere fra den oprindelige gruppe, og koalitionen skal mindst omfatte et eller andet oprindeligt kendt antal deltagere. Deling af hemmeligheder er kernen i mange protokoller til sikker databehandling: for eksempel til sikker evaluering af en funktion med noget delt input, hvor hemmelige delte ressourcer bruges. Men hvis angribere genererer delte ressourcer, kan der opstå en sårbarhed, og rigtigheden af disse ressourcer skal verificeres. I en verificerbar hemmelighedsdelingsordning er deling af en hemmelighed ledsaget af individuelle aktieforpligtelser. Forpligtelser afslører intet, der kunne hjælpe angribere, men giver hver enkelt part mulighed for at kontrollere, om deres delinger er korrekte og luge angribere ud [8] .
Forpligtelsesordningen kan enten være fuldt forpligtende (Alice kan ikke ændre indholdet af kassen efter overførslen, selvom hun har ubegrænsede computerressourcer) eller perfekt skjule (Bob kan ikke åbne kassen, før Alice har overført nøglen, selvom han har ubegrænset computerressourcer). ), men ikke samtidigt [9] .
Et interessant spørgsmål opstår i kvantekryptografi : eksisterer der på kvanteniveau ubetinget sikre bit-bundne forpligtelsesordninger, det vil sige protokoller, der (i det mindste asymptotisk) er bindende og skjuler, selvom der ikke er nogen grænser for beregningsressourcer? Det er håbet, at der vil være en måde at udnytte kvantemekanikkens iboende egenskaber på , såsom i kvantenøglefordelingsprotokollen . [ti]
I 1993 blev der foreslået en protokol til implementering af bit-forpligtelser inden for kvantemekanik, og denne protokols ubetingede sikkerhed har været generelt accepteret i et stykke tid. Dette resultat viste sig dog at være forkert. Usikkerheden ved denne protokol, kaldet BCJL-protokollen, blev bevist i efteråret 1995. I 1996 beviste Dominic Myers teoretisk, at det er umuligt at implementere en ubetinget sikker ordning. Enhver sådan protokol kan reduceres til en protokol, når systemet er i en af to klare tilstande efter transmissionsfasen, afhængigt af den bit Alice ønsker at låse. Hvis protokollen skjuler sig perfekt, kan Alice ensartet transformere disse tilstande til hinanden ved hjælp af egenskaberne fra Schmidt-nedbrydningen , hvilket effektivt undertrykker bindingsegenskaben [11] .