Acompany 技術ブログ/技術ブログ記事一覧/📝コミットメントと暗号論的擬似乱数
📝

コミットメントと暗号論的擬似乱数

プロフィール
千種シャミア（ギャル）
性格：はしゃぐことが好きだがしっかりした面も持ち合わせている
趣味：バイク（原付）、カフェ巡り、ファッション
 
本山アリス（クールな変人）
性格：クールなオタク
趣味：論文を読む、Twitter廃人
 

序章

夏の蒸し暑さがまた残っている愛知県の片田舎。その通学路に、シャミアとアリスが木々の影を踏んで気だるそうに歩いている。シャミアはカバンからボトルを取り出して口元に運んだが、ボトルからは何も出なかった。シャミアが隣に歩いているアリスに目配せする。横からの視線を感じて、アリスはカラカラのボトルをシャミアに向けて振る。
「この先すぐ自販機があるからもうちょっと頑張って。」
しばらく歩くと駄菓子屋の屋根の下に自販機が見えた。自販機で天然水を買い、2人は屋根の陰に並んで立った。水を一口飲んでからアリスはこう言った。
「コインの裏表を当てましょう。シャミアが当てたらアイスを奢るよ。当たらなかったら奢って。」
いいよ。シャミアは乗り気に答えた。するとアリスは5円のコインを両手の間に挟んでシャミアの目の前に閉じた手を突っ込んだ。表だとシャミアが答えた。それを聞いたアリスは閉じた両手の上下をグッと翻して上の手を離した。裏だった。
シャミアは何か言いたそうな表情だった。
「ルールはルールだからね〜」
それを見えないかのようにアリスが言い、肘でシャミアを駄菓子屋のほうへ小突いた。

コミットメント

序章のようにコインの裏表を当てるゲームは暗号学で「コミットメント・スキーム（commitment scheme）」と呼ばれている。これからは単にコミットメントと呼ぶ。コミットメントの参加者のAliceからBobに１ビットの情報 を送ることが目的である。
コミットメントの流れを次のようにまとめることができる。
  1. プロトコルが始まる前にセキュリティ・パラメータ（メッセージのビット数など）を決める。後で述べるように、が大きければ大きいほどAliceとBobが不正をするハードルも上がる。
  1. Aliceが1ビットの を決めて、Bobとやり取りする
  1. Aliceが の値をBobに自己申告する。そしてAliceはBobとやり取りして、申告した の値が本当の の値だとBobへの説得を試みる
ここでのステップ２はコミット・フェーズ（commit phase）と呼ばれる。そしてステップ3は公開フェーズ（reveal phase）と呼ばれる。
冒頭のアリスがシャミアからコインの裏表を隠すアクションはコミット・フェーズとして捉えられる。序章のアリスはシャミアが答える前にコインの状態を知られたくないように、コミット・フェーズが終わった時にAliceはBobに の値を知られたくない。もっと詳しく述べるとBobが の値を正しく当てる確率は にすぎない。セキュリティ・パラメータ を大きくすれば、Bobの正解確率は急速に に収束する。
通常この制約は秘匿性（hiding）と呼ばれる。有限の計算能力を持つBobに対して成り立つ場合は計算量的秘匿性（computational-hiding）という。そして無限の計算能力を持つBobに対して成り立つ場合は統計的秘匿性（statistical-hiding）という。
📎
は無視可能関数を表す。正確な定義は以下のようになる。
任意の正値多項式 に対して、十分に大きな を取れば が成り立つとき、 を無視可能関数という。このような無視可能関数を一般に で表す。
が十分に大きければ、 は非常に小さくなる。
例えば、 は無視可能関数である。
冒頭のようにアリスがシャミアに「正解」を披露することは公開フェーズとして捉えられている。AliceがBobに と違う値を主張した場合に、Bobがそれを受け入れる確率は しかない。通常この制約は拘束性（binding）と呼ばれる。有限の計算能力を持つAliceに対して拘束性が成り立つ場合は計算量的拘束性（computational-binding）という。そして無限の計算能力を持つAliceに対して成り立つ場合は統計的拘束性（statistical-binding）という。残念ながら序章のアリスは文字通り手の裏を返すように正解を変えることができる。
面と向かって冒頭のゲームをやる際にはアリスの不正を簡単に検知できる。しかし、ゲーム参加者が例えば電話越しの場合にはそう簡単にはいかない。幸いなことに、暗号学では疑似乱数生成器を使ってコミットメントを実現できることが知られている[1]。

擬似乱数生成器を用いたコミットメント方式

擬似乱数生成器とは、短い乱数列をその乱数列より長い一見ランダムな乱数列に伸ばす決定的アルゴリズムである。( を参照)
を（暗号論的）擬似乱数生成器とする。Aliceは を送信することを考える。
  • コミット・フェーズ
      1. Bobは乱数 を選びAliceに送信する
      1. Aliceは乱数 を選び を計算する
      1. ならば、Aliceは をBobに送信する ならば、Aliceは をBobに送信する
  • 公開フェーズ
      1. Aliceは の値の宣言 と一緒に をBobに送信する
      1. Bobは送られた を使って を計算し、 ならば と決める。そうでなければ と決める。
コミット・フェーズの安全性解析
の時に、AliceがBobに送ったメッセージはランダムに選んだビット列に等しい。 の時に、AliceからBobに送ったメッセージは疑似乱数である。疑似乱数と乱数列の（計算的）識別不可性により、このプロトコルは計算量的秘匿性を持つ。
公開フェーズの安全性解析
Aliceが公開フェーズで と のどちらも宣言できるなら、定義から を満たすような と が存在しなければいけない。ところで、図1に示されるように の値は 通りを超えない。 の可能な値は 通りあるため、公開フェーズでとどちらも宣言できる に出会える確率はせいぜい しかない[1]。よって、無限計算能力のAliceでも の確率でしかコミットフェーズと違う の値を宣言できない。
このプロトコルは簡単だが計算量的秘匿性と統計的拘束性を実現している。
図１違うとに対してと仮定する。赤い線はの取れる値を表す。単純な観察から、以外の値は違うとの組み合わせで表せる。赤い線の本数はである。
図１違うとに対してと仮定する。赤い線はの取れる値を表す。単純な観察から、以外の値は違うとの組み合わせで表せる。赤い線の本数はである。

コミットメントの限界

統計的拘束性(resp. 秘匿性)は計算的拘束性(resp. 秘匿性)より強い。そこで、統計的拘束性と統計的秘匿性を同時に実現できるかを考えたい。しかし、これらは両立できないことが知られている。
ここで誤解を恐れずに前節のプロトコルを使って説明しよう。公開フェーズではほとんどの に対して、 と のどちらかしか宣言できない。これを統計的拘束性を持つプロトコル全てに拡大できる。厳密にいうと、コミット・フェーズのやり取り を固定した場合は の確率を除いて、 と のどちらかの主張しか より高い確率（無視できない確率）で受け入れられない。そのため、無限の計算能力を持つBobは公開フェーズのありとあらゆるやり取りに対して、 と を宣言した場合の受け入れ確率を計算できる。例えば の真の値が の場合、 の宣言のみに対して受け入れ確率が より高いやり取りが存在する。これを利用して の真の値を予測できるため、統計的秘匿性は満たされていない。
 
* AliceとBobのやり取りの長さは の多項式 に抑えられることに注意する。

まとめ

本稿はコミットメントの定義から始まり、疑似乱数を使ったコミットメントのプロトコルを紹介した。また、コミットメントの安全性の限界を紹介した。

参考文献

  1. Naor, M. (1991). Bit commitment using pseudorandomness. Journal of cryptology, 4, 151-158.
  1. M. Blum. Coin Flipping by Telephone. In CRYPTO’81, volume ECE Report 82-04, pages 11–15. 1981.
 
Xでポスト