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

[前回の記事](http://qiita.com/yyu/private/b4a9db1a2b2cd3dfb193)で高校生判定プロトコルと現金支払いプロトコルについて述べましたが、新しいプロトコルを考案したので公開します。これを読んで、何か分からないことや改良する方法を考えついた方はコメントなどで知らせていただけると幸いです。

# 個人情報認証プロトコル

## 登場人物

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

<dl>
  <dt>JK</dt>
  <dd>自分の<strong>年齢</strong>や<strong>性別</strong>などを公開したいが、自分の意図しない情報は公開したくない</dd>

  <dt>おっさん</dt>
  <dd>ある人間について、<strong>年齢</strong>や<strong>性別</strong>といった特定の個人情報を確定させたい</dd>
</dl>

[高校生判定プロトコル](http://qiita.com/yyu/private/b4a9db1a2b2cd3dfb193#%E9%AB%98%E6%A0%A1%E7%94%9F%E5%88%A4%E5%AE%9A%E3%83%97%E3%83%AD%E3%83%88%E3%82%B3%E3%83%AB)で書いたように、例えば`JK`が健康保険証などを用いてしまうと、名前や住所などといった`おっさん`には公開したくない情報が流出してしまいます。

## プロトコルの制約

### `JK`が公開できる個人情報

このプロトコルで公開できる個人情報には次の制約があります。

- 顔写真と住所がついた**公的身分証明書**によって確認できる情報

例えば、（僕の知る限り）血液型などといった情報は公的身分証明証では確認できないので、このプロトコルを用いて公開することはできません。

### `JK`が使用できる公的身分証明書

公的身分証明書には、学校などが発行する学生証や自治体が発行する住基カードなど様々なものがありますが、このプロトコルで使用できる公的身分証明書は次の条件があります。

- 顔写真と住所がついており、[デビットカード](http://ja.wikipedia.org/wiki/%E3%83%87%E3%83%93%E3%83%83%E3%83%88%E3%82%AB%E3%83%BC%E3%83%89)の発行に用いることができる身分証明書

つまり、学校などが発行する学生証は恐らくデビットカードの発行に用いることができないので、このプロトコルでは使うことができませんし、健康保険証は顔写真がないので同じく使うことはできません。一方で、運転免許証はこの条件を満すので使うことができます。また、デビットカードの発行に用いることができる身分証明書はデビットカード会社によって異なるので、このプロトコルで使用可能なデビットカード会社を次で定義します。
なお、この記事では以降、「公的身分証明書」という言葉を用いた場合は、暗黙の内にこの条件を満す公的身分証明書であるとします。

### デビットカード会社

このプロトコルでは、公平な第三者機関としてデビットカード会社を仮定します。デビットカード会社は次の能力があるものとします。

- デビットカードの**暗証番号**と**公的身分証明書のコピー**を郵送で受け取る
- 郵送されてきた公的身分証明書のコピーが**本当に存在する公的身分証明書**からコピーされたものかを判定する
- 公的身分証明書のコピーが実在する公的身分証明書からのコピーであった場合、郵送された書類で指定した暗証番号で口座などへアクセスできるデビットカードを公的身分証明書に記載された住所へ郵送する

ここで公平な第三者とは、`JK`と`おっさん`のどちらにも協力しないということです。`JK`と`おっさん`の両方がこの第三者を信用していると言い替えることもできます。
また、デビットカード会社によっては年齢による申し込み制限を設けているところがありますが、今回仮定するデビットカード会社はそのような制限を行っていないものとします。

## プロトコル

ここでは簡単のため、`JK`は自分の**年齢**と**性別**を公開し、その情報を`おっさん`が認証すると仮定します。また、`JK`は公的身分証明書として[住基カード](http://ja.wikipedia.org/wiki/%E4%BD%8F%E6%B0%91%E5%9F%BA%E6%9C%AC%E5%8F%B0%E5%B8%B3%E3%82%AB%E3%83%BC%E3%83%89)を使用するものとします[^id_card]。

[^id_card]: 無料あるいは少額で誰でも作成でき、顔写真と住所が記載されており、さらに性別など様々な情報があることから、このプロトコルの実行においては住基カードが最適であると思われる。なお、2016年から開始される[個人番号カード](http://ja.wikipedia.org/wiki/%E5%80%8B%E4%BA%BA%E7%95%AA%E5%8F%B7%E3%82%AB%E3%83%BC%E3%83%89)を用いてもよい。

（住基カードの見本：[http://www.city.itako.lg.jp/index.php?code=87](http://www.city.itako.lg.jp/index.php?code=87)）
> ![住基カード](https://qiita-image-store.s3.amazonaws.com/0/10815/de9c59e4-b00b-3798-5aba-8ed01199dc33.gif)

1. `JK`は公的身分証明書のコピーを作成する
2. `JK`は**公開したい情報**と**顔写真**だけが自分と同じであり、その他は全てデタラメな本物とそっくりの偽の公的身分証明書のコピーを$n$枚作成する（この例では、**誕生年**と**性別**は`JK`の公的身分証明書と同じだが、その他の情報はデタラメなものとする）
3. `JK`は**デビットカードの申し込み書類**と封筒をそれぞれ$n + 1$組入手する。
4. `JK`と`おっさん`は喫茶店などで会う（この時`JK`は（1）と（2）で作ったコピー（$n + 1$枚）と（3）で用意したデビットカードに関する書類を持参する）
5. `JK`は`おっさん`に（1）と（2）で作った$n + 1$枚のコピーを渡す（この時、コピーはシャッフルされていて、`おっさん`はどれが本物の公的身分証明書のコピーであるのか判定できない）
6. `おっさん`は`JK`に関する**知りたい情報**が$n + 1$枚のコピー全てにおいて一致しているかをチェックする（この例では**誕生年**と**性別**をチェックする。また、公的身分証明書のコピー全てに記載された顔写真と`JK`の顔が一致しているのかもチェックする。このチェックに失敗すれば、プロトコルはここで失敗となる）
7. `JK`は`おっさん`に**デビットカードの申し込み書類**$n + 1$組を渡す
8. `おっさん`は`JK`に見られないように、デビットカードの書類$n + 1$枚全てに**同じ暗証番号**を書き込み、公的身分証明書のコピーと共に封筒に入れて糊付けする（`JK`は封筒の中を見ることはできないので、`おっさん`が書いた暗証番号は分からない）
9. `JK`と`おっさん`は$n + 1$枚の封筒を全てポストへ投函する
10. デビットカード会社は届いた$n + 1$組の公的身分証明書のコピーをチェックする（このうち$n$枚は`JK`が（2）で作成した偽の公的身分証明書のコピーなので、これらは書類不備となるが、（1）で用意した本物の公的身分証明書のコピーのみは受理される）
11. デビットカード会社は`JK`の公的身分証明書のコピーに記載されている住所に対して、デビットカードを送付する
12. `JK`はデビットカードを持参して`おっさん`と**ATM**へ行く
13. `JK`はATMにデビットカードを挿入する（デビットカードの表面には`JK`の名前などが打刻されているので、それを`おっさん`に見られないようにする）
14. `JK`と`おっさん`はATMを操作して、出金など暗証番号が必要な操作を実行する
15. `おっさん`は（8）で設定した暗証番号を入力する
16. 暗証番号が正しく受理されればプロトコルは成功であり、失敗すればプロトコルは失敗となる（この時、`おっさん`は暗証番号の入力をやり直すことはできない）

このプロトコルでは確かに`おっさん`は`JK`の本当の公的身分証明書を見ることになりますが、$n$枚のダミーデータによって、それを隠蔽しています。ダミーにおいても本物においても`おっさん`が確定させたい情報は同じなので、`おっさん`にとってはどれかが本物であればよいということになります。

## マリシャスな振る舞い

`JK`や`おっさん`が行えるマリシャス（悪意ある）な振る舞いについて検証していきます。

### `おっさん`が偽の公的身分証明書コピー生成システムを`JK`に提供する

このプロトコルで`JK`がネックになるのは、ダミーの生成です。これを自動化するアプリケーションを開発するのはそれほどの技術的な困難はありませんが、自動化アプリケーションの開発者は`JK`が信頼できる人であるか、あるいはオープンソースになっていて、ソースコードを`JK`が検証したのちにコンパイルしたものでなければなりません。
なぜなら、自動ダミーデータ生成アプリケーションの開発者が`おっさん`もしくはその協力者であった場合、一見ランダムに生成されているようで、名前の文字列や誕生日などといった情報にダミーデータであることを表す情報が埋め込まれている可能性があります。例えばダミーデータ生成アプリケーションで生成されたデータは全て「誕生年と誕生月と誕生日の和を$11$で割った余りが必ず$0$になる」といった規則を持たせておけば、`おっさん`はダミーデータを判別して`JK`の公的身分証明書を突き止めることができます。

### `おっさん`がATMでの暗証番号認証失敗時に再試行を行う

`おっさん`がATMでの暗証番号認証失敗時に再試行を行うことを許可してしまうと、次の手法で`JK`の個人情報が流出する可能性があります[^retry]。

[^retry]: デビットカードには、暗証番号を何回か間違えるとカードが使えなくなるという機能があるので、この問題は気にしなくてもよいかもしれない。

1. `おっさん`は（8）で暗証番号を設定する際に、$n + 1$枚全てに別々の暗証番号を設定し、設定した暗証番号と個人情報の対応を記録する（`JK`は`おっさん`の設定する暗証番号を見てはならないので、暗証番号が全て同じになっていることを保証できない）
2. （15）で暗証番号の入力を繰り返し行い、成功した暗証番号に対応する個人情報が`JK`の本当の個人情報であると決定する

ただ、このようなマリシャスな`おっさん`を逆手に取って、`JK`は次のマリシャスな行為が可能になります。

1. `JK`は本物の公的身分証明書のコピーを用いずにこのプロトコルを実行する（`おっさん`に見せるコピーは全てダミーなので、`JK`は`おっさん`の設定した暗証番号を持つデビットカードを入手できない）
2. `JK`は適当な暗証番号を持つデビットカードを入手する
3. `おっさん`は暗証番号を最大で$n + 1$回行う（$n + 1$回の試行で、`JK`が適当に用意したデビットカードの暗証番号と偶然一致してしまう可能性がある）

このように、複数回の暗証番号入力を行うことになるとプロトコルが破綻することもありえるので、`JK`と`おっさん`の両方にとってマリシャスな振る舞いの意味をなくすために、複数回の暗証番号入力は認めないものとします。

### `JK`が他人の公的身分証明書を用いる

`JK`が他人の公的身分証明書を入手する手段について考えてみましょう。次の二つのパターンがあります。

- 他人から同意なく奪う、もしくは偶然落ちているものを拾う
- 協力者から貸してもらう

まず、前者の場合ここのプロトコルで用いる公的身分証明書は**住所**の記載が前提となっており、デビットカードはその住所へ郵送されることになっています。ですので、他人から同意なく入手した公的身分証明書を用いたとしても、郵送されるデビットカードが受け取れずにプロトコルが失敗します。
また、協力者がいて公的身分証明書を貸してもらっている場合、協力者の住所へデビットカードが郵送され、協力者を経由して`JK`へデビットカードが渡る可能性はあります。ですが、そもそもこのプロトコルで用いる公的身分証明書は**顔写真**が前提となっています。協力者の公的身分証明書に記載されている顔写真が`JK`の顔と異なるため、`JK`は次のどちらかの選択をする必要があります。

- 顔写真を偽造する
- 顔写真を偽造しない

まず、顔写真を偽造した場合、もはやそれは本物の公的身分証明書ではないということになるのでデビットカード会社によって書類不備となりデビットカードが発行されません。また、顔写真を偽造せずに用いた場合、`おっさん`が実際の`JK`と公的身分証明書のコピーの写真と比較するので、顔がとても似ている場合を除き`おっさん`に公的身分証明書が他人の物であると分ってプロトコルが失敗します。
このような理由から、このプロトコルで使える公的身分証明書は**顔写真**が必須となっています。

## 既知の脆弱性

### `おっさん`が総当たり的な身元調査を行う

このプロトコルで使用する公的身分証明書は$n + 1$枚であり、`JK`がこのプロトコルを真摯に実行していたとすれば、この中に本当の公的身分証明書があるということになります。つまり$n + 1$枚のコピー全てに書かれた情報を調査することで、いつかは`JK`の公的身分証明書に記載された個人情報に到達できてしまいます。さらに悪いことに、`おっさん`は探偵業者などを使うことで調査能力をお金で分散並列処理することができます。
この`おっさん`による総当たりについては、今のところダミーの数$n$を巨大にするしかないですが、そうすることで一回のプロトコルにおける`JK`の負担が増加してしまいます。この部分に関しては今後の課題です。