Verpflichtungsprogramm

Ein Commitment-Schema ist ein kryptografisches Primitiv , das es ermöglicht, sich auf einen gewählten Wert (oder eine gewählte Aussage) festzulegen und diesen vor anderen geheim zu halten, wobei der festgelegte Wert später offengelegt werden kann. ^{[ 1 ]} Commitment-Schemata sind so konzipiert, dass eine Partei den Wert oder die Aussage nach der Festlegung nicht mehr ändern kann; sie sind also bindend . Commitment-Schemata finden wichtige Anwendung in verschiedenen kryptografischen Protokollen, darunter sicheres Münzwerfen, Zero-Knowledge-Beweise und sichere Berechnungen .

Man kann sich ein Commitment-Schema gut vorstellen, indem man sich vorstellt, dass der Absender eine Nachricht in eine verschlossene Kiste legt und diese dem Empfänger übergibt. Der Inhalt der Kiste ist für den Empfänger verborgen, da er das Schloss nicht selbst öffnen kann. Da der Empfänger die Kiste besitzt, kann die darin enthaltene Nachricht nicht verändert werden – sie kann nur dann enthüllt werden, wenn der Absender ihm zu einem späteren Zeitpunkt den Schlüssel aushändigt.

Die Interaktionen in einem Commitment-System finden in zwei Phasen statt:

1. die Commit-Phase, in der ein Wert ausgewählt und festgelegt wird
2. Die Enthüllungsphase, in der der Wert vom Absender offengelegt wird und der Empfänger anschließend dessen Echtheit überprüft.

In der obigen Metapher entspricht die Commit-Phase dem Absender, der die Nachricht in die Box legt und diese verschließt. Die Reveal-Phase entspricht der Übergabe des Schlüssels an den Empfänger, der damit die Box öffnet und ihren Inhalt überprüft. Die verschlossene Box symbolisiert die Commitment-Phase, der Schlüssel den Beweis.

In einfachen Protokollen besteht die Commit-Phase aus einer einzigen Nachricht vom Sender an den Empfänger. Diese Nachricht wird als Commitment bezeichnet . Es ist entscheidend, dass der gewählte Wert zu diesem Zeitpunkt nicht vom Empfänger aus der Nachricht extrahiert werden kann (dies wird als Verbergungseigenschaft bezeichnet ). Eine einfache Reveal-Phase besteht aus einer einzigen Nachricht, der Eröffnungsnachricht , vom Sender an den Empfänger, gefolgt von einer Überprüfung durch den Empfänger. Der in der Commit-Phase gewählte Wert muss der einzige sein, den der Sender berechnen kann und der in der Reveal-Phase gültig ist (dies wird als Bindungseigenschaft bezeichnet ) .

Das Konzept der Commitment-Schemata wurde vermutlich erstmals 1988 von Gilles Brassard , David Chaum und Claude Crépeau formalisiert ^{[ 2 ]} , und zwar im Rahmen verschiedener Zero-Knowledge-Protokolle für NP , die auf unterschiedlichen Arten von Commitment-Schemata basieren ^{[ 3 ] [ 4 ]} . Zuvor wurde das Konzept jedoch ohne formale Behandlung verwendet ^{[ 5 ] [ 6 ].} Der Begriff der Commitments tauchte erstmals in Arbeiten von Manuel Blum ^{[ 7 ]} , Shimon Even [ ^{8 ]} und Adi Shamir et al. ^{[ 9 ] auf} . Die Terminologie scheint von Blum geprägt worden zu sein ^{[ 6 ],} obwohl Commitment-Schemata synonym auch als Bit-Commitment-Schemata bezeichnet werden können – wobei dieser Begriff manchmal dem Spezialfall vorbehalten ist, in dem der zugesicherte Wert ein Bit ist . Zuvor wurde Commitment mittels Einweg-Hashfunktionen betrachtet, beispielsweise im Rahmen der Lamport-Signatur , dem ursprünglichen Einmal-Ein-Bit-Signaturverfahren.

Angenommen, Alice und Bob möchten einen Streit per Münzwurf beilegen . Befinden sie sich physisch am selben Ort, könnte ein typischer Ablauf wie folgt aussehen:

1. Alice "sagt" den Münzwurf an.
2. Bob wirft die Münze.
3. Wenn Alice richtig rät, gewinnt sie, andernfalls gewinnt Bob.

Wenn Alice und Bob sich nicht am selben Ort befinden, entsteht ein Problem. Sobald Alice den Münzwurf „angesagt“ hat, kann Bob das Ergebnis so festlegen, wie es ihm am besten passt. Wenn Alice ihre „Ansage“ Bob nicht mitteilt, kann sie, nachdem Bob die Münze geworfen und das Ergebnis verkündet hat, ebenfalls behaupten, das für sie beste Ergebnis vorhergesagt zu haben. Alice und Bob können mithilfe von Vereinbarungen ein Verfahren entwickeln, das es beiden ermöglicht, dem Ergebnis zu vertrauen.

1. Alice sagt den Münzwurf voraus, teilt Bob aber lediglich ihre Zusage zu ihrer Vorhersage mit.
2. Bob wirft die Münze und meldet das Ergebnis.
3. Alice enthüllt, wozu sie sich verpflichtet hat.
4. Bob vergewissert sich, dass Alices Anruf ihrer Zusage entspricht.
5. Wenn Alices Enthüllung mit dem von Bob gemeldeten Münzergebnis übereinstimmt, gewinnt Alice.

Damit Bob die Ergebnisse zu seinen Gunsten verfälschen kann, muss er den in Alices Commitment verborgenen Call verstehen. Ist das Commitment-Schema gut, kann Bob die Ergebnisse nicht verfälschen. Ebenso wenig kann Alice das Ergebnis beeinflussen, wenn sie den Wert ihres Commitments nicht ändern kann.

Ein praktisches Beispiel für dieses Problem findet sich, wenn Menschen (oft in den Medien) eine Entscheidung treffen oder eine Antwort in einem „versiegelten Umschlag“ abgeben, der später geöffnet wird. Die Frage „Mal sehen, ob der Kandidat das wirklich so geantwortet hat“, beispielsweise in einer Quizshow, kann als Beispiel für dieses System dienen.

Ein besonders motivierendes Beispiel ist die Verwendung von Commitment-Schemata in Zero-Knowledge-Beweisen . Commitments werden in Zero-Knowledge-Beweisen hauptsächlich aus zwei Gründen eingesetzt: Erstens ermöglichen sie dem Beweiser die Teilnahme an „Cut-and-Choose“-Beweisen, bei denen dem Verifizierer eine Auswahl an Informationen präsentiert wird und der Beweiser nur die Informationen offenlegt, die dieser Auswahl entsprechen. Commitment-Schemata erlauben es dem Beweiser, alle Informationen im Voraus festzulegen und erst später im Beweis die relevanten Informationen preiszugeben. ^{[ 10 ]} Zweitens werden Commitments auch vom Verifizierer in Zero-Knowledge-Beweisen verwendet, der seine Auswahl häufig vorab in einem Commitment festlegt. Dies ermöglicht die parallele Erstellung von Zero-Knowledge-Beweisen, ohne dem Beweiser zusätzliche Informationen preiszugeben. ^{[ 11 ]}

Das Lamport- Signaturverfahren ist ein digitales Signatursystem , das auf der Verwaltung zweier Sätze geheimer Datenpakete , der Veröffentlichung verifizierbarer Hashwerte dieser Datenpakete und der selektiven Offenlegung von Teilen der geheimen Datenpakete in einer Weise basiert, die den zu signierenden Daten genau entspricht. Dadurch wird die vorherige öffentliche Festlegung der geheimen Werte zu einem entscheidenden Bestandteil der Funktionsweise des Systems.

Da das Lamport-Signatursystem nicht mehrfach verwendet werden kann, wurde ein System entwickelt, das viele Lamport-Schlüsselsätze unter einem einzigen öffentlichen Wert zusammenfasst, der einer Person zugeordnet und von anderen verifiziert werden kann. Dieses System verwendet Hash -Bäume , um viele veröffentlichte Lamport-Schlüsselsätze in einen einzigen Hash-Wert zu komprimieren, der dem potenziellen Autor später verifizierter Daten zugeordnet werden kann.

Eine weitere wichtige Anwendung von Commitments findet sich im verifizierbaren Secret Sharing , einem zentralen Baustein sicherer Mehrparteienberechnungen . Bei einem Secret-Sharing- Verfahren erhält jede der mehreren Parteien einen Anteil an einem Wert, der vor allen anderen verborgen bleiben soll. Schließen sich genügend Parteien zusammen, können ihre Anteile genutzt werden, um das Geheimnis zu rekonstruieren. Selbst eine böswillige Gruppe von zu geringer Größe sollte jedoch nichts erfahren. Secret Sharing bildet die Grundlage vieler Protokolle für sichere Berechnungen : Um eine Funktion einer gemeinsamen Eingabe sicher zu berechnen, werden die geheimen Anteile manipuliert. Werden die Anteile jedoch von böswilligen Parteien generiert, ist es wichtig, dass deren Korrektheit überprüft werden kann. In einem verifizierbaren Secret-Sharing-Verfahren wird die Verteilung eines Geheimnisses von Commitments für die einzelnen Anteile begleitet. Die Commitments geben nichts preis, was einer unehrlichen Gruppe helfen könnte, aber die Anteile ermöglichen es jeder einzelnen Partei, die Korrektheit ihrer Anteile zu überprüfen. ^{[ 12 ]}

Formale Definitionen von Commitment-Verfahren unterscheiden sich stark in Notation und Ausgestaltung. Ein erstes Unterscheidungsmerkmal ist, ob das Commitment-Verfahren perfekte oder rechnerische Sicherheit hinsichtlich der Verbergungs- oder Bindungseigenschaften bietet. Ein weiteres Unterscheidungsmerkmal ist, ob das Commitment interaktiv ist, d. h. ob sowohl die Commit-Phase als auch die Reveal-Phase als durch ein kryptografisches Protokoll ausgeführt betrachtet werden können , oder ob sie nicht-interaktiv sind und aus zwei Algorithmen, Commit und CheckReveal , bestehen . Im letzteren Fall kann CheckReveal oft als eine derandomisierte Version von Commit angesehen werden , wobei die von Commit verwendete Zufälligkeit die Ausgangsinformation darstellt.

Wenn die Zusage C zu einem Wert x als C:=Commit(x,open) berechnet wird, wobei open die für die Berechnung der Zusage verwendete Zufallsvariable ist, dann reduziert sich CheckReveal (C,x,open) auf die einfache Überprüfung der Gleichung C=Commit (x,open) .

Mithilfe dieser Notation und Kenntnissen über mathematische Funktionen und Wahrscheinlichkeitstheorie formalisieren wir verschiedene Versionen der Bindungs- und Verbergungseigenschaften von Commitments. Die beiden wichtigsten Kombinationen dieser Eigenschaften sind perfekt bindende und rechnerisch verbergende Commitment-Schemata sowie rechnerisch bindende und perfekt verbergende Commitment-Schemata. Es ist zu beachten, dass kein Commitment-Schema gleichzeitig perfekt bindend und perfekt verbergend sein kann – ein rechnerisch unbeschränkter Angreifer kann einfach für jeden Wert von x und open Commit(x,open) generieren , bis er ein Paar findet, das C ausgibt , und in einem perfekt bindenden Schema identifiziert dies x eindeutig .

Sei open aus einer Menge der Größe n gewählt , d. h. es kann als k- Bit-Zeichenkette dargestellt werden, und sei das zugehörige Commitment-Schema. Da die Größe von k die Sicherheit des Commitment-Schemas bestimmt, wird sie als Sicherheitsparameter bezeichnet . ${\displaystyle 2^{k}}$${\displaystyle {\text{Commit}}_{k}}$

Dann ist für alle nicht-uniformen probabilistischen Polynomzeitalgorithmen, die und von zunehmender Länge k ausgeben , die Wahrscheinlichkeit, dass und eine vernachlässigbare Funktion in k ist . ${\displaystyle x,x'}$${\displaystyle open,open'}$${\displaystyle x\neq x'}$${\displaystyle {\text{Commit}}_{k}(x,open)={\text{Commit}}_{k}(x',open')}$

Dies ist eine Form der asymptotischen Analyse . Es ist auch möglich, dieselbe Anforderung mit konkreten Sicherheitskriterien zu formulieren : Ein Commit-Schema Commit ist sicher, wenn für alle Algorithmen, die in der Zeit t laufen und ausgeben, die Wahrscheinlichkeit, dass und höchstens ist . ${\displaystyle (t,\epsilon )}$${\displaystyle x,x',open,open'}$${\displaystyle x\neq x'}$${\displaystyle {\text{Commit}}(x,open)={\text{Commit}}(x',open')}$${\displaystyle \epsilon }$

Sei die Gleichverteilung über die Anfangswerte für den Sicherheitsparameter k. Ein Commitment-Schema ist jeweils perfektes, statistisches oder rechnerisches Verstecken, wenn für alle Wahrscheinlichkeitsensembles und gleich , statistisch nahe beieinander oder rechnerisch nicht unterscheidbar sind . ${\displaystyle U_{k}}$${\displaystyle 2^{k}}$${\displaystyle x\neq x'}$${\displaystyle \{{\text{Commit}}_{k}(x,U_{k})\}_{k\in \mathbb {N} }}$${\displaystyle \{{\text{Commit}}_{k}(x',U_{k})\}_{k\in \mathbb {N} }}$

Im Rahmen der universellen Kompositionsfähigkeit (UC) lassen sich Commitment-Schemata nicht realisieren . Der Grund dafür ist, dass UC-Commitments extrahierbar sein müssen , wie Canetti und Fischlin ^{[ 13 ]} gezeigt haben und im Folgenden erläutert werden.

Die ideale Commitment-Funktionalität, hier mit F bezeichnet , funktioniert im Wesentlichen wie folgt: Der Committer C sendet den Wert m an F , welches ihn speichert und eine Empfangsbestätigung an den Empfänger R sendet . Später sendet C eine Bestätigungsbestätigung an F , welches wiederum m an R weiterleitet .

Nehmen wir nun an, wir haben ein Protokoll π , das diese Funktionalität realisiert. Angenommen, der Committer C ist manipuliert. Im UC-Framework bedeutet dies im Wesentlichen, dass C nun von der Umgebung kontrolliert wird, welche versucht, die Protokollausführung vom idealen Prozess zu unterscheiden. Betrachten wir eine Umgebung, die eine Nachricht m auswählt und C anschließend anweist , sich gemäß π zu verhalten , als ob C sich zu m verpflichtet hätte . Hierbei ist zu beachten, dass der Empfänger nach dem Empfang einer Verpflichtung die Nachricht „recet“ ausgeben muss, um F zu realisieren . Nachdem die Umgebung diese Nachricht empfangen hat, weist sie C an , die Verpflichtung zu öffnen.

Das Protokoll ist nur dann sicher, wenn dieses Szenario nicht vom Idealfall zu unterscheiden ist, in dem die Funktionalität mit einem Simulator S interagiert . Hierbei hat S die Kontrolle über C. Insbesondere muss F immer dann, wenn R eine „Empfangsbestätigung“ ausgibt, dasselbe tun. Dies ist nur möglich, wenn S C anweist, einen Wert an F zu senden. Zu diesem Zeitpunkt ist m jedoch S noch nicht bekannt . Daher ist es unwahrscheinlich, dass F beim Öffnen des Commitments während der Protokollausführung m ausgibt , es sei denn, S kann m aus den Nachrichten extrahieren , die es vor der Ausgabe der Empfangsbestätigung durch R aus der Umgebung empfangen hat.

Ein in diesem Sinne extrahierbares Protokoll kann jedoch nicht statistisch verborgen sein. Angenommen, ein solcher Simulator S existiert. Betrachten wir nun eine Umgebung, die anstatt C zu beschädigen, stattdessen R beschädigt . Zusätzlich führt sie eine Kopie von S aus . Von C empfangene Nachrichten werden an S weitergeleitet , und Antworten von S werden an C weitergeleitet .

Die Umgebung weist C zunächst an , sich auf eine Nachricht m festzulegen . Im Verlauf der Interaktion legt S sich auf einen Wert m′ fest . Diese Nachricht wird an R übergeben, der m′ ausgibt . Laut Annahme gilt m′ = m mit hoher Wahrscheinlichkeit . Im Idealfall müsste der Simulator nun m generieren . Dies ist jedoch unmöglich, da die Festlegung zu diesem Zeitpunkt noch nicht erfolgt ist. Die einzige Nachricht, die R im Idealfall empfangen kann, ist daher eine Empfangsbestätigung. Es entsteht somit ein Widerspruch.

Ein Verpflichtungsschema kann entweder perfekt bindend sein (Alice kann ihre Verpflichtung nach ihrer Abgabe nicht mehr ändern, selbst wenn ihr unbegrenzte Rechenressourcen zur Verfügung stehen); oder perfekt verbergend (Bob kann die Verpflichtung nicht ohne Alices Offenlegung herausfinden, selbst wenn ihm unbegrenzte Rechenressourcen zur Verfügung stehen); oder als instanzabhängiges Verpflichtungsschema formuliert werden, das je nach Lösung eines anderen Problems entweder verbergend oder bindend ist. ^{[ 14 ] [ 15 ]} Ein Verpflichtungsschema kann nicht gleichzeitig perfekt verbergend und perfekt bindend sein.

Bit-Commitment-Verfahren lassen sich im Random-Oracle- Modell trivial konstruieren. Gegeben sei eine Hash-Funktion H mit einer 3k - Bit-Ausgabe. Um die k -Bit-Nachricht m zu committen , generiert Alice eine zufällige k- Bit-Zeichenkette R und sendet diese an Bob: H( R || m ). Die Wahrscheinlichkeit, dass R′ , m′ existieren, wobei m′ ≠ m , sodass H( R′ || m′ ) = H( R || m ) gilt, beträgt ≈ 2 ^{k  − k} . Um jedoch eine beliebige Vermutung für die Nachricht m zu testen , muss Bob 2 ^{^k} (bei einer falschen Vermutung) oder durchschnittlich 2 ^{^k − 1} (bei einer richtigen Vermutung) Anfragen an das Random Oracle stellen. ^{[ 16 ]} Frühere Verfahren, die auf Hash-Funktionen basieren, lassen sich im Wesentlichen als Verfahren betrachten, die auf der Idealisierung dieser Hash-Funktionen als Random Oracle beruhen.

Aus jeder injektiven Einwegfunktion lässt sich ein Bit-Commitment-Schema erstellen . Das Schema beruht auf der Tatsache, dass jede Einwegfunktion (mittels des Satzes von Goldreich-Levin ) so modifiziert werden kann, dass sie ein rechnerisch hartes Prädikat besitzt (wobei die Injektivität erhalten bleibt).

Sei f eine injektive Einwegfunktion mit h einem Hardcore-Prädikat. Um ein Bit b zu setzen , wählt Alice eine zufällige Eingabe x und sendet das Tripel

${\displaystyle (h,f(x),b\oplus h(x))}$

Alice sendet x an Bob, wobei XOR die bitweise Addition modulo 2 bezeichnet. Um den Wert zu decommitten, sendet Alice einfach x an Bob. Bob verifiziert dies, indem er f ( x ) berechnet und mit dem gespeicherten Wert vergleicht. Dieses Verfahren ist verschleiernd, da Bob zur Wiederherstellung von b auch h ( x ) berechnen muss . Da h ein rechenintensives Prädikat ist, ist die Rekonstruktion von h ( x ) aus f ( x ) mit einer Wahrscheinlichkeit größer als 0,5 genauso schwierig wie die Invertierung von f . Die perfekte Bindung folgt aus der Tatsache, dass f injektiv ist und somit f ( x ) genau ein Urbild besitzt. ${\displaystyle \oplus }$

Da wir nicht wissen, wie man aus einer beliebigen Einwegfunktion eine Einwegpermutation konstruiert, reduziert dieser Abschnitt die Stärke der kryptographischen Annahme, die für die Konstruktion eines Bit-Commitment-Protokolls erforderlich ist.

1991 zeigte Moni Naor , wie man ein Bit-Commitment-Schema aus einem kryptografisch sicheren Pseudozufallszahlengenerator erstellt . ^{[ 17 ]} Die Konstruktion ist wie folgt: Wenn G ein Pseudozufallszahlengenerator ist, der n Bits auf 3ⁿ Bits abbildet , und Alice sich auf ein Bit b festlegen möchte :

• Bob wählt einen zufälligen 3 n -Bit-Vektor R aus und sendet R an Alice.
• Alice wählt einen zufälligen n -Bit-Vektor Y und berechnet den 3 n- Bit-Vektor G ( Y ).
• Falls b = 1, sendet Alice G ( Y ) an Bob, andernfalls sendet sie das bitweise Exklusiv-Oder von G ( Y ) und R an Bob.

Um die Bindung aufzuheben, sendet Alice Y an Bob, der dann überprüfen kann, ob er ursprünglich G ( Y ) oder G ( Y ) R erhalten hat . ${\displaystyle \oplus }$

Dieses Schema ist statistisch bindend, d. h. selbst wenn Alice rechnerisch unbegrenzt ist, kann sie nicht mit einer Wahrscheinlichkeit von mehr als 2 ^{− n} betrügen . Um zu betrügen, müsste Alice ein Y' finden , sodass G ( Y' ) = G ( Y ) R gilt. Wenn sie einen solchen Wert fände, könnte sie ihre Entscheidung rückgängig machen, indem sie die Wahrheit und Y sendet oder die gegenteilige Antwort und Y' . Allerdings können G ( Y ) und G ( Y' ) jeweils nur ²ⁿ mögliche Werte erzeugen (also ^2²n ), während R aus ^2³n Werten ausgewählt wird . Da sie R nicht auswählt , beträgt die Wahrscheinlichkeit ^, dass ein Y' existiert ^, das die zum Betrügen notwendige Gleichung erfüllt, ^{2²n /} 2³n ⁼ 2 ^{− n .}${\displaystyle \oplus }$

Die Verschleierungseigenschaft ergibt sich aus einer Standardreduktion: Wenn Bob feststellen kann, ob Alice sich für eine Null oder eine Eins entschieden hat, kann er auch die Ausgabe des Pseudozufallsgenerators G von echtem Zufall unterscheiden, was der kryptographischen Sicherheit von G widerspricht .

Alice wählt eine Gruppe von Primzahlordnung p mit Erzeuger g .

Alice wählt zufällig einen geheimen Wert x zwischen 0 und p  − 1, den sie festlegt, berechnet c = g ^x und veröffentlicht c . Das Problem des diskreten Logarithmus besagt, dass es aus c rechnerisch unmöglich ist, x zu berechnen . Daher kann Bob unter dieser Annahme x nicht berechnen . Andererseits kann Alice kein x ′ <> x berechnen , sodass g ^{x ′} = c gilt. Das Schema ist also bindend.

Dieses Verfahren ist nicht perfekt verschleiernd, da jemand die Verpflichtung herausfinden könnte, wenn er das Problem des diskreten Logarithmus löst . Tatsächlich ist dieses Verfahren im Hinblick auf das Standard-Verbergungsspiel, bei dem ein Angreifer nicht erraten können sollte, welche der beiden von ihm gewählten Nachrichten die Verpflichtung darstellt – ähnlich dem IND-CPA -Spiel –, überhaupt nicht verschleiert. Eine Konsequenz daraus ist, dass ein Angreifer, wenn der Raum möglicher Werte für x klein ist, einfach alle ausprobieren könnte und die Verpflichtung somit nicht mehr verborgen bliebe.

Ein besseres Beispiel für ein perfekt bindendes Commitment-Schema ist eines, bei dem das Commitment die Verschlüsselung von x mit einem semantisch sicheren Public-Key-Verschlüsselungsverfahren mit perfekter Vollständigkeit ist und das Decommitment die Folge von Zufallsbits, die zur Verschlüsselung von x verwendet wurden . Ein Beispiel für ein informationstheoretisch verborgenes Commitment-Schema ist das Pedersen-Commitment-Schema ^{[ 18 ]} , das unter der Annahme des diskreten Logarithmus rechnerisch bindend ist ^{[ 19 ]} . Zusätzlich zum obigen Schema verwendet es einen weiteren Generator h aus der Primzahlgruppe und eine Zufallszahl r . Das Commitment wird gesetzt ^{[ 20 ]} .${\displaystyle c=g^{x}h^{r}}$

Diese Konstruktionen sind eng mit den algebraischen Eigenschaften der zugrundeliegenden Gruppen verwandt und basieren auf ihnen; ursprünglich schien der Begriff eng mit der Algebra verknüpft zu sein. Es wurde jedoch gezeigt, dass statistisch bindende Commitment-Schemata auf allgemeinen unstrukturierten Annahmen basieren können, und zwar mithilfe des Konzepts des interaktiven Hashings für Commitments aus allgemeinen Komplexitätsannahmen (speziell und ursprünglich basierend auf beliebigen Einwegpermutationen), wie in ^{[ 21 ] beschrieben.}

Alice wählt eine Zahl so, dass , wobei und große geheime Primzahlen sind. Zusätzlich wählt sie eine Primzahl , sodass und . Anschließend berechnet Alice eine öffentliche Zahl als Element maximaler Ordnung in der Gruppe. ^{[ 22 ]} Schließlich bestätigt Alice ihr Geheimnis, indem sie zunächst eine Zufallszahl aus generiert und dann berechnet . ${\displaystyle N}$${\displaystyle N=p\cdot q}$${\displaystyle p}$${\displaystyle q}$${\displaystyle e}$${\displaystyle e>N^{2}}$${\displaystyle gcd(e,\phi (N^{2}))=1}$${\displaystyle g_{m}}$${\displaystyle \mathbb {Z} _{N^{2}}^{*}}$${\displaystyle m}$${\displaystyle r}$${\displaystyle \mathbb {Z} _{N^{2}}^{*}}$${\displaystyle c=m^{e}g_{m}^{r}}$

Die Sicherheit der obigen Verpflichtung beruht auf der Schwierigkeit des RSA-Problems und bietet perfekte Verschleierung und rechnerische Bindung. ^{[ 23 ]}

Das Pedersen-Commitment-Schema führt eine interessante homomorphe Eigenschaft ein, die eine Addition zwischen zwei Commitments ermöglicht. Genauer gesagt: Gegeben zwei Nachrichten und sowie Zufallswerte und , ist es möglich, ein neues Commitment zu erzeugen, sodass: . Formal: ${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle r_{1}}$${\displaystyle r_{2}}$${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}+m_{2},r_{1}+r_{2})}$

${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=g^{m_{1}}h^{r_{1}}\cdot g^{m_{2}}h^{r_{2}}=g^{m_{1}+m_{2}}h^{r_{1}+r_{2}}=C(m_{1}+m_{2},r_{1}+r_{2})}$

Um die oben genannte Verpflichtung von Pedersen in eine neue Nachricht umzuwandeln , muss die Zufälligkeit hinzugefügt werden. ${\displaystyle m_{1}+m_{2}}$${\displaystyle r_{1}}$${\displaystyle r_{2}}$

Die oben erwähnte RSA-basierte Commitment-Operation besitzt analog dazu eine homomorphe Eigenschaft bezüglich der Multiplikation. Gegeben seien zwei Nachrichten und mit den Zufallsfunktionen bzw. . Man kann berechnen: . Formal: . ${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle r_{1}}$${\displaystyle r_{2}}$${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}\cdot m_{2},r_{1}+r_{2})}$${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=m_{1}^{e}g_{m}^{r_{1}}\cdot m_{2}^{e}g_{m}^{r_{2}}=(m_{1}\cdot m_{2})^{e}g_{m}^{r_{1}+r_{2}}=C(m_{1}\cdot m_{2},r_{1}+r_{2})}$

Um die obige Verpflichtung für eine neue Nachricht zu öffnen , müssen die Zufallselemente hinzugefügt werden. Diese neu generierte Verpflichtung wird ähnlich wie eine neue Verpflichtung verteilt . ${\displaystyle m_{1}\cdot m_{2}}$${\displaystyle r_{1}}$${\displaystyle r_{2}}$${\displaystyle m_{1}\cdot m_{2}}$

Manche Commitment-Verfahren erlauben es, nur einen Teil des zugesicherten Wertes nachzuweisen. Bei diesen Verfahren ist der geheime Wert ein Vektor aus vielen einzeln trennbaren Werten. ${\displaystyle X}$

${\displaystyle X=(x_{1},x_{2},...,x_{n})}$

Die Commitment- Berechnung erfolgt in der Commit-Phase. Normalerweise würde der Beweiser in der Reveal-Phase alle Elemente des Vektors sowie zusätzliche Beweisdaten offenlegen (wie beispielsweise bei einem einfachen Bit-Commitment ). Stattdessen kann der Beweiser einen beliebigen Wert aus dem Vektor offenlegen und einen effizienten Beweis dafür erstellen, dass es sich um das authentische i-te Element des ursprünglichen Vektors handelt, das das Commitment erzeugt hat . Der Beweis erfordert keine Offenlegung anderer Werte als i, und es ist unmöglich, gültige Beweise zu erstellen, die für eines der Elemente andere Werte als den wahren Wert offenlegen. ^{[ 24 ]}${\displaystyle C}$${\displaystyle X}$${\displaystyle X}$${\displaystyle R}$${\displaystyle X}$${\displaystyle i}$${\displaystyle C}$${\displaystyle X}$${\displaystyle x_{i}}$${\displaystyle x_{i}}$

Vektor-Hashing ist ein einfaches Verfahren zur teilweisen Enthüllung von Vektor-Commitments, das auf Bit-Commitments basiert. Die Werte werden zufällig gewählt. Einzelne Commitments werden durch Hashing erzeugt . Das Gesamt-Commitment wird wie folgt berechnet: ${\displaystyle m_{1},m_{2},...m_{n}}$${\displaystyle y_{1}=H(x_{1}||m_{1}),y_{2}=H(x_{2}||m_{2}),...}$

${\displaystyle C=H(y_{1}||y_{2}||...||y_{n})}$

Um ein Element des Vektors zu beweisen , gibt der Beweiser die Werte an. ${\displaystyle X}$

${\displaystyle (i,y_{1},y_{2},...,y_{i-1},x_{i},m_{i},y_{i+1},...,y_{n})}$

Der Verifizierer kann aus und berechnen und anschließend überprüfen, ob der Hash aller Werte die Commitment-Bedingung erfüllt . Leider ist der Beweis von der Größe und der Verifizierungszeit abhängig. Alternativ, wenn die Menge aller Werte ist, ist die Commitment-Bedingung von der Größe und der Beweis von der Größe und Verifizierungszeit abhängig. In beiden Fällen skaliert die Commitment-Bedingung bzw. der Beweis mit , was nicht optimal ist. ${\displaystyle y_{i}}$${\displaystyle x_{i}}$${\displaystyle m_{i}}$${\displaystyle y}$${\displaystyle C}$${\displaystyle O(n)}$${\displaystyle C}$${\displaystyle y}$${\displaystyle O(n)}$${\displaystyle O(1)}$${\displaystyle O(n)}$

Ein gängiges Beispiel für ein praktisches Verfahren zur partiellen Offenlegung ist ein Merkle-Baum , in dem ein binärer Hashbaum aus den Elementen des Baums erstellt wird . Dieses Verfahren erzeugt Verpflichtungen der Größe O(n²) und Beweise der Größe O(n²) und einer Verifizierungszeit von O(n²). Der Wurzel-Hash des Baums ist die Verpflichtung n . Um zu beweisen, dass eine aufgedeckte Verpflichtung Teil des ursprünglichen Baums ist, müssen nur Hashwerte des Baums, jeweils einer aus jeder Ebene, als Beweis offengelegt werden. Der Verifizierer kann dem Pfad vom beanspruchten Blattknoten bis zur Wurzel folgen, die Geschwisterknoten auf jeder Ebene hashen und schließlich einen Wurzelknotenwert erhalten, der gleich n sein muss . ^{[ 25 ]}${\displaystyle X}$${\displaystyle O(1)}$${\displaystyle O(\log _{2}{n})}$${\displaystyle C}$${\displaystyle x_{i}}$${\displaystyle \log _{2}{n}}$${\displaystyle C}$

Ein Kate-Zaverucha-Goldberg (KZG)-Commitment verwendet paarungsbasierte Kryptographie , um ein partielles Offenbarungsschema mit Commitment-Größen, Beweisgrößen und Beweisverifizierungszeiten zu erstellen. Anders ausgedrückt: Wenn die Anzahl der Werte in zunimmt, werden die Commitments und Beweise nicht größer, und der Verifizierungsaufwand für die Beweise erhöht sich nicht. ${\displaystyle O(1)}$${\displaystyle n}$${\displaystyle X}$

Eine KZG-Verpflichtung erfordert einen vorbestimmten Satz von Parametern zur Erstellung eines Paares und eines vertrauenswürdigen Falltürelements. Beispielsweise kann ein Tate-Paar verwendet werden. Angenommen, sind die additiven Gruppen und die multiplikative Gruppe des Paares. Anders ausgedrückt: Das Paar ist die Abbildung . Sei das Falltürelement (falls die Primzahlordnung von und ist ), und seien und die Erzeuger von bzw. . Im Rahmen der Parametereinstellung nehmen wir an, dass und bekannte und gemeinsame Werte für beliebig viele positive ganzzahlige Werte von sind , während der Falltürwert selbst verworfen wird und niemandem bekannt ist. ${\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}}$${\displaystyle \mathbb {G} _{T}}$${\displaystyle e:\mathbb {G} _{1}\times \mathbb {G} _{2}\rightarrow \mathbb {G} _{T}}$${\displaystyle t\in \mathbb {F} _{p}}$${\displaystyle p}$${\displaystyle \mathbb {G} _{1}}$${\displaystyle \mathbb {G} _{2}}$${\displaystyle G}$${\displaystyle H}$${\displaystyle \mathbb {G} _{1}}$${\displaystyle \mathbb {G} _{2}}$${\displaystyle G\cdot t^{i}}$${\displaystyle H\cdot t^{i}}$${\displaystyle i}$${\displaystyle t}$

Eine KZG-Verpflichtung formuliert den Vektor der zu verpflichtenden Werte als Polynom um. Zunächst berechnen wir ein Polynom, sodass für alle Werte von in unserem Vektor gilt. Die Lagrange-Interpolation ermöglicht es uns, dieses Polynom zu berechnen. ${\displaystyle p(i)=x_{i}}$${\displaystyle x_{i}}$

${\displaystyle p(x)=\sum _{i=0}^{n-1}x_{i}\prod _{0\leq j<n,j\neq i}{\frac {x-j}{i-j}}}$

Gemäß dieser Formulierung kodiert das Polynom nun den Vektor, wobei . Seien die Koeffizienten von , sodass . Die Verpflichtung wird wie folgt berechnet: ${\displaystyle p(0)=x_{0},p(1)=x_{1},...}$${\displaystyle p_{0},p_{1},...,p_{n-1}}$${\displaystyle p}$${\textstyle p(x)=\sum _{i=0}^{n-1}p_{i}x^{i}}$

${\displaystyle C=\sum _{i=0}^{n-1}p_{i}Gt^{i}}$

Dies wird einfach als Skalarprodukt zwischen den vorgegebenen Werten und den Polynomkoeffizienten berechnet . Da es sich um eine additive Gruppe mit Assoziativität und Kommutativität handelt, ist gleich einfach , da alle Additionen und Multiplikationen mit aus der Auswertung herausgerechnet werden können. Da der Wert der Falltür unbekannt ist, entspricht die Verpflichtung im Wesentlichen dem Polynom, ausgewertet an einer unbekannten Zahl, wobei das Ergebnis in einem undurchsichtigen Element von verschleiert wird . ${\displaystyle G\cdot t^{i}}$${\displaystyle p_{i}}$${\displaystyle \mathbb {G} _{1}}$${\displaystyle C}$${\displaystyle G\cdot p(t)}$${\displaystyle G}$${\displaystyle t}$${\displaystyle C}$${\displaystyle \mathbb {G} _{1}}$

Ein KZG-Beweis muss zeigen, dass die ermittelten Daten den authentischen Wert von zum Zeitpunkt der Berechnung darstellen. Sei der ermittelte Wert, den wir beweisen müssen. Da der Vektor von in ein Polynom umformuliert wurde, müssen wir beweisen, dass das Polynom , ausgewertet an der Stelle , den Wert annimmt . Vereinfacht gesagt, müssen wir lediglich beweisen, dass . Dies zeigen wir, indem wir nachweisen, dass die Subtraktion von eine Nullstelle an der Stelle ergibt . Wir definieren das Polynom als ${\displaystyle x_{i}}$${\displaystyle C}$${\displaystyle y=x_{i}}$${\displaystyle x_{i}}$${\displaystyle p}$${\displaystyle i}$${\displaystyle y}$${\displaystyle p(i)=y}$${\displaystyle y}$${\displaystyle p}$${\displaystyle i}$${\displaystyle q}$

${\displaystyle q(x)={\frac {p(x)-y}{x-i}}}$

Dieses Polynom selbst ist der Beweis dafür, dass , denn wenn existiert, dann ist durch teilbar , was bedeutet, dass es eine Nullstelle in hat , also (oder anders ausgedrückt: ). Der KZG-Beweis wird zeigen, dass existiert und diese Eigenschaft besitzt. ${\displaystyle p(i)=y}$${\displaystyle q}$${\displaystyle p(x)-y}$${\displaystyle x-i}$${\displaystyle i}$${\displaystyle p(i)-y=0}$${\displaystyle p(i)=y}$${\displaystyle q}$

Der Beweiser führt die obige Polynomdivision durch und berechnet anschließend den KZG-Beweiswert.${\displaystyle q}$${\displaystyle \pi }$

${\displaystyle \pi =\sum _{i=0}^{n-1}q_{i}Gt^{i}}$

Dies entspricht dem oben Genannten. Mit anderen Worten: Der Beweiswert ist das Polynom, das erneut am Falltürwert ausgewertet wird , der im Generator von verborgen ist . ${\displaystyle G\cdot q(t)}$${\displaystyle q}$${\displaystyle t}$${\displaystyle G}$${\displaystyle \mathbb {G} _{1}}$

Diese Berechnung ist nur möglich, wenn die obigen Polynome ohne Rest teilbar sind, da der Quotient in diesem Fall ein Polynom und keine rationale Funktion ist . Aufgrund der Konstruktion der Falltür ist es nicht möglich, eine rationale Funktion am Falltürwert auszuwerten, sondern nur ein Polynom mithilfe von Linearkombinationen der zuvor berechneten bekannten Konstanten von . Daher ist es unmöglich, einen Beweis für einen falschen Wert von zu erbringen . ${\displaystyle q}$${\displaystyle G\cdot t^{i}}$${\displaystyle x_{i}}$

Um den Beweis zu verifizieren, wird die bilineare Abbildung der Paarung verwendet, um zu zeigen, dass der Beweiswert ein reelles Polynom zusammenfasst , das die gewünschte Eigenschaft erfüllt, nämlich dass es gleichmäßig durch geteilt wurde . Die Verifizierungsberechnung überprüft die Gleichheit. ${\displaystyle \pi }$${\displaystyle q}$${\displaystyle p(x)-y}$${\displaystyle x-i}$

${\displaystyle e(\pi ,H\cdot t-H\cdot i)\ {\stackrel {?}{=}}\ e(C-G\cdot y,H)}$

wobei die bilineare Abbildungsfunktion wie oben ist. ist eine vorab berechnete Konstante, die auf der Grundlage von berechnet wird . ${\displaystyle e}$${\displaystyle H\cdot t}$${\displaystyle H\cdot i}$${\displaystyle i}$

Indem man die Berechnung in der Paarungsgruppe umschreibt , und und einsetzt und eine Hilfsfunktion zum Anheben in die Paarungsgruppe verwendet, wird die Beweisüberprüfung deutlicher. ${\displaystyle \mathbb {G} _{T}}$${\displaystyle \pi =q(t)\cdot G}$${\displaystyle C=p(t)\cdot G}$${\displaystyle \tau (x)=e(G,H)^{x}}$

${\displaystyle e(\pi ,H\cdot t-H\cdot i)=e(C-G\cdot y,H)}$

${\displaystyle e(G\cdot q(t),H\cdot t-H\cdot i)=e(G\cdot p(t)-G\cdot y,H)}$

${\displaystyle e(G\cdot q(t),H\cdot (t-i))=e(G\cdot (p(t)-y),H)}$

${\displaystyle e(G,H)^{q(t)\cdot (t-i)}=e(G,H)^{p(t)-y}}$

${\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}$

Unter der Annahme, dass die bilineare Abbildung korrekt konstruiert wurde, zeigt dies, dass , ohne dass der Prüfer die Werte von oder kennt. Der Prüfer kann sich dessen sicher sein, denn wenn , dann liefern die Polynome am Falltürwert denselben Wert . Dies beweist die Identität der Polynome, da der Falltürwert bei korrekter Parameterkonstruktion unbekannt ist, was bedeutet, dass es unmöglich ist, ein Polynom so zu konstruieren, dass es am Falltürwert einen bestimmten Wert annimmt (gemäß dem Schwartz-Zippel-Lemma ). Wenn nun verifiziert wird, dass wahr ist, dann ist die Existenz von verifiziert, daher muss durch teilbar sein , also aufgrund des Faktorsatzes . Dies beweist, dass der -te Wert des festgelegten Vektors gleich gewesen sein muss , da dies das Ergebnis der Auswertung des festgelegten Polynoms an der Stelle ist . ${\displaystyle q(x)(x-i)=p(x)-y}$${\displaystyle p}$${\displaystyle q}$${\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}$${\displaystyle x=t}$${\displaystyle q(x)(x-i)=p(x)-y}$${\displaystyle q}$${\displaystyle p(x)-y}$${\displaystyle (x-i)}$${\displaystyle p(i)-y=0}$${\displaystyle i}$${\displaystyle y}$${\displaystyle i}$

Darüber hinaus kann ein KZG-Commitment erweitert werden, um die Werte beliebiger Werte von (nicht nur eines einzelnen Wertes) zu beweisen, wobei die Beweisgröße gleich bleibt , die Beweisverifizierungszeit jedoch mit skaliert . Der Beweis selbst ist derselbe, aber anstatt eine Konstante zu subtrahieren , subtrahieren wir ein Polynom mit mehreren Nullstellen an allen Stellen, die wir beweisen wollen, und anstatt durch zu dividieren, dividieren wir an denselben Stellen durch . ^{[ 26 ]}${\displaystyle k}$${\displaystyle X}$${\displaystyle O(1)}$${\displaystyle O(k)}$${\displaystyle y}$${\displaystyle x-i}$${\textstyle \prod _{i}x-i}$

Es ist eine interessante Frage in der Quantenkryptographie, ob bedingungslos sichere Bit-Commitment-Protokolle auf Quantenebene existieren, also Protokolle, die (zumindest asymptotisch) bindend und verschleiernd sind, selbst wenn keine Beschränkungen der Rechenressourcen bestehen. Man könnte hoffen, dass es einen Weg gibt, die intrinsischen Eigenschaften der Quantenmechanik zu nutzen , wie es bei Protokollen für bedingungslos sichere Schlüsselverteilung der Fall ist .

Dies ist jedoch unmöglich, wie Dominic Mayers 1996 gezeigt hat . Jedes derartige Protokoll lässt sich auf ein Protokoll reduzieren, bei dem sich das System nach der Commitment-Phase in einem von zwei reinen Zuständen befindet, abhängig davon, welches Bit Alice committen möchte. Ist das Protokoll bedingungslos verschleiernd, kann Alice diese Zustände mithilfe der Eigenschaften der Schmidt-Zerlegung unitär ineinander transformieren und so die Bindungseigenschaft effektiv umgehen.

Eine subtile Annahme des Beweises ist, dass die Commit-Phase zu einem bestimmten Zeitpunkt abgeschlossen sein muss. Dies lässt Raum für Protokolle, die einen kontinuierlichen Informationsfluss erfordern, bis das Bit enthüllt oder das Protokoll abgebrochen wird. In letzterem Fall ist es nicht mehr bindend. ^{[ 28 ]} Allgemeiner gilt Mayers' Beweis nur für Protokolle, die Quantenphysik , nicht aber die spezielle Relativitätstheorie nutzen . Kent hat gezeigt, dass es bedingungslos sichere Protokolle für Bit-Commitment gibt, die das Prinzip der speziellen Relativitätstheorie nutzen , wonach sich Information nicht schneller als Licht ausbreiten kann. ^{[ 29 ]}

Physikalische nicht klonbare Funktionen (PUFs) basieren auf der Verwendung eines physikalischen Schlüssels mit interner Zufälligkeit, der schwer zu klonen oder zu emulieren ist. Elektronische, optische und andere Arten von PUFs ^{[ 30 ]} wurden in der Literatur ausführlich im Zusammenhang mit ihren potenziellen kryptographischen Anwendungen, einschließlich Commitment-Schemata, diskutiert. ^{[ 31 ] [ 32 ]}

• Unbewusste Übertragung
• Akkumulator (Kryptographie)
• Schlüsselunterzeichnerpartei
• Vertrauensnetz
• Zerocoin
• Anagramme – von Naturphilosophen des 17. Jahrhunderts verwendet, um die Priorität einer Entdeckung festzulegen, ohne sie anderen preiszugeben.

• Quantum-Bit-Commitment auf arxiv.org
• Kate-Zaverucha-Goldberg (KZG) Polynomverpflichtungen konstanter Größe - Alin Tomescu
• Kate polynomiale Verpflichtungen