云中雨雾

    不经意传输及其优化方案

    2021/06/15 22:34 下午 标签: #密码学理论

    本文整理了美国俄勒冈州立大学电子工程和计算机科学学院副教授Mike Rosulek关于安全多方计算与混淆电路的演讲主题的主要内容, 文中图片均来源于Mike Rosulek的演讲报告幻灯片. 整理如有错误之处, 恳请批评指正, 谢谢!

    不经意传输(Oblivious Transfer, OT)是MPC的一种特殊情况, 有两个参与者Sender(\(S\), Alice)和Receiver(\(R\), Bob), \(S\)有两个秘密信息\(m_0,m_1\), \(R\)有一个秘密的选择比特\(c\), 不经意传输协议将使得\(R\)根据\(c\)的取值获得信息\(m_c\), 但对\(m_{1-c}\)一无所知, 同时\(S\)由于不知\(c\)的具体取值, 因而对\(R\)具体获得的是\(m_0\)还是\(m_1\)一无所知. 不经意传输协议的一个重要应用是在混淆电路中用于传输Evaluator的输入所对应的标签值, 此外不经意传输在其他MPC协议中也有很重要的应用. 在混淆电路中使用的是对称加密运算, 因而是非常快速且廉价的(cheap), 但不经意传输中需要使用大量的公钥加密运算, 因此计算是非常昂贵(Inherently expensive)的. Impagliazzo和Rudich指出仅使用对称加密原语来构造不经意传输协议是不可能的1. 下面将主要介绍不经意传输协议的一些优化方案.

    一个标准的OT协议是一个确定性的功能函数, 输入信息都是由参与方给定的. 一个随机OT(Random OT, ROT)协议是一个随机化的功能函数, \(m_0,m_1,c\)都是协议均匀随机生成而非参与方给定的. Beaver去随机化定理2告诉我们, ROT可以很容易地转化为标准OT. 如果我们需要大量的标准OT, 可以通过离线/在线阶段来生成. 首先在离线预计算阶段中生成大量的ROT, 然后在在线阶段中使用Beaver去随机化技巧将ROT转化为确定性的标准OT. 下面我们将介绍Beaver在线阶段的转换方法.

    Beaver去随机化方案

    如下图所示, 设预计算阶段的ROT协议使发送方Alice获得两个随机信息\(m_0^r, m_1^r\), 接收方Bob获得\(c^r, m_{c^{r}}^r\), 这里的上标\(r\)与图中的美元符号含义相同, 设在线阶段Alice的需要发送的信息为\(m_0,m_1\), Bob的选择比特为\(c\). Beaver去随机化的主要思想是Alice使用ROT的两个随机信息\(m_0^r, m_1^r\)作为一次一密(OTP)来加密需要他发送的信息\(m_0,m_1\), 并将盲化结果\((x_0,x_1)\)发给Bob. 如果\(c=c^r\), Alice发送的两个信息是\(x_0=m_0^r\oplus m_0, x_1=m_1^r\oplus m_1\), Bob本地计算\(x_c\oplus m_{c^r}^r=x_c\oplus m_c^r=m_c\)即可得到选择比特\(c\)对应的秘密\(m_c\), 但无法获得\(m_{1-c}\). 但如果\(c\neq c^r\), 按照上述步骤我们会发现Bob将无法获得正确的信息, 除非Alice交换\(m_0^r, m_1^r\)来加密\(m_0,m_1\).

    Beaver Derandomization 1

    于是很自然地解决办法是, 我们可以让Bob告诉Alice是否有\(c=c^r\), 为此, Bob向Alice发送\(d=c\oplus c^r\), 然后Alice计算\(x_0=m_d^r\oplus m_0,x_1=m_{1\oplus d}^r\oplus m_1\), 并发送\(x_0,x_1\)给Bob, Bob计算\(x_c\oplus m_{c^r}^r=x_c\oplus m_{c\oplus d}^r=m_c\). 正确性容易验证, 若\(d=0\), 说明\(c=c^r\), Alice使用\(m_0^r\)来加密\(m_0\), \(m_1^r\)来加密\(m_1\); 若\(d=1\), 说明\(c\neq c^r\), Alice使用\(m_0^r\)来加密\(m_1\), \(m_1^r\)来加密\(m_0\). 容易看出, Bob这样做是安全的, 因为Alice从\(d\)中无法获知\(c^r\)的具体信息.

    Beaver Derandomization 2

    离线阶段的ROT的开销仍然是昂贵的, 但在线阶段由于只有简单的XOR运算, 因此非常快速. 需要特别注意的一点是, 一个ROT实例只能生成一个标准OT实例, 这是因为在线阶段中我们将ROT的输出作为一次一密的密钥来加密参与方所发送的消息, 因此一个ROT只能使用一次.

    OT扩展

    我们先从公钥加密(PKE)说起, 由于公钥加密的开销比对称加密(SKE)的开销大, 因此我们通常通过同时使用PKE和SKE的混合加密来最小化PKE的开销: 首先使用昂贵的PKE加密短密钥\(s\), 然后使用使用\(s\)通过廉价的SKE来加密长信息\(M\). 于是, 通过\(\lambda\)比特的PKE和廉价的SKE, 我们实现了\(N\)比特的PKE, 其中\(\lambda\)代表计算安全参数. 那么, 有没有类似于混合加密的方法, 仅通过\(\lambda\)次OT实例和廉价的SKE来得到大量的OT实例呢? 这就是OT扩展的出发点.

    Analogy

    Beaver在1996年提出了OT扩展(OT extension)3. Beaver注意到Yao协议需要的OT数量正比于函数的输入的长度, 我们可以使用混淆电路来构造这样一个OT扩展协议: Alice和Bob分别输入长度为\(\lambda\)比特的\(s_A\)和\(s_B\), 使用\(s_A\oplus s_B\)作为伪随机种子: (1) 生成\(2n\)个随机串, 组成\(n\)对随机消息\((m_{1,0},m_{1,1}),\cdots,(m_{n,0},m_{n,1})\); (2) 选取一个\(n\)比特串\(r\); 最终Alice得到所有随机消息对\(\{m_{i,b}\}_{i,b}\), Bob得到\(r\)以及\(r\)的第\(i\)比特\(r_i\)所对应的消息\(\{m_{i,r_i}\}_i\), 其中\(i\in\{1,\cdots,n\}\), 这里的\(n\gg \lambda\).

    通过这种方式生成的ROT实例数为\(n\), 而实际使用的ROT实例数仅为\(\lambda\), 通常将这部分实际使用的OT实例称为Base OT. 虽然Beaver的OT扩展协议并不实用, 因为需要使用Yao协议对包含大量PRG的布尔电路求值, 但它告诉我们OT扩展的想法是切实可行的.

    Beaver OT extension

    IKNP协议: 半诚实安全的OT扩展协议

    2003年的美密会Yuval Ishai, Joe Kilian, Kobbi Nissim, Erez Petrank共同发表了“Extending Oblivious Transfers Efficiently”, 即著名的IKNP协议4, 其原理主要是基于矩阵变换, IKNP协议标志着OT扩展逐渐走向实用.

    协议描述

    假设Alice和Bob想生成\(n\)个OT, Bob拥有一个长为\(m\)的选择比特串\(r\), 这里\(r\)的每个比特都是每次OT的一个选择比特. Bob将\(r\)的比特分解排成一列向量, 然后将向量的每个元素重复并按行扩充成一个\(n\times\lambda\)维0-1矩阵\(R\), 该矩阵每行的元素要么全为0, 要么全为1. Bob对该矩阵进行秘密共享, 生成两个秘密份额矩阵\((T,T')\), 若原始矩阵的行向量全为0, 则\(T,T'\)在该行的元素相同, 反之则不相同(如图中橙色部分表示原始矩阵行向量全为1的秘密份额). Alice随机生成一个长为\(\lambda\)的比特串\(s\). 然后双方交换身份执行\(\lambda\)次Base OT(次数取决于矩阵的列数), 对于第\(i\)次Base OT, Bob将秘密份额矩阵的第\(i\)列元素\((T_i,T'_i)\)作为Base OT发送方的输入信息, Alice将\(s\)的第\(i\)个比特\(s_i\)作为Base OT接收方输入的选择比特, 若\(s_i=0\), 则Alice获得\(T_i\)(即右侧后面那个矩阵的第\(i\)列), 反之则Alice获得\(T'_i\)(即右侧前面那个矩阵的第\(i\)列). 运行\(\lambda\)次之后, Alice获得矩阵\(Q\). 易见, 当\(r\)的某一位置上的选择比特为0时, Alice所得矩阵\(Q\)的行向量\(q_i\)与Bob秘密份额矩阵在该位置的所对应的行向量\(t_i\)相等, 而当\(r\)的某一位置上的选择比特为1时, Alice所得矩阵\(Q\)在该位置所对应行的行向量\(q_i\)等于Bob秘密份额矩阵在该位置的所对应行的行向量\(t_i\)异或上\(s\). 即

    \[q_i=\begin{cases} t_i,& \text{若} r_i=0\\t_i\oplus s, & \text{若} r_i=1 \end{cases} \]

    其中\(r_i\)是\(R\)的第\(i\)行. 上式也可以统一写成如下形式:

    \[q_i=t_i\oplus r_i\wedge s, \tag{1} \]

    IKNP 1

    我们可以将上述过程抽象成下图的形式: 对于每个\(i\), Bob得到\(t_i\), Alice可以计算\(q_i\)和\(q_i\oplus s\). 根据(1)式的关系, 我们可以将Alice所计算的的\(q_i\)和\(q_i\oplus s\), 根据\( r_i\)的不同, 表示成下图中\(t_i\)与\(s\)关系的形式, 这可以看成是OT扩展中Alice作为发送者所拥有的秘密信息, 而从Bob的视角来看, 他所拥有的\(t_i\)刚好是Alice秘密信息中的其中一个!

    但是, 对于Alice表格的每一行来说, 由于重用\(s\), 导致了关联性. 为此, Alice和Bob可以采用一个随机预言机\(H\)来破坏这种关联性即可. IKNP协议的文章中指出, 实际上不需要更强的RO模型假设, 只需要假设\(H\)是一个关联健壮哈希函数(Correlation Robust Hash Function, CRHF)即可. 给定\(t_1,\cdots,t_n\)和秘密\(s\), \(H(t_1\oplus s),\cdots,H(t_n\oplus s)\)是独立(伪)随机的, 通常称该性质为关联健壮性(Correlation Robustness), 而满足这种性质的哈希函数称为关联健壮哈希函数. 以上便是完整的IKNP协议的全过程.

    如果从更高的视角来看IKNP协议, 可以想象一下我们有一个\(n\times \lambda\)维的高瘦矩阵, 其中\(n\gg \lambda\). 我们通过对矩阵的每列进行\(\lambda\)次Base OT实例, 每次传输一个\(n\)比特长的串,通过逐行计算\(H\)来扩展随机OT实例. 很容易通过Beaver Derandomization Theorem将该随机OT扩展转换为标准OT扩展, 这里不做过多说明.

    协议的安全性

    安全性方面, IKNP协议是半诚实安全的. 具体而言, Alice可以是恶意的, 但Bob只能是半诚实的, 下面将介绍如果Bob是恶意的, IKNP协议会存在的问题.

    如上图所示, 假设Bob在生成选择比特矩阵时, 在第二行的图示位置篡改了其中一比特. Alice和Bob在第二行有一比特不一致, 当且仅当Alice在Base OT中输入的\(s\)的第二个比特\(s_2=1\). 若Alice对该行进行Hash运算并在其他大型协议中使用这些结果而被Bob检测到, 则Bob将能得到\(s\)的一比特信息! Bob通过使用类似地方法, 在每列的不同位置篡改一个比特, 便可以获得Alice在该OT扩展协议中唯一的秘密信息\(s\), 进而攻破整个OT扩展协议. 因此, IKNP协议仅是半诚实安全的.

    KOS协议: 恶意安全的IKNP协议

    回顾IKNP协议的等式\(q_i=t_i\oplus R_i\wedge s\)和恶意敌手Bob的整个攻击过程, 这是由于\(R\)的第\(i\)行\(R_i\)所有元素不一致造成的. 若\(R_i\)的汉明重量(Hamming Weight)很低, 那么Bob可以通过观察\(H(q_i)\)来猜测(或检查)\(s\)的某些比特. 那么, 如何保证Bob在协议中使用的\(R_i\in\{0^n,1^n\}\)呢? Keller, Orsini, Scholl发表于2015年美密会的一致性检查(Consistency check)技术5可以做到这一点.

    如下图所示, 由于IKNP等式\(q_i=t_i\oplus R_i\wedge s\)对矩阵的所有行\(i\)都成立且所有行的\(s\)都相同, 因此这些行数集合组成的子集\(C\)所对应的式子求异或之和后该等式仍然是成立的, 即有以下等式

    \[(\bigoplus_{i\in C} q_i)=(\bigoplus_{i\in C} t_i)\oplus(\bigoplus_{i\in C} R_i)\wedge s, \tag{2} \]

    为此, Alice可以发起挑战, 选取随机行数组成的集合\(C\)发给Bob. Bob计算\(t^*=\bigoplus_{i\in C}t_i, R^*=\bigoplus_{i\in C}R_i\), 并发送\(t^*,R^*\)给Alice作为应答. 由于Alice有\(s\)和\(q_i\), 因此她可以计算\(q^*=\bigoplus_{i\in C}q_i\), 并验证等式(2)是否成立. KOS协议的一致性检查的主要思想在于如果\(R_i\in\{0^n,1^n\}\), 那么对于行的任意组合来说其异或和的结果必然也属于\(\{0^n,1^n\}\)这个集合; 如果存在某个\(R_i\)不属于这个集合, 那么Bob将有1/2的概率通过一致性检查从而作弊成功, 此外, Bob也可以通过猜测\(s\)使其发送的信息\(t^*,R^*\)通过一致性检查, 为此只需将一致性检查重复\(\lambda=128\)次, 如果Bob能通过所有的一致性检查, 则Alice可以认为Bob输入的\(R_i\)确实是属于\(\{0^n,1^n\}\)这个集合的. 但是, 该一致性检查技术的每次检查会泄露矩阵\(R\)的一比特信息, 为此Bob只需添加\(\lambda=128\)个额外的随机行到\(R\)中来盲化应答.

    KOS Protocol

    KOS协议针对半诚实安全的IKNP协议进行了改进, 通过引入一致性检查, 实现了恶意安全的IKNP协议. KOS协议也是目前已知最快的恶意安全的IKNP型OT扩展协议, 其通信开销几乎和半诚实安全的通信开销相同.

    1-out-of-\(N\) OT扩展协议

    以上所介绍的OT协议都是随机2选1的OT扩展协议, 即1-out-of-2 OT extension. 下面我们考虑通过Kolesnikov和Kumaresan发表在2013年美密会的方案6, 从编码的角度可以将IKNP协议推广到随机1-out-of-\(N\) OT扩展协议.

    从编码的角度看IKNP协议

    在IKNP协议中, Bob有一个选择比特串\(r\), 将其扩充为一个矩阵并进行秘密共享. KK13中指出, IKNP协议将Bob选择比特扩充为矩阵的步骤, 将0映射为\(0^\lambda\), 1映射为\(1^\lambda\), 这是一种简单的重复码(repetition code), 如果将其视为一种纠错码, 或许我们可以采用不同的纠错码进行推广.

    首先, 我们从编码的角度来看IKNP协议, Bob拥有选择比特串\(r\), 设\(C:\{0,1\}^1\to\{0,1\}^\lambda\)是用于编码Bob的选择比特\(r_i\)的重复码, 然后对该码字矩阵进行秘密分享. 设Bob的秘密分享矩阵为\(T,T'\), 则矩阵的元素可分别表示为\(t_i,t_i\oplus C(r_i)\). 这样, IKNP等式(1)可以推广为如下形式

    \[t_i=q_i\oplus C(r_i)\wedge s. \tag{3} \]

    在双方执行完Base OT后, 对于矩阵的第\(i\)行, Bob已知\(t_i\), Alice已知\(q_i\oplus C(0)\wedge s\)和 \(q_i\oplus C(1)\wedge s.\)

    从Bob的视角, 利用等式(3), 可重写Alice的两个值为

    \[{\color{red}t_i\oplus C(r_i)\wedge s}\oplus C(0)\wedge s, \qquad{\color{red}t_i\oplus C(r_i)\wedge s}\oplus C(1)\wedge s. \]

    当\(C\)是一个线性码时, 有\([C(a)\wedge s]\oplus[C(b)\wedge s]=C(a\oplus b)\wedge s\)成立, 则Alice的两个值可以进一步写成

    \[t_i\oplus{\color{red}C(r_i\oplus0)\wedge s}, \qquad t_i\oplus{\color{red}C(r_i\oplus1)\wedge s}. \]

    再令\(C(0)\wedge s=0^\lambda\), 则Alice的两个值进一步变为

    \[t_i, \qquad t_i\oplus C(1)\wedge s, \]

    两者的先后次序取决于\(r_i\)的具体取值.

    最后, 再使用随机预言机RO来破坏重用\(s\)导致的关联性, 即Alice的两个值进一步变为

    \[H(t_i), \qquad H(t_i\oplus C(1)\wedge s). \]

    而Bob的值则变为\(H(t_i)\).

    IKNP协议的推广

    下面我们考虑选取其他编码方案, 为了方便说明, 我们考虑一个简单编码方案: \(C:\{0,1\}^3\to \{0,1\}^k\), 即此时\(r_i\in\{0,1\}^3\), 总共8种取值. 对于矩阵的第\(i\)行, Alice可以计算8个值:

    \[q_i\oplus C(000)\wedge s, q_i\oplus C(001)\wedge s,\cdots,q_i\oplus C(111)\wedge s. \]

    从Bob的视角来看, 这8个值在RO模型下的形式分别为

    \[H(t_i\oplus C(r_i\oplus 000)\wedge s),H(t_i\oplus C(r_i\oplus 001)\wedge s ),\cdots,H(t_i\oplus C(r_i\oplus 111)\wedge s). \]

    Bob根据\(r_i\)的值通过Base OT可以得到\( H(q_i\oplus C(r_i)\wedge s)\). 对于已知的\(t\)和码字\(c\), Bob只知道其他值形式为\(t\oplus c\wedge s\). 在RO模型中, 若所有非零码字\(c_i\)的汉明重量都满足大于或等于\(\lambda\), 则\(H(t_1\oplus c_1\wedge s),\cdots,H(t_n\oplus c_n\wedge s)\)是伪随机的, 这样其他值在Bob的视角看来都是随机的, 因此可以保证方案的安全性.

    KK13的文章中的一个重要结论是: 一个最小码距为\(\lambda\)的编码\(C:\{0,1\}^\ell\to \{0,1\}^k\), 通过\(k\)次Base OT, 可以给出一个(随机)1-out-of-\(2^\ell\)的OT扩展协议, 这里的最小码距与安全性相关, 通常取为计算安全参数\(\lambda\). 他们指出, 通过使用最小码距为128的Walsh-Hadamard码\(C:\{0,1\}^8\to\{0,1\}^{256}\), 可以给出一个随机1-out-of-256 OT扩展协议, 这是一个半诚实安全的协议.

    此外, Orru, Orsini和Scholl于2016年的工作中7指出, 通过使用最小码距为171的BCH码\(C:\{0,1\}^{76}\to \{0,1\}^{512}\), 可以给出一个随机1-out-of-\(2^{76}\) OT扩展协议, 他们同时给出了半诚实安全和恶意安全下的版本.

    同年的CCS会议上, Kolesnikov, Kumaresan, Rosulek和Trieu的工作8中指出, 在半诚实模型下, 我们不需要编码\(C\)的线性性质, 由于协议过程不需要译码, 因此也不需要\(C\)的纠错性质, 而只要\(C\)能以压倒性概率保证汉明重量大于等于计算安全参数即可, 因此可以使用任意输入长度的伪随机函数\(C:\{0,1\}^{\color{red} *}\to \{0,1\}^{\sim480}\)来取代编码\(C\), 这样, 我们可以构造一个半诚实安全的随机\(\infty\)-out-of-1 OT扩展协议, 这里的伪随机函数\(C\)也被称为伪随机编码(Pseudo-Random Code, PRC).

    性能比较

    以下是1-out-of-2和1-out-of-\(N\) OT扩展协议在不同安全模型下的对比. 结论: OT是廉价的!

    相关代码参见Github: osu-crypto/libOTe: A fast, portable, and easy to use Oblivious Transfer Library (github.com).

    参考文献

    1. Russell Impagliazzo, Steven Rudich. Limits on the Provable Consequences of One-Way Permutations. STOC'89. ↩

    2. Donald Beaver. Efficient Multiparty Protocols Using Circuit Randomization. CRYPTO 1991. ↩

    3. Donald Beaver. Correlated pseudorandomness and the complexity of private computations. STOC'96. ↩

    4. Yuval Ishai, Joe Kilian, Kobbi Nissim, Erez Petrank. Extending Oblivious Transfers Efficiently. CRYPTO 2003. ↩

    5. Marcel Keller, Emmanuela Orsini, Peter Scholl. Actively Secure OT Extension with Optimal Overhead. CRYPTO 2015. ↩

    6. Vladimir Kolesnikov, Ranjit Kumaresan. Improved OT Extension for Transferring Short Secrets. CRYPTO 2013. ↩

    7. Michele Orrù, Emmanuela Orsini, Peter Scholl. Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection. CT-RSA 2017. ↩

    8. Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu. Efficient Batched Oblivious PRF with Applications to Private Set Intersection. CCS'16. ↩


    本文标题:     不经意传输及其优化方案
    本文作者: 云中雨雾
    本文链接: https://weiviming.github.io/16237676401097.html
    本站文章采用 知识共享署名4.0 国际许可协议进行许可
    除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
    最后编辑时间: 2021-06-15T22:34:00+08:00