はじめに
“Yes”か“No”の二択で答えられるような質問をするとがたびたびあるが、質問者の前では本当に自分が考えている答えを言いにくい時がある。たとえば上司に「自分はよい上司か？」と問われ、もし“No”と答えたら報復人事や減給が行われたりする可能性がある。このような時に利用できるプロトコルにRRT（Randomized Response Technique）というものがある。これを利用することで、特定の個人が“Yes”か“No”のどちらを回答したのかを断定的に明らかにすることなく、一方で統計的にどちらの回答の方が多いのかを調べることができる。この文章ではRTTをトランプのようなカードを利用して行う方法について述べる。なお、この文章の内容はPrivacy-Preserving Polling using Playing Cardsを参考にしている。
この文章を読んで分からないことや改善するべきことを見つけた場合は、気軽にコメントなどで教えて欲しい。
$$
\def\card#1{\boxed{\Rule{0px}{1.5ex}{0.75ex}#1}}
\def\heartcard{\card{\color{red}{♥,}}}
\def\clubcard{\card{♣,}}
\def\commitedcard{\card{\hphantom{\Rule{2px}{0px}{0px}}?\hphantom{\Rule{6px}{0px}{0px}}}}
\def\yescards{\heartcard,\heartcard,\clubcard}
\def\nocards{\heartcard,\clubcard,\clubcard}
\def\threecommitedcards{\commitedcard,\commitedcard,\commitedcard}
\def\threeheartcards{\heartcard,\heartcard,\heartcard}
\def\threeclubcards{\clubcard,\clubcard,\clubcard}
$$
準備
このプロトコルでは2種類のカード$\heartcard$と$\clubcard$を利用する。これらのカードはどちらも裏が$\commitedcard$となっていて、裏から区別することはできない。このようなカードはたとえばトランプなどから同じスートのものを持ってくるといった方法で簡単に調達できる。
ナイーブなプロトコル
まず、回答者をアリスとし質問者をボブとする。つまりボブが“Yes”または”No”で答えられるような質問をして、アリスがそれに回答するという場合を考える。次のような方法でRRTを実行する。
- ボブがアリス“Yes”または“No”で答えられる質問をする
- アリスは次のように3枚のカードを裏向きで用意する
- “Yes”の場合、アリスは$\heartcard$を2枚、$\clubcard$を1枚を裏にしてシャッフルし$\threecommitedcards$を作る
- “No”の場合、アリスは$\heartcard$を1枚、$\clubcard$を2枚を裏にしてシャッフルし$\threecommitedcards$を作る
-
ボブは$\threecommitedcards$の中から1枚を選び、表にする。もし$\heartcard$ならば“Yes”とみなし、$\clubcard$ならば“No”とみなす
-
（2）と（3）を交互に$m$回実行する
-
“Yes”の回数が$a$回で、“No”の回数が$b$回であるとする（ただし$a + b = m$）。このとき次のような方程式を満す$y, n$を計算する
\begin{align*}
\left{
\begin{array}{l}
a = \frac{2}{3}y + \frac{1}{3}n \
b = \frac{2}{3}n + \frac{1}{3}y
\end{array}
\right.
\end{align*}
```
6. アリスがボブの質問に“Yes”である確率$P_y$と“No”である確率$P_n$は次のようになる
```math
\begin{align*}
P_y &:= \frac{y}{m} \\
P_n &:= \frac{n}{m}
\end{align*}
```
Example
このプロトコルがどのように動作するのかを実際の数字を当てはめて確かめる。たとえばボブがプロトコルの回数$m$を100として実行したとする。そして、$\heartcard$が60枚、$\clubcard$が40枚という結果であったとする。この時（5）の方程式は次のようになる。
\begin{align*}
\left\{
\begin{array}{l}
60 = \frac{2}{3}y + \frac{1}{3}n \\
40 = \frac{2}{3}n + \frac{1}{3}y
\end{array}
\right.
\end{align*}
方程式を解くと次のようになる。
y = 80 \\
n = 20
従って、アリスは80%の確率でボブの質問に“Yes”と答えていて、20%の確率で“No”と答えたと言える。
チート対策
このプロトコルにはアリスがチートを行う余地がある。アリスはプロトコルの（2）で次のように不正なカード列を作る可能性がある。
- $\threeheartcards$
- $\threeclubcards$
このようなカード列は“Yes”や“No”が$\frac{1}{3}$や$\frac{2}{3}$という前提で集計しているボブの計算に影響を与えてしまう。そこで次のような方法でアリスのチートを確率的に排除することができる。
まず、アリスは上記のプロトコル通りに回答を表すカード列を作る。ただし、回答を表すカード列とは別に_Truth Card_という1枚のカードを用意する。このTruth Cardは次のような意味を持つ。
- もしTruth Cardが$\heartcard$の場合は、回答はそのままである
- もしTruth Cardが$\clubcard$の場合は、回答の意味を反転させる
たとえば次の表のような意味になる。ただしTruth Cardと区別するため、今までのプロトコルで利用していた3枚のカード列のことを_Response Cards_と呼ぶ。
| Response Cards | Truth Card | Meaning |
|---|---|---|
| $\yescards$ | $\heartcard$ | Yes |
| $\nocards$ | $\clubcard$ | Yes |
| $\nocards$ | $\heartcard$ | No |
これを用いて次のようにプロトコルを改良する。
プロトコル
- ボブがアリス“Yes”または“No”で答えられる質問をする
- アリスは次のようにResponse Cardsを3枚とTruth Cardを1枚の合計4枚のカード列を$k$行裏向きで用意する
- “Yes”の場合、“Yes”を意味するようなResponse Cardsを3枚とTruth Cardを1枚ランダムに$k$組用意する
- たとえば$\nocards$と$\clubcard$や$\yescards$と$\heartcard$など
- この時、$k$行のカード列はどれも“Yes”を意味している必要はあるが、表現の仕方が異っていてもよい
- “No”の場合、“No”を意味するようなResponse Cardsを3枚とTruth Cardを1枚ランダムに$k$組用意する
- “Yes”の場合と同様
- ボブはランダムにアリスの$k$行あるカード列からランダムに$k - 1$行を選び、Truth Cardを除く3枚のResponse Cardsを公開する
- もし$\threeheartcards$や$\threeclubcards$がある場合、アリスが不正をしたことが明らかになる
- ボブは残った1行のカード列のうち、Response Cardsから1枚とTruth Cardを見る
- Response Cardsからの1枚が$\heartcard$かつTruth Cardが$\heartcard$の場合、“Yes”とみなす
- Response Cardsからの1枚が$\heartcard$かつTruth Cardが$\clubcard$の場合、“No”とみなす
- Response Cardsからの1枚が$\clubcard$かつTruth Cardが$\heartcard$の場合、“No”とみなす
- Response Cardsからの1枚が$\clubcard$かつTruth Cardが$\clubcard$の場合、“Yes”とみなす
このようにすることで、アリスはたしかにResponse Cardsを全て$\threeheartcards$にするなどの不正はできるが、成功する確率を$\frac{1}{k}$にすることができる。$k$を十分に大きくすればアリスの不正を防ぐことができると言ってよい。また、ボブは$k - 1$のResponse Cardsを公開するが、Truth Cardを公開しないのでアリスの回答を知ることはできない。このようにすることで、アリスの不正を防ぐことができる。
まとめ
このようにすることで、“Yes”か“No”で答えるような質問の回答をファジーにし、個人のプライバシーを守るような方法を構成できる。なお、この方法は紛失通信（Oblivious Transfer）などを利用することでコンピュータでも実行できる。
また、今回は単純のためにアリスとボブの二者間で実行したが、このプロトコルは簡単に1人の質問者とたくさんの回答者で実行することができる。これは、たとえば信頼できる匿名投票ができない場合に利用することができる。つまり匿名とされている投票から個人を特定されることを恐れて、防御として嘘の回答するといった回答者をRRTでは排除できると考えられるので、匿名投票よりも信頼できる統計が得られる可能性がある。