Efficient Batched Oblivious Transfer Protocol

参考文献：

1. Beaver, D. 1996. “Correlated Pseudorandomness and the Complexity of Private Computations”. In: 28th Annual ACM Symposium on Theory of Computing. ACM Press. 479–488.
2. Ishai, Y., J. Kilian, K. Nissim, and E. Petrank. 2003. “Extending Oblivious Transfers Efficiently”. In: Advances in Cryptology – CRYPTO 2003. Ed. by D. Boneh. Vol. 2729. Lecture Notes in Computer Science. Springer, Heidelberg. 145–161.
3. Kolesnikov, V. and R. Kumaresan. 2013. “Improved OT Extension for Transferring Short Secrets”. In: Advances in Cryptology – CRYPTO 2013, Part II. Ed. by R. Canetti and J. A. Garay. Vol. 8043. Lecture Notes in Computer Science. Springer, Heidelberg. 54–70. doi: 10.1007/978-3-642-40084-1_4.
4. Kolesnikov, V., R. Kumaresan, M. Rosulek, and N. Trieu. 2016. “Efficient Batched Oblivious PRF with Applications to Private Set Intersection”. In: ACM CCS 16: 23rd Conference on Computer and Communications Security. Ed. by E. R. Weippl, S. Katzenbeisser, C. Kruegel, A. C. Myers, and S. Halevi. ACM Press. 818–829.

Public Key-Based OT

可以基于公钥加密，来构造不经意传输协议。构造如下：

在描述 多方协议 之前，先定义两种安全参数：

1. 计算安全参数（computational security parameter）：记为$\kappa$，约束敌手离线计算（如攻击某个加密方案）的困难程度，一般选取$128,256$
2. 统计安全参数（ statistical security parameter）：记为$\sigma$，约束敌手在线交互时偏离协议（而不被发现）的概率，一般选取$40,80$

Beaver’s non-black-box construction（1996）

在混淆电路的计算中，假设Bob的输入为$m$比特，那么就需要与Alice利用$m$次OT协议来获得对应的标签和选择比特。往往$m$是多项式长度的，因此需要对应次数的公钥加密，然而公钥加密的开销巨大。我们希望利用较少次数的OT，就可以达成多项式次OT的效果。

Beaver给出了一种方案：

1. 发送方$S$，接收方$R$，功能$F$；$S$的输入为$X=\{(x_1^0,x_1^1),\cdots ,(x_m^0,x_m^1)\}$，$R$的输入为$b=(b_1,\cdots ,b_m)$，$F$的作用是实现OT。令 G : { 0 , 1 } κ → { 0 , 1 } m G:\{0,1\}^\kappa \to \{0,1\}^m G:{0,1}κ→{0,1}m是 PRG。
2. $R$生成$\kappa$比特的随机数$r$，计算$b^{\prime }=b\oplus G(r)$发送给$S$
3. $S$发送$X,b^{\prime }$给$F$，$R$发送$r$给$F$
4. $F$解密$b=b^{\prime }\oplus G(r)$，然后发送对应的$x_i^{b_i}$给$R$

在 ideal world 里，$F$是可信第三方。在 real world 里，可以通过混淆电路来实现它：$S$构建$F$对应的 GC 发送给$R$，$S$的输入为$X,b^{\prime }$（不需要OT），$R$的输入仅仅为$r$（需要$\kappa$次OT），$R$计算电路获得$x_i^{b_i}$（实现了$m$次OT）。

也就是说，只需要$\kappa$次公钥操作，就存在一种方案来成批地实现$m=poly(\kappa )$次OT协议。

IKNP（2003）

然而，Beaver的构造更多是理论意义上的，因为$F$对应的 GC 过大，实际上计算很低效。 Ishai 等人在 OT 的基础上仅仅添加了对称操作（ symmetric-key operations），利用$k$次 base-OT，达成了$m\gg k$次的高效 OT：

1. $R$的选择比特串（choice bits）为 r ∈ { 0 , 1 } m r \in \{0,1\}^m r∈{0,1}m，$S$的选择比特串为 s ∈ { 0 , 1 } k s \in \{0,1\}^k s∈{0,1}k，且$m\gg k$

2. $R$随机选择两个矩阵$T,U\in {\mathbb{F}}_2^{m\times k}$，满足
   $$T=\left[\begin{array}{c}{t}_1\\ t_2\\ ⋮\\ t_m\end{array}\right],U=\left[\begin{array}{c}{u}_1\\ u_2\\ ⋮\\ u_m\end{array}\right],T\oplus U=\left[\begin{array}{c}{r}_1\cdot 1^k\\ r_2\cdot 1^k\\ ⋮\\ r_m\cdot 1^k\end{array}\right]$$
   这里的$\cdot$是向量数乘， t i , u i ∈ { 0 , 1 } k t_i,u_i \in \{0,1\}^k ti​,ui​∈{0,1}k是行向量（下角标代表行向量，上角标代表列向量）。换个方向看，就是
   $$U=T+\underset{k}{\underbrace{\left[rr\cdots r\right]}}$$

3. $S$根据$s$，和$R$一起执行$k$次OT协议，挑选列向量：如果$s_i=0$，那么获得$T$的第$i$列 t i ∈ { 0 , 1 } m t^i \in \{0,1\}^m ti∈{0,1}m；否则，获得$U$的第$i$列 u i ∈ { 0 , 1 } m u^i \in \{0,1\}^m ui∈{0,1}m；将获得的向量排成矩阵$Q\in {\mathbb{F}}_2^{m\times k}$，
   $$Q=\left[\begin{array}{cccc}{t}^1\oplus (s_1\cdot r)& t^2\oplus (s_2\cdot r)& \cdots & t^k\oplus (s_k\cdot r)\end{array}\right]$$
   换个方向看，
   $$Q=\left[\begin{array}{c}{t}_1\oplus (r_1\cdot s)\\ t_2\oplus (r_2\cdot s)\\ ⋮\\ t_m\oplus (r_m\cdot s)\end{array}\right]$$
   这里，$q_i=t_i$或者$q_i\oplus s=t_i$，取决于$r_i$

4. 令 H : { 0 , 1 } k → { 0 , 1 } n H:\{0,1\}^k \to \{0,1\}^n H:{0,1}k→{0,1}n是ROM，给定$m$对秘密 x i 0 , x i 1 ∈ { 0 , 1 } n x_i^0,x_i^1 \in \{0,1\}^n xi0​,xi1​∈{0,1}n，$S$分别加密两者：
   $$\begin{gathered} c_i^0=x_i^0\oplus H(q_i) \\ {c}_i^1=x_i^1\oplus H(q_j\oplus s) \end{gathered}$$
   将这$2m$个密文发送给$R$

5. $R$手里有$t_i$和$r$，但不知道$s$，因此只能计算出$H(t_i)$，在每一对密文中就只能解密其中一个密文。确切地说是$c_i^{r_i}$：当$r_i=0$，那么$q_i=t_i$，可以解密$c_i^0$得到$x_i^0$；当$r_i=1$，那么$q_i=t_i\oplus s$，可以解密$c_i^1$得到$x_i^1$

在上述协议中，只有 step 3 使用了$k$次 base-OT 协议，在 step 5 中实际完成了$m$次 $1$-out-of-$2$ OT 协议。

一般地，选取$k=\kappa$

KK（2013）

Kolesnikov 和 Kumaresan 指出，INKP本质上使用了一个编码方案，$k$重复码（repetition code）：将信息 r i ∈ { 0 , 1 } r_i \in \{0,1\} ri​∈{0,1}编码为$encode(r_i)=r_i\cdot 1^k$

如果我们使用长度为$k$的$l$维线性纠错码$C$，那么就可以构造出 $1$-out-of-$2^l$ OT协议：

1. $R$的选择比特串（choice bits）为矩阵 r ∈ { 0 , 1 } m × l r \in \{0,1\}^{m \times l} r∈{0,1}m×l，$S$的选择比特串为 s ∈ { 0 , 1 } k s \in \{0,1\}^k s∈{0,1}k，且$m\gg k$

2. $R$随机选择两个矩阵$T,U\in {\mathbb{F}}_2^{m\times k}$，满足
   $$T=\left[\begin{array}{c}{t}_1\\ t_2\\ ⋮\\ t_m\end{array}\right],U=\left[\begin{array}{c}{u}_1\\ u_2\\ ⋮\\ u_m\end{array}\right],T\oplus U=\left[\begin{array}{c}C(r_1)\\ C(r_2)\\ ⋮\\ C(r_m)\end{array}\right]=C(r)$$

   其中 t i , u i ∈ { 0 , 1 } k t_i,u_i \in \{0,1\}^k ti​,ui​∈{0,1}k是行向量。简记$C(r)=V$，那么换个方向，
   $$U=T+\left[V^1{V}^2\cdots V^k\right]$$

3. $S$根据$s$，和$R$一起执行$k$次OT协议，挑选列向量：如果$s_i=0$，那么获得$T$的第$i$列 t i ∈ { 0 , 1 } m t^i \in \{0,1\}^m ti∈{0,1}m；否则，获得$U$的第$i$列 u i ∈ { 0 , 1 } m u^i \in \{0,1\}^m ui∈{0,1}m；将获得的向量排成矩阵$Q\in {\mathbb{F}}_2^{m\times k}$，
   $$Q=\left[\begin{array}{cccc}{t}^1\oplus (s_1\cdot V^1)& t^2\oplus (s_2\cdot V^2)& \cdots & t^k\oplus (s_k\cdot V^k)\end{array}\right]$$
   这里的$\cdot$是向量数乘。换个方向看，
   $$Q=\left[\begin{array}{c}{t}_1\oplus (V_1\wedge s)\\ t_2\oplus (V_2\wedge s)\\ ⋮\\ t_m\oplus (V_m\wedge s)\end{array}\right]=\left[\begin{array}{c}{t}_1\oplus (C(r_1)\wedge s)\\ t_2\oplus (C(r_2)\wedge s)\\ ⋮\\ t_m\oplus (C(r_m)\wedge s)\end{array}\right]$$
   这里的$\wedge$是按位与（bitwise-AND）

4. 令 H : { 0 , 1 } k → { 0 , 1 } n H:\{0,1\}^k \to \{0,1\}^n H:{0,1}k→{0,1}n是ROM，给定$m$组秘密
   x i 0 , x i 1 , ⋯ , x i 2 l − 1 ∈ { 0 , 1 } n x_i^{0},x_i^{1},\cdots,x_i^{2^l-1} \in \{0,1\}^n xi0​,xi1​,⋯,xi2l−1​∈{0,1}n
   $S$分别加密它们：
   $$\begin{array}{rl}{c}_i^0& =x_i^0\oplus H(q_i\oplus (C(0)\wedge s))\\ c_i^1& =x_i^1\oplus H(q_i\oplus (C(1)\wedge s))\\ & ⋮\\ c_i^{2^l-1}& =x_i^{2^l-1}\oplus H(q_i\oplus (C(2^l-1)\wedge s))\end{array}$$
   然后将这$m\times 2^l$个密文发送给$R$

5. $R$手里有$t_i$和$r$，但不知道$s$，因此只能计算出$H(t_i)$，在每一组的$2^l$个密文中只能解密其中$1$个密文。确切地说是$c_i^{r_i}$：
   $$x_i^{r_i}=c_i^{r_i}\oplus H(q_i\oplus (C(r_i)\wedge s))=c_i^{r_i}\oplus H(t_i)$$

对于其他的密文，由于$R$不掌握$s$，因此无法预测密钥$H(q_i\oplus (C(r_i^{\prime }|r_i^{\prime }\ne r_i)\wedge s))$的值。假设线性码$C$的极小距离是$\kappa$，那么$dist[C(r_i^{\prime }),C(r_i)]\ge \kappa$，只有猜对这$\kappa$个位置的 s j ∈ { 0 , 1 } s_j \in \{0,1\} sj​∈{0,1}的比特值，敌手才能够计算出$r_i^{\prime }$对应的密钥，复杂度$O(2^{\kappa })$是指数级。

在 KK 方案中，仅仅花费了$k$次 $1$-out-of-$2$ base-OT协议，但实际上实现了$m=poly(\kappa )$次的 $1$-out-of-$2^l$ OT协议！

为了适配更高效的底层编码$C$，我们需要更大的线性空间，可设置$k=2\kappa$

Efficient Batched Oblivious PRF（2016）

Kolesnikov 等人发现，实际上编码方案$C$并不需要纠错码的全部性质：

1. 在 KK 方案中用不到解码，因此$C$不必拥有高效解码算法
2. 只要对于所有可能的$r,r^{\prime }$对，其差分$C(r)\oplus C(r^{\prime })$的汉明重量以压倒性概率大于等于安全参数$\kappa$即可，即使编码$C$的极小距离小于$\kappa$

伪随机码 (pseudorandom code，PRC)：令 C : { 0 , 1 } ∗ → { 0 , 1 } k C:\{0,1\}^* \to \{0,1\}^k C:{0,1}∗→{0,1}k是带有足够长的输出的ROM，那么就很难找到近碰撞（near-collision）—— 难以找到$r,r^{\prime }$，使得汉明重量很小，即$wt[C(r)\oplus C(r^{\prime })]<\kappa$；当$k=4\kappa$时，随机函数就 make near-collisions negligible。

也就是说，用 PRC 替换了线性纠错码后，we remove the a-priori bound on the size of the receiver’s choice string！对于任意的 r ∈ { 0 , 1 } ∗ r \in \{0,1\}^* r∈{0,1}∗，$S$都可以计算出对应的秘密$H(q_i\oplus (C(r)\wedge s))$，那么利用 KK 协议就获得了 $1$-out-of-$\infty$ OT协议。

上述的OT协议可以视为一批 Oblivious PRF：映射$F:r\mapsto H(q\oplus (C(r)\wedge s))$，$S$拥有秘密$s$，$R$的输入是$r$，且函数的输出是伪随机的。

1. 对于每一组的$\infty$个秘密，$R$只知道其中的$1$个函数值（$r_i$对应的）：
   $$F((q_i,s),r_i)=H(q_i\oplus (C(r_i)\wedge s))=H(t_i)$$
   确切地说其实是知道$t_i$，但这并不影响$R$对其他的函数值$F((q_i,s),r_i^{\prime }|r_i^{\prime }\ne r_i)$的一无所知。

   但是 $r_i$ 对应的 $t_i$ 不是 $R$ 自己生成的么？还有怎么计算其他 $r_i^{\prime }$ 的函数值呢？看不懂了 (╯︵╰)

2. 同时根据OT协议的安全要求，$S$也不知道$R$输入的$r_i$

这里是一批次同时计算$m$个OPRF的协议，这$m$个OPRF实例都共享$S$的同一个密钥$s$以及伪随机码$C$

细节还请看 Kolesnikov et al. (2016) 的论文吧~~