離散対数問題に基づいた完全秘匿かつ計算量的拘束な方式
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/10/02 08:50 UTC 版)
「ビットコミットメント」の記事における「離散対数問題に基づいた完全秘匿かつ計算量的拘束な方式」の解説
Aliceはある素数pを位数とする群とその生成元gを選ぶ。 Aliceは秘密の整数xを{0,...,p-1}からランダムに選び、c=gxを計算してcを公開する。離散対数問題より、cからxを計算することは計算量的に困難であるから、この仮定のもとではBobはxを計算できない。一方、Aliceもgx' =cなるx' <> xを計算することはできないので、完全拘束性を持つ。 しかし、離散対数問題を解くことが出来る者であれば秘密の整数xを計算できるので、この方式は完全秘匿ではない（実際、この方式は秘匿性の定義におけるゲームの観点からすれば全く秘匿性を持たない。このゲームは、IND-CPAゲームと同様に敵に2つのメッセージのうち、どちらがコミットされた値かを当てさせるゲームである。） 完全に秘匿なコミットメント方式の例は以下である。 素数位数qの群Gと群の生成元gについて合意があるものとする。アリスは秘密mを持っているとする。（mは{1,...,q-1}の要素） ボブは{1,...,q-1}からランダムにyを選び、h=gyを計算する。hをアリスに送る。 アリスは乱数rを{1,...,q-1}から選び、c=gmhrを計算する。cをボブに送る。 公開フェーズではアリスは(m,r)をボブに送る。ボブはc=gmhrかどうかを確認する。 アリスが二通りの開け方が出来るならば、(g,h)からyが求められる。また、任意のコミットメントcと秘密mに対してc=gmhrとなるrは一意に決まる。よって完全秘匿性が言える。
※この「離散対数問題に基づいた完全秘匿かつ計算量的拘束な方式」の解説は、「ビットコミットメント」の解説の一部です。
「離散対数問題に基づいた完全秘匿かつ計算量的拘束な方式」を含む「ビットコミットメント」の記事については、「ビットコミットメント」の概要を参照ください。
- 離散対数問題に基づいた完全秘匿かつ計算量的拘束な方式のページへのリンク
