注册页面模板,重庆seo培训,专业网站设计公司排行榜,营销型网站建设哪里好在安全多方计算中#xff08;MPC#xff09;中#xff0c;算术秘密分享是最基础的机制。一直有在接触#xff0c;但是一直没有整理清楚最基础的加法和乘法计算流程。
算术秘密分享
概念#xff1a; 一个位宽为 l l l-bit的数 x x x#xff0c;被拆分为两个在 Z 2 l \ma…在安全多方计算中MPC中算术秘密分享是最基础的机制。一直有在接触但是一直没有整理清楚最基础的加法和乘法计算流程。
算术秘密分享
概念 一个位宽为 l l l-bit的数 x x x被拆分为两个在 Z 2 l \mathbb{Z}_{2^l} Z2l环上的数之和。 形式化描述 对于一个位宽为 l l l-bit的数 x x x其算术秘密分享是 ⟨ x ⟩ A \langle x\rangle^A ⟨x⟩A则满足 x ≡ ⟨ x ⟩ 0 A ⟨ x ⟩ 1 A m o d 2 l x \equiv \langle x\rangle^A_0\langle x\rangle^A_1~\mathrm{mod}~2^l x≡⟨x⟩0A⟨x⟩1A mod 2l其中 ⟨ x ⟩ 0 A , ⟨ x ⟩ 1 A ∈ Z 2 l \langle x\rangle^A_0, \langle x\rangle^A_1 \in \mathbb{Z}_{2^l} ⟨x⟩0A,⟨x⟩1A∈Z2l。 Share分享算法 P i P_i Pi生成随机数 r ∈ R Z 2 l r\in_R\mathbb{Z}_{2^l} r∈RZ2l令 ⟨ x ⟩ i A x − r \langle x \rangle^A_ix-r ⟨x⟩iAx−r作为自己的share并将随机数 r r r发给另一方 P 1 − i P_{1-i} P1−i即 ⟨ x ⟩ 1 − i A r \langle x \rangle^A_{1-i}r ⟨x⟩1−iAr。 Reconstruct重构算法 P 1 − i P_{1-i} P1−i将自己的share发给 P i P_i Pi然后 P i P_i Pi计算 x ⟨ x ⟩ 0 A ⟨ x ⟩ 1 A x\langle x\rangle^A_0\langle x\rangle^A_1 x⟨x⟩0A⟨x⟩1A重构真实的 x x x值。
算术秘密分享的加法
加法非常简单两方在本地直接计算share的加法即满足真实值的加法。 当计算 z x y zxy zxy时 P i P_i Pi在本地计算 ⟨ z ⟩ i A ⟨ x ⟩ i A ⟨ y ⟩ i A \langle z\rangle^A_i\langle x\rangle^A_i\langle y\rangle^A_i ⟨z⟩iA⟨x⟩iA⟨y⟩iA。 本地可加性很好证明 P 0 P_0 P0计算 ⟨ z ⟩ 0 A ⟨ x ⟩ 0 A ⟨ y ⟩ 0 A \langle z\rangle^A_0\langle x\rangle^A_0\langle y\rangle^A_0 ⟨z⟩0A⟨x⟩0A⟨y⟩0A同时 P 1 P_1 P1计算 ⟨ z ⟩ 1 A ⟨ x ⟩ 1 A ⟨ y ⟩ 1 A \langle z\rangle^A_1\langle x\rangle^A_1\langle y\rangle^A_1 ⟨z⟩1A⟨x⟩1A⟨y⟩1A于是 z ⟨ z ⟩ 0 A ⟨ z ⟩ 1 A ⟨ x ⟩ 0 A ⟨ y ⟩ 0 A ⟨ x ⟩ 1 A ⟨ y ⟩ 1 A x y z \langle z\rangle^A_0\langle z\rangle^A_1\langle x\rangle^A_0\langle y\rangle^A_0\langle x\rangle^A_1\langle y\rangle^A_1xy z⟨z⟩0A⟨z⟩1A⟨x⟩0A⟨y⟩0A⟨x⟩1A⟨y⟩1Axy因此成立。 因此在MPC中秘密分享的加法只需简单的本地加法不会引入任何通信开销。
算术秘密分享的乘法
相比于加法乘法则复杂很多需要依靠双方的通信来实现。 当计算 z x ⋅ y zx\cdot y zx⋅y时需要依赖预处理阶段生成的乘法三元组Beaver Triple c a ⋅ b ca\cdot b ca⋅b注意 a , b , c a, b, c a,b,c均与真实的输入 x , y x, y x,y无关。 下面是基于Beaver Triple计算秘密分享乘法的流程 P i P_i Pi本地计算 ⟨ e ⟩ i A ⟨ x ⟩ i A − ⟨ a ⟩ i A \langle e\rangle^A_i\langle x\rangle^A_i-\langle a\rangle^A_i ⟨e⟩iA⟨x⟩iA−⟨a⟩iA和 ⟨ f ⟩ i A ⟨ y ⟩ i A − ⟨ b ⟩ i A \langle f\rangle^A_i\langle y\rangle^A_i-\langle b\rangle^A_i ⟨f⟩iA⟨y⟩iA−⟨b⟩iA双方共同计算重构出 e ⟨ e ⟩ 0 A ⟨ e ⟩ 1 A x − a e\langle e\rangle^A_0\langle e\rangle^A_1x-a e⟨e⟩0A⟨e⟩1Ax−a和 f ⟨ f ⟩ 0 A ⟨ f ⟩ 1 A y − b f\langle f\rangle^A_0\langle f\rangle^A_1y-b f⟨f⟩0A⟨f⟩1Ay−b P i P_i Pi本地计算 ⟨ z ⟩ i A i ⋅ e ⋅ f f ⋅ ⟨ a ⟩ i A e ⋅ ⟨ b ⟩ i A ⟨ c ⟩ i A \langle z\rangle^A_ii\cdot e\cdot ff\cdot \langle a\rangle^A_ie\cdot \langle b\rangle^A_i\langle c\rangle^A_i ⟨z⟩iAi⋅e⋅ff⋅⟨a⟩iAe⋅⟨b⟩iA⟨c⟩iA最后重构输出 z ⟨ z ⟩ 0 A ⟨ z ⟩ 1 A z\langle z\rangle^A_0\langle z\rangle^A_1 z⟨z⟩0A⟨z⟩1A。
证明 ⟨ z ⟩ 0 A f ⋅ ⟨ a ⟩ 0 A e ⋅ ⟨ b ⟩ 0 A ⟨ c ⟩ 0 A \langle z\rangle^A_0f\cdot \langle a\rangle^A_0e\cdot \langle b\rangle^A_0\langle c\rangle^A_0 ⟨z⟩0Af⋅⟨a⟩0Ae⋅⟨b⟩0A⟨c⟩0A ⟨ z ⟩ 1 A e ⋅ f f ⋅ ⟨ a ⟩ 1 A e ⋅ ⟨ b ⟩ 1 A ⟨ c ⟩ 1 A \langle z\rangle^A_1e\cdot ff\cdot \langle a\rangle^A_1e\cdot \langle b\rangle^A_1\langle c\rangle^A_1 ⟨z⟩1Ae⋅ff⋅⟨a⟩1Ae⋅⟨b⟩1A⟨c⟩1A z ⟨ z ⟩ 0 A ⟨ z ⟩ 1 A e ⋅ f a ⋅ f e ⋅ b c ( x − a ) ( y − b ) a ( y − b ) ( x − a ) b c x y − b x − a y a b a y − a b b x − a b a b x y z\langle z\rangle^A_0\langle z\rangle^A_1\\~~~e\cdot fa\cdot fe\cdot bc\\~~~(x-a)(y-b)a(y-b)(x-a)bc\\~~~xy-bx-ayabay-abbx-abab\\~~~xy z⟨z⟩0A⟨z⟩1A e⋅fa⋅fe⋅bc (x−a)(y−b)a(y−b)(x−a)bc xy−bx−ayabay−abbx−abab xy 故成立。
Beaver Triple的生成
上面已经介绍了基于Beaver Triple计算乘法的流程但是需要注意 c a b cab cab也是秘密分享的形式 c a b ( ⟨ a ⟩ 0 A ⟨ a ⟩ 1 A ) ( ⟨ b ⟩ 0 A ⟨ b ⟩ 1 A ) ⟨ a ⟩ 0 A ⟨ b ⟩ 0 A ⟨ a ⟩ 1 A ⟨ b ⟩ 1 A ⟨ a ⟩ 0 A ⟨ b ⟩ 1 A ⟨ a ⟩ 1 A ⟨ b ⟩ 0 A cab\\~~~(\langle a\rangle^A_0\langle a\rangle^A_1)(\langle b\rangle^A_0\langle b\rangle^A_1)\\~~~\langle a\rangle^A_0 \langle b\rangle^A_0\langle a\rangle^A_1 \langle b\rangle^A_1\langle a\rangle^A_0\langle b\rangle^A_1\langle a\rangle^A_1\langle b\rangle^A_0 cab (⟨a⟩0A⟨a⟩1A)(⟨b⟩0A⟨b⟩1A) ⟨a⟩0A⟨b⟩0A⟨a⟩1A⟨b⟩1A⟨a⟩0A⟨b⟩1A⟨a⟩1A⟨b⟩0A 可以看到第一项 ⟨ a ⟩ 0 A ⟨ b ⟩ 0 A \langle a\rangle^A_0 \langle b\rangle^A_0 ⟨a⟩0A⟨b⟩0A和第二项 ⟨ a ⟩ 1 A ⟨ b ⟩ 1 A \langle a\rangle^A_1 \langle b\rangle^A_1 ⟨a⟩1A⟨b⟩1A均可以在 P 0 , P 1 P_0, P_1 P0,P1本地计算因此无需通信。而重点就在于后两项 ⟨ a ⟩ 0 A ⟨ b ⟩ 1 A , ⟨ a ⟩ 1 A ⟨ b ⟩ 0 A \langle a\rangle^A_0\langle b\rangle^A_1, \langle a\rangle^A_1\langle b\rangle^A_0 ⟨a⟩0A⟨b⟩1A,⟨a⟩1A⟨b⟩0A两个share分别在两方因此必然引入通信通常我们将这两项称作“交叉项”或CrossTerm。 那么Beaver Triple的生成本质上也就是解决交叉项计算的问题。下面介绍两种常用的计算方式
基于同态加密HE的Beaver Triple生成 流程如下 P 0 P_0 P0将 E n c ( ⟨ a ⟩ 0 A ) Enc(\langle a\rangle^A_0) Enc(⟨a⟩0A)和 E n c ( ⟨ b ⟩ 0 A ) Enc(\langle b\rangle^A_0) Enc(⟨b⟩0A)发给 P 1 P_1 P1 P 1 P_1 P1生成一个随机数 r r r计算 d E n c ( ⟨ a ⟩ 0 A ) ⟨ b ⟩ 1 A × E n c ( ⟨ b ⟩ 0 A ) ⟨ a ⟩ 1 A × E n c ( r ) dEnc(\langle a\rangle^A_0)^{\langle b\rangle^A_1} \times Enc(\langle b\rangle^A_0)^{\langle a\rangle^A_1} \times Enc(r) dEnc(⟨a⟩0A)⟨b⟩1A×Enc(⟨b⟩0A)⟨a⟩1A×Enc(r)然后将 d d d发给 P 0 P_0 P0 P 0 P_0 P0计算 ⟨ c ⟩ 0 A ⟨ a ⟩ 0 A ⟨ b ⟩ 0 A D e c ( d ) ⟨ a ⟩ 0 A ⟨ b ⟩ 0 A ⟨ a ⟩ 0 A ⟨ b ⟩ 1 A ⟨ a ⟩ 1 A ⟨ b ⟩ 0 A r \langle c\rangle^A_0\langle a\rangle^A_0\langle b\rangle^A_0Dec(d)\langle a\rangle^A_0\langle b\rangle^A_0\langle a\rangle^A_0 \langle b\rangle^A_1\langle a\rangle^A_1 \langle b\rangle^A_0r ⟨c⟩0A⟨a⟩0A⟨b⟩0ADec(d)⟨a⟩0A⟨b⟩0A⟨a⟩0A⟨b⟩1A⟨a⟩1A⟨b⟩0Ar P 1 P_1 P1计算 ⟨ c ⟩ 1 A ⟨ a ⟩ 1 A ⟨ b ⟩ 1 A − r \langle c\rangle^A_1\langle a\rangle^A_1\langle b\rangle^A_1-r ⟨c⟩1A⟨a⟩1A⟨b⟩1A−r。
证明 c ⟨ c ⟩ 0 A ⟨ c ⟩ 1 A ⟨ a ⟩ 0 A ⟨ b ⟩ 0 A ⟨ a ⟩ 1 A ⟨ b ⟩ 1 A ⟨ a ⟩ 0 A ⟨ b ⟩ 1 A ⟨ a ⟩ 1 A ⟨ b ⟩ 0 A a b c\langle c\rangle^A_0\langle c\rangle^A_1\\~~~\langle a\rangle^A_0 \langle b\rangle^A_0\langle a\rangle^A_1 \langle b\rangle^A_1\langle a\rangle^A_0\langle b\rangle^A_1\langle a\rangle^A_1\langle b\rangle^A_0\\~~~ab c⟨c⟩0A⟨c⟩1A ⟨a⟩0A⟨b⟩0A⟨a⟩1A⟨b⟩1A⟨a⟩0A⟨b⟩1A⟨a⟩1A⟨b⟩0A ab 故成立。
如上采用的加密算法Enc是Pailler同态加密算法其同态性如下
明文加法 密文乘法明文乘法 密文指数幂
因此在上面流程的第3步中Dec(d)时才会将乘法转成加法指数幂转成乘法。关于背后的原理参考我的另一篇博客【密码学基础】半/全同态加密算法基础学习笔记
基于不经意传输OT的Beaver Triple生成 另一种常用的方式是基于COT相关性不经意传输的方式。 下面是计算交叉项 ⟨ a ⟩ 0 A ⟨ b ⟩ 1 A \langle a\rangle^A_0\langle b\rangle^A_1 ⟨a⟩0A⟨b⟩1A的流程
在 P 0 , P 1 P_0, P_1 P0,P1之间建立COT协议通信其中 P 0 P_0 P0作为发送方 P 1 P_1 P1作为接收方在第 i i i轮的COT通信中 P 1 P_1 P1输入 ⟨ b ⟩ 1 A [ i ] \langle b\rangle^A_1[i] ⟨b⟩1A[i]作为自己的选择比特 P 0 P_0 P0输入相关性函数 f Δ i ( x ) ( ⟨ a ⟩ 0 A ⋅ 2 i − x ) m o d 2 l f_{\Delta_i}(x)(\langle a\rangle^A_0 \cdot 2^i - x)~\mathrm{mod}~2^l fΔi(x)(⟨a⟩0A⋅2i−x) mod 2l P 0 P_0 P0获得消息对 ( s i , 0 , s i , 1 ) (s_{i, 0}, s_{i, 1}) (si,0,si,1)其中 s i , 0 ∈ R Z 2 l s_{i, 0}\in _R\mathbb{Z}_{2^l} si,0∈RZ2l s i , 1 f Δ i ( s i , 0 ) ( ⟨ a ⟩ 0 A ⋅ 2 i − s i , 0 ) m o d 2 l s_{i, 1}f_{\Delta_i}(s_{i, 0})(\langle a\rangle^A_0 \cdot 2^i - s_{i, 0})~\mathrm{mod}~2^l si,1fΔi(si,0)(⟨a⟩0A⋅2i−si,0) mod 2l P 1 P_1 P1获得 s i , ⟨ b ⟩ 1 A [ i ] ( ⟨ b ⟩ 1 A [ i ] ⋅ ⟨ a ⟩ 0 A ⋅ 2 i − s i , 0 ) m o d 2 l s_{i, \langle b\rangle^A_1[i]}(\langle b\rangle^A_1[i]\cdot \langle a\rangle^A_0 \cdot 2^i - s_{i, 0})~\mathrm{mod}~2^l si,⟨b⟩1A[i](⟨b⟩1A[i]⋅⟨a⟩0A⋅2i−si,0) mod 2l ⟨ u ⟩ 0 A ( ∑ i 0 l s i , 0 ) m o d 2 l \langle u\rangle^A_0(\sum_{i0}^ls_{i, 0})~\mathrm{mod}~2^l ⟨u⟩0A(∑i0lsi,0) mod 2l, ⟨ u ⟩ 1 A ( ∑ i 0 l s i , ⟨ b ⟩ 1 A [ i ] ) m o d 2 l \langle u\rangle^A_1(\sum_{i0}^l s_{i, \langle b\rangle^A_1[i]})~\mathrm{mod}~2^l ⟨u⟩1A(∑i0lsi,⟨b⟩1A[i]) mod 2l
证明 ⟨ a ⟩ 0 A ⟨ b ⟩ 1 A ⟨ u ⟩ 0 A ⟨ u ⟩ 1 A ∑ i 0 l s i , 0 ∑ i 0 l s i , ⟨ b ⟩ 1 A [ i ] ∑ i 0 l ( s i , 0 ⟨ b ⟩ 1 A [ i ] ⋅ ⟨ a ⟩ 0 A ⋅ 2 i − s i , 0 ) ∑ i 0 l ( ⟨ b ⟩ 1 A [ i ] ⋅ ⟨ a ⟩ 0 A ⋅ 2 i ) \langle a\rangle^A_0 \langle b\rangle^A_1\langle u\rangle^A_0\langle u\rangle^A_1\\~~~~~~~~~~~~~~~~\sum_{i0}^ls_{i, 0}\sum_{i0}^l s_{i, \langle b\rangle^A_1[i]}\\~~~~~~~~~~~~~~~~\sum_{i0}^l(s_{i, 0}\langle b\rangle^A_1[i]\cdot \langle a\rangle^A_0 \cdot 2^i - s_{i, 0})\\~~~~~~~~~~~~~~~~\sum_{i0}^l(\langle b\rangle^A_1[i]\cdot \langle a\rangle^A_0 \cdot 2^i) ⟨a⟩0A⟨b⟩1A⟨u⟩0A⟨u⟩1A ∑i0lsi,0∑i0lsi,⟨b⟩1A[i] ∑i0l(si,0⟨b⟩1A[i]⋅⟨a⟩0A⋅2i−si,0) ∑i0l(⟨b⟩1A[i]⋅⟨a⟩0A⋅2i) 注到这一步已经非常直观了其实就是在二进制中做乘法一个数的每一位去乘另一个数然后移位乘上对应位的2的幂次累加对每一位的乘法结果求和。
举例 假设 ⟨ a ⟩ 0 A 3 , ⟨ b ⟩ 1 A 5 ( 101 ) 2 \langle a\rangle^A_03, \langle b\rangle^A_15(101)_2 ⟨a⟩0A3,⟨b⟩1A5(101)2于是 ⟨ a ⟩ 0 A ⟨ b ⟩ 1 A ⟨ u ⟩ 0 A ⟨ u ⟩ 1 A ∑ i 1 l ( s i , 0 s i , ⟨ b ⟩ 1 A [ i ] ) ∑ i 1 l ( s i , 0 ⟨ b ⟩ 1 A [ i ] ⋅ ⟨ a ⟩ 0 A ⋅ 2 i − s i , 0 ) ∑ i 1 l ( ⟨ b ⟩ 1 A [ i ] ⋅ ⟨ a ⟩ 0 A ⋅ 2 i ) 1 ⋅ 3 ⋅ 2 0 0 ⋅ 3 ⋅ 2 1 1 ⋅ 3 ⋅ 2 2 3 0 12 15 \langle a\rangle^A_0 \langle b\rangle^A_1\langle u\rangle^A_0\langle u\rangle^A_1\\~~~~~~~~~~~~~~~~\sum_{i1}^l (s_{i, 0}s_{i, \langle b\rangle^A_1[i]})\\~~~~~~~~~~~~~~~~\sum_{i1}^l (s_{i, 0}\langle b\rangle^A_1[i]\cdot \langle a\rangle^A_0 \cdot 2^i - s_{i, 0})\\~~~~~~~~~~~~~~~~\sum_{i1}^l (\langle b\rangle^A_1[i]\cdot \langle a\rangle^A_0 \cdot 2^i)\\~~~~~~~~~~~~~~~~1\cdot 3 \cdot 2^00 \cdot 3\cdot 2^11\cdot 3\cdot 2^2\\~~~~~~~~~~~~~~~~3012\\~~~~~~~~~~~~~~~~15 ⟨a⟩0A⟨b⟩1A⟨u⟩0A⟨u⟩1A ∑i1l(si,0si,⟨b⟩1A[i]) ∑i1l(si,0⟨b⟩1A[i]⋅⟨a⟩0A⋅2i−si,0) ∑i1l(⟨b⟩1A[i]⋅⟨a⟩0A⋅2i) 1⋅3⋅200⋅3⋅211⋅3⋅22 3012 15 故计算正确。
