公開硬貨と秘密硬貨
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/08 03:46 UTC 版)
両者がランダム列を共有できれば（共有ランダム列プロトコル）、乱択プロトコルを作成するのは簡単である。ランダム列を共有しない場合でも（秘密ランダム列プロトコル）、小さな通信コストで乱択プロトコルを構築することが可能である。n ビットの文字列を使った共有ランダム列乱択プロトコルは、追加の O(log n) ビットの通信を行う秘密ランダム列プロトコルでシミュレート可能である。 直感的に、若干の誤りの増加を伴えば充分なランダム性を持った文字列の集合で乱択プロトコルを実行することができる。この集合は事前に両者で共有しておく。従って、アリスとボブはその集合のうち、どの文字列を使用するかに関して合意すればよい。このとき、文字列の集合は選択のための通信を効率的に行うためにも最小限でよい。形式的な証明は以下の通り。 最大エラー率 0.1 の乱択プロトコル P を考える。 R {\displaystyle R} は長さ n {\displaystyle n} の文字列が 100 n {\displaystyle 100n} 個存在する集合であり、各文字列には r 1 , r 2 , . . . , r 100 n {\displaystyle r_{1},r_{2},...,r_{100n}} と番号が振られている。 R {\displaystyle R} を使った新たなプロトコル P R ′ {\displaystyle P'_{R}} は、無作為に r i {\displaystyle r_{i}} 番の文字列を選択した上で、それを共有ランダム列として P を実行する。 r i {\displaystyle r_{i}} を選択するのに必要な通信ビット数は O(log 100n) = O(log n) である。 入力 ( x , y ) {\displaystyle (x,y)} について、 P {\displaystyle P} と P R ′ {\displaystyle P'_{R}} が正しい値を得る確率をそれぞれ p ( x , y ) {\displaystyle p(x,y)} と p R ′ ( x , y ) {\displaystyle p'_{R}(x,y)} と定義する。 ある固定の ( x , y ) {\displaystyle (x,y)} について、Hoeffdingの不等式を使うと、次のような式が得られる: Pr R [ | p R ′ ( x , y ) − p ( x , y ) | ≥ 0.1 ] ≤ 2 exp ( − 2 ( 0.1 ) 2 ⋅ 100 n ) < 2 − 2 n {\displaystyle \Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}} 従って、 ( x , y ) {\displaystyle (x,y)} を任意とした場合、次のようになる: Pr R [ ∃ ( x , y ) : | p R ′ ( x , y ) − p ( x , y ) | ≥ 0.1 ] ≤ ∑ ( x , y ) Pr R [ | p R ′ ( x , y ) − p ( x , y ) | ≥ 0.1 ] < ∑ ( x , y ) 2 − 2 n = 1 {\displaystyle \Pr _{R}[\exists (x,y):\,|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq \sum _{(x,y)}\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]<\sum _{(x,y)}2^{-2n}=1} 最後の等号は、 ( x , y ) {\displaystyle (x,y)} の組み合わせが 2 2 n {\displaystyle 2^{2n}} 個あるからである。全ての ( x , y ) {\displaystyle (x,y)} について以下が成り立つ R 0 {\displaystyle R_{0}} が存在する。 | p R 0 ′ ( x , y ) − p ( x , y ) | < 0.1 {\displaystyle |p'_{R_{0}}(x,y)-p(x,y)|<0.1} P {\displaystyle P} の最大エラー率は 0.1 であることから、 P R 0 ′ {\displaystyle P'_{R_{0}}} のエラー率は最大で 0.2 となる。
※この「公開硬貨と秘密硬貨」の解説は、「通信複雑性」の解説の一部です。
「公開硬貨と秘密硬貨」を含む「通信複雑性」の記事については、「通信複雑性」の概要を参照ください。
公開硬貨と秘密硬貨
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/12/15 06:53 UTC 版)
Babai がMAの証明系を定義した直後、シャフィ・ゴールドワッサーらは IP[f(n)] の対話型証明系を定義した論文のドラフト版を発表した。これは MA プロトコルと同様のマシン構成だが、入力長 n に対して f(n) 回のラウンドが許されていた。各ラウンドで、検証者は計算を行って証明者にメッセージを渡し、証明者も計算を行って検証者にメッセージを返す。そして全ラウンドの最後に検証者は決定しなければならない。例えば、IP[3] プロトコルなら、メッセージの並びは VPVPVPV となる。ここで、V は検証者のターン、P は証明者のターンである。 Arthur-Merlin プロトコルでは、Babai は同様のクラスを AM[f(n)] と定義した。これも f(n) 回のラウンドを許すものだが、彼はマシンに条件を1つ追加した。検証者は証明者に対して計算に使用したランダムビット列を全て提示しなければならないというものである。結果として検証者は証明者に対して何も隠せないことになる。なぜなら証明者の計算能力は無限なので、ランダムビット列さえ分かれば、検証者の計算を全てシミュレート可能だからである。ランダムビット列（硬貨投げ）が両方のマシンから見えるため、これを「公開硬貨」プロトコルと呼ぶ。一方 IP の手法を対照的に「秘密硬貨」プロトコルと呼ぶ。 公開硬貨の基本的な問題は次のようなものである。証明者が言語に属さない文字列を検証者に悪意を持って受理させようとした場合、検証者が内部状態を見せないようにするためにして証明者の計画を妨害する可能性がある。この問題があるため、IP 証明系が定義された。 1986年、ゴールドワッサーとシプサーは驚くべき結果を示した。すなわち、IP で認識できる言語は、Arthur-Merlin 公開硬貨プロトコルでも2ラウンド追加するだけで認識可能であり、結果としてほとんど差がないことがわかったのである。つまり、公開硬貨プロトコルも秘密硬貨プロトコルもほぼ同じであることが示された。実際、Babai は 1988年、任意の定数 k について AM[k] が IP[k] と比較して劣らないことを示した。
※この「公開硬貨と秘密硬貨」の解説は、「対話型証明系」の解説の一部です。
「公開硬貨と秘密硬貨」を含む「対話型証明系」の記事については、「対話型証明系」の概要を参照ください。
- 公開硬貨と秘密硬貨のページへのリンク
