参考文献：
可以基于公钥加密，来构造不经意传输协议。构造如下：
在描述 多方协议 之前，先定义两种安全参数：
在混淆电路的计算中，假设Bob的输入为 m m m比特，那么就需要与Alice利用 m m m次OT协议来获得对应的标签和选择比特。往往 m m m是多项式长度的，因此需要对应次数的公钥加密，然而公钥加密的开销巨大。我们希望利用较少次数的OT，就可以达成多项式次OT的效果。
Beaver给出了一种方案：
在 ideal world 里， F F F是可信第三方。在 real world 里，可以通过混淆电路来实现它： S S S构建 F F F对应的 GC 发送给 R R R， S S S的输入为 X , b ′ X,b' X,b′（不需要OT）， R R R的输入仅仅为 r r r（需要 κ kappa κ次OT）， R R R计算电路获得 x i b i x_i^{b_i} xibi（实现了 m m m次OT）。
也就是说，只需要 κ kappa κ次公钥操作，就存在一种方案来成批地实现 m = p o l y ( κ ) m=poly(kappa) m=poly(κ)次OT协议。
然而，Beaver的构造更多是理论意义上的，因为 F F F对应的 GC 过大，实际上计算很低效。 Ishai 等人在 OT 的基础上仅仅添加了对称操作（ symmetric-key operations），利用 k k k次 base-OT，达成了 m ≫ k m gg k m≫k次的高效 OT：
R R R的选择比特串（choice bits）为 r ∈ { 0 , 1 } m r in {0,1}^m r∈{0,1}m， S S S的选择比特串为 s ∈ { 0 , 1 } k s in {0,1}^k s∈{0,1}k，且 m ≫ k m gg k m≫k
R R R随机选择两个矩阵 T , U ∈ F 2 m × k T,U in mathbb F_2^{m times k} T,U∈F2m×k，满足
T = [ t 1 t 2 ⋮ t m ] , U = [ u 1 u 2 ⋮ u m ] , T ⊕ U = [ r 1 ⋅ 1 k r 2 ⋅ 1 k ⋮ r m ⋅ 1 k ] T= begin{bmatrix} t_1\ t_2\ vdots\ t_m end{bmatrix},,,, U= begin{bmatrix} u_1\ u_2\ vdots\ u_m end{bmatrix},,,, T oplus U = begin{bmatrix} r_1 cdot 1^k\ r_2 cdot 1^k\ vdots\ r_m cdot 1^k\ end{bmatrix} T=⎣ ⎡t1t2⋮tm⎦ ⎤,U=⎣ ⎡u1u2⋮um⎦ ⎤,T⊕U=⎣ ⎡r1⋅1kr2⋅1k⋮rm⋅1k⎦ ⎤
这里的 ⋅ cdot ⋅是向量数乘， t i , u i ∈ { 0 , 1 } k t_i,u_i in {0,1}^k ti,ui∈{0,1}k是行向量（下角标代表行向量，上角标代表列向量）。换个方向看，就是
U = T + [ r r ⋯ r ] ⏟ k U = T + underbrace{ left[ r,, r,, cdots,, r right] }_{k} U=T+k [rr⋯r]
S S S根据 s s s，和 R R R一起执行 k k k次OT协议，挑选列向量：如果 s i = 0 s_i=0 si=0，那么获得 T T T的第 i i i列 t i ∈ { 0 , 1 } m t^i in {0,1}^m ti∈{0,1}m；否则，获得 U U U的第 i i i列 u i ∈ { 0 , 1 } m u^i in {0,1}^m ui∈{0,1}m；将获得的向量排成矩阵 Q ∈ F 2 m × k Q in mathbb F_2^{m times k} Q∈F2m×k，
Q = [ t 1 ⊕ ( s 1 ⋅ r ) t 2 ⊕ ( s 2 ⋅ r ) ⋯ t k ⊕ ( s k ⋅ r ) ] Q = begin{bmatrix} t^1 oplus (s_1 cdot r) & t^2 oplus (s_2 cdot r) & cdots & t^k oplus (s_k cdot r) end{bmatrix} Q=[t1⊕(s1⋅r)t2⊕(s2⋅r)⋯tk⊕(sk⋅r)]
换个方向看，
Q = [ t 1 ⊕ ( r 1 ⋅ s ) t 2 ⊕ ( r 2 ⋅ s ) ⋮ t m ⊕ ( r m ⋅ s ) ] Q = begin{bmatrix} t_1 oplus (r_1 cdot s)\ t_2 oplus (r_2 cdot s)\ vdots\ t_m oplus (r_m cdot s)\ end{bmatrix} Q=⎣ ⎡t1⊕(r1⋅s)t2⊕(r2⋅s)⋮tm⊕(rm⋅s)⎦ ⎤
这里， q i = t i q_i=t_i qi=ti或者 q i ⊕ s = t i q_i oplus s=t_i qi⊕s=ti，取决于 r i r_i ri
令 H : { 0 , 1 } k → { 0 , 1 } n H:{0,1}^k to {0,1}^n H:{0,1}k→{0,1}n是ROM，给定 m m 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 S S分别加密两者：
c i 0 = x i 0 ⊕ H ( q i ) c i 1 = x i 1 ⊕ H ( q j ⊕ s ) c_i^0=x_i^0 oplus H(q_i)\c_i^1=x_i^1 oplus H(q_j oplus s) ci0=xi0⊕H(qi)ci1=xi1⊕H(qj⊕s)
将这 2 m 2m 2m个密文发送给 R R R
R R R手里有 t i t_i ti和 r r r，但不知道 s s s，因此只能计算出 H ( t i ) H(t_i) H(ti)，在每一对密文中就只能解密其中一个密文。确切地说是 c i r i c^{r_i}_i ciri：当 r i = 0 r_i=0 ri=0，那么 q i = t i q_i=t_i qi=ti，可以解密 c i 0 c_i^0 ci0得到 x i 0 x_i^0 xi0；当 r i = 1 r_i=1 ri=1，那么 q i = t i ⊕ s q_i=t_i oplus s qi=ti⊕s，可以解密 c i 1 c_i^1 ci1得到 x i 1 x_i^1 xi1
在上述协议中，只有 step 3 使用了 k k k次 base-OT 协议，在 step 5 中实际完成了 m m m次 1 1 1-out-of- 2 2 2 OT 协议。
一般地，选取 k = κ k = kappa k=κ
Kolesnikov 和 Kumaresan 指出，INKP本质上使用了一个编码方案， k k k重复码（repetition code）：将信息 r i ∈ { 0 , 1 } r_i in {0,1} ri∈{0,1}编码为 e n c o d e ( r i ) = r i ⋅ 1 k encode(r_i)=r_i cdot 1^k encode(ri)=ri⋅1k
如果我们使用长度为 k k k的 l l l维线性纠错码 C C C，那么就可以构造出 1 1 1-out-of- 2 l 2^l 2l OT协议：
R R R的选择比特串（choice bits）为矩阵 r ∈ { 0 , 1 } m × l r in {0,1}^{m times l} r∈{0,1}m×l， S S S的选择比特串为 s ∈ { 0 , 1 } k s in {0,1}^k s∈{0,1}k，且 m ≫ k m gg k m≫k
R R R随机选择两个矩阵 T , U ∈ F 2 m × k T,U in mathbb F_2^{m times k} T,U∈F2m×k，满足
T = [ t 1 t 2 ⋮ t m ] , U = [ u 1 u 2 ⋮ u m ] , T ⊕ U = [ C ( r 1 ) C ( r 2 ) ⋮ C ( r m ) ] = C ( r ) T=begin{bmatrix} t_1\ t_2\ vdots\ t_m end{bmatrix},,,, U=begin{bmatrix} u_1\ u_2\ vdots\ u_m end{bmatrix},,,, T oplus U =begin{bmatrix} C(r_1)\ C(r_2)\ vdots\ C(r_m)\ end{bmatrix} = C(r) T=⎣ ⎡t1t2⋮tm⎦ ⎤,U=⎣ ⎡u1u2⋮um⎦ ⎤,T⊕U=⎣ ⎡C(r1)C(r2)⋮C(rm)⎦ ⎤=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 C(r) = V C(r)=V，那么换个方向，
U = T + [ V 1 V 2 ⋯ V k ] U = T + left[ V^1,, V^2,, cdots,, V^k right] U=T+[V1V2⋯Vk]
S S S根据 s s s，和 R R R一起执行 k k k次OT协议，挑选列向量：如果 s i = 0 s_i=0 si=0，那么获得 T T T的第 i i i列 t i ∈ { 0 , 1 } m t^i in {0,1}^m ti∈{0,1}m；否则，获得 U U U的第 i i i列 u i ∈ { 0 , 1 } m u^i in {0,1}^m ui∈{0,1}m；将获得的向量排成矩阵 Q ∈ F 2 m × k Q in mathbb F_2^{m times k} Q∈F2m×k，
Q = [ t 1 ⊕ ( s 1 ⋅ V 1 ) t 2 ⊕ ( s 2 ⋅ V 2 ) ⋯ t k ⊕ ( s k ⋅ V k ) ] Q =begin{bmatrix} 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{bmatrix} Q=[t1⊕(s1⋅V1)t2⊕(s2⋅V2)⋯tk⊕(sk⋅Vk)]
这里的 ⋅ cdot ⋅是向量数乘。换个方向看，
Q = [ t 1 ⊕ ( V 1 ∧ s ) t 2 ⊕ ( V 2 ∧ s ) ⋮ t m ⊕ ( V m ∧ s ) ] = [ t 1 ⊕ ( C ( r 1 ) ∧ s ) t 2 ⊕ ( C ( r 2 ) ∧ s ) ⋮ t m ⊕ ( C ( r m ) ∧ s ) ] Q =begin{bmatrix} t_1 oplus (V_1 wedge s)\ t_2 oplus (V_2 wedge s)\ vdots\ t_m oplus (V_m wedge s)\ end{bmatrix} =begin{bmatrix} t_1 oplus (C(r_1) wedge s)\ t_2 oplus (C(r_2) wedge s)\ vdots\ t_m oplus (C(r_m) wedge s)\ end{bmatrix} Q=⎣ ⎡t1⊕(V1∧s)t2⊕(V2∧s)⋮tm⊕(Vm∧s)⎦ ⎤=⎣ ⎡t1⊕(C(r1)∧s)t2⊕(C(r2)∧s)⋮tm⊕(C(rm)∧s)⎦ ⎤
这里的 ∧ wedge ∧是按位与（bitwise-AND）
令 H : { 0 , 1 } k → { 0 , 1 } n H:{0,1}^k to {0,1}^n H:{0,1}k→{0,1}n是ROM，给定 m m 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 S S分别加密它们：
c i 0 = x i 0 ⊕ H ( q i ⊕ ( C ( 0 ) ∧ s ) ) c i 1 = x i 1 ⊕ H ( q i ⊕ ( C ( 1 ) ∧ s ) ) ⋮ c i 2 l − 1 = x i 2 l − 1 ⊕ H ( q i ⊕ ( C ( 2 l − 1 ) ∧ s ) ) begin{aligned} 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))\ & vdots\ c_i^{2^l-1} &= x_i^{2^l-1} oplus H(q_i oplus (C(2^l-1) wedge s))\ end{aligned} ci0ci1ci2l−1=xi0⊕H(qi⊕(C(0)∧s))=xi1⊕H(qi⊕(C(1)∧s))⋮=xi2l−1⊕H(qi⊕(C(2l−1)∧s))
然后将这 m × 2 l m times 2^l m×2l个密文发送给 R R R
R R R手里有 t i t_i ti和 r r r，但不知道 s s s，因此只能计算出 H ( t i ) H(t_i) H(ti)，在每一组的 2 l 2^l 2l个密文中只能解密其中 1 1 1个密文。确切地说是 c i r i c^{r_i}_i ciri：
x i r i = c i r i ⊕ H ( q i ⊕ ( C ( r i ) ∧ s ) ) = c i r i ⊕ H ( t 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) xiri=ciri⊕H(qi⊕(C(ri)∧s))=ciri⊕H(ti)
对于其他的密文，由于 R R R不掌握 s s s，因此无法预测密钥 H ( q i ⊕ ( C ( r i ′ ∣ r i ′ ≠ r i ) ∧ s ) ) H(q_i oplus (C(r_i' | r_i' neq r_i) wedge s)) H(qi⊕(C(ri′∣ri′=ri)∧s))的值。假设线性码 C C C的极小距离是 κ kappa κ，那么 d i s t [ C ( r i ′ ) , C ( r i ) ] ≥ κ dist[C(r_i'),C(r_i)] ge kappa dist[C(ri′),C(ri)]≥κ，只有猜对这 κ kappa κ个位置的 s j ∈ { 0 , 1 } s_j in {0,1} sj∈{0,1}的比特值，敌手才能够计算出 r i ′ r_i' ri′对应的密钥，复杂度 O ( 2 κ ) O(2^kappa) O(2κ)是指数级。
在 KK 方案中，仅仅花费了 k k k次 1 1 1-out-of- 2 2 2 base-OT协议，但实际上实现了 m = p o l y ( κ ) m=poly(kappa) m=poly(κ)次的 1 1 1-out-of- 2 l 2^l 2l OT协议！
为了适配更高效的底层编码 C C C，我们需要更大的线性空间，可设置 k = 2 κ k=2kappa k=2κ
Kolesnikov 等人发现，实际上编码方案 C C C并不需要纠错码的全部性质：
伪随机码 (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 ′ r,r' r,r′，使得汉明重量很小，即 w t [ C ( r ) ⊕ C ( r ′ ) ] < κ wt[C(r) oplus C(r')] < kappa wt[C(r)⊕C(r′)]<κ；当 k = 4 κ k=4kappa k=4κ时，随机函数就 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 S S都可以计算出对应的秘密 H ( q i ⊕ ( C ( r ) ∧ s ) ) H(q_i oplus (C(r) wedge s)) H(qi⊕(C(r)∧s))，那么利用 KK 协议就获得了 1 1 1-out-of- ∞ infty ∞ OT协议。
上述的OT协议可以视为一批 Oblivious PRF：映射 F : r ↦ H ( q ⊕ ( C ( r ) ∧ s ) ) F:r mapsto H(q oplus (C(r) wedge s)) F:r↦H(q⊕(C(r)∧s))， S S S拥有秘密 s s s， R R R的输入是 r r r，且函数的输出是伪随机的。
对于每一组的 ∞ infty ∞个秘密， R R R只知道其中的 1 1 1个函数值（ r i r_i ri对应的）：
F ( ( q i , s ) , r i ) = H ( q i ⊕ ( C ( r i ) ∧ s ) ) = H ( t i ) F((q_i,s),r_i) = H(q_i oplus (C(r_i) wedge s)) = H(t_i) F((qi,s),ri)=H(qi⊕(C(ri)∧s))=H(ti)
确切地说其实是知道 t i t_i ti，但这并不影响 R R R对其他的函数值 F ( ( q i , s ) , r i ′ ∣ r i ′ ≠ r i ) F((q_i,s),r_i'|r_i' neq r_i) F((qi,s),ri′∣ri′=ri)的一无所知。
但是 r i r_i ri 对应的 t i t_i ti 不是 R R R 自己生成的么？还有怎么计算其他 r i ′ r_i' ri′ 的函数值呢？看不懂了 (╯︵╰)
同时根据OT协议的安全要求， S S S也不知道 R R R输入的 r i r_i ri
这里是一批次同时计算 m m m个OPRF的协议，这 m m m个OPRF实例都共享 S S S的同一个密钥 s s s以及伪随机码 C C C
细节还请看 Kolesnikov et al. (2016) 的论文吧~~
本文发布于:2024-01-29 06:56:37，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170648260113506.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
