PIR

# PIRとは
Private Information Retrievalの頭字語で、取得したいデーターをデーターベース側にはっきりと伝えずにクエリをする方法

# 2種類のPIR
## Information-theoretic PIR (IT-PIR)
クエリ先がお互いに共謀しないことが前提の、攻撃者の計算リソースに依存しないで、クエリのプライバシーを守る方法

### 2サーバーのIT-PIR

#### 前提
- データーベース$x$は、長さ$N$のビットベクター
- サーバー1とサーバー2が、同じ内容のデーターベース$x$を持つ

#### 具体例を含めた手順
$N=5$
$x=[0,1,1,0,1]$
$\oplus=XOR$

1. ランダムに$x$の1-basedのインデックスの集合$S$を作る。これがクエリ。
    e.g. $S=[1,3,5]$

2. ユーザーがインデックス$i$をデーターベースにクエリする。サーバー1には、$S$をそのまま送る。サーバー2には$S$に$i$が含まれていればSから$i$を除いたもの、$i$が含まれていなければ、$S$に$i$を足したものを送る。

    e.g. $i=3$ならば、サーバー1には$[1,3,5]$、サーバー2には$[1,5]$を送る。

3. サーバー1,2は、受け取ったインデックスのビットを$x$から取り出して、$XOR$したものをユーザーに返す。
    e.g. 
    サーバー1: $x[1] \oplus x[3] \oplus x[5] = 0 \oplus 1 \oplus 1 = 1 \oplus 1 = 0$
    サーバー2: $x[1] \oplus x[5] = 0 \oplus 1 = 1$

4. サーバー1,2が返したビットをXORしたものを、クエリ結果とする
    例 $X[3] = 0 \oplus 1 = 1$

#### サーバー1の結果 XOR サーバー2の結果が、正しいクエリ結果になる理由
ビットベクター全体をXORすると、ベクター内の$1$の数が奇数の場合に$1$、偶数の場合に$0$が結果になる。以下、$S$に$i$が含まれる場合と、含まれないケースで考える。$a$はサーバー1、$b$はサーバー2。

- $S$に$i$が含まれない場合

    $a = S$
    $b = S \cup i$（手順2）
    $a \oplus b = S \oplus (S \cup i) = i$（$S$中の1の数の2倍は偶数なので0）

- $S$に$i$が含まれる場合

    $a = S \setminus i$
    $b = S \setminus i \cup i$（手順2）
    $a \oplus b = (S \setminus i) \oplus (S \setminus i \cup i) = i$（$S \setminus i$中の1の数の2倍は偶数なので0）

##### 注意点
* このやり方は、クエリの戻り値は１ビットになるものの、クエリ事態ががDBの長さと同じNビットなので、最悪の方法であるDB全体を手元にコピーすることとコストは同じ。

* クエリの長さがNになるのは、クエリをビットのベクターで表すと長さがNになるため。例えば、$N=5, S=[1,3,5]$であれば$S=[1,0,1,0,1]$になる。

## Computational PIR (CPIR)
解くことが難しい数学的な問題を使って、クエリのプライバシーを守る方法。

### Quaratic Residuosity問題を利用したCPIR
#### 前提
- $M$は、$s$行 x $t$列で、各要素がビットのMatrix
- DBサーバーは1つ

|記号|定義|
|---|----|
|$Z^*_N$ | $ \\{ x \mid 1 \le x \le N, GCD(N, x) = 1 \\} $|
|$y$が$QR$| $ \exists\, w ∈ Z^* s.t. w^2 = y \pmod N $|
|$y$が$QNR$| $y$が$QR$でない|
|$(\frac{y}{N})$| ヤコビ記号で、$(\frac{y}{N})=1$を満たす数は、半分$QR$で、半分$QNR$になる。$(\frac{y}{N})=-1$なら全て$QNR$。ヤコビ記号は、$y$が$QR$で$N$で割り切れない場合に$1$, $y$が$QNR$なら$-1$、$y$が$N$で割り切れる場合に$0$になる。|
|$Z^{+1}_N$| $ \\{y\;\in\;Z^*_N \mid (\frac{y}{N})=1 \\}$|

##### QNRの性質
$x$が$QR$の場合、$Q_N(x) = 0$
$x$が$QNR$の場合、$Q_N(x) = 1$
として、
$Q_N(xy)=Q_N(x) \oplus Q_N(y)$

$x$と$y$のどちらかが$QNR$のときだけ、$xy$は$QNR$になる。

#### 目的
($a$行, $b$列)の要素を、DBからDBに$a$と$b$について知られずに取得する

#### 手順
1. $N=p_1 \cdot p_2$を計算。$p_1,p_2$は素数。
2. DBに$N$を送る（$p1$, $p2$は送らない）。
3. $y_1,..,y_t$の、$t$個の数を、以下を満たす形で$Z^{+1}_N$ から選ぶ。
   - $1 \leq b \leq t$を選び、$y_b$を$QNR$、それ以外を$QR$にする。
4. $y_1,..,y_t$をDBに送る。
5. DBが、全ての行$r$と、$j=1$〜$t$について、$Z_r$を以下の形で計算する。
$$
Z_r = \displaystyle \prod_{j=1}^t \omega_{r,j}
$$
   - $M_{r,j} = 0$の場合、$\omega_{r,j} = y_j^2$ 
   - $M_{r,j} = 1$の場合、$\omega_{r,j} = y_j$

    注意点
    - $M_r,j$は、DBの$r$行$j$列
    - $j \ne b$の場合は、$QR = QR \cdot QR$なので、$\omega_{r,j}$は常に$QR$になる。
    - $j = b$の場合は、$y_j$は$QNR$なので、$M_{r,j} = 1$の場合は、$\omega_{r,j} = y_j = QNR$、$M_{r,j} = 0$の場合は、$\omega_{r,j} = y_j^2 = QNR \cdot QNR = QR$になる。
  
6. DBが $Z_1,...,Z_s$をユーザーに返す
7. $Z_1,...,Z_s$から、$Z_a$（クエリ対象の要素が含まれる$a$行）を取り出す。
8. $Z_a$が$QR$であれば、$M_{a,b}=0$。$QNR$であれば$M_{a,b}=1$
    $QR$、$QNR$の判別：

    ```math
Z^*_N=\{ x \mid 1 \leq x < N, GCD(N, x) = 1 \} \\\
q \in Z^*_N \\\
    ```

    として、$q \equiv x^2 \pmod N$ は、$q^{(n-1)/2} \pmod N$が、$1$なら解が存在。$-1$なら存在しない。
    $N=p_1 \cdot p_2$で、$p_1$, $p_2$は素数なので、それぞれについて判別式をつかって解があるかを調べる。そのどちらか一方だけに解があれば$Z_a$は$QNR$。そうでなければ$QR$。$p_1$, $p_2$を知らない場合は、この方法は使えないため、プライバシーが守られる。

#### ZaがQRであれば結果0、QNRなら結果が1となる理由
上記の3で設定した条件から、例えば$t=3$, $b=2$として、$\omega_{1,2,3}$ を$QR/QNR$で表すと、$\omega_2$以外は$QR$なので、

- $\omega_2$が$QR$の場合（$M_{r,j} = 0$の場合）は、
$QR, QR, QR$

- $\omega_2$が$QNR$の場合（$M_{r,j} = 1$の場合）は、
$QR, QNR, QR$

になる。$\omega_2$が$QR$で$\omega_{1,2,3}$の全てが$QR$になる場合は、$QR$は$x \in Z^*$の二乗なので、

```math
Z_a = y_1 \cdot y_2 \cdot y_3 \\\
= x_1^2 \cdot x_2^2 \cdot x_3^2 \\\ 
= (x_1 \cdot x_2 \cdot x_3) \cdot (x_1 \cdot x_2 \cdot x_3)
```

$x_1, x_2, x_3$は$N$と互いに素で、それらを掛け合わせた$x_1 \cdot x_2 \cdot x_3$も$N$と互いに素になるので、$x_1 \cdot x_2 \cdot x_3 \in Z_N^*$、$Z_a$は$QR$になる。$\omega_2$が$QR$だと、$M_{r,j} = 0$になるので、$Z_a$が$QR$のとき、$M_{r,j} = 0$。
$QR$への変換は法$N$なので、$(x_1 \cdot x_2 \cdot x_3) \cdot (x_1 \cdot x_2 \cdot x_3)$は$N$未満の数になる。

$\omega_2$が$QNR$（$M_{r,j} = 1$）の場合は、上が成り立たず、$Z_a$は$QNR$になる。

### 参考文献
- PIR Wiki: https://en.wikipedia.org/wiki/Private_information_retrieval
- Private Information Retrieval (PIRの元祖の論文):　Single Database, Computationally-Private Information Retrieval
- Single Database, Computationally-Private Information Retrieval (CPIRの実例の参照先):  X
- https://web.cs.ucla.edu/~rafail/PUBLIC/34.pdf
- Probabilistic encryption (Quadratic Reduosity問題の詳細):
 https://www.sciencedirect.com/science/article/pii/0022000084900709
- Quadratic Residuosity問題 Wiki https://en.wikipedia.org/wiki/Quadratic_residuosity_problem