コミットメントスキーム

コミットメントスキームは、選択した値（または選択したステートメント）を他の人には隠したままコミットし、後でコミットした値を明らかにできる暗号プリミティブです。 ^[1]コミットメントスキームは、当事者がコミットした後で値やステートメントを変更できないように設計されています。つまり、コミットメントスキームは拘束力があります。コミットメントスキームは、安全なコイン投げ、ゼロ知識証明、安全な計算など、多くの暗号化プロトコルで重要なアプリケーションを持っています。

コミットメント スキームを視覚的に表すには、送信者が鍵のかかった箱にメッセージを入れ、その箱を受信者に渡すと考えると分かりやすいでしょう。箱の中のメッセージは受信者には隠されており、受信者は自分で鍵を開けることはできません。受信者が箱を持っているため、中のメッセージは変更できません。送信者が後で鍵を渡した場合にだけ、メッセージが公開されます。

コミットメント スキームにおけるやり取りは、次の 2 つのフェーズで行われます。

1. コミットフェーズでは値が選択されコミットされます
2. 送信者が値を明らかにし、受信者がその真正性を検証する公開フェーズ

上記の比喩では、コミット フェーズは送信者がメッセージを箱に入れてロックすることです。公開フェーズは送信者が受信者にキーを渡し、受信者がそのキーを使用して箱を開けて内容を確認することです。ロックされた箱はコミットメントであり、キーは証明です。

単純なプロトコルでは、コミット フェーズは送信者から受信者への単一のメッセージで構成されます。このメッセージはコミットメントと呼ばれます。選択された特定の値がその時点で受信者によってメッセージから抽出できないことが重要です (これは隠蔽特性と呼ばれます)。単純な公開フェーズは、送信者から受信者への単一のメッセージ (オープニング) と、それに続く受信者によるチェックで構成されます。コミット フェーズで選択された値は、送信者が計算でき、公開フェーズで検証できる唯一の値である必要があります (これはバインディング特性と呼ばれます)。

コミットメント方式の概念は、おそらく1988 年にGilles Brassard、David Chaum、Claude Crépeauによって初めて形式化されました^[2] 。NPのさまざまなゼロ知識プロトコルの一部として、さまざまな種類のコミットメント方式に基づいています^{[3] [4]} 。しかし、この概念はそれ以前にも正式に扱われることなく使用されていました。^{[5] [6]}コミットメントの概念は、Manuel Blum、^[7] Shimon Even、^[8] Adi Shamirらの著作で最初に登場しました。^[9]この用語は Blum によって考案されたようですが^{[6]、コミットメント方式は}ビットコミットメント方式とも呼ばれ、コミットされた値がビットである特殊なケースのために予約されていることもあります。それ以前は、一方向ハッシュ関数によるコミットメントが、たとえば、元の 1 回限りの 1 ビット署名方式 であるLamport 署名の一部として考えられていました。

アリスとボブがコイン投げで何らかの紛争を解決したいとします。彼らが物理的に同じ場所にいる場合、典型的な手順は次のようになります。

1. アリスはコイン投げを「コール」し、
2. ボブはコインを投げ、
3. アリスの予測が正しければアリスが勝ち、そうでなければボブが勝ちます。

アリスとボブが同じ場所にいない場合、問題が発生します。アリスがコイン投げを「コール」すると、ボブはコイン投げの「結果」が自分にとって最も望ましいものになるように規定できます。同様に、アリスがボブに「コール」をアナウンスしない場合、ボブがコインを投げて結果を発表した後、アリスは自分にとって最も望ましい結果をコールしたと報告できます。アリスとボブは、両者が結果を信頼できるようにするための手順でコミットメントを使用できます。

1. アリスはコイントスを「コール」しますが、ボブにはコールの約束だけを伝えます。
2. ボブはコインを投げて結果を報告します。
3. アリスは自分が何を約束したのかを明かす。
4. ボブはアリスの電話が約束と一致していることを確認し、
5. アリスの発見がボブが報告したコインの結果と一致した場合、アリスが勝ちます。

ボブが結果を有利に傾けるには、アリスのコミットメントに隠された呼び出しを理解できなければなりません。コミットメント スキームが適切であれば、ボブは結果を歪めることはできません。同様に、アリスはコミットする値を変更できない場合、結果に影響を与えることはできません。

この問題の現実世界での応用は、人々（多くの場合メディア関係者）が「封印された封筒」で決定を約束したり、回答をしたりして、後でそれを開封する場合です。たとえばゲーム番組での「候補者が本当にそう答えたかどうか見てみましょう」は、このシステムのモデルとして役立ちます。

1 つの具体的な動機付けとなる例は、ゼロ知識証明におけるコミットメント スキームの使用です。コミットメントは、ゼロ知識証明で主に 2 つの目的で使用されます。1 つ目は、証明者が「カット アンド チョイス」証明に参加できるようにすることです。この証明では、検証者に学習する内容の選択肢が提示され、証明者は検証者の選択に対応する情報のみを明らかにします。コミットメント スキームを使用すると、証明者はすべての情報を事前に指定し、証明の後半で明らかにする必要がある情報のみを明らかにすることができます。^[10] 2 つ目は、コミットメントは、多くの場合、コミットメントで事前に選択を指定する検証者によってもゼロ知識証明で使用されます。これにより、証明者に追加情報を明らかにすることなく、ゼロ知識証明を並行して作成できます。^[11]

ランポート署名方式は、 2 セットの秘密データ パケットを維持し、データ パケットの検証可能なハッシュを公開し、署名するデータに特に準拠した方法で部分的な秘密データ パケットを選択的に公開するデジタル署名システムです。このように、秘密値に対する事前の公開コミットメントは、システムの機能の重要な部分になります。

Lamport 署名システムは複数回使用できないため、多数の Lamport キー セットを単一の公開値にまとめ、個人に結び付けて他の人が検証できるようにするシステムが開発されました。このシステムはハッシュ ツリーを使用して、公開されている多数の Lamport キー コミットメント セットを単一のハッシュ値に圧縮し、後で検証されるデータの将来の作成者に関連付けることができます。

コミットメントのもう 1 つの重要な応用は、検証可能な秘密共有です。これは、安全なマルチパーティ計算の重要な構成要素です。秘密共有スキームでは、複数のパーティのそれぞれが、誰にも知られないようにする値の「シェア」を受け取ります。十分な数のパーティが集まると、そのシェアを使用して秘密を再構築できますが、十分な規模ではない悪意のある集団でさえ何も知りません。秘密共有は、安全な計算のための多くのプロトコルの根幹にあります。共有された入力の関数を安全に計算するために、代わりに秘密のシェアが操作されます。ただし、悪意のあるパーティによってシェアが生成されると、それらのシェアが正しいかどうかをチェックできることが重要になる場合があります。検証可能な秘密共有スキームでは、秘密の配布に個々のシェアへのコミットメントが伴います。コミットメントは、不正な集団に役立つ情報を何も明らかにしませんが、シェアにより、各パーティが自分のシェアが正しいかどうかをチェックできます。^[12]

コミットメント スキームの正式な定義は、表記法とフレーバーが大きく異なります。最初のフレーバーは、コミットメント スキームが、隠蔽または結合プロパティに関して完全なセキュリティまたは計算セキュリティを提供するかどうかです。もう 1 つのフレーバーは、コミットメントが対話型であるかどうか、つまり、コミット フェーズと公開フェーズの両方が暗号化プロトコルによって実行されていると見なせるかどうか、またはそれらが非対話型で、 Commit と CheckReveal の 2 つのアルゴリズムで構成されるかどうかです。後者の場合、CheckReveal はCommitの非ランダム化バージョンと見なすことができ、 Commitによって使用されるランダム性が開始情報となります。

値xへのコミットメントCがC:=Commit(x,open)として計算され、 openがコミットメントの計算に使用されるランダム性である場合、CheckReveal (C,x,open) は単純に方程式C=Commit (x,open)を検証することになります。

この表記法と数学関数および確率論に関する知識を使用して、コミットメントの結合特性と隠蔽特性のさまざまなバージョンを形式化します。これらの特性の最も重要な 2 つの組み合わせは、完全に結合し計算的に隠蔽するコミットメント スキームと、計算的に結合し完全に隠蔽するコミットメント スキームです。コミットメント スキームは、完全に結合し完全に隠蔽することはできないことに注意してください。計算的に無制限の攻撃者は、C を出力するペアが見つかるまで、 xとopenのすべての値に対してCommit(x,open) を生成するだけでよく、完全に結合したスキームでは、これによってx が一意に識別されます。

open をサイズ のセットから選択するとします。つまり、これはkビットの文字列として表すことができます。また、 は対応するコミットメント スキームです。kのサイズによってコミットメント スキームのセキュリティが決まるため、これはセキュリティ パラメータと呼ばれます。 ${\displaystyle 2^{k}}$${\displaystyle {\text{コミット}}_{k}}$

次に、増加する長さkのおよび を出力するすべての非一様 確率多項式時間アルゴリズムについて、および の確率はkにおいて無視できる関数です。 ${\displaystyle x,x'}$${\displaystyle open,open'}$${\displaystyle x\neq x'}$${\displaystyle {\text{Commit}}_{k}(x,open)={\text{Commit}}_{k}(x',open')}$

これは漸近解析の形式です。具体的なセキュリティを使用して同じ要件を述べることもできます。コミットメント スキームCommit は、時間tで実行され、および の確率が最大でを出力するすべてのアルゴリズムに対して安全です。 ${\displaystyle (t,\epsilon )}$${\displaystyle x,x',open,open'}$${\displaystyle x\neq x'}$${\displaystyle {\text{Commit}}(x,open)={\text{Commit}}(x',open')}$${\displaystyle \epsilon }$

をセキュリティパラメータkの開始値にわたる一様分布とします。すべての確率集団に対して と が等しい、統計的に近い、または計算上区別がつかない場合、コミットメント方式はそれぞれ完全、統計的、または計算上の隠蔽です。 ${\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} }}$

ユニバーサルコンポーザビリティ(UC)フレームワークではコミットメントスキームを実現することは不可能である 。その理由は、CanettiとFischlin ^{[13]が示し、以下で説明するように、UCコミットメントは}抽出可能でなければならないためである。

ここでFで示される理想的なコミットメント機能は、おおよそ次のように動作します。コミッターC は値m をFに送信し、 F はそれを保存して「受領」を受信者Rに送信します。その後、C は「オープン」を Fに送信し、 F はm をRに送信します。

ここで、この機能を実現するプロトコルπ があると仮定します。コミッターCが破損していると仮定します。UC フレームワークでは、これは基本的にCが環境によって制御されることを意味します。環境は、プロトコルの実行を理想的なプロセスと区別しようとします。メッセージm を選択し、mにコミットしたかのように、πで規定されたとおりに動作するようにCに指示する環境を考えてみましょう。ここで、 F を実現するために、受信者はコミットメントを受け取った後、メッセージ「receipt」を出力する必要があることに注意してください。環境はこのメッセージを確認すると、コミットメントを開くように C に指示します。

このシナリオが、機能がシミュレータSと対話する理想的なケースと区別がつかない場合にのみ、プロトコルは安全です。ここでは、S はCを制御します。特に、R が「受領書」を出力するたびに、F も同様に行う必要があります。これを行う唯一の方法は、S がCにFに値を送信するように指示することです。ただし、この時点では、m はSに認識されていないことに注意してください。したがって、プロトコル実行中にコミットメントが開かれると、 R が受領書を出力する 前にS が環境から受信したメッセージからm を抽出できない限り、 F がmに対して開かれる可能性は低くなります。

しかし、この意味で抽出可能なプロトコルは、統計的に隠蔽することはできません。そのようなシミュレータS が存在すると仮定します。ここで、 C を破壊する代わりにR を破壊する環境を考えてみましょう。さらに、 Sのコピーを実行します。Cから受信したメッセージはSに送られ、Sからの応答はCに転送されます。

環境は最初にC にメッセージmをコミットするように指示します。対話のどこかの時点で、S は値m′をコミットします。このメッセージはRに渡され、 R はm′ を出力します。仮定により、高い確率でm' = mになることに注意してください。ここで、理想的なプロセスでは、シミュレーターはmを導き出す必要があります。しかし、この時点ではコミットメントがまだ開かれていないため、これは不可能であり、理想的なプロセスでRが受信できる唯一のメッセージは「受信」メッセージです。したがって、矛盾が生じます。

コミットメントスキームは、完全に拘束力を持つ（アリスが無制限の計算リソースを持っていても、一度行ったコミットメントを変更することは不可能である）、または完全に隠蔽する（ボブが無制限の計算リソースを持っていても、アリスに明らかにされない限り、ボブがコミットメントを見つけることはできない）、またはインスタンス依存のコミットメントスキームとして定式化される（別の問題の解決方法に応じて、隠蔽または拘束のいずれかになる）。^{[14] [15]}コミットメントスキームは、完全に隠蔽し、同時に完全に拘束力を持つことはできない。

ビットコミットメント方式は、ランダムオラクルモデルで簡単に構築できます。3 kビットの出力を持つハッシュ関数H が与えられた場合、kビットのメッセージm をコミットするために、アリスはランダムなkビットの文字列R を生成し、ボブに H( R || m )を送信します。m′ ≠ mであるR′、m′ が存在し、 H( R′ || m′ ) = H( R || m )となる確率は ≈ 2 ^{− k}ですが、メッセージmの推測をテストするには、ボブはランダムオラクルに 2 ^k回(推測が間違っている場合) または 2 ^{k -1}回 (平均して、正しい推測の場合) のクエリを実行する必要があります。 ^[16]ハッシュ関数に基づく以前の方式は、本質的には、これらのハッシュ関数をランダムオラクルとして理想化することに基づく方式であると考えられることに注意してください。

任意の単方向関数からビットコミットメント スキームを作成できます。このスキームは、すべての単方向関数が (ゴールドライヒ-レビンの定理を介して) 計算的にハードコアな述語を持つように変更できる(単方向プロパティを保持したまま) という事実に依存しています。

fを単方向の単射関数とし、hをハードコア述語とする。ビットbにコミットするために、アリスはランダムな入力xを選び、トリプルを送信する。

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

をボブに送信します。ここで、 はXOR、つまり2 を法とするビット加算を表します。デコミットするには、アリスはx をボブに送信するだけです。ボブはf ( x )を計算し、コミットされた値と比較して検証します。この方式は、ボブがb を復元するにはh ( x )を復元する必要があるため、隠蔽的です。hは計算的にハードコアな述語であるため、確率が 1/2 を超えるf ( x )から h ( x ) を復元することは、 f を反転するのと同じくらい困難です。完全結合は、 fが単射であり、したがってf ( x ) には正確に 1 つの原像があるという事実から生じます。 ${\displaystyle \oplus }$

任意の一方向関数から一方向順列を構築する方法がわからないため、このセクションでは、ビットコミットメント プロトコルを構築するために必要な暗号化仮定の強度が低下することに注意してください。

1991年にモニ・ナオールは暗号的に安全な疑似乱数生成器からビットコミットメント方式を作成する方法を示した。^[17]構成は以下のとおり。Gがnビットから3nビットを取る疑似乱数生成器である場合、アリスがビットbにコミットしたい場合：

• ボブはランダムな3nビットのベクトルRを選択し、Rをアリスに送信します。
• アリスはランダムなnビットのベクトルYを選択し、3nビットのベクトルG ( Y )を計算します。
• b = 1の場合、アリスはG ( Y ) をボブに送信し、それ以外の場合はG ( Y ) とRのビットごとの排他的論理和をボブに送信します。

コミットを解除するために、アリスはボブにY を送信します。ボブは最初にG ( Y ) を受信したのか、それともG ( Y ) R を受信したのかを確認できます。 ${\displaystyle \oplus }$

この方式は統計的に拘束力があり、つまり、アリスが計算上無制限であっても、 2 ^{− n を}超える確率で不正行為を行うことはできません。アリスが不正行為を行うには、 G ( Y' ) = G ( Y ) RとなるY' を見つける必要があります。アリスがそのような値を見つけることができれば、真実とY を送ることでデコミットするか、反対の答えとY' を送ることができます。しかし、G ( Y ) とG ( Y' ) はそれぞれ 2 ⁿ通りの値 (つまり 2 ^{2 n} )しか生成できませんが、 Rは 2 ^{3 n}通りの値から選ばれます。アリスはR を選ばないため、不正行為に必要な式を満たすY' が存在する確率は2 ^{2 n} /2 ^{3 n} = 2 ^{− n}です。 ${\displaystyle \oplus }$

隠蔽特性は標準的な還元から得られ、ボブがアリスが 0 と 1 のどちらをコミットしたかを判断できる場合、ボブは疑似乱数ジェネレータGの出力を真の乱数と区別することもできますが、これはGの暗号セキュリティと矛盾します。

アリスは乗法生成子gを持つ素数位数pの環を選択します。

アリスは、コミットする秘密の値x を0からp  − 1までランダムに選択し、 c = g ^{x を}計算してc を公開します。離散対数問題では、 cからx を計算することは計算上不可能であるため、この仮定の下ではボブはx を計算できません。一方、アリスは、g ^{x ′} = cとなるようなx ′ <> x を計算できないため、この方式は拘束力があります。

この方式は、離散対数問題を解くことができればコミットメントを見つけることができるため、完全に隠蔽されているわけではありません。実際、この方式は、IND-CPA ゲームと同様に、攻撃者が選択した 2 つのメッセージのうちどちらにコミットされているかを推測できない標準的な隠蔽ゲームに関して、まったく隠蔽されていません。この結果の 1 つは、 xの可能な値の空間が小さい場合、攻撃者はそれらをすべて試すだけで、コミットメントが隠蔽されないことです。

完全に拘束力のあるコミットメント方式のより良い例は、コミットメントが意味的に安全な完全な完全性を持つ公開鍵暗号化方式によるxの暗号化であり、デコミットメントがx の暗号化に使用されるランダムビットの文字列である場合です。情報理論的に隠蔽されたコミットメント方式の例は、離散対数仮定の下で計算的に拘束力のある ペダーセンコミットメント方式です。 ^[19]上記 の方式に加えて、素数群の別のジェネレータhと乱数rを使用します。コミットメントは に設定されます。^[20]${\displaystyle c=g^{x}h^{r}}$

これらの構成は、基になる群の代数的性質と密接に関連し、それに基づいており、その概念はもともと代数と非常に関連しているように思われた。しかし、一般的な複雑性仮定（具体的には、元々は任意の一方向の順列に基づく）からのコミットメントに対するインタラクティブハッシュの概念を介して、一般的な非構造化仮定に基づく統計的に拘束力のあるコミットメントスキームを構築することが可能であることが示された。^[21]

アリスはとなるような素数 を選択する。ここでとは大きな秘密の素数である。さらに、およびとなるような素数を選択する。次にアリスは、群の最大位数の元として公開数を計算する。^[22]最後に、アリスは最初にから乱数を生成し、次に を計算することで秘密を守る。 ${\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}}$

上記のコミットメントの安全性はRSA問題の難しさに依存しており、完全な隠蔽と計算結合を備えています。^[23]

Pedersen コミットメント スキームは、2 つのコミットメント間の加算を可能にする興味深い準同型特性を導入します。より具体的には、2 つのメッセージとランダム性、およびがそれぞれ与えられた場合、次のような新しいコミットメントを生成することができます。正式には、 ${\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})}$

上記の Pedersen コミットメントを新しいメッセージに開くには、ランダム性とを追加する必要があります。 ${\displaystyle m_{1}+m_{2}}$${\displaystyle r_{1}}$${\displaystyle r_{2}}$

同様に、上記の RSA ベースのコミットメントは、乗算演算に関して準同型特性を持ちます。ランダム性 と を持つ2つのメッセージ が与えられている場合、次を計算できます。正式には、次です 。 ${\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})}$

上記のコミットメントを新しいメッセージに公開するには、ランダム性とを追加する必要があります。この新しく生成されたコミットメントは、への新しいコミットメントと同様に配布されます。 ${\displaystyle m_{1}\cdot m_{2}}$${\displaystyle r_{1}}$${\displaystyle r_{2}}$${\displaystyle m_{1}\cdot m_{2}}$

一部のコミットメント スキームでは、コミットされた値の一部のみの証明が許可されます。これらのスキームでは、秘密の値は、個別に分離可能な多数の値のベクトルです。 ${\displaystyle X}$

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

コミットメントはコミットフェーズでから計算されます。通常、明らかにするフェーズでは、証明者は のすべてといくつかの追加の証明データ（単純なビットコミットメントなど）を明らかにします。代わりに、証明者はベクトルから任意の単一の値を明らかにし、それがコミットメントを作成した元のベクトルの の真正な要素であるという効率的な証明を作成できます。証明では以外の値を明らかにする必要はなく、 のいずれかに真の値とは異なる値を明らかにする有効な証明を作成することは不可能です。 ^[24]${\displaystyle C}$${\displaystyle X}$${\displaystyle X}$${\displaystyle R}$${\displaystyle X}$${\displaystyle i}$${\displaystyle C}$${\displaystyle X}$${\displaystyle x_{i}}$${\displaystyle x_{i}}$

ベクトルハッシュは、ビットコミットメントに基づく単純なベクトルコミットメント部分公開方式である。値はランダムに選択される。個々のコミットメントはハッシュによって作成される。全体のコミットメントは次のように計算される。 ${\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})}$

ベクトルの1つの要素を証明するために、証明者は値を明らかにする。 ${\displaystyle X}$

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

検証者は、とからを計算し、すべての値のハッシュがコミットメント であることを検証できます。残念ながら、証明はサイズと検証時間の点で問題があります。あるいは、 がすべての値のセットである場合、コミットメントはサイズであり、証明はサイズと検証時間の点で問題があります。いずれにしても、コミットメントまたは証明は に比例しますが、これは最適ではありません。 ${\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)}$

実用的な部分公開方式の一般的な例は、 の要素のバイナリハッシュツリーが作成されるMerkle ツリーです。この方式は、サイズ のコミットメントと、サイズおよび検証時間 の証明を作成します。ツリーのルートハッシュはコミットメント です。公開されたが元のツリーの一部であることを証明するには、ツリーの各レベルから 1 つずつハッシュ値のみを証明として公開する必要があります。検証者は、要求されたリーフノードからルートまでのパスをたどり、各レベルの兄弟ノードをハッシュし、最終的に に等しいルートノード値に到達できます。^[25]${\displaystyle X}$${\displaystyle O(1)}$${\displaystyle O(\log _{2}{n})}$${\displaystyle C}$${\displaystyle x_{i}}$${\displaystyle \log _{2}{n}}$${\displaystyle C}$

Kate-Zaverucha-Goldberg コミットメントは、ペアリングベースの暗号化を使用して、コミットメント サイズ、証明サイズ、証明検証時間で部分公開スキームを構築します。言い換えると、の値の数が増えても、コミットメントと証明は大きくならず、証明の検証にそれ以上の労力はかかりません。 ${\displaystyle O(1)}$${\displaystyle n}$${\displaystyle X}$

KZG コミットメントでは、ペアリングと信頼されたトラップドア要素を作成するための事前に決定されたパラメータ セットが必要です。たとえば、Tate ペアリングを使用できます。 が加法群であり、 がペアリング の乗法群であると仮定します。言い換えると、ペアリングはマップ です。がトラップドア要素 ( がおよびの素数位数である場合) とし、 および がそれぞれ および の生成元であるとします。パラメータ設定の一部として、 およびはの任意の数の正の整数値に対して既知で共有される値であると仮定しますが、トラップドア値自体は破棄され、誰にも知られません。 ${\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}$

KZGコミットメントは、コミットされる値のベクトルを多項式として再定式化する。まず、ベクトルのすべての値に対して多項式を計算する。ラグランジュ補間により、その多項式を計算できる。 ${\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}}}$

この定式化では、多項式はベクトル をエンコードします。ここでは の係数で、となります。コミットメントは次のように計算されます。 ${\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}}$

これは、あらかじめ決められた値と多項式係数とのドット積として単純に計算されます。は結合法則と可換法則を持つ加法群なので、のすべての加算と乗算は評価から分散できるため、 は単に に等しくなります。 トラップドア値は不明なので、コミットメントは本質的には誰にも知られていない数値で評価された多項式であり、結果は の不透明な要素に難読化されます。 ${\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}}$

KZG 証明では、明らかにされたデータが が計算されたときの の真正な値であることを証明する必要があります。 を証明しなければならない明らかにされた値とします。 のベクトルは多項式に再定式化されたので、多項式が で評価されたときに値 をとることを証明する必要があります。簡単に言えば、 を証明すればよいのです。から を引くと で根が得られることを証明することでこれを行います。多項式を次のように 定義します。${\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}}}$

この多項式はそれ自体が の証明です。なぜなら が存在する場合、 はで割り切れる、つまり に根を持つため、（つまり、）となるからです。KZG 証明は が存在し、この特性を持つことを実証します。 ${\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}$

証明者は上記の多項式除算を計算し、KZG証明値を計算する。${\displaystyle q}$${\displaystyle \pi }$

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

これは、上記のように と等しくなります。言い換えると、証明値はの生成器に隠されたトラップドア値 で再度評価された多項式です。 ${\displaystyle G\cdot q(t)}$${\displaystyle q}$${\displaystyle t}$${\displaystyle G}$${\displaystyle \mathbb {G} _{1}}$

この計算は、上記の多項式が割り切れる場合にのみ可能です。その場合、商は有理関数ではなく多項式 だからです。トラップドアの構造上、トラップドア値で有理関数を評価することはできず、事前に計算された の既知の定数の線形結合を使用して多項式を評価することしかできません。これが、 の誤った値に対する証明を作成することが不可能な理由です。 ${\displaystyle q}$${\displaystyle G\cdot t^{i}}$${\displaystyle x_{i}}$

証明を検証するために、ペアリングの双線型写像を使用して、証明値が、 が で均等に分割されるという望ましい特性を示す実多項式を要約していることを示します。検証計算では、等式をチェックします。 ${\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)}$

ここで、は上記の双線形写像関数です。は事前に計算された定数で、に基づいて計算されます。 ${\displaystyle e}$${\displaystyle H\cdot t}$${\displaystyle H\cdot i}$${\displaystyle i}$

ペアリング群 の計算を書き直し、とを代入し、 をペアリング群に持ち上げるヘルパー関数とすることで、証明の検証がより明確になります。 ${\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)}$

双線形写像が有効に構築されていると仮定すると、これは、検証者が または が何であるかを知らなくても であることが証明されます。の場合、多項式は落とし戸値 で同じ出力に評価されるため、検証者はこれを確信できます。 これは、多項式が同一であることを示しています。なぜなら、パラメータが有効に構築されている場合、落とし戸値は誰にも知られておらず、落とし戸で特定の値を持つように多項式を設計することは不可能であるからです (シュワルツ–ジッペルの補題による)。が真であることが検証された場合、 が存在することが検証されるため、 は で多項式割り切れるはずであり、因数定理により となります。これは、コミットされたベクトルの 番目の値が に等しかったに違いないことを証明します。これは、コミットされた多項式を で評価した出力だからです。 ${\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}$

さらに、KZGコミットメントは、 （1つの値だけではなく）任意の の値を証明するように拡張することができ、証明サイズは のままですが、証明検証時間は に比例します。証明は同じですが、定数 を引く代わりに、証明したいすべての場所で多重根を生成する多項式を引き、 で割る代わりに、同じ場所でで割ります。 ^[26]${\displaystyle k}$${\displaystyle X}$${\displaystyle O(1)}$${\displaystyle O(k)}$${\displaystyle y}$${\displaystyle x-i}$${\textstyle \prod _{i}x-i}$

量子暗号において、無条件に安全なビットコミットメントプロトコル、つまり計算リソースに制限がない場合でも（少なくとも漸近的に）拘束力と秘匿性を持つプロトコルが量子レベルに存在するかどうかは興味深い問題です。無条件に安全な鍵配布プロトコルのように、量子力学の本質的な特性を利用する方法があるかもしれないと期待できます。

しかし、これは不可能であり、ドミニク・メイヤーズが1996年に示した（元の証明については^{[27]を参照）。そのようなプロトコルはどれも、アリスがコミットしたいビットに応じて、システムがコミットメントフェーズ後に2つの純粋な状態のいずれかにあるプロトコルに還元できる。プロトコルが無条件に隠蔽されている場合、アリスは}シュミット分解の特性を使用してこれらの状態を互いにユニタリ変換することができ、結合特性を効果的に無効にすることができる。

証明の微妙な仮定の1つは、コミットフェーズはある時点で終了しなければならないということである。これにより、ビットが公開されるかプロトコルがキャンセルされるまで継続的な情報フローを必要とするプロトコルの余地が残され、その場合、プロトコルはもはや拘束力を持たない。^[28]より一般的には、マイヤーズの証明は量子物理学を利用するプロトコルにのみ適用され、特殊相対性理論には適用されない。ケントは、情報は光より速く移動できないという特殊相対性理論の原理を利用する、ビットコミットメントのための無条件に安全なプロトコルが存在することを示した。^[29]

物理的に複製不可能な関数（PUF）は、複製やエミュレートが困難な内部ランダム性を持つ物理キーの使用に依存しています。電子式、光学式、その他のタイプのPUF ^[30]は、コミットメントスキームを含む潜在的な暗号化アプリケーションに関連して、文献で広く議論されています。^{[31] [32]}

• 無意識の転送
• アキュムレータ（暗号化）
• 鍵署名パーティー
• 信頼のウェブ
• ゼロコイン
• アナグラム— 17世紀の自然哲学者が、他人に明かさずに発見の優先順位を確立するために使用した。

• arxiv.org における量子ビットコミットメント
• Kate-Zaverucha-Goldberg (KZG) 定数サイズの多項式コミットメント - Alin Tomescu
• ケイト多項式コミットメント