PSIとPSU、そしてactiveな敵に対して安全なプロトコルについて簡単に調べたのでメモを残しておきます。以下の論文はgoogle scholarで出ます。

Extending Oblivious Transfers Efficiently(2003)

Y Ishai, J Kilian, K Nissim ,E Petrankの研究。

概要この研究では1回のOTが安全なら複数回のOTが安全であることを証明しています。

より形式的には $k ^ c$ OTを $k$ OTに帰着します。 $k$ が安全なら、それをブラックボックス的に用いた $k ^ c$ も安全であるという事実を示しています。

まず、一方向性関数が存在すれば、疑似ランダム関数が存在するということが知られています。しかし、一方向性関数からOTへの帰着は困難です。しかし、Beaverの定理によれば一方向性関数と小さなOTが存在すれば、大きなOTが存在すること（拡張の存在）が分かりました。

この研究でやられたことは主に

一方向性関数から疑似ランダム関数を構成し、ランダムオラクルモデルにおけるOTを効率的に拡張するプロトコルを提案。
Correlational robustnessという性質を定義した。疑似ランダム性のような性質で、疑似ランダム関数族を得るのに使える。

です。

Efficient Private Matching and Set Intersection(2004)

M J. Freedman,K Nissim, B PinkasnによるPSIの概念や他の応用方法(PSI-CAやマルチパーティ型PSI)が提案された研究です。

Private Set IntersectionまたはPrivate Set Unionとはサーバーとクライアントの持つ各々の集合について共通集合または和集合を計算し、その結果をクライアントが得る。サーバーは何も得られないというプロトコルです。データベース上の計算において集合演算は幅広く活用されています。もともとはTTPを用いた方法や安全性のない平文でのやりとりが行われていましたが、PSIはそれを解決しています。

この論文でPSIは

Oblivious Polynomial Evaluation (OPE,1999)
paillier暗号などの加法準同型性を持つ暗号

を用いて与えられました。

Privacy Preserving Set Operations(2005)

L Kissner , D Song の研究。

和集合、共通集合、element reduction(要調査)に対するマルチパーティ計算プロトコルを提案しました。PPT-bounded adversaryモデルにおいても、passiveとactiveに対する安全性が保証されます。ここで提案されたプロトコルは、のちにMPSIやMPSUと呼ばれています。

Keyword Search and Oblivious Pseudorandom Functions(2005)

M J. Freedman, Y Ishai, B Pinkas, O Reingoldの研究。OPRFとはOPEの鍵付き疑似ランダム関数版のことです。

送信者は鍵 $k$ を入力し、受信者は $x$ を入力する。
受信者は $f _ k(x)$ を得られる。送信者の鍵 $k$ の情報も受信者の入力 $x$ の値も漏れない。

OTやOPE同様にPSIに利用されます。

Honest-Verifier Private Disjointness Testing without Random Oracles (2006)

Susan Hohenberger Stephen A. Weisの研究。

PSI-CAを初めて正式に定義しました。 PSI－CAとは共通集合や部分集合の要素集合ではなく、その大きさ（つまり濃度）しか学習しないプロトコルです。つまり、サーバーが集合 $S$ 、クライアントが集合 $C$ を入力したとき、 $|S \cap C|$ を出力します。実装は困難であり、PSIやPSUでは情報量が多すぎるような場合に利用するPSIのより発展的な研究です。計算量が[tex:O(n²)]です。

Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection(2009)

Stanisław Jarecki and Xiaomin Liuの研究です。プロトコルにOPRFを用いて、通信ラウンド数が一定かつコミット型という特徴を持ちます。

Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model(2010）

E D Cristofaro, J Kim, G Tsudikの研究。ここで初めてAPSI(Authorized Private Set Intersection)が定義されました。DDH仮定のもと、ランダムオラクルモデルで安全性が証明されます。CRSモデルを使わず、計算複雑性と通信複雑度が線形である初めての研究です。

ディジタル署名での認証とPSIの合わせ技で、PPIT(Privacy Policy based Information Transfer)と関連している。PPITとはクライアントが取得権限を持っている情報しか得られないプロトコルです。APSIは、共通集合のうちユーザーが権限を持っている情報しか得られません。

Semi-homomorphic Encryption and Multiparty Computation(2011)

R Bendlin, I Damg˚ard, C Orlandi,S Zakariasの研究です。BDOZとも呼ばれています。加法準同型性を活用して、効率的にactiveな敵に対して安全なマルチパーティ計算プロトコルを提案しました。このプロトコルのプリプロセスの考え方はSPDZに活用されています。

Fast and Private Computation of Cardinality of Set Intersection and Union(2012)

E D Cristofaro,P Gasti,G Tsudikの研究。初めて線形時間で動作するPSI-CAとPSU-CAのプロトコルを実現しました。

Phasing: Private set intersection using permutation-based hashing(2015)

M Zohner,G Segev,T Schneider,B Pinkasの研究。 Permutation based-hashingを活用し、この2015年時点で最速のPSIを実現しました。

MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer (2016)

M Keller, E Orsiniの研究。activeな敵に対して安全かつ高速なマルチパーティ計算プロトコルです。オンラインフェーズはSPDZのものと全く同じですが、プリプロセスにおけるトリプルの生成が高速化されています。

この研究より前にFredriskenは、SPDZのプリプロセスにおけるトリプルの生成を二元体上で高速化しました。MASCOTでは任意の大きな有限体において、OTを使用したプリプロセスの実行を可能にしました。トリプルの生成には２つのk-bitの積を計算するgilboaの提案したプロトコルを利用します。