JK・おっさんプロトコル Ⅲ

# はじめに

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

# 登場人物

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

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

  <dt>おっさん</dt>
  <dd>いくつかの趣味を持っており、<code>JK</code>と共通する趣味のみを<code>JK</code>へ伝えたいが、共通しない趣味については秘密にしたい</dd>
</dl>

# プロトコルの準備

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

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

```math
	\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角形カードは、材質は厚紙のような、不透明な素材でできているものとして、表裏があるものとします。そして、表が次のようになっています[^example]。

[^example]: ここでは例として、正4角形カードを用いることにしました。

![ncard.png](https://qiita-image-store.s3.amazonaws.com/0/10815/bd04b43f-ae6c-bc03-0297-d6f094f01854.png)

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

![back.png](https://qiita-image-store.s3.amazonaws.com/0/10815/1395f12a-f113-2e09-027b-fc33b2192fd0.png)

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

![3.png](https://qiita-image-store.s3.amazonaws.com/0/10815/905d2509-6b8e-550c-d376-9d2287091dd0.png)

## 回転

この正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`と`おっさん`の和集合よりも大きくなるようにする）

| 趣味 | 数字 |
|:----:|:---:|
| 読書 |  0  |
|テニス|  1  |
| 映画 |  2  |
| 卓球 |  3  |
|サッカー| 4 |
| 掃除 |  5  |
| 料理 | 6   |
| 空手 | 7   |

- この表に基づいて集合の要素を置き換える。`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$を総当たり的に試しています。