暗号理論教室
暗号理論教室

コミットメントプロトコルとその安全性定義

コミットメントプロトコル

コミットメントプロトコル (C, R)とは、
  • （コミットフェーズ） 送信者Cが受信者Rに対し、トランスクリプトcを通して、ある値vにコミットする。
  • （オープンフェーズ）その後、送信者Cは受信者Rに対し、コミットメントcをその値vにオープンする。
2段階からなるプロトコルである。

ただし、
  • (秘匿性) 受信者Rは、コミットメント（を表すトランスクリプト）cを見ても、送信者Cによってどんな値vがコミットされたかわからない。
  • (束縛性) 送信者Cは、値vへのコミットメントcを、後に、vとは異なる他の値v'にはオープンできない。
ことを要求する。

よりフォーマルには、

定義(コミットメント)
効率的なアルゴリズムの組 (C, R) が（Mをメッセージ空間とする）コミットメントスキームであるとは、
  • (完遂性) 任意の v ∈ M について、
    • Pr[ (d, c) ← (S(v), R),　(-, v') ← (S(d), R(c))　：　v = v' ]　=　1.
  • (秘匿性) 任意の効率的なアルゴリズムR* について、
    • Pr[ (v0, v1, s) ← R*,　b ← {0,1},　(-, b') ← (S(vb), R*(s))　：　b' = b ]
は1/2をネグリジブルにしか超えない。
  • (束縛性) 任意の効率的なアルゴリズムS* について、
    • Pr[ （(d1, d2), c）← (S*, R),　(-, v1) ← (S*(d1), R(c)),　(-, v2) ← (S*(d2), R(c))
      • 　 ：　v1 ≠ ⊥,　v2 ≠ ⊥, v1 ≠ v2 ]
がネグリジブル。

同時発生的な頑健性

コミットメントに関して同時発生的な頑健性
試行 cmimcomA(m=(m1,...,ml), z) :
  • Run (C(m1)||・・・||C(ml), A(z), R||・・・||R)
  • m'1,...,m'l ← Aが各Rにコミットした値
    • ただし、そのトランスクリプトがある左インタラクションのコピーなら、m'i ← ⊥.
  • return m'1,...,m'l.

試行 csiscomS(z) :
  • Run (S(z), R||・・・||R)
  • m'1,...,m'l ← Sが各Rにコミットした値
  • return m'1,...,m'l.

定義(concurrentNMc)
（Mをメッセージ空間とする）コミットメントスキーム(C, R)が
コミットメントに関して同時発生的に頑健であるとは、
任意の多項式l(n)、任意の効率的な攻撃者Aに対し、ある効率的なシミュレータSが存在し、
以下の2つの分布が計算的に識別不可能であることをいう：
  • { cmimcomA(m, z) }m∈Ml, z∈B*
  • { csiscomS(z) }m∈Ml, z∈B*.

デコミットメントに関して同時発生的な頑健性
試行 cmimdecomA(m=(m1,...,ml), z) :
  • Run (C(m1)||・・・||C(ml), A(z), R||・・・||R)
  • m'1,...,m'l ← Aが各Rにデコミットした値
    • ただし、（フェーズごとに見て）トランスクリプトがある左インタラクションのコピーなら、m'i ← ⊥.
  • return m'1,...,m'l.

試行 csisdecomS(m=(m1,...,ml), z) :
  • Run (S(z), R||・・・||R)
    • ただし、各 i 番目のインタラクションについて、そのコミットフェースが終了したらSにmiを渡す。
  • m'1,...,m'l ← Sが各Rにデコミットした値
  • return m'1,...,m'l.

定義(concurrentNMd)
（Mをメッセージ空間とする）コミットメントスキーム(C, R)が
デコミットメントに関して同時発生的に頑健であるとは、
任意の多項式l(n)、任意の効率的な攻撃者Aに対し、ある効率的なシミュレータSが存在し、
以下の2つの分布が計算的に識別不可能であることをいう：
  • { cmimdecomA(m, z) }m∈Ml, z∈B*
  • { csisdecomS(m, z) }m∈Ml, z∈B*.

コミットメントスキームの構成

基本的なコミットメントスキーム

Naor コミットメント
構成(Naor) [Naor 91]
[部品]
  • 疑似乱数生成器 G: {0,1}n → {0,1}3n
[パラメータ]
  • セキュリティパラメータ : 1n
  • コミッターCの入力 : v (∈{0,1})
[コミットメントフェーズ] 　※ λ, (r), (α).
  • R→C : r ← {0,1}3n,　 r を送る。
  • C→R : s ← {0,1}n
    • v =? 0 : α = G(s),　v =? 1 : α = G(s) + r
    • αを送る。
[デコミットメントフェーズ] 　※ (v,s).
  • C→R : (v, s) を送る。
  • R : v =? 0 : α =? G(s),　v =? 1 : α =? G(s) + r.

定理(Naor) [Naor 91]
G が拡大因子 3n の疑似乱数生成器ならば、
構成(Naor)は統計束縛なコミットメントスキームである。

Naorコミットメントはマリアブルである。
実際、以下の中間攻撃者Aは送信者のコミットメントを反転することができる。

C A R
←r
←r
→α
→α+r
→v,s
→1+v,s

Blum コミットメント
構成(Blum) [Blum 82]
[部品]
  • 一方向置換 f: {0,1}n → {0,1}n
  • f のハードコア述語 b : {0,1}n → {0,1}
[パラメータ]
  • セキュリティパラメータ : 1n
  • コミッターCの入力 : v (∈{0,1})
[コミットメントフェーズ] 　※ (α,σ).
  • C→R : s ← {0,1}n,　 α = f(s),　σ = b(s) + v,　 (α,σ)を送る。
[デコミットメントフェーズ] 　※ (v,s).
  • C→R : (v, s) を送る。
  • R : α =? f(s) ∧ σ =? b(s) + v.

定理(Blum) [Blum 82]
f が一方向置換で、bがそのハードコア述語ならば、
構成(Blum)は完全束縛なコミットメントスキームである。

Blumコミットメントもマリアブルである。

同時発生的に頑健なコミットメントスキーム

OPVスキーム
構成(OPV) [OPV 09]
[部品]
  • nmZK = {Pt, Vt}t : a constant-round tag-based one-left many-right perfect cNMZK argument of knowledge
  • (wiP, wiV) : a constant-round WI proof of knowledge
  • Com : a non-interactive statistically-binding commitment scheme
  • SS = (SG, Sig, SVer) : a secure signature scheme
[パラメータ]
  • セキュリティパラメータ : 1k
  • コミッターCの入力 : m (∈{0,1}k)
[コミットメントフェーズ] 　※ (c, PK, PPK(c)), (c0, c1, wiP(c0,c1)), (σ0).
  • C→R : s ← {0,1}k, c = Com(m, s), cを送る。
  • C→R : (PK,SK) ← SG(1k), PKを送る。
  • C⇔R :
    • C : call PPK on (c; m,s) for 『 ∃m, s : c = Com(m,s) 』
    • R : call VPK on (c). VPKがrejectなら、アボート
  • R→C : i∈{0,1} : mi,si ← {0,1}k, ci = Com(mi, si). c0,c1を送る。
  • R⇔C :
    • R : b←{0,1}, call wiP on (c0,c1; mb,sb) for
      • 『 ∃m, s : c0 = Com(m,s) OR c1 = Com(m,s) 』
    • C : call wiV on (c0,c1). wiVがrejectなら、アボート
  • C→R : trans0 ← the transcript so far, σ0 ← Sig(SK,trans0), σ0を送る。
  • R : SVer(PK,trans0,σ0) =? 0 : アボート
[デコミットメントフェーズ] 　※ (m, PPK(c,c0,c1), σ1).
  • C→R : mを送る。
  • C⇔R :
    • C : call PPK on (c,c0,c1; m,s) for
      • 『 ∃m, s : c = Com(m,s) OR c0 = Com(m,s) OR c1 = Com(m,s) 』
    • R : call VPK on (c,c0,c1). VPKがrejectなら、アボート
  • C→R : trans1 ← the transcript so far, σ1 ← Sig(SK,trans1), σ1を送る。
  • R : SVer(PK,trans1,σ1) =? 0 : アボート

定理(OPV) [OPV09]
nmZKが a constant-round tag-based one-left many-right perfect cNMZK argument of knowledgeで、
(wiP, wiV)が a constant-round WI proof of knowledgeで、
Comが a non-interactive statistically-binding commitment schemeで、
SSがa secure signature schemeならば、
構成(OPV)はコミットメントに関してもデコミットメントに関しても同時発生的に頑健である。


系(OPV) [OPV09]
クローフリー置換が存在するならば、
コミットメントに関してもデコミットメントに関しても同時発生的に頑健な
定数ラウンドのコミットメントスキームが存在する。















「コミットメント」をウィキ内検索
最終更新：2010年01月26日 17:42