I kryptografi är ett åtagandeschema eller ett bitförpliktelseschema ( eng. Commitment scheme ) en kryptografisk primitiv som gör att du kan fixa valfritt utvalt värde (valt uttalande, bit information), hålla det dolt för andra, med möjlighet att senare avslöja det fasta värdet [1] . Åtagandescheman är utformade på ett sådant sätt att en part inte kan ändra värdet eller påståendet efter inlämnandet, det vill säga åtagandescheman implementerar databindning . Åtagandescheman kan användas i ett antal kryptografiska protokoll , inklusive säker myntkastning , noll-kunskapsbevis, konfidentiellt beräkningsprotokoll och andra.
För att föreställa dig hur systemet fungerar, överväg att en avsändare lägger ett meddelande i en hänglåst låda och skickar lådan vidare till mottagaren. Meddelandet är dolt för mottagaren, som inte själv kan öppna låset. Från det ögonblick meddelandelådan är i mottagarens ägo kan innehållet i lådan inte ändras av avsändaren – lådan öppnas helt enkelt om avsändaren senare bestämmer sig för att ge nyckeln till mottagaren.
Interaktionen mellan två parter i skyldighetssystemet sker i två steg:
I enkla åtagandesystem består överföringsfasen av att skicka ett enda meddelande från avsändaren till mottagaren. Detta budskap kallas ett åtagande. Det är viktigt att det specifika värdet som valts inte kan vara känt för mottagaren i denna fas (detta kallas en dolda egenskap). Den enkla avslöjandefasen kommer att bestå av att skicka ett enda meddelande från avsändaren till mottagaren, följt av en åtagandekontroll utförd av mottagaren. Värdet som väljs under överföringsfasen måste vara det enda som avsändaren kan beräkna och som kontrolleras under expansionsfasen (detta kallas bindningsegenskapen).
Begreppet åtagandesystem formaliserades kanske först av Gilles Brassard , David Chaum och Claude Crepeau 1988 [2] som en del av olika NP-klassnoll-kunskapssäkra protokoll baserade på olika typer av åtagandesystem [3] . Konceptet har använts tidigare, men utan formell övervägande. Begreppet skyldigheter dök upp i verk av Manuel Bloom [4] och andra, eller som en del av, säg, Lamport -signaturen för det ursprungliga engångs-enbitssignaturschemat.
Anta att Alice och Bob vill lösa ett argument genom att kasta ett mynt . Om de fysiskt befinner sig på samma plats går proceduren så här:
Om Alice och Bob inte är på samma plats, finns det problem med att lösa den här tvisten. Efter att Alice har gjort en gissning och berättat det för Bob kan han ljuga om resultatet av myntkastningen på ett sådant sätt att resultatet blir en vinst för honom. På liknande sätt, om Alice inte tillkännager sin gissning för Bob, efter att Bob vänt myntet och tillkännager resultatet, kan Alice rapportera att hon förutspådde resultatet som var vinnande för henne. Alice och Bob kan använda ett åtagandeschema i denna procedur, vilket gör att de båda kan lita på resultatet:
För att Bob ska förvränga resultaten till hans fördel måste han bryta den underförstådda skyldigheten. Om åtagandeschemat är välbyggt kan Bob inte förvränga resultaten. Dessutom kan Alice inte påverka resultatet om hon inte kan ändra värdet hon förutsäger innan kast och begår [4] [5] .
Den verkliga tillämpningen av detta problem finns när människor (ofta i media) fattar ett beslut och ger ett svar i ett "förseglat kuvert" som öppnas vid ett senare tillfälle.
Ett välkänt specifikt exempel är användningen av åtagandesystemet i nollkunskapsbevis . Åtaganden används i dessa protokoll för två huvudsakliga syften: för det första att tillåta avsändaren att delta i system där verifieraren får välja vad som ska kontrolleras, och avsändaren kommer bara att visa vad som matchar verifierarens val. Åtagandesystem tillåter avsändaren att specificera all information i förväg och avslöja endast vad som behöver vetas senare i beviset [6] . Åtaganden används också i nollkunskapsbevis av verifieraren, som ofta anger sitt val i förväg i åtagandet. Detta gör att noll-kunskapsbevis kan byggas parallellt utan att avslöja redundant information från avsändaren till mottagaren [7] .
En annan viktig användning av åtagandeschemat är implementeringen av verifierbar hemlighetsdelning , som är en viktig byggsten i det konfidentiella dataprotokollet . I ett hemligt delningssystem är meddelandet uppdelat i delar - "andelar", och var och en av de flera parterna får "andelar" som måste döljas för alla utom ägaren till en viss del. Hemligheten kan endast återskapas av en koalition av deltagare från den ursprungliga gruppen, och koalitionen måste innehålla åtminstone något initialt känt antal deltagare. Att dela hemligheter är kärnan i många protokoll för säker datoranvändning: till exempel för säker utvärdering av en funktion med viss delad input, där hemliga delade resurser används. Men om angripare genererar delade resurser kan en sårbarhet uppstå och riktigheten av dessa resurser skulle behöva verifieras. I ett verifierbart hemlighetsdelningssystem åtföljs delning av en hemlighet av individuella aktieåtaganden. Åtaganden avslöjar ingenting som kan hjälpa angripare, men låter varje enskild part kontrollera om deras andelar är korrekta och sålla bort angripare [8] .
Åtagandeschemat kan antingen vara helt bindande (Alice kan inte ändra innehållet i lådan efter överföringen, även om hon har obegränsade datorresurser) eller helt gömma sig (Bob kan inte öppna lådan förrän Alice har överfört nyckeln, även om han har obegränsat datorresurser). ), men inte samtidigt [9] .
En intressant fråga uppstår inom kvantkryptografi : finns det på kvantnivå ovillkorligt säkra bitbundna åtagandescheman, det vill säga protokoll som (åtminstone asymptotiskt) binder och gömmer sig, även om det inte finns några gränser för beräkningsresurser? Förhoppningen är att det kommer att finnas ett sätt att utnyttja kvantmekanikens inneboende egenskaper , såsom i kvantnyckeldistributionsprotokollet . [tio]
1993 föreslogs ett protokoll för implementering av bitåtaganden inom kvantmekaniken, och den ovillkorliga säkerheten i detta protokoll har varit allmänt accepterad under ganska lång tid. Detta resultat visade sig dock vara felaktigt. Osäkerheten i detta protokoll, kallat BCJL-protokollet, bevisades hösten 1995. 1996 bevisade Dominic Myers teoretiskt att det är omöjligt att implementera ett ovillkorligt säkert schema. Vilket som helst sådant protokoll kan reduceras till ett protokoll när systemet är i ett av två klara tillstånd efter sändningsfasen, beroende på vilken bit Alice vill låsa. Om protokollet gömmer sig perfekt, kan Alice enhetligt omvandla dessa tillstånd till varandra genom att använda egenskaperna för Schmidt-nedbrytningen , vilket effektivt undertrycker den bindande egenskapen [11] .