基于Oblivious PRFs的不經意傳輸協定（OT）

Oblivious PRFs

OPRF protocol

令 F F F是定義在 ( K , X , Y ) (K,X,Y) (K,X,Y)上的帶密鑰的安全 P R F PRF PRF。協定的雙方是發送者（擁有 k k k）和接收者（擁有 x x x），協定有如下性質，

1. 接收者可以學習到 y : = F ( k , x ) y:=F(k,x) y:=F(k,x)
2. 接收者無法學習到其他點 x ′ ≠ x x'\neq x x′​=x的函數值。
3. 發送者無法學習到關于 x x x的任何資訊。

一種基于CDH的執行個體

K = Z q K=Z_q K=Zq​， G G G是生成元為 g g g的素數 q q q階循環群。令 F : K × X → Y F: K \times X \rightarrow Y F:K×X→Y是如下形式的 P R F PRF PRF，

F ( k , x ) : = H ′ ( x , H ( x ) k ) F(k,x) := H'(x,H(x)^k) F(k,x):=H′(x,H(x)k)

其中 H : X → G H:X \rightarrow G H:X→G， H ′ : X × G → Y H': X \times G \rightarrow Y H′:X×G→Y都是基于 R O M ROM ROM的Hash函數。

發送者的私鑰為 k ← R Z q k \leftarrow_R Z_q k←R​Zq​，公鑰為 u = g k ∈ G u=g^k \in G u=gk∈G。接收者要計算點 x ∈ X x \in X x∈X的函數值。協定如下：

1. 接收者選擇 ρ ← R Z q \ { 0 } \rho \leftarrow_R Z_q \backslash\{0\} ρ←R​Zq​\{0} 和 τ ← R Z q \tau \leftarrow_R Z_q τ←R​Zq​，計算 v ← H ( x ) ρ ⋅ g τ ∈ G v \leftarrow H(x)^\rho \cdot g^\tau \in G v←H(x)ρ⋅gτ∈G，發送 v v v給發送者
2. 發送者計算 w ← v k ∈ G w \leftarrow v^k \in G w←vk∈G，發送 w w w給接收者
3. 接收者計算 y ← H ′ ( x , ( w ⋅ u − τ ) 1 / ρ ) ∈ Y y \leftarrow H'(x,(w\cdot u^{-\tau})^{1/\rho}) \in Y y←H′(x,(w⋅u−τ)1/ρ)∈Y

安全性：在惡意發送者存在的情況下， τ \tau τ是均勻的導緻 v ∈ G v \in G v∈G是均勻的，上述協定是安全的。在惡意接收者存在的情況下，在one more Diffie-Hellman assumption下（敵手學習某些 ( v , w : = v α ) (v,w:=v^\alpha) (v,w:=vα)對，然後挑戰者發送一些 v v v，敵手同時正确計算出所有的 w = v α w=v^\alpha w=vα的機率可忽略），上述協定是安全的。

基于OPRF的OT協定

令 F F F是定義在 ( K p r f , [ n ] , K ) (K_{prf},[n],K) (Kprf​,[n],K)上的的 P R F PRF PRF，令 Π \Pi Π是計算 F F F的OPRF協定，再令 ( E , D ) (E,D) (E,D)是定義在 ( K , M , C ) (K,M,C) (K,M,C)上的對稱加密方案。

發送者擁有 m 1 , ⋯   , m n ∈ M m_1,\cdots,m_n \in M m1​,⋯,mn​∈M，接收者希望獲得 m i m_i mi​。OT協定的流程為：

1. 發送者選擇 k ← R K p r f k \leftarrow_R K_{prf} k←R​Kprf​，自行計算 k i ← F ( k , i ) k_i \leftarrow F(k,i) ki​←F(k,i)，然後計算 c i ← R E ( k i , m i ) c_i \leftarrow_R E(k_i,m_i) ci​←R​E(ki​,mi​)，最後發送 C : = ( c 1 , ⋯   , c n ) C:=(c_1,\cdots,c_n) C:=(c1​,⋯,cn​)給接收者
2. 接收者根據索引 i i i，利用協定 Π \Pi Π和發送者互動，計算出 k i = F ( k , i ) k_i = F(k,i) ki​=F(k,i)，最後輸出 m i ← D ( k i , c i ) m_i \leftarrow D(k_i,c_i) mi​←D(ki​,ci​)

上述協定中，發送者隻需執行 1 1 1次第一步，接收者可以執行 l l l次第二步來擷取至多 l l l個不同的消息。

安全性：在惡意發送者存在的情況下，根據OPRF協定的安全性，發送者無法學習到關于 i i i的任何資訊，上述OT協定是安全的。在惡意接收者存在的情況下，根據OPRF協定的安全性，接收者至多解密 l l l個消息（這裡 l l l是協定第二步的執行次數），上述OT協定是安全的。