În criptografie , o schemă de angajare sau o schemă de angajament de biți ( ing. Schema de angajare ) este o primitivă criptografică care vă permite să fixați orice valoare selectată (instrucțiune selectată, bit de informație), păstrând-o ascunsă pentru alții, cu posibilitatea de a dezvălui ulterior. valoarea fixă [1 ] . Schemele de angajament sunt concepute astfel încât o parte să nu modifice valoarea sau afirmația după depunere, adică schemele de angajament implementează legarea datelor . Schemele de angajament găsesc aplicație într-un număr de protocoale criptografice , inclusiv aruncarea securizată a monedelor , dovada zero-cunoștințe, protocolul de calcul confidențial și altele.
Pentru a vă imagina cum funcționează schema, luați în considerare un expeditor care plasează un mesaj într-o cutie cu lacăt și transmite cutia destinatarului. Mesajul este ascuns destinatarului, care nu poate deschide singur lacătul. Din momentul în care căsuța de mesaj este în posesia destinatarului, conținutul cutiei nu poate fi schimbat de către expeditor — caseta este pur și simplu deschisă dacă expeditorul decide ulterior să dea cheia destinatarului.
Interacțiunea a două părți în schema de obligații are loc în două etape:
În schemele simple de angajare, faza de transmisie constă în trimiterea unui singur mesaj de la emițător la receptor. Acest mesaj se numește angajament. Este important ca valoarea specială aleasă să nu poată fi cunoscută destinatarului în această fază (aceasta se numește o proprietate de ascundere). Faza de dezvăluire simplă va consta în trimiterea unui singur mesaj de la expeditor către destinatar, urmată de o verificare a angajamentului efectuată de destinatar. Valoarea aleasă în faza de transmisie trebuie să fie singura pe care expeditorul o poate calcula și care este verificată în faza de extindere (aceasta se numește proprietatea de legare).
Conceptul de scheme de angajament a fost probabil pentru prima dată oficializat de Gilles Brassard , David Chaum și Claude Crepeau în 1988 [2] ca parte a diferitelor protocoale de verificare a cunoștințelor zero de clasă NP bazate pe diferite tipuri de scheme de angajament [3] . Conceptul a fost folosit înainte, dar fără o considerație formală. Conceptul de obligații a apărut în lucrările lui Manuel Bloom [4] și alții, sau ca parte, de exemplu, a semnăturii Lamport a schemei originale de semnătură de un singur bit.
Să presupunem că Alice și Bob vor să rezolve o ceartă aruncând o monedă . Dacă sunt fizic în același loc, procedura decurge astfel:
Dacă Alice și Bob nu sunt în același loc, există o problemă în rezolvarea acestei dispute. După ce Alice a ghicit și i-a spus-o lui Bob, acesta poate minți în legătură cu rezultatul aruncării monedei în așa fel încât rezultatul să fie un câștig pentru el. În mod similar, dacă Alice nu își anunță ghicitul lui Bob, după ce Bob întoarce moneda și anunță rezultatul, Alice poate raporta că a prezis rezultatul care a fost câștigător pentru ea. Alice și Bob pot folosi o schemă de angajament în această procedură, care le permite ambilor să aibă încredere în rezultat:
Pentru ca Bob să modifice rezultatele în favoarea lui, trebuie să încalce obligația implicită. Dacă schema de angajament este bine construită, atunci Bob nu poate denatura rezultatele. De asemenea, Alice nu poate influența rezultatul dacă nu poate schimba valoarea pe care o prezice înainte de aruncare și comite [4] [5] .
Aplicarea reală a acestei probleme există atunci când oamenii (de multe ori în mass-media) iau o decizie și oferă un răspuns într-un „plic sigilat” care este deschis la o dată ulterioară.
Un exemplu specific bine-cunoscut este utilizarea schemei de angajament în dovezile de zero cunoștințe . Angajamentele sunt utilizate în aceste protocoale în două scopuri principale: în primul rând, pentru a permite expeditorului să participe la scheme în care verificatorului i se va oferi posibilitatea de a alege ce să verifice, iar expeditorul va arăta doar ceea ce se potrivește cu alegerea verificatorului. Schemele de angajament permit expeditorului să specifice toate informațiile în prealabil și să dezvăluie doar ceea ce trebuie cunoscut mai târziu în dovadă [6] . Angajamentele sunt, de asemenea, folosite în dovezile de zero cunoștințe de către verificator, care de multe ori își specifică alegerea din timp în angajament. Acest lucru permite construirea de dovezi cu cunoștințe zero în paralel fără a dezvălui informații redundante de la expeditor la destinatar [7] .
O altă utilizare importantă a schemei de angajament este în implementarea partajării secrete verificabile , care este un element critic al protocolului de calcul confidențial . Într-o schemă de partajare secretă, mesajul este împărțit în părți - „acțiuni”, iar fiecare dintre mai multe părți primește „acțiuni” care trebuie ascunse tuturor, cu excepția proprietarului unei anumite părți. Secretul poate fi recreat doar de o coaliție de participanți din grupul original, iar coaliția trebuie să includă cel puțin un număr de participanți cunoscut inițial. Partajarea secretelor se află în centrul multor protocoale pentru calcularea securizată: de exemplu, pentru evaluarea securizată a unei funcții cu o anumită intrare partajată, în care sunt utilizate resursele partajate secrete. Cu toate acestea, dacă atacatorii generează resurse partajate, ar putea apărea o vulnerabilitate și corectitudinea acestor resurse ar trebui verificată. Într-o schemă verificabilă de partajare a secretelor, partajarea unui secret este însoțită de angajamente individuale de acționare. Angajamentele nu dezvăluie nimic care ar putea ajuta atacatorii, dar permit fiecărei părți individuale să verifice dacă acțiunile lor sunt corecte și să elimine atacatorii [8] .
Schema de angajament poate fi fie complet obligatorie (Alice nu poate schimba conținutul cutiei după transfer, chiar dacă are resurse de calcul nelimitate) sau perfect ascunsă (Bob nu poate deschide cutia până când Alice nu a transferat cheia, chiar dacă are un număr nelimitat). resurse de calcul). ), dar nu simultan [9] .
O întrebare interesantă apare în criptografia cuantică : există la nivel cuantic scheme de angajament de biți necondiționat sigure , adică protocoale care (cel puțin asimptotic) se leagă și se ascund, chiar dacă nu există limite ale resurselor de calcul? Se speră că va exista o modalitate de a exploata proprietățile intrinseci ale mecanicii cuantice , cum ar fi protocolul de distribuție a cheilor cuantice . [zece]
În 1993, a fost propus un protocol pentru implementarea angajamentelor de biți în mecanica cuantică, iar securitatea necondiționată a acestui protocol a fost în general acceptată de ceva timp. Cu toate acestea, acest rezultat s-a dovedit a fi incorect. Nesiguranța acestui protocol, numit protocol BCJL, a fost dovedită în toamna anului 1995. În 1996, Dominic Myers a demonstrat teoretic că este imposibil să se implementeze o schemă sigură necondiționat. Orice astfel de protocol poate fi redus la un protocol atunci când sistemul este într-una dintre cele două stări clare după faza de transmisie, în funcție de bitul pe care Alice vrea să îl blocheze. Dacă protocolul se ascunde perfect, atunci Alice poate transforma unitar aceste stări una în alta folosind proprietățile descompunerii Schmidt , suprimând efectiv proprietatea de legare [11] .