LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@exfinen(_ _)

PIR

Last updated at Posted at 2020-10-04

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$の判別：

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^*$の二乗なので、

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$になる。

参考文献

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?