はじめに

前回の記事では、デビットカードなどを用いて公開したい個人情報をJKとおっさんの間でやりとりするためのプロトコルを提案しました。今回はJKとおっさんの中でそれぞれの趣味を持っているとき、お互いにどんな趣味を持っているのかを秘密にしたまま共通する趣味を特定する方法を紹介します。この文章を読んで、何か質問などがあれば気軽にコメントして欲しいと思います。

登場人物

ここには次のような登場人物がいると仮定します。

JK

いくつかの趣味を持っており、おっさんと共通する趣味なら知りたいが、自分の趣味は秘密にしたい

おっさん

いくつかの趣味を持っており、JKと共通する趣味のみをJKへ伝えたいが、共通しない趣味については秘密にしたい

プロトコルの準備

ここでは、JKとおっさんの間で行われる今後のプロトコルの中で必要なものをいくつか定義します。なお、この正n角形カードのアイディアは次の文献から持ち込みました。

品川和雅, 西出隆志 “カード組を用いた秘密計算プロトコル” 筑波大学学士学位論文, 2015

    \newcommand\heartcard{\boxed{\color{red}{♥\,}}}
    \newcommand\clubcard{\boxed{♣\,}}
    \newcommand\commitedcard{\boxed{?\,}}
    \newcommand\ccwith[1]{\boxed{?_{#1}\,}}
    \newcommand\heartclub{\heartcard\clubcard}
    \newcommand\clubheart{\cluåbcard\heartcard}
    \newcommand\twocommitedcards{\commitedcard\commitedcard}

正n角形カードの導入

正n角形カードとは、手で持てるくらいの大きさで正n角形となっているカードです。正n角形カードは、材質は厚紙のような、不透明な素材でできているものとして、表裏があるものとします。そして、表が次のようになっています¹。

そして、裏は表が見えないようになっています。

この正n角形カードは、上を向いている部分によってある数値を決めます。例えば、上の例であれば$0$であり、次の例では$3$を指します。

回転

この正n角形カードは、回転させることで 時計 のような計算ができるという点が特徴です。時計では、例えば3時を指している時計の短針を$5$進めると、$3 + 5 = 8$より8時を指すようになります。ところが、11時を指している時計の短針を$5$進めると$11 + 5 = 16$ですが、16時というのは通常の時計では表現できず、4時となります。これは通常の時計が12を法とする世界で計算しているので、$11 + 5 \equiv 4 \pmod{12}$となるからです。
正n角形カードも時計とよく似た性質を持っています。例えば$0$を指す正4角形カードを$3$回左へ90°回転させると、示す値は$3$となり、これは$0 + 3 \equiv 3 \pmod{4}$となり、足し算となります。逆に右へ回転させると、今度は引き算と等しくなります。このようにして、正n角形カードでは回転を用いて値を足したり引いたりすることができます。
さらに正n角形カードの利点として、“裏向きにすると、現在示している値が分からなくなる”ということがあげられます。

加算

次のような手順で、裏になった正n角形カード$\ccwith{A}$と$\ccwith{B}$がある時、それぞれのカードの値を公開することなく$\ccwith{A + B}$を計算します。

1. $\ccwith{A}$と$\ccwith{B}$の表と表がくっつくように重ねる（ここでは上を$\ccwith{A}$、下を$\ccwith{B}$とする）
2. 重ねたカードを任意の回数右へ回転させる（この時$r$回転させたとすると、上のカードは$\ccwith{A + r}$となり、下のカードは$\ccwith{B - r}$となる。また、カードが裏になったので右回転によって加算となる）
3. 片方のカードを公開する（ここでは上のカード$\ccwith{A + r}$を公開したとする）
4. 公開していないカードを右へ $A + r$回転する（つまり、カードは$\ccwith{B - r + A + r}$となる）
5. 裏になっているカードが加算の結果となる（つまり、$B - r + A + r = B + A$）

この時$r$が分ってしまうと、公開した$A + r$から$A$が分ってしまいます。$r$は無作為に回転させるなどして、分からないようにします。

減算

裏になった正n角形カード$\ccwith{A}$と$\ccwith{B}$の減算は加算と同様に計算できます。

1. $\ccwith{A}$と$\ccwith{B}$の表と表がくっつくように重ねる（ここでは上を$\ccwith{A}$、下を$\ccwith{B}$とする）
2. 重ねたカードを任意の回数左へ回転させる（この時$r$回転させたとすると、上のカードは$\ccwith{A - r}$となり、下のカードは$\ccwith{B - r}$となる）
3. 片方のカードを公開する（ここでは上のカード$\ccwith{A - r}$を公開したとする）
4. 公開していないカードを左へ $A - r$回転する（つまり、カードは$\ccwith{B - r - (A - r)}$となる）
5. 裏になっているカードが加算の結果となる（つまり$B - r - (A - r) = B - A$）

コピー

裏になったカードをコピーする方法には次のようにします。

1. $0$を示すカードを$n$枚か用意して、重ねて裏にする
2. コピーしたいカード$\ccwith{A}$と（1）のカードで加算を行う（この時重ねたカードは重ねたまま回転させる）
3. $\ccwith{0 + A}$となって、$n$枚のカードへコピーされる

事前の準備

ここでは簡単のため、JKの趣味は$\{テニス, 映画, 料理\}$であるとして、おっさんの趣味を$\{映画, 空手\}$であるとします。まず、次のような事前の準備をします。

• JKとおっさんは下記のような趣味と数字をづける表を作成する（この表はJKとおっさんの和集合よりも大きくなるようにする）

• この表に基づいて集合の要素を置き換える。JKの趣味は$S_A = \{1, 2, 6\}$となり、おっさんの趣味は$S_B = \{2, 7\}$となる
• JKとおっさんは正n角形カードをいくつか用意する（この例では$n$角形の正$n$角形カードを用いる）

プロトコル

1. JKは次のような$PCH_i = \sum_{l = 1, l \ne i}^{|S_A|}a_l$をおっさんに知られないように計算する。ここで、$a_i$とはJKの趣味の$i$番目の集合の要素とする（たとえば$PCH_1$は$1$番目の要素である$1$以外を全て足した和なので、$\sum_{l = 1, l \ne 1}^{|S_A|}a_i = 2 + 6 = 8$となる）
2. JKは趣味の全ての和$PCH = \sum_{i = 1}^{|S_A|}a_i$を計算して、$PCH$を正$n$角形カードで表し、カードを裏にする（このカードを$\ccwith{PCH}$と表記する）
3. JKは$\ccwith{PCH}$を裏のままおっさんへ渡す
4. おっさんは$\ccwith{PCH}$を$|S_B|$枚コピーする（この時コピーした$i$枚目のカードを$\ccwith{PCH}_i$とする）
5. おっさんはJKに知られないように$b_j$を正$n$角形カードで表しカードを裏にする（$b_j$はおっさんの$j$番目の趣味の数字を表し、たとえば$b_1$は$2$となる。また、これらの裏になったカードを$\ccwith{b_j}$とする）
6. おっさんは$\ccwith{PCH}_i-\ccwith{b_j}$を裏のまま計算する（これの結果を$\ccwith{PCH - b_j}_i$とする）
7. おっさんは$\ccwith{PCH - b_j}_i$をJKへ送信する
8. JKは$PCH_i$をおっさんに知られないように正$n$角形カードで表し裏にする（これを$\ccwith{PCH_i}$とする）
9. JKは$\ccwith{PCH - b_j}_i - \ccwith{PCH_i}$を裏のまま計算し、その後カードを表にする。もしカードが$0$になっていたらJKの$i$番目の趣味がおっさんの趣味でもあるということを指す

アイディア

上記のプロトコルは大変複雑ですが、アイディアは比較的簡単です。このプロトコルのアイディアはJKの趣味の和からおっさんの趣味の要素の数字を引いて、それがJKの趣味からちょうどひとつの要素が減った集合になっているのかを調査するというものです。計算中の数字がJKやおっさんの間で互いに明らかになるとまずいので、計算は全部裏になった正n角形カードを利用しています。プロトコルで示した$PCH$がJKの趣味の和であり、$b_j$がおっさんの趣味です。$PCH - b_j = PCH_i$（つまり$PCH - b_j - PCH_i = 0$）ならばJKの$i$番目の趣味とおっさんの$j$番目の趣味が一致したということになります。今回のプロトコルでは、この$i$と$j$を総当たり的に試しています。