暗号・パズル・ゲーム研究室

気まずくならない告白

アリスとボブは友達です。友達としてはお互いに好意を持っていますが、異性としてお互いにどう思っているのかは知りません。もし直接告白してしまうと、片想いだった場合に友達関係が解消されてしまうリスクがあります。なるべく気まずくならないように、両想いかどうかを知ることはできないでしょうか？

もし両想いなら二人ともハッピーです。もしお互いに「異性としては興味なし」ならば、友達関係は継続しますし、お互いの足並みが揃っているので、この場合も二人ともハッピーです。気まずくなるのは片想いのときです。「両想いかどうか」だけを知ることができて、「両想いではない」と判定された場合も「お互いに興味なし」と「どちらかの片想い」の二つの状態が区別できないような仕組みがあったら、気まずくならない告白ができたことになりそうです。

好きを1、興味なしを0とみなすと、「両想いかどうか」は「二人の入力の掛け算」で表せます。実際、両想いのときは1×1=1ですし、それ以外のときは1×0=0×1=0×0=0ですので、「掛け算の結果が1のときは両想い、0のときは両想いでない」とみなせます。

0と1の計算は、偽（false）と真（true）の論理演算とみなせるので、上の計算は論理積（logical AND）と呼ばれています。そして、入力をできるだけ隠したまま論理積を出力する方式（プロトコル）をANDプロトコルと呼びます。ここでは、5枚のカードを用いるANDプロトコル（通称ファイブカードトリック）を紹介します。ぜひ遊んでみてください。

キノコ派？タケノコ派？

アリスとボブとキャロルはお互いのことをまだあまり知りません。いま世間では共和党と民主党の話でもちきりです。もし三人とも同じ政党を支持していたら、政治の話で盛り上がれそうです。異なる政党を支持している場合、政治の話はしない方が無難です。このように、２択の質問に対して、三人が同じ意見を持っているかどうかだけを確かめる方法はないでしょうか？

共和党と民主党だとセンシティブすぎるので、ここからはキノコ派とタケノコ派で考えてみましょう。こちらも古くからの論争テーマで、三人とも同じ派閥ならば例のお菓子を買いに行けますが、そうでないなら例のお菓子は買いに行けません。

このような計算を3入力等号判定関数と呼び、これを計算する方式を3入力等号判定プロトコルと呼びます。ここでは、6枚のカードを用いる3入力等号判定プロトコル（通称シックスカードトリック）を紹介します。ぜひ遊んでみてください。

3人いるけどオセロで遊ぶ？

アリスとボブとキャロルはお互いのことをとても気遣う性格です。いまここにオセロが一式あったとします。「3人のうちオセロで遊びたい人数」は0人か1人か2人か3人のいずれかですが、もし0人ならオセロで遊ばないだけですし、もし2人ならちょうどオセロ1台で遊べます。しかし、遊びたい人数が1人または3人のときは、お互いに気を遣いあって、気まずくなる可能性があります。遊びたい人数が「0人または2人である」ということだけを確かめる方法はないでしょうか？

このような計算を3入力排他的論理和（XOR: exclusive OR）関数と呼び、これを計算する方式を3入力XORプロトコルと呼びます。3入力XOR関数は0か1かを表す入力a,b,cを受け取り、a+b+cが奇数ならば1、偶数ならば0を出力します。上の例の場合、遊びたい人は1、遊びたくない人は0を入力して、出力結果が1（遊びたい人数が1人または3人）ならオセロでは遊ばないことにすれば良いでしょう。ここでは、8枚のカードを用いる3入力XORプロトコルを紹介します。ぜひ試してみてください。