Oblivious Transfer(OT)と似たプロトコルOblivious Polynomial Evaluation(OPE)について解説します。1-out-of-2 OTについて説明すると、

送信者は2個のデータを送り、受信者はその中から１つだけデータを選ぶことが出来る。
送信者は受信者がどのデータを受け取ったかの情報が得られず、受信者は選ばなかったデータの情報が得られない。

という仕組みを持ったプロトコルです。一般的にはk-out-of-N OTと言います。OPEでは

送信者は体上の多項式 $P$ を知っていて、受信者はある体上の要素 $x$ を入力にその多項式Pを評価できる。
この時、送信者は $x$ の情報を得られず、受信者は多項式 $P$ の情報を得られない。

という仕組みを持っています。この記事ではこのプロトコルの実現方法について解説します。参考論文と合わせて読むとわかりやすいと思います。

OPEプロトコル
- プロトコルのアイデア
- プロトコル
OPEの安全性
- 送信者の安全性
- 受信者の安全性
まとめ
参考文献

OPEプロトコル

まずプロトコルの実現方法について説明します。その後、プロトコルの簡単に安全性の証明方法を述べます。

プロトコルのアイデア

まず、送信者は多項式 $P$ を隠すため、二変数多項式 $Q(x,y)$ を使って一変数多項式 $P(x)$ を間接的に評価するという手法を取ります。 $Q(x,y)$ は以下の条件を満たさなければなりません。

$Q(x,y)$ の $y$ の次数と $P(x)$ の次数は同じ。これを $d _ P = d _ {Q,y}$ と表す。
$Q(x,y)$ の $x$ の次数を $d _ {Q,x}$ と表す。
任意の $y$ について、 $Q(0,y) = P(y)$ 。

次に、受信者は自分の入力 $\alpha$ を隠すため一変数多項式 $S(x)$ を使います。 $S(x)$ は以下の条件を満たさなければなりません。 - $S(0)=\alpha$ である。

次数 $d_S$ は $ds=d _ p/d _ {Q,x}$ である。

さらにに $R(x)=Q(x,S(x))$ とする。 $d _ R=d _ {Q, x} + d _ p\times d _ s$ である。この送信者はこの $R(x)$ を評価することで、 $P(\alpha)$ を得ます。

つまり、 $Q(x,y)$ 空間にあるy切片 $P(y)$ を隠蔽できます。Sは $\alpha$ を直接いれるのでなく、 $S(0)=\alpha$ として $\alpha$ を隠すためにある多項式です。

プロトコル

このプロトコルの入出力は以下から成ります。

アリスの入力：体 $\mathcal{F}$ 上で次元 $d _ p$ の多項式 $P(x)$
ボブの入力：体 $\mathcal{F}$ の要素 $\alpha \in \mathcal{F}$
出力（ボブの出力）： $P(\alpha)$
セキュリティパラメータ： $m,d _ {Q,x}$ ( $d _ {Q,x}$ は $d _ p$ の整数倍)

多項式 $Ｒ$ の次数 $d _ R$ は定義より、 $d _ R = d _ {Q,x} + d _ p d _ s$ のように計算できます。実際にプロトコルの処理の流れを示します。まず、1から3の処理を $1 \leq j \leq n$ の間繰り返し、最後に4を行います。

1: ボブは $n = d _ R+1$ 個の0でない点 $x _ 1,\dots,x _ n$ を選ぶ。

2: ボブは $\mathcal{F}$ からランダムに $m-1$ 個の値 $y _ {j,1},\dots,y _ {j,m-1}$ を選び、長さmの配列 $\langle y _ {j,1},\dots,y _ {j,m-1},S(x _ j)\rangle$ を作る。配列をシャッフルして $\langle z _ {j,1},\dots,z _ {j,m} \rangle$ とし、 $x _ j$ とともにアリスに送る。

3: アリスはランダムな二変数多項式 $Q$ を選択する。以下から１つ選択するような1-out-of-m OTを1回行う。ボブは $Q(x _ j,S (x _ j))$ を選んで情報を得る。 $R(x _ j)=Q(x _ j,S (x _ j))=P(x _ j)$ であることに注意。（疑問ーここでなぜ、S(x _ j)をボブは選べるのか）

$Q(x _ j,z _ {j,1}),\dots,Q(x _ j,z _ {j,m})$

4: ボブは $n$ 個の点から $R(\cdot)$ を補間し、 $R(0)=P(\alpha)$ を計算する。

OPEの安全性

送信者の安全性

送信者はランダムな二変数多項式 $Q$ の中に $P$ を隠します。受信者は $R(x _ j)$ の $n$ 個の値を使って $Q$ を補間でき、n個の方程式を得られます。定理３により、このうちボブが多項式 $P$ の値のうち $P(\alpha)$ のみを学習できることが分かるので、 $P$ が漏洩することはありません。

定理3

多項式 $Q$ を $x$ が次数 $k$ 、 $y$ が次数 $l$ の多項式とする。そこで、多項式 $Q(x,y)$ 空間でy方向にしか値が変動しない $P$ を $P(0,y)$ として埋め込む。

$P(0,y)=\Sigma ^ l _ {j = 1} a_{0,j} y ^ j =a_{0,1} y + \dots + a_{0,l} y ^ l$

0でないような $2k+1$ 個の $x _ i$ を集めることで、 $R(x _ i)=Q(x _ i,y _ i)=Q(x _ i , )$ を $Q$ のtex:2k+1個の値を得られる。つまり、以下を満たす。

$P$ の係数 $\{a _ {0,j} | 1\leq j \leq l \}$ から一つ以上の線形関係（例えば、 $Q'(x,y)$ ）は求まらない。つまり、多項式 $P$ を得られない。
$Q$ の $2k+1$ 個の値を使って、 $Q$ と同じ次数の $Q'(x,y)$ を求められる。 $Q'(x,y)$ は方程式 $R(x _ j)=Q(x _ j,S (x _ j))=P(x _ j)$ を満たす。

一つ目の条件で安全性を保証し、二つ目の条件で $P(\alpha)$ が得られることを保証していることなります。（ちょっとここ微妙なのでしっかりと理解している人いたら教えてください..）

受信者の安全性

受信者の安全性について説明する。ここで以下の仮定を利用する。

psuedorandomness assumption

入力 $k,m,n,|F|$ における多項式時間アルゴリズムDが任意の $a\in \mathcal{F}$ について、 $A _ n ^ {k,a,m}$ がランダム選択されたことを判定するのと、 $A _ n ^ {R,m}$ がランダムに選択されたことを判定できる確率の差は、 $k,m,n,|F|$ における任意の多項式より小さい。

これはほぼ元論文のまま書いた形だが、ここの $A _ {n} ^ {R,m}$ と $A _ n^{k,\alpha,m}$ は

ボブは $\mathcal{F}$ からランダムに $m-1$ 個の値 $y _ {j,1},\dots,y _ {j,m-1}$ を選び、長さmの配列 $\langle y _ {j,1},\dots,y _ {j,m-1},S(x _ j)\rangle$ を作る。配列をシャッフルして $\langle z _ {j,1},\dots,z _ {j,m} \rangle$ とし、 $x _ j$ とともにアリスに送る。

$\langle y _ {j,1},\dots,y _ {j,m-1},S(x _ j)\rangle$ と $\langle z _ {j,1},\dots,z _ {j,m} \rangle$ のことです。(なぜなのかは参考文献の論文を参照してください) psuedorandomness assumptionを利用することで以下の二つは見分けがつかないことが分かります。つまり、受信者側にとってはランダムな並びにしか見えないので $S(0)=\alpha$ が漏洩しないことを意味します。

$A _ {n} ^ {R,m} = \left( \begin{array}{cccc} x _ 1,z _ {1,1},\dots,z _ {1,m} \\ \vdots \\ x _ n,z _ {n,1},\dots,z _ {n,m} \end{array} \right)$

$A _ n^{k,\alpha,m} = \left( \begin{array}{cccc} x _ 1,y _ {1,1},\dots,y _ {1,m-1},S(x _ j)\\ \vdots \\ x _ n,y _ {n,1},\dots,y _ {n,m-1},S(x _ n) \end{array} \right)$

まとめ

Oblivious Polynomial Evaluationの実現方法例と、その安全性について解説しました。OTを応用した面白い技術だと思います！ちなみにこの論文ではk-out-of-n OTについても説明されています。読んでみると面白いかもしれません。

間違いありましたらコメントに書いていただけると大変助かります..

参考文献

M Naor, B Pinkas "Oblivious Polynomial Evaluation" 1999

暗号勉強会

あまりコードが出てこない話

Oblivious Polynomial Evaluationについて解説！