擬似乱数生成器に基づくビットコミットメント方式
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/10/02 08:50 UTC 版)
「ビットコミットメント」の記事における「擬似乱数生成器に基づくビットコミットメント方式」の解説
一方向性関数から一方向性置換を得る方法は知られていないため、この章ではビットコミットメント方式を構成するのに必要な暗号論的仮定を弱める。 1991年にMoni Naorによって暗号論的擬似乱数を用いてビットコミットメント方式を構成する手法が示された。その構成法は以下の通りである。 Gをnビットの入力から3nビットの乱数を出力する擬似乱数生成器とし、Aliceがあるビットbを秘密に持つとする。 Bobはランダムに3nビットのベクトルRを選んでAliceに送る。 AliceはランダムにnビットのベクトルYを選び、3nビットのG(Y)を計算する。 もしb=1であればAliceはG(Y)をBobに送り、そうでなければ(b=0ならば)をBobに送る。 秘密を明かすにはAliceがYをBobに送れば、Bobは先ほど受け取ったのがG(Y)とのどちらだったかを確かめることができる。 この方式は情報理論的拘束性を持つ。すなわち、Aliceが無限の計算能力を持っていたとしても、2-nより高い確率で不正をすることはできない。また計算量的秘匿性も簡単な帰着によって得られる。もしBobがAliceが選んだのが0,1のどちらか当てられるとすれば、彼は擬似乱数生成器Gの出力と真の乱数とを区別できるということである。これは擬似乱数生成器の定義に矛盾する。
※この「擬似乱数生成器に基づくビットコミットメント方式」の解説は、「ビットコミットメント」の解説の一部です。
「擬似乱数生成器に基づくビットコミットメント方式」を含む「ビットコミットメント」の記事については、「ビットコミットメント」の概要を参照ください。
- 擬似乱数生成器に基づくビットコミットメント方式のページへのリンク
