「MPC-Mike Rosulek 」:Oblivious Transfer and Extension
本系列是总结Mike Rosulek教授在上海期智研究院的密码学学术讲座。
这是Mike教授的第三个分享:Oblivious Transfer and Extension
Roadmap
- Precomputation: can compute OTs even before you know your input!
- OT extension: 128 OTs suffice for everything.
OT在多方安全计算中扮演着重要的角色,但OT的实际开销往往很大,因为他不可能使用廉价的加密方法来实现[ImpagliazzoRudich89]。因此在这篇文章中,会介绍一些前沿的方法来提高OT的效率:离线预计算和OT扩展。
Offline Precomputation
Random OT
在提出random OT概念前,我们先回顾一下standard OT:

在standard OT中,Alice选择两个输入:$m_0, m_1$,Bob选择一个输入:$c$。
经过一次OT后,Bob可以得到Alice输入中的一个:$m_c$,而不知道另一个输入 $m_{1-c}$ 。而Alice不知道Bob的输入 $c$ ,也就不知道Bob选择的哪一个。
上述过程中,需要双方选择他们各自的输入,双方的输入确定,Bob得到的结果也是确定的:$m_c$ 。
相对于standard OT的确定性,random OT不需要双方选择输入,而是直接随机采样许多 $m_0, m_1, c$ 作为random OT instances。

Beaver Derandomization Theorem[Beaver91] :
There is a cheap protocol that securely evaluates an instance of satandard OT using an instance of random OT.
【Beaver的去随机化理论提出:存在一些高效的协议能将一个random OT 转化为一个standard OT instance.】
根据Beaver的去随机化理论,在运行OT协议时,可以先离线生成许多random OTs。在online phase:即OT的输入是由Alice和Bob的输入确定的,可以用Beaver的方法高效地将离线生成的random OT去随机化,即变成standard OT。
Beaver Derandomization
Beaver去随机化过程分为两个阶段:离线阶段和在线阶段(standard OT)

在离线阶段,生成大量random OT instances,其中Alice知道 $m_0^\$, m_1^\$ $ ,Bob知道 $c^\$, m_{c^{\$}}^\$$ 。
而Beaver的去随机化的核心思想是:用生成的random OT instance的 $m_0^\$, m_1^\$ $ 作为one-time pad的密钥,分别加密Alice在线时的输入 $m_0, m_1$ 。而Bob只能用唯一知道的密钥 $ m_{c^{\$}}^\$ $ 解密其中一个,而不知道另一个。
Bob在线时的输入: $c=c^\$$
Bob可以用 $ m_{c^{\$}}^\$ $直接解密: $x_c \oplus m^\$_{c^\$} = x_c \oplus m^\$_c = m_c$ ,得到想要的 $m_c$ ,而对 $m_{1-c}$ 一无所知。
Bob在线时输入: $c\neq c^\$$
如果Bob还想用 $ m_{c^{\$}}^\$ $直接解密得到 $m_c$: $x_c \oplus m^\$_{c^\$} =x_c \oplus m^\$_{1\oplus c} =m_c$ ,Alice在加密时 $m_0, m_1$ 时,必须交换其密钥 $m_0^\$, m_1^\$ $ :
为了Bob能得到正确的 $m_c$ ,Bob应该告诉Alice什么时候要交换密钥,什么时候不用交换密钥。
方法就是用一个1-bit one-time pad,Bob 计算出 $d = c\oplus c^\$$ ,由此告诉Alice是否需要交换密钥($d = 0$ 告诉Alice不需要交换密钥,$d = 1$告诉Alice需要交换密钥),而Alice对 $c, c^\$$ 都一无所知。
因此Beaver的去随机化的完整过程:

Bob计算出 $d = c\oplus c^\$$ ,发送给Alice,以此告诉Alice是否需要交换密钥 $m_0^\$, m_1^\$ $ 。
Alice输入 $m_0, m_1$ ,根据 $d$ 的值选择密钥 $m_0^\$, m_1^\$ $ 来分别加密$m_0, m_1$ :
$$ \begin{align} x_0 &= m_d^\$ \oplus m_0 \\ x_1 &= m_{1\oplus d}^\$ \oplus m_1 \end{align} $$再将其发送给Bob
Bob用唯一已知的密钥 $ m_{c^{\$}}^\$ $来解密得到 $m_c$: $x_c \oplus m^\$_{c^\$} =x_c \oplus m^\$_{1\oplus c} =m_c$ ,而对 $m_{1-c}$ 一无所知。
最后分析一下Beaver去随机方法的开销:离线阶段生成一个random OT instance和之前的OT开销相同,但在在线阶段,只需要一些简单的异或运算。
OT Extension
An Analogy from Encryption
公钥加密(Public-key encryption, PKE)本质上具有不可避免的高昂开销[ImpagliazzoRudich89] ,但是在现实的加密方案中,可以通过混合公钥加密和对称加密的方式,将实现PKE的开销降到最低。
即PKE of λ bits + cheap SKE = PKE of N bits
Use (expensive) PKE to encrypt short s
【用PKE来加密共享短密钥,比如DH算法】
Use (cheap) symmetric-key encryption with key s to encrypt long M
【再将短密钥通过密钥扩展算法获得长密钥,作为对称加密的密钥】
OT本质上也具有不可避免的高昂开销[ImpagliazzoRudich89] ,所以如果将OT与公钥加密类比,是否存在一种混合加密方案,也能实现λ instances of OT + cheap SKE = N instances of OT?
Beaver OT Extension
Beaver利用Yao的两方安全计算,提出了一种OT的扩展协议[Beaver96] 实现$\lambda$ instances of OT + cheap SKE = $N$ instances of OT.
Beaver OT扩展协议其实是一个两方安全计算电路:该电路将Alice和Bob的输入作为伪随机的种子,以此生成$n$ OT instances,包括输出给Alice的random strings和输出给Bob的choice bits+choice strings。

该电路的输入位是 $\lambda$ bit,因此Alice和Bob需要做 $\lambda$ 次OTs,而该电路可以生成 $n>>\lambda$ OTs,由此实现了$\lambda$ instances of OT + cheap SKE = $N$ instances of OT.
但是用Yao’s garbled circuits的方法实现Beaver OT扩展协议几乎是不可能的,因为这太复杂了。
IKNP Protocol
而Yuval Ishai, Joe Kilian, Kobbi Nissim, Erez Petrank在Crypto 2003年发表的论文:Extending Oblivious Transfers Efficiently,提出了一种可实现、更高效的OT扩展协议,以此实现 $\lambda$ instances of OT + cheap SKE = $N$ instances of OT。
该协议能够用有限的OTs(比如128次OTs)实现足够多次的OTs(比如1 million),下面将详细阐述协议是如何实现的。
IKNP Details
Bob:
has input $r $
$\Rightarrow$ extend to matrix
【把输入 $r$ 重复多次扩展为矩阵 $R$,矩阵的每行 $R_i$ (ith row of $R$)要么是全1或者全0,而且该矩阵的高是million级别的,宽度可以为128】
$\Rightarrow$ secret share as ($T, T’$)
【然后对该矩阵$R$做秘密分享,即拆分为两个矩阵 $T,T’$ 】
【秘密分享的策略是随机生成一个矩阵 $T$ ,而 $T’=T\oplus R$ ,观察下图可以看出 $R_i = T_i \oplus T_i’$ ,即两个矩阵的每行要么相同($r=0$),要么相反($r=1$) 】
Alice:
chooses random string $s$
OT for each column $\Rightarrow$ Alice obtains matrix $Q$
【从列的角度做OT,Alice每次根据 $s$ 的值从Bob的($T,T’$)选择一列,如果 $s_i=0$ ,从矩阵$T$选择第i列,如果 $s_i=1$ ,从矩阵$T’$选择第i列,得到矩阵 $Q$】
【这里的OT中,Bob是sender,Alice是receiver】
观察Alice经过128次OT得到的矩阵 $Q$ ,可以发现Alice得到的矩阵 $Q$ 和Bob拥有的矩阵 $T$ 有如下关系:
Whenever $r_i = 0$, Alice row = Bob row
Whenever$r_i =1$, Alice row=Bob row $\oplus s$
For every i: Bob knows $t_i$ ; Alice knows $q_i$ and $q_i\oplus s$ .
【再从行的角度观察Alice和Bob得到的信息,Alice每次收到 $q_i$ 后,都可以通过和random string $s$ 异或得到 $q_i$ 和 $q_i\oplus s$ ,而这其中的一个值与Bob知道的 $t_i$ 相同】
【Alice:因为不知道Bob的 $r_i$ 值,所以不知道Bob选择的 $t_i$ 到底是和 $q_i$ 相等还是和 $q_i\oplus s$ 相等】
【Bob:因为不知道Alice的 $s$ 值,所以只知道选择的 $t_i$ 等于$q_i$ 和$q_i\oplus s$ 中的一个,而不知道另一个】
但是从Bob视角重写Alice得到的信息,我们知道得到:
- $r_i=0: q_i=t_i$
- $r_i=1:q_i=t_i\oplus s$
至此,我们几乎已经实现了行角度的OT,Alice有两个值:$q_i$ 和 $q_i\oplus s$ ,Bob根据 $r_i$ 从中选择得到一个,而对另一个一无所知。
Break correlations by applying random oracle
上面我说是“几乎实现了行角度的OT”,为什么是几乎呢?
因为string s的原因,这些OT instances具有一定的线性相关性。所以为了破坏其中的线性相关性,对这些strings都执行一个任意的密码学函数 $H$ :
$\Rightarrow$ Random OT instance for each row, using base OT for each column
【由此,通过从列的角度做base OT,得到了足够多的行角度random OT instances】
最后,总结一下IKNP如何实现$\lambda$ instances of OT + cheap SKE = $N$ instances of OT。
Bob有一个tall matrix($\lambda$ 列, $n>>\lambda$ 行),Alice从列的角度根据秘密字符串 $s$ 做 $\lambda$ 次base OTs。

最后Alice和Bob得到了行角度的 $n$ 个扩展OTs。

Malicious Bob in IKNP Protocol
[KellerOrsiniScholl15] 介绍了如果有恶意的参与方,IKNP受到的威胁
假设Bob是恶意的:
Bob:
有一个输入 $r $
$\Rightarrow$ 对其扩展为矩阵 $R$ ,但是恶意地翻转了 $t_2$ 的第二位bit:
$\Rightarrow$再做秘密共享为 ($T, T’$) ,同样的,$T’$ 中也有一位被翻转了:
Alice:
选择一个随机串 $s$
对每列做OT $\Rightarrow$ Alice得到矩阵 $Q$
因为 $r_2=0$ ,本应该有 $q_i = t_i$ 。但因为Bob恶意翻转了一位,所以Alice得到的 $q_i$ 和 $t_i$ 在第二位不同
…
所以在Alice和Bob同时使用 $H(row)$ 破坏线性相关性后,Bob会发现得到的 $H(row#2)$ 值不同,Bob就知道Alice选择的随机串中 $s_2=1$ 。
如此以来,Bob每次都恶意翻转某一列的一个bit,就可以学到 $s$ 的所有比特信息。
Consistency Check
所以如何保证Bob没有恶意篡改矩阵 $R_i$ ($R$ 矩阵的第i行)?
[KellerOrsiniScholl15] 提出了一种一致性检验方法来检测Bob是否恶意篡改了矩阵。

Alice在执行IKNP中通过多次检验上述方程的一致性,来检测Bob是否恶意篡改了扩展矩阵。
同时,为了保护扩展矩阵的位信息,Bob也使用一个随机矩阵来加密 $R^*$ 。
IKNP可以通过上述一致性检验来实现malicious security,而引入的额外开销很小。
Generalizing IKNP
IKNP协议生成了许多二选一的OT instances,这里将介绍如何对IKNP协议一般化,以生成多选一的OT instances。
再次回顾一下IKNP的做法:
Bob有一个选择串 $r$
扩展为矩阵 $R$ ,矩阵的每行是全0或全1
再对矩阵R做秘密分享
从行的角度看矩阵扩展,把0
编码为 000...
,把1
编码为111...
。所以可以把矩阵扩展看作对 $r$ 的bit的一种编码方式(repetition code)。

因此,一般化IKNP的核心思想就是:用具有差错校正的编码方式对 $r$ 的bit进行编码。
Coding view of IKNP
现在,我们从编码的方式看IKNP。
Bob:
Bob 有一个输入 $r$
对 $r$ 的比特进行编码:
在这种编码方式下进行秘密分享
Alice 对每列做OT,得到矩阵$Q$
Bob得到的 $t_i$ 和Alice得到的 $q_i$ 有如下关系:$t_i = q_i\oplus C(r_i)\wedge s$
如果是在编码$C(0)=000…, C(1)=111…$ 下:
- $r_i=0 \Rightarrow t_i = q_i\oplus (000…)\wedge s=q_i$
- $r_i=1 \Rightarrow t_i=q_i\oplus (111…)\wedge s=q_i\oplus s$
For every i: Bob knows $t_i$; Alice knows $q_i\oplus C(0)\wedge s$ and $q_i\oplus C(1)\wedge s$
【此时Alice知道$q_i\oplus C(0)\wedge s$ 和 $q_i\oplus C(1)\wedge s$ ,Bob知道$t_i$ 】
从Bob的视角重写Alice得到的 $q_i=t_i\oplus C(r_i)\wedge s$
当$C$是一种线性编码时,即满足: $[C(a)\wedge s]\oplus [C(b)\wedge s]=C(a\oplus b)\wedge s$ and $C(0)\wedge s = 000…$
得到:
化简:
Use random oracle to destroy correlations
【再破坏其线性相关性】
Generalizing IKNP
刚刚我们考虑的是只对 $\{0, 1\}$ 编码,即: $C:\{0, 1\}\rightarrow \{0, 1\}^k$ 编码。
现在考虑编码更多的bits,即 $C:\{0, 1\}^3\rightarrow \{0, 1\}^k$ ,同样地,$C$是线性编码。
同样的运行IKNP:
For every i: Alice can compute 8 (things)
【之前Alice是可以计算$q_i\oplus C(0)\wedge s$ 和 $q_i\oplus C(1)\wedge s$ 】
现在是对 $\{0, 1\}^3$ 编码,就可以计算:
$q_i\oplus C(000)\wedge s, q_i\oplus C(001)\wedge s, \cdots,q_i\oplus C(111)\wedge s$
同样的,从Bob的角度重写Alice得到的值$q_i=t_i\oplus C(r_i)\wedge s$
并且 $C$ 是线性编码,满足$[C(a)\wedge s]\oplus [C(b)\wedge s]=C(a\oplus b)\wedge s$ and $C(0)\wedge s = 000…$ ,化简后:
对上述Alice计算出的8个串,Bob只知道其中的一个 $t_i$ ,而这个 $t_i$ 等于Alice知道的第几个串,这取决于Bob的选择的 $r_i$ ,使得 $C(r_i\oplus \cdots)=000…$ 。
In the random oracle model: $H(t_1 \oplus c_1 \wedge s),…H(t_n \oplus c_n \wedge s)$ pseudorandom if all $c_i$ have Hamming weight $\ge \lambda$
【在破坏线性相关性时,只有当所有 $c_i$ 的汉明重量(Hamming weight)$\ge\lambda$ 时,$H(\cdot)$ 和随机串才具有不可区分性】
汉明重量(Hamming weight):汉明重量是一串符号中非0符号的个数。
汉明距离(Hamming distance):两个字符串对应位置的不同字符的个数。
就此,我们介绍了扩展的IKNP协议,[KolesnikovKumaresan13] 提到使用这样的编码: $C:\{0, 1\}^l\rightarrow \{0, 1\}^k$ (编码字符串的汉明距离 $\ge \lambda$) 执行 $k$ 次base OT,就能实现从 $2^l$ 中选一个的OT扩展(1-out-of- $2^l$ OT extension)。
1-out-of-256 OT[KolesnikovKumaresan13] :
Walsh-Hadamard code $C:\{0, 1\}^8\rightarrow \{0, 1\}^k$ (min. dist. 128)
1-out-of- $2^{76}$ OT[OrruOrsiniScholl16] :
BCH code $C:\{0, 1\}^{76}\rightarrow \{0, 1\}^{512}$ (min. dist. 171)
1-out-of-∞ OT[KolesnikovKumaresanRosulekTrieu16]
这篇文章提出,对于任意的伪随机编码$C:\{0, 1\}^*\rightarrow \{0, 1\}^{~480}$ ,只需要满足最小的hamming dist.,而不用要求编码 $C$ 的线性性质,就可以实现1-out-of-∞ OT。
就此,IKNP协议的介绍到此结束。也正是因为IKNP协议,使得OT的效率大幅提高。
「MPC-Mike Rosulek 」:Oblivious Transfer and Extension