隐私計算研習社
本文是 筆記分享 | 組隊學習密碼學（3）——隐私求交的關鍵路徑及其應用 的續集，本章主要介紹不經意的僞随機函數構造。
1
不經意僞随機函數(OPRF)的架構
下圖是基于不經意的僞随機函數的技術架構，OPRF允許一個參與方獲得密鑰，另一個參與方獲得密鑰下的特定值的僞随機函數，接下來我們重點來講一下OPRF的構造。
接下來我們将從以下幾個方面來引入不經意的僞随機函數。
2
基礎不經意傳輸(OT)的構造
在基礎OT協定中，Bob持有兩個消息，Alice持有一個選擇向量，Alice想要從兩個消息中選擇一個，同時Bob不知道Alice具體會選擇哪個。
我們接下來來介紹一種簡單的構造方式，Alice生成一把公私鑰對，并随機選擇一個随機數，并按照如下的順序進行放置，Bob使用Alice生成的公鑰進行加密，同時Alice僅對一個消息具有解密能力，正确性顯而易見。在該方案中，我們可以使用任意的公鑰加密算法來執行個體化該算法。
3
OT擴充(OT Extension)的構造
但是基礎OT協定都是公鑰操作，如果需要傳輸大量消息，那麼會導緻巨大的計算開銷。我們希望使用少量的公鑰操作來執行個體化大量的對稱操作，這也是OT擴充協定設計的初衷，接下來我們來介紹IKNP03的協定。
IKNP03中有兩個參與方，Bob具有選擇向量r，并對其進行擴充，得到兩個秘密分享的矩陣，具體的構造如下所示：
Alice在這個使用得到了0，1對應的密鑰，Bob獲得了其中的一個密鑰，即具有其中一個消息的解密能力。
以下是基于的DH密鑰協商協定構造不經意的僞随機函數的一個示例，但是我們會發現基于DH的算法需要很多次公鑰加密操作，實際場景中非常難使用。
接下來我們來看一下如何使用IKNP03的思路來構造OPRF，下圖是主要構造的方式，在KKRT16中發表，需要說明的一點是，q,s是Alice的僞随機函數密鑰，r是Bob對該輪的查詢。
4
PSI的性能優化方式
之前所講的所有方案都是需要對元素一個個比較，這需要平方次數的比較，接下來我們介紹一種優化方法，使得複雜度從平方次降到線性次。
Bob使用布谷鳥哈希，Alice使用普通哈希，對集合元素進行分組，這樣兩個參與方隻需要對特定的桶進行比較操作即可。
我們發現Bob每個桶裡隻有一個元素，Alice每個桶裡有若幹個元素，Bob隻需要對Alice同理的元素進行固定次比較即可，大大降低了比較次數，具體的優化請參見Benny Pinkas在2015年發表的論文。