はじめに

本記事では、ゼロ知識証明、マルチパーティ計算、電子投票など多くの暗号プロトコルの基本的な構成要素となっているコミットメント方式について説明します。

コミットメント方式の概要

コミットメント方式とは、送信者と受信者の2パーティーからなり、送信者が受信者に読めない情報を送信し、後に付加的な情報を送信することで受信者に読めるようにする技術です。

コミットメント方式は、コミットフェーズ（commit phase）と公開フェーズ（reveal phase / open phase）の2つのフェーズから構成されます。なお、コミットフェーズの前に準備段階が含まれる場合もあります。

• コミットフェーズ（commit phase）
  送信者は、送信（コミット）したい値を暗号化して受信者に送信します。
• 公開フェーズ（reveal phase / open phase）
  送信者は、コミットフェーズで暗号化して送信した値についての付加的な情報と、コミットしたい値を受信者に送信します（公開）。 受信者は両フェーズで受信した値をもとに、コミットしたい値が正しいものだったかを検証します。

さらに、コミットメント方式は、以下の相反する秘匿性（hiding）と拘束性（binding）の2つの性質を満たします。

• 秘匿性（hiding）
  コミットフェーズの終了時、受信者は送信者からコミットされた値についてのいかなる情報も得ることができません。
• 拘束性（binding）
  公開フェーズ時、送信者がコミットフェーズでコミットした値とは異なる値を送信したとしても、検証を通過することはありません。

これらの性質が、無制限の計算能力があっても破ることができない場合に完全秘匿や完全拘束といい、計算量に依存する場合に計算量秘匿や計算量拘束といいます。

どちらも完全であるコミットメント方式が存在することが望まれますが、実際には完全秘匿かつ完全拘束なコミットメント方式は存在せず、少なくともどちらかの性質が計算量に依存するものとなってしまいます。

📎 完全秘匿かつ完全拘束なコミットメントが存在しないことの説明
いま、コミットしたい値を $m$ 、付加的な情報を $r$ 、暗号化に使う関数を $C:(m,r)\mapsto C(m,r)$ として、完全秘匿かつ完全拘束なコミットメントが構成できたとします。このとき、コミットフェーズで送信者が $c=C(m,r)$ を送信する時、 $c=C(m’,r’)$ であるような $m'(\neq m)$ と $r'(\neq r)$ が存在しなければなりません。このような $(m’,r’)$ が存在しないと仮定すると、受信者が無制限の計算能力を持っていれば $(m,r)$ を見つけられることになり、完全秘匿であることに矛盾します。一方で、 $(m’,r’)$ が存在するとき、送信者も無制限の計算能力を持っていれば、送信者も $(m’,r’)$ を見つけることができてしまいます。このとき、公開フェーズで $(m’,r’)$ を送信することによりコミットフェーズで送信した値を偽ることができてしまい、完全拘束であることに矛盾します。

トランプの色あてゲーム

コミットメント方式の理解のために、以下のようなトランプの色あてゲームを考えてみましょう。

ここに表面が赤のトランプと黒のトランプを1枚ずつ用意します。裏面はどちらのトランプも同じ色、例えば白になっているとしましょう。

ゲームは以下のように進行します。

１．Aさんは、Bさんに見えないように赤か黒のトランプ1枚好きな方を選んで、それを白い面、つまり裏面が表になるようにして場に置きます。

２．Bさんは、トランプの表面の色が赤か黒かを予想して、Aさんに伝えます。

３．場にあるカードをひっくり返して表面を見せます。

カードの表面の色がBさんの予想通りならBさんの勝ち、そうでなければAさんの勝ちとなります。

コミットメント方式との関係

このゲームの中には、実はコミットメント方式の考え方が含まれています。

コミットフェーズと公開フェーズには以下のように対応します。

• コミットフェーズ
  １．はコミットフェーズとみなせます。Aさんが白い面が表になるようにしてトランプを場に置く、という動作は、ある意味暗号化とみなすことができ、トランプの裏面という暗号化された値（白色）がBさんに伝わっています。
• 公開フェーズ
  ３．は公開フェーズとみなせます。Aさんがトランプをひっくり返して表を向けたことで、Bさんにはコミットしていた値（ここでは赤か黒かの色）が伝わります。

秘匿性と拘束性については以下のように考えることができます。

• 秘匿性
  １．の時点で表面の色の情報の分からなさを秘匿性とみなすことができます。
  １．のコミットフェーズが終了した時、Bさんは裏返しになっている側の色が赤であるのか、黒であるのかを見極めることはできません。ただし、Bさんが透視能力を持っていたり、Bさんが先に使うカードにキズをつけていた場合は話が変わってくるかもしれません。
• 拘束性
  ３．でカードをひっくり返すとき、１． で確定していたはずの表面の色を異なる色に公開できるかの度合いを拘束性とみなすことができます。
  Aさんがゲームの進行にあるような、カードをひっくり返す以外の動きを全くしない場合であれば、ひっくり返すカードを別の色にすり替えるなどのズルをすることはできません。ただし、Aさんがマジシャンであったり、Bさんの視線を何らかの方法でそらしてカードを別のものに入れ替える等のズルをした場合は話が変わってくるかもしれません。

これらの秘匿性と拘束性をもっと厳密に、すなわちこの色あてゲームをより不正のないゲームにすることを考えると、以下に具体例として示すようなコミットメント方式を使うことが考えられます。

コミットメント方式の具体例

先にも説明したように、完全秘匿または完全拘束のどちらかを満たすことが可能ですが、これらがどちらも完全なものにすることはできません。ここでは計算量秘匿かつ完全拘束なコミットメント方式と、完全秘匿かつ計算量拘束なコミットメント方式の例を1つずつを紹介します。

計算量秘匿かつ完全拘束なコミットメント方式の例

計算量秘匿かつ完全拘束なコミットメント方式は、公開鍵暗号でみられるような確率的暗号化関数、つまり値を暗号化するとき、そのたびに別の値に暗号化されるような関数、を利用することで構成できることが知られています。

先にこの方式の具体的な構成例を示します。

通信の流れ

送信者は値 $m\in\{0,1\}$ を送ることを考えます。通信は以下のように進行します。

• コミットフェーズ
  送信者は異なる素数 $p,q$ をとり、 $n=pq,\,e=(p-1)(q-1)$ とします。
  また、送信者は、乱数 $r\in\{1,\ldots,n\}$ をとり、 $f(r)=r^e\mod n$ と、 $r$ の最下位ビット $b(r)$ を計算します。これらを用いて $E_r(m)=(f(r),b(r)\oplus m)$ とします。
  送信者は $(n,e)$ と $E_r(m)$ を受信者に送信します。
• 公開フェーズ
  送信者は $(m,r)$ を受信者に送信します。
  受信者は $(f(r),b(r)\oplus m)$ を計算して、コミットフェーズで送られてきていた $E_r(m)$ と比較して検証します。

計算量秘匿かつ完全拘束であることの説明

ここでは確率的暗号化関数 $E_r$ を、一方向性置換 $f$ とハードコア述語 $b$ とよばれるものを利用して構成しています。

簡単に、一方向性置換とハードコア述語と呼ばれるものについて説明をします。

• 一方向性関数、一方向性置換
  $f$ が一方向性関数であるとは、入力 $x$ に対して関数値 $y=f(x)$ は簡単に計算できるが、逆関数の値 $x= f^{-1}(y)$ を求めることが（計算量的に）非常に困難である関数のことです。
  特に、全単射で定義域と値域が一致するような一方向性関数 $f$ のことを一方向性置換といいます。
• ハードコア述語
  $b$ が一方向性関数 $f$ のハードコア述語であるとは、入力 $x$ に対して、 $b(x)$ を計算することは簡単だが、一方向性関数 $f(x)$ を与えられても $b(x)$ を計算することが難しいようなバイナリを出力する関数のことです。

一方向性置換 $f$ とハードコア述語 $b$ の利用によって、このコミットメント方式が計算量秘匿かつ完全拘束な性質を持つことを確認します。

• 計算量秘匿性
  $f$ の一方向性は計算量に依存しているため、無制限の計算能力がある受信者は $f(r)$ の値から $r$ を復元できます。よって $b(r)$ の計算をすることができ、これとコミットフェーズで送られてきていた $b(r)\oplus m$ との排他的論理和をとることで $m$ を得ることができます。したがって計算量秘匿であることがわかります。
• 完全拘束性
  コミットメントの値に含まれる $f$ は、異なる $r$ に対しては異なる値をとるので、各 $r$ に対して $E_r$ の値域に被りがないことがわかります。さらに、 $r$ を固定した場合には $b(r)\oplus m$ の値は $m\in\{0,1\}$ に対して全単射に対応がつくので、コミットフェーズ時と公開フェーズ時で異なる値を送信すると、そのことが簡単にわかり検証を通過できません。したがって完全拘束であることがわかります。

ここではRSA仮定が成り立つことを仮定して、一方向性置換とハードコア述語を構成してみます。

RSA仮定とは、異なる素数 $p,q$ をとり、$n=pq,\,e=(p-1)(q-1)$ としたとき、ある整数 $y$ に対して $x^e\equiv y\pmod n$ をみたすような $x$ を多項式時間で求めることが難しい、という仮定です。

いま、これらの文字を用いて関数 $f$ を $f(x)= x^e\mod n$ で定めます。このとき、RSA仮定が成り立つとすれば $f(x)$ から $x$ を求めることは困難なので、 $f$ は一方向性置換です。また、 $b(x)$ を $x$ の最下位ビット、つまり $x$ が偶数ならば $0$ 、奇数ならば $1$ を出力する関数として定めます。すると、 $f(x)$ を知っても $x$ が奇数であるか偶数であるかは分からないので、 $b$ はハードコア述語となります。

したがって、RSA仮定が成り立つ場合、この $f$ や $b$ を用いた確率的暗号化関数 $E_r(m)=(f(r),b(r)\oplus m)$ を使ったコミットメント方式は、計算量秘匿かつ完全拘束です。

完全秘匿かつ計算量拘束なコミットメント方式の例

完全秘匿かつ計算量拘束なコミットメント方式は、クローフリー関数対というものを用いることで構成できることが知られています。

先にこの方式の具体的な構成例を示します。

通信の流れ

送信者は値 $m\in\{0,1\}$ を送ることを考えます。通信は以下のように進行します。

• 準備
  受信者は素数 $p$ と $\{1,\ldots,p-1\}=\{g^i\mod p\mid i=1,\ldots,p-1\}$ をみたすような $g$ をとります。また、ランダムに $z\in\{1,\ldots,p-1\}$ とります。そして $(p,g,z)$ を送信者に送信します。
• コミットフェーズ
  送信者は乱数 $r\in\{1,\ldots,p-1\}$ を選び、 $f_m(r)=z^mg^r \mod p$ を計算して $f_m(r)$ を受信者に送信します。
• 公開フェーズ
  送信者は $(m,r)$ を受信者に送信します。 受信者は $z^mg^r\mod p$ を計算し、コミットフェーズで送られてきていた $f_m(r)$ と比較して検証します。

なお、このような離散対数仮定を利用したコミットメント方式はペダーセンコミットメントとよばれています。

完全秘匿かつ計算量拘束であることの説明

まずは簡単に、クローとクローフリーと呼ばれるものついて説明します。

• クロー
  同じ値域 $D$ をもつ関数 $f_0$ と $f_1$ を考えます。$f_0$ と $f_1$ のクロー $(x,y)$ とは、 $f_0(x)=f_1(y)$ をみたす $(x,y)$ のことです。
• クローフリー、クローフリー関数対、クローフリー置換対
  $(f_0,f_1)$ のクローを求めることが（計算量的に）非常に困難な場合、関数のペア $(f_0,f_1)$ がクローフリーである、クローフリー関数対であるなどと言われます。 特に、クローフリー関数対 $(f_0,f_1)$ について、どちらの関数の定義域も値域も同じ $D$ であった場合に、 $(f_0,f_1)$ はクローフリー置換対と言われます。

クローフリー関数対が完全秘匿かつ計算量拘束な性質を持っていることを確認してみます。

• 完全秘匿性
  $f_0,f_1$ の値域は同一であり、出力される値は同じ確率分布に従うため、 $f_0$ を用いて計算された値なのか、 $f_1$ を用いて計算された値なのかは区別がつきません。したがって完全秘匿です。
• 計算量拘束性
  無制限の計算能力をもつ送信者であれば、もしコミットフェーズで送信したものが $f_0(x)$ であった場合でも、 $f_0(x)=f_1(y)$ であるような $f_1(y)$ を見つけることができます。このとき、 $f_1(y)$ を公開フェーズで送信することにより拘束性が破られることになるので、計算量拘束であるといえます。

ここでは離散対数仮定が成り立つことを仮定して、クローフリー置換対を構成してみます。

離散対数仮定とは、素数 $p$ と2整数 $g,y$ に対して、方程式 $y\equiv g^x\pmod p$ をみたすような $x$ を多項式時間で求めることが難しい、という仮定です。

いま、 $m\in\{0,1\}$ に対して、通信の流れで説明した文字 $p,g,z$ を用いて関数 $f_m$ を $f_m(x)= z^m g^x\mod p$ で定めると、 $(f_0,f_1)$ はクローフリーです。

クローが形成できるならば、 $f_0(x)\equiv f_1(y)\pmod p$ をみたすペアが求められる、すなわち $g^x\equiv zg^y\pmod p$ から $z\equiv g^{x-y}\pmod p$ をみたす $x-y$ 、つまり $(x,y)$ を求められるということを意味しますが、離散対数仮定が成り立っている場合、これは困難です。

したがって、離散対数仮定が成り立つ場合、このクローフリー置換対 $(f_0,f_1)$ を利用して構成したコミットメント方式は、完全秘匿かつ計算量拘束です。

まとめ

• コミットメント方式とは、送信者が受信者に読めない情報を送信し、後に付加的な情報を送信することで受信者に読めるようにする技術
• コミットメント方式は、コミットフェーズと公開フェーズの2つのフェーズから構成され、秘匿性と拘束性の2つの性質をもつ
• 計算量秘匿かつ完全拘束なコミットメント方式は確率的暗号化関数を用いて構成できる
• 完全秘匿かつ計算量拘束なコミットメント方式はクローフリー関数対を用いて構成できる

参考文献

[1] O. Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, 2001.

[2] H. Delfs and H. Knebel, Introduction to Cryptography: Principles and Applications , Springer, Berlin, 2002.

[3] I.B. Damgård , The Application of Claw Free Functions in Cryptography: – Unconditional Protection in Cryptographic Protocols, Ph.D. thesis, Aarhus University, 1988.