カードベース暗号はじめて体験キット

はじめに

みなさんは〈秘密計算〉という言葉を聞いたことがありますか？〈秘密計算〉とは、秘密の情報を持つ人が何人かいるときに、秘密情報を他の人にできる限り隠したまま、全員の秘密情報についての計算を行うための技術です。〈秘密計算〉は普通はコンピュータの上で実行されますが、実はカードを使って秘密計算を実行できることが知られています。カードを使った秘密計算のことを〈カードベース暗号〉と言います。〈カードベース暗号はじめて体験キット〉はカードベース暗号を手軽に体験するためキットです。このページでは〈カードベース暗号はじめて体験キット〉の使い方や、キットで体験できる〈カードベース暗号プロトコル〉の仕組みの説明を行います。

遊ぶための準備

キット内容

円盤２枚（穴7個の円盤と穴6個の円盤が1枚ずつ）
説明書３枚
カード 20枚（ハート10枚とクラブ10枚）
プラスチック部品 2セット

コマの組み立て方

プラスチック部品には、回転軸（大きい部品）とピン（小さい部品）があります。下図のように、回転軸を中央の穴に、ピンを周辺の穴に差してください。ピンは丸い方が上側です。

完成したコマを裏向きから見ると、下図のようになります。

ピンは全部で12個ありますが、穴7個の円盤にはピン6個、穴6個の円盤にはピン5個しか使わないため、ピン1個は余ります。これは予備のピンとして取っておきましょう。

①気まずくならない告白

シチュエーション

太郎さんと花子さんがお付き合いをする場面を考えましょう。普通であれば面と向かって告白をしますが、片思いであった場合は気まずいです。例えば太郎さんは〈花子さんを好き〉、花子さんは〈興味なし〉だった場合、太郎さんの前向きな気持ちが花子さんに伝わってしまいます。これでは両者ともに気まずくなり、今後の関係にも響きそうです。そこでお互いの気持ちを隠したまま、〈両思いである〉もしくは〈両思いでない〉かを決めましょう。

遊び方

解説

手順1では最初に、赤のカードを裏にして上図のように置きます。次に太郎さんと花子さんは、赤と黒のカードを裏にして置きます。このとき太郎さんは〈花子さんを好き〉である場合、太郎さんが置く赤のカードは、最初に置いた赤のカードと隣になるように置かれます。同様に花子さんも〈太郎さんを好き〉である場合、最初に置いた赤のカードと隣になるように赤のカードを置きます。このようにして置くと、〈両思いである〉ときは赤3枚が連続して置かれます。反対に〈両思いでない〉ときは、赤3枚は連続しません。
手順2ではコマを回しましょう。これによってカードの並びが巡回的にランダムにシャッフルされます。
手順3で5枚のカードをすべてめくると、〈両思いである〉か〈両思いでない〉か分かります。ここで手順1で、〈両思いである〉ときは赤3枚が連続して置かれていたことを思い出しましょう。手順2でコマを回しても、この連続関係はそのままなので、最後にカード5枚をめくれば〈両思いである〉ことが分かります。〈両思いでない〉ときは、手順2でコマを回したおかげで、太郎さんと花子さんが置いたカードは全く分からなくなります。つまり両者の気持ち（特に相手のことが好きという前向きな想い）を隠したまま、気まずくならない告白を実現できました。

②キノコ派？タケノコ派？

シチュエーション

今度は3人がチョコレートを買う場面を考えましょう。キノコやタケノコの形をしたチョコレートが目に入りました。この商品はきのこたけのこ戦争で知られるように、どちらが美味しいか論争が存在し、気を遣う問題です。もしも3人の意見が分かれてしまうと、多数派と少数派で激しい口論に発展する可能性もあります。そこで自分が〈キノコ派〉か〈タケノコ派〉かを隠したまま、3人が〈全員同じ意見である〉か〈そうではない〉かを決めましょう。〈全員同じ意見である〉場合はその商品を購入し、〈そうではない〉場合は別の美味しいチョコレートを買うことにします。

遊び方

解説

手順1で3人は、赤と黒のカードを裏にして置きます。例えばAさんは〈キノコ派〉である場合は1の場所に赤、2の場所に黒を置きます。Aさんが〈タケノコ派〉である場合は1の場所に黒、2の場所に赤を置きます。もしも3人が全員〈キノコ派〉であった場合は、1,3,5の場所に赤が置かれ、2,4,6の場所に黒が置かれます。つまり全員が〈キノコ派〉の場合、赤と黒が交互に置かれます。もしも3人が〈タケノコ派〉であった場合は逆に、1,3,5の場所に黒が置かれ、2,4,6の場所に赤が置かれます。しかしこの場合も、赤と黒が交互に置かれます。
手順2でコマを回しましょう。
手順3で6枚を全てめくり、赤と黒が交互に現れた場合は〈全員同じ意見である〉ことが分かります。赤3枚と黒3枚が連続して現れた場合は〈そうではない〉ことが分かります。手順1で3人とも派閥が同じ場合は、赤と黒が交互に置かれていたのを思い出しましょう。この関係は手順2でコマを回しても崩れないため、手順3ですべてのカードをめくることによって〈全員同じ意見である〉ことだけが分かります。〈そうではない〉場合でも、手順2でコマを回したおかげで、どのカードを誰が置いたのか全く分からなくなり、自分の派閥が漏れることはありません。

③ANDプロトコル

シチュエーション

3人以上のグループで、これから〈全員でカラオケに行くかどうか〉を決める場面を考えましょう。仲間外れを作りたくないので、全員がカラオケに行きたい場合のみ行くことにして、1人でも行きたくない人がいれば解散しようと思います。そのため、「カラオケに行きたい人は手を挙げてください」と普通に手を挙げてしまうと、もし自分だけ行きたくない場合、気まずくなる可能性があります。そこで、それぞれの人の気持ちを隠したまま、〈全員がカラオケに行く〉もしくは〈カラオケにでない〉かを決めたいと思います。

ANDプロトコル

n入力AND関数とは、n入力x1, x2, ..., xn（それぞれ0か1の値をとる）に対して、すべての入力が1なら1を出力し、そうでないなら0を出力する関数です。実は、①は2入力AND関数の秘密計算をしていました。実際、入力値の1を〈相手を好き〉、0を〈興味なし〉とし、出力値の1を〈両思いである〉、0を〈両思いでない〉とすると、二人とも〈相手を好き〉のときだけ〈両思いである〉と判定されるので、たしかにAND関数を計算していることが分かります。

残念ながら、3入力以上のAND関数の秘密計算には、①の方法は使えません。なぜなら、①の方法は2入力AND関数の結果を公開してしまうため、入力の秘密が守られないからです。そこで、入力も出力もどちらも〈伏せられたカード組〉で与えられるような2入力ANDプロトコルを考えてみましょう。もしそのようなプロトコルが作れたら、次のようにして3入力ANDプロトコルが作れます。まず、AさんとBさんは自分の入力を〈伏せられたカード組〉としてテーブルの上に置きます。次に、2入力ANDプロトコルを実行し、AさんとBさんのANDの結果を〈伏せられたカード組〉として得ます。この〈伏せられたカード組〉と、Cさんの入力を表す〈伏せられたカード組〉に対して、2入力ANDプロトコルを実行すると、3入力AND関数の値が得られます。

遊び方

解説

このプロトコルでaとbの値が漏れない、つまり安全であることを解説します。

aを表すカード2枚は、手順4でめくることになります。ここで手順3でコマを回したため、aを表すカード2枚は〈そのまま〉もしくは〈入れ替わった〉のどちらかになります。これにより手順4で現れるカードは、左から黒赤もしくは赤黒のどちらかになり、aの値に依存しません。したがってaの値は漏れないことが分かります。
bを表すカード2枚はめくらないので、bの値は漏れません。

④XORプロトコル

XORプロトコル

2入力XOR関数とは、a, b（それぞれ0か1の値をとる）を入力として受け取り、両方が同じ値なら0を、異なる値なら1を出力する関数です。これはaとbのXORの値を、a⊕bと表します。0⊕0=0、0⊕1=1、1⊕0=1、1⊕1=0なので、1⊕1=0を除けば普通の足し算と一致しています。これはビットの世界では、2を0と同一視する（mod 2を取る）ことが普通なので、これはビットの世界の足し算を表しています。

ちなみに、XORは、排他的論理和（eXclusive OR）の略称です。

XORプロトコルは、2組の〈伏せられたカード組〉を入力として受け取り、そのXORの値を表す〈伏せられたカード組〉を出力するプロトコルです。入出力のフォーマットは③のANDプロトコルと同じなので、ANDプロトコルの出力をXORプロトコルの入力として使うなど、組合せて使うこともできます。

遊び方

解説

このプロトコルでaとbの値が漏れない理由は、ANDプロトコルのときと全く同じです。

aを表すカード2枚は、手順4でめくることになります。ここで手順3でコマを回したため、aを表すカード2枚は〈そのまま〉もしくは〈入れ替わった〉のどちらかになります。これにより手順4で現れるカードは、左から黒赤もしくは赤黒のどちらかになり、aの値に依存しません。したがってaの値は漏れないことが分かります。
bを表すカード2枚はめくらないので、bの値は漏れません。

⑤COPYプロトコル

COPYプロトコル

COPYプロトコルは、1組の〈伏せられたカード組〉を入力として受け取り、その値を表す〈伏せられたカード組〉を2組出力するプロトコルです。入出力のフォーマットは③のANDプロトコルや④のXORプロトコルと同じなので、ANDプロトコルやXORプロトコルと組合せて使うこともできます。

遊び方

解説

このプロトコルでaの値が漏れない理由は、ANDプロトコルのときと同じです。

aを表すカード2枚は、手順4でめくることになります。ここで手順3でコマを回したため、aを表すカード2枚は〈そのまま〉もしくは〈入れ替わった〉のどちらかになります。これにより手順4で現れるカードは、左から黒赤もしくは赤黒のどちらかになり、aの値に依存しません。したがってaの値は漏れないことが分かります。

Page updated

Google Sites

Report abuse