企业网站建设框架图,网站建设人员构成,濮阳市城乡建设管理局网站,黄冈网站建设设计近年来#xff0c;VOLE#xff08;向量不经意线性评估#xff09;被用于构造各种高效安全多方计算协议#xff0c;具有较低的通信复杂度。最近的CipherGPT则是基于VOLE对线性层进行计算。
1 VOLE总体设计
VOLE的功能如下#xff0c;VOLE发送 Δ \Delta Δ和 b b b给send…近年来VOLE向量不经意线性评估被用于构造各种高效安全多方计算协议具有较低的通信复杂度。最近的CipherGPT则是基于VOLE对线性层进行计算。
1 VOLE总体设计
VOLE的功能如下VOLE发送 Δ \Delta Δ和 b b b给sender发送 a a a和 c c c给receiver并且 c , a , b c, a, b c,a,b满足线性关系 c Δ ⋅ a b c\Delta\cdot a b cΔ⋅ab。
现在主流的VOLE是基于LPN (Learning with Parity Noise)假设/问题来构造的。
2 基于LPN假设的VOLE构造
2.1 前置知识
1 LPN假设 LPN是一个重要的抗量子计算的困难问题。事实上解决LPN问题等价于解决编码理论中的随机线性码纠错问题Decoding a random linear code problem。LPN的表述为
随机生成矩阵 A A A随机生成秘密行向量 s s s随机生成错误行向量 e e e满足 H W ( e ) r ⋅ n HW(e)r\cdot n HW(e)r⋅n其中参数 r r r是噪声比率计算向量 b s ⋅ A e bs\cdot Ae bs⋅Ae
则有 ( A , b ) ≈ c ( A ′ , b ′ ) (A, b)\approx _c(A^\prime, b^\prime) (A,b)≈c(A′,b′)其中 ( A ′ , b ′ ) (A^\prime, b^\prime) (A′,b′)是随机生成的。解决LPN问题即使是解决如下问题给定 A , b A, b A,b求解 s , e s, e s,e的值。 在密码实践中为了保证具体的LPN参数设定是困难的通常选取较大的 k k k较大的 n n n以及较小的 r r r。
2 函数秘密分享Functional Secret Sharing, FSS FSS它允许计算 P 0 , P 1 P_0, P_1 P0,P1合作计算某个函数 f f f在某个点上的估值 f ( x ) f(x) f(x)。计算完成后 P 0 P_0 P0得到一份share为 f 0 ( x ) f_0(x) f0(x) P 1 P_1 P1得到另一份share为 f 1 ( x ) f_1(x) f1(x)满足 f ( x ) f 0 ( x ) f 1 ( x ) f(x)f_0(x)f_1(x) f(x)f0(x)f1(x)其中 f 0 ( x ) , f 1 ( x ) f_0(x), f_1(x) f0(x),f1(x)是伪随机的。 FSS形式化定义如下 给定函数 f f fFSS定义了一对算法 ( G e n , E v a l ) (Gen, Eval) (Gen,Eval) F S S . G e n ( 1 λ , f ) FSS.Gen(1^\lambda, f) FSS.Gen(1λ,f)给定安全参数 λ \lambda λ和函数 f f f生成一对密钥 ( K 0 , K 1 ) (K_0, K_1) (K0,K1) F S S . E v a l ( b , K b , x ) FSS.Eval(b, K_b, x) FSS.Eval(b,Kb,x)给定参与方索引 b ∈ { 0 , 1 } b\in \{0, 1\} b∈{0,1}密钥 K b K_b Kb和函数输入 x x x输出 f b ∈ G f_b\in \mathbb G fb∈G G \mathbb G G表示群
由此可见在FSS过程中涉及到AES对称加密。
3 VOLE生成器 VOLE定义了两个算法即 V O L E ( S e t u p , E x p a n d ) VOLE(Setup, Expand) VOLE(Setup,Expand) S e t u p ( 1 λ , F , n , x ) Setup(1^\lambda, \mathbb F, n, x) Setup(1λ,F,n,x)输出一对种子 ( s e e d 0 , s e e d 1 ) (seed_0, seed_1) (seed0,seed1)其中 s e e d 1 seed_1 seed1包含输入 x x x E x p a n d ( σ , s e e d σ ) Expand(\sigma, seed_\sigma) Expand(σ,seedσ)如 σ 0 \sigma0 σ0输出 ( u , v ) (u, v) (u,v)如 σ 1 \sigma1 σ1输出 w w w
于是VOLE满足以下正确性 ( u , v ) ← E x p a n d ( 0 , s e e d 0 ) , w ← E x p a n d ( 1 , s e e d 1 ) (u, v)\leftarrow Expand(0, seed_0), w\leftarrow Expand(1, seed_1) (u,v)←Expand(0,seed0),w←Expand(1,seed1)满足 w u ⋅ x v wu\cdot xv wu⋅xv。
2.2 VOLE的构造方法
现在介绍如何定义Setup和Expand算法直觉就是在Setup中分配给 P 0 , P 1 P_0, P_1 P0,P1的种子 s e e d 0 , s e e d 1 seed_0, seed_1 seed0,seed1就具有某种线性关系同时在Expand时仍保持这种线性关系。
尝试1 Setup构造如下 s e e d 0 ← ( a , b ) ∈ R F k × F k , s e e d 1 ← ( c a ⋅ x b , x ) ∈ F k × F seed_0\leftarrow(a, b)\in _R\mathbb F^k\times \mathbb F^k, seed_1\leftarrow (ca\cdot xb, x)\in \mathbb F^k\times \mathbb F seed0←(a,b)∈RFk×Fk,seed1←(ca⋅xb,x)∈Fk×F 其中 ( a , b ) (a, b) (a,b)是随机生成的因此 c c c也是随机的。 Expand构造如下 随机生成一个矩阵 C ∈ F k × n ( k n ) C\in \mathbb F^{k\times n}(kn) C∈Fk×n(kn)并将 C C C作为公开参数发布出去然后计算 E x p a n d ( 0 , s e e d 0 ) ( a ⋅ C , b ⋅ C ) , E x p a n d ( 1 , s e e d 1 ) c ⋅ C Expand(0, seed_0)(a\cdot C, b\cdot C), Expand(1, seed_1)c\cdot C Expand(0,seed0)(a⋅C,b⋅C),Expand(1,seed1)c⋅C 由此可见Expand保持了 a , b , c a, b, c a,b,c的线性关系并把种子的长度从 k k k扩展到了 n n n。
尝试2 但是上面的构造方式并非伪随机【这里我不是很理解】借助LPN假设来解决这个问题Expand构造如下 E x p a n d ( 0 , s e e d 0 ) ( a ⋅ C μ , b ⋅ C − ν b ) , E x p a n d ( 1 , s e e d 1 ) c ⋅ C ν c Expand(0, seed_0)(a\cdot C\mu, b\cdot C-\nu_b), Expand(1, seed_1)c\cdot C\nu_c Expand(0,seed0)(a⋅Cμ,b⋅C−νb),Expand(1,seed1)c⋅Cνc 根据LPN可知Expand算法的输出是伪随机的【具体原因】但是线性关系难以满足因为这里 ν c ≠ μ ⋅ x − ν b \nu_c \neq \mu\cdot x-\nu_b νcμ⋅x−νb但是如果可以限制 ν c μ ⋅ x − ν b \nu_c \mu\cdot x-\nu_b νcμ⋅x−νb也就是 ν b ν c μ ⋅ x \nu_b\nu_c \mu\cdot x νbνcμ⋅x线性关系就维持住了。幸运的事依靠FSS可以生成伪随机 ν b , ν c \nu_b, \nu_c νb,νc满足这个关系。
正式构造 假设LPN假设中公开参数为 F , k , n , t r n , C ∈ F k × n \mathbb F, k, n, trn, C\in \mathbb F^{k\times n} F,k,n,trn,C∈Fk×n则VOLE生成器 G G G可以定义为 S e t u p ( 1 λ , x ) Setup(1^\lambda, x) Setup(1λ,x)
随机生成 ( a , b ) ∈ F k × F k (a, b)\in \mathbb F^k \times \mathbb F^k (a,b)∈Fk×Fk随机生成 μ ∈ F n \mu\in \mathbb F^n μ∈Fn满足 H W ( μ ) t HW(\mu)t HW(μ)t计算 c a ⋅ x b ca\cdot x b ca⋅xb ( K 0 , K 1 ) ← F S S . G e n ( 1 λ , f ) (K_0, K_1)\leftarrow FSS.Gen(1^\lambda, f) (K0,K1)←FSS.Gen(1λ,f)满足 F S S . E v a l ( 0 , K 0 ) F S S . E v a l ( 1 , K 1 ) x ⋅ μ FSS.Eval(0, K_0)FSS.Eval(1, K_1)x\cdot \mu FSS.Eval(0,K0)FSS.Eval(1,K1)x⋅μ s e e d 0 ← ( K 0 , μ , a , b ) , s e e d 1 ← ( K 1 , x , c ) seed_0\leftarrow (K_0, \mu, a, b), seed_1\leftarrow (K_1, x, c) seed0←(K0,μ,a,b),seed1←(K1,x,c)输出 s e e d 0 , s e e d 1 seed_0, seed_1 seed0,seed1 E x p a n d ( σ , s e e d σ ) Expand(\sigma, seed_\sigma) Expand(σ,seedσ)
若 σ 0 \sigma0 σ0 s e e d 0 ( K 0 , μ , a , b ) seed_0(K_0, \mu, a, b) seed0(K0,μ,a,b)计算 ν 0 ← F S S . E v a l ( 0 , K 0 ) \nu_0\leftarrow FSS.Eval(0, K_0) ν0←FSS.Eval(0,K0)输出 ( u , v ) ← ( a ⋅ C μ , b ⋅ C − ν 0 ) (u, v)\leftarrow (a\cdot C\mu, b\cdot C-\nu_0) (u,v)←(a⋅Cμ,b⋅C−ν0)。即尝试2中的 E x p a n d ( 0 , s e e d 0 ) ( a ⋅ C μ , b ⋅ C − ν 0 ) Expand(0, seed_0)(a\cdot C\mu, b\cdot C-\nu_0) Expand(0,seed0)(a⋅Cμ,b⋅C−ν0)若 σ 1 \sigma1 σ1 s e e d 1 ( K 1 , x , c ) seed_1(K_1, x, c) seed1(K1,x,c)计算 ν 1 ← F S S . E v a l ( 1 , K 1 ) \nu_1\leftarrow FSS.Eval(1, K_1) ν1←FSS.Eval(1,K1)输出 w ← c ⋅ C ν 1 w\leftarrow c\cdot C\nu_1 w←c⋅Cν1。即尝试2中的 E x p a n d ( 1 , s e e d 1 ) c ⋅ C ν 1 Expand(1, seed_1)c\cdot C\nu_1 Expand(1,seed1)c⋅Cν1
值得注意的是 ν 0 , ν 1 \nu_0, \nu_1 ν0,ν1的生成基于FSS在Setup中满足 F S S . E v a l ( 0 , K 0 ) F S S . E v a l ( 1 , K 1 ) x ⋅ μ FSS.Eval(0, K_0)FSS.Eval(1, K_1)x\cdot \mu FSS.Eval(0,K0)FSS.Eval(1,K1)x⋅μ因此很容易得到 ν 0 ν 1 x ⋅ μ \nu_0\nu_1x\cdot \mu ν0ν1x⋅μ故现在的构造方法符合LPN伪随机性并且满足线性关系。
3 VOLE在MPC乘法中的应用
在MPC中安全加法很容易进行只需在本地做加法即可。而乘法则是困难的需要双方进行通信实现。 现在考虑乘法 z x y zxy zxy其中 x x x在 P 0 P_0 P0方 y y y在 P 1 P_1 P1方双方需要联合计算乘法结果。在算术秘密分享机制下双方将自己的输入进行拆分因此计算如下 x y ( ⟨ x ⟩ 0 ⟨ x ⟩ 1 ) ( ⟨ y ⟩ 0 ⟨ y ⟩ 1 ) ⟨ x ⟩ 0 ⟨ y ⟩ 0 ⟨ x ⟩ 1 ⟨ y ⟩ 1 ⟨ x ⟩ 0 ⟨ y ⟩ 1 ⟨ x ⟩ 1 ⟨ y ⟩ 0 xy (\langle x\rangle_0\langle x\rangle_1)(\langle y\rangle_0\langle y\rangle_1)\langle x\rangle_0\langle y\rangle_0\langle x\rangle_1\langle y\rangle_1\langle x\rangle_0\langle y\rangle_1\langle x\rangle_1\langle y\rangle_0 xy(⟨x⟩0⟨x⟩1)(⟨y⟩0⟨y⟩1)⟨x⟩0⟨y⟩0⟨x⟩1⟨y⟩1⟨x⟩0⟨y⟩1⟨x⟩1⟨y⟩0 其中前两项均可以在本地计算而后两项交叉项CrossTerm是MPC计算的重难点。 以 ⟨ x ⟩ 0 ⟨ y ⟩ 1 \langle x\rangle_0\langle y\rangle_1 ⟨x⟩0⟨y⟩1为例借助VOLE让 P 0 P_0 P0计算出 v v v【即上面Expand中的 v b ⋅ C − ν 0 vb\cdot C-\nu_0 vb⋅C−ν0】 让 P 1 P_1 P1计算出 w w w【即上面Expand中的 w c ⋅ C ν 1 wc\cdot C\nu_1 wc⋅Cν1】满足 ⟨ x ⟩ 0 ⟨ y ⟩ 1 w − v \langle x\rangle_0\langle y\rangle_1w-v ⟨x⟩0⟨y⟩1w−v【 w − v ν 0 ν 1 c ⋅ C − b ⋅ C u ⋅ x c ⋅ C − b ⋅ C w-v\nu_0\nu_1c\cdot C-b\cdot Cu\cdot xc\cdot C-b\cdot C w−vν0ν1c⋅C−b⋅Cu⋅xc⋅C−b⋅C其中 C C C公开 b ⋅ C , c ⋅ C b\cdot C, c\cdot C b⋅C,c⋅C分别在两方计算出来是明文了因此 w − v w-v w−v的结果也可算】即可解决交叉项的计算问题。
4 基于VOLE生成器构造VOLE
VOLE生成器本质是一种伪随机数生成器生成的两串伪随机数恰好是线性相关的。 预计算生成随机种子
可信第三方TTP随机生成 r x ∈ F r_x\in \mathbb F rx∈F调用VOLE生成器 G G G计算 ( s e e d 0 , s e e d 1 ) ← S e t u p ( 1 λ , r ) (seed_0, seed_1)\leftarrow Setup(1^\lambda, r) (seed0,seed1)←Setup(1λ,r)将 s e e d 0 seed_0 seed0发给 P 0 P_0 P0将 ( r x , s e e d 1 ) (r_x, seed_1) (rx,seed1)发给 P 1 P_1 P1
预计算生成 ( r u , r v , r w ) (r_u, r_v, r_w) (ru,rv,rw) P 0 P_0 P0计算 ( r u , r v ) ← E x p a n d ( 0 , s e e d 0 ) (r_u, r_v)\leftarrow Expand(0, seed_0) (ru,rv)←Expand(0,seed0) P 1 P_1 P1计算 r w ← E x p a n d ( 1 , s e e d 1 ) r_w\leftarrow Expand(1, seed_1) rw←Expand(1,seed1)
在线计算 现在 P 0 P_0 P0拥有 ( u , v ) (u, v) (u,v) P 1 P_1 P1拥有 x x x【于是我们又回到了最开头那幅图】 P 1 P_1 P1计算 m x ← x − r x m_x\leftarrow x-r_x mx←x−rx并将 m x m_x mx发给 P 0 P_0 P0 P 0 P_0 P0计算 m u ← u − r u , m v ← m x r u v − r v m_u\leftarrow u-r_u, m_v\leftarrow m_xr_uv-r_v mu←u−ru,mv←mxruv−rv并发给 P 1 P_1 P1 P 1 P_1 P1计算 w ← m u x m v r w w\leftarrow m_uxm_vr_w w←muxmvrw
正确性 预计算阶段得到的随机向量满足 r w r u ⋅ r x r v r_wr_u\cdot r_xr_v rwru⋅rxrv于是 P 1 P_1 P1方 w m u x m v r w ( u − r u ) x ( m x r u v − r v ) ( r u ⋅ r x r v ) ( u − r u ) x ( ( x − r x ) r u v − r v ) ( r u ⋅ r x r v ) u x − r u x r u x − r u r x v − r v r u r x r v u x v wm_uxm_vr_w\\~~~~(u-r_u)x(m_xr_uv-r_v)(r_u\cdot r_xr_v)\\~~~~(u-r_u)x((x-r_x)r_uv-r_v)(r_u\cdot r_xr_v)\\~~~~ux-r_uxr_ux-r_ur_xv-r_vr_ur_xr_v\\~~~~uxv wmuxmvrw (u−ru)x(mxruv−rv)(ru⋅rxrv) (u−ru)x((x−rx)ruv−rv)(ru⋅rxrv) ux−ruxrux−rurxv−rvrurxrv uxv
这个形式和图中的 c Δ ⋅ a b c\Delta\cdot ab cΔ⋅ab完全一致。由此可见至此我们已经成功构造出VOLE的线性表达式。
CipherGPT中的乘法计算【简化清晰版】
假设Client拥有 x x xServer拥有 y y y现在要计算 z x y zxy zxy为了更清晰的表达这里的推导暂不区分矩阵和向量重在梳理算法流程。 此时 y y y是Server端模型参数因此推理时提前已知于是可以通过VOLE生成器在预处理阶段构造VOLE关系 w u ⋅ y v w u\cdot yv wu⋅yv其中Client拥有 ( u , v ) (u, v) (u,v)Server拥有 ( y , w ) (y, w) (y,w)。 那么重点来了如何在在线阶段实现 z x y zxy zxy的计算
Client计算 x s x − u x_sx-u xsx−u并将 x s x_s xs发送给ServerServer计算 x s ⋅ y ( x − u ) ⋅ y x ⋅ y − u ⋅ y x_s\cdot y(x-u)\cdot yx\cdot y-u\cdot y xs⋅y(x−u)⋅yx⋅y−u⋅y于是我们知道 x ⋅ y ( x s u ) ⋅ y x s ⋅ y u ⋅ y x s ⋅ y w − v x\cdot y(x_su)\cdot yx_s\cdot yu\cdot yx_s\cdot yw-v x⋅y(xsu)⋅yxs⋅yu⋅yxs⋅yw−v很容易发现将 x s ⋅ y w x_s\cdot yw xs⋅yw分配给Server将 − v -v −v分配给Client即可实现乘法计算
参考资料
基于LPN假设构造VOLE
