ABY – A Framework for efficient Mixed-Protocol Secure Two-Party Computation 阅读笔记(Arithmetic部分)

ABY – A Framework for efficient Mixed-Protocol Secure Two-Party Computation 阅读笔记(Arithmetic部分)

今天看了秘密分享架构中的ABY架构,尤其看了Arithmetic sharing部分,对于该秘密分享机制下的加法与乘法的计算有了一定的了解,而且了解了如何通过Pailler同态加密方法产生c=axb的三元组。但是对于OT-Base产生三元组的方法不太了解,明天会对非对称加密体系,安全分享公钥的方法还有Diffie-Hellman算法进行学习以求更加熟悉OT-Base办法

1). Share Semantics:

1. Shared values:

对于一个数x的l字节Arithmetic共享\langle x\rangle ^A,我们有\langle x\rangle^A_0 + \langle x\rangle^A_1=\langle x\rangle^A , \langle x\rangle_0^A,\langle x\rangle_1^A\in Z_{2^l}

2. Sharing:

定义Shri^A_i(x): P_i随机选r\in Z_{2^l},\langle x\rangle_i^A=x-r,并发送r给P_{1-i}P_{1-i}\langle x\rangle_{1-i}^{A} 设为r

3. Reconstruction:

定义Rec_i^A(x): P_{1-i}\langle x\rangle_{1-i}^AP_{i}P_i计算x=\langle x\rangle_0^A+\langle x\rangle_1^A

2). Operations:

1. Addition

需要计算\langle z\rangle^A=\langle x\rangle^A+\langle y\rangle^A,只需要P_i本地计算\langle z\rangle_i^A=\langle x\rangle_i^A+\langle y\rangle_i^A

2. Multiplication

需要计算\langle z\rangle^A=\langle x\rangle^A\langle y\rangle^A

初始状态:

A: \langle x\rangle^A_0,\langle y\rangle^A_0

B:\langle x\rangle^A_1,\langle y\rangle_1^A

目标状态:

A:\langle z\rangle^A_0

B:\langle z\rangle^A_1

s.t. \langle z\rangle^A_0+\langle z\rangle^A_1=\langle z\rangle_A=\langle x\rangle_A\times\langle y\rangle_A

方案如下:

  1. 准备三元组(a,b,c=a\times b) 然后将(a,b,c=a\times b) 加法共享给P_0,P_1(具体方案会在之后介绍)

    A:\langle x\rangle_0^A,\langle y\rangle_0^A,\langle a\rangle^A_0,\langle b\rangle_0^A,\langle c\rangle_0^A

    B:\langle x\rangle_1^A,\langle y\rangle_1^A,\langle a\rangle_1^A,\langle b\rangle_1^A,\langle c\rangle_1^A

  2. 两方各自计算\langle e\rangle^A_i=\langle x\rangle^A_i-\langle a\rangle^A_i,\langle f\rangle_i^A=\langle y\rangle^A_i-\langle b\rangle^A_i(盲化\langle x\rangle,\langle y\rangle

    A:\langle x\rangle_0^A,\langle y\rangle_0^A,\langle a\rangle^A_0,\langle b\rangle_0^A,\langle c\rangle_0^A,\langle e\rangle_0^A,\langle f\rangle_0^A

    B:\langle x\rangle_1^A,\langle y\rangle_1^A,\langle a\rangle_1^A,\langle b\rangle_1^A,\langle c\rangle_1^A,\langle e\rangle^A_1,\langle f\rangle_1^A

  3. 双方共享自己的\langle e\rangle,\langle f\rangle

    A:\langle x\rangle_0^A,\langle y\rangle_0^A,\langle a\rangle^A_0,\langle b\rangle_0^A,\langle c\rangle_0^A,\langle e\rangle^A,\langle f\rangle^A

    B:\langle x\rangle_1^A,\langle y\rangle_1^A,\langle a\rangle_1^A,\langle b\rangle_1^A,\langle c\rangle_1^A,\langle e\rangle^A,\langle f\rangle^A

  4. 计算\langle z\rangle_0^A=f\times \langle a\rangle^A_0+e\times \langle b\rangle^A_0+\langle c\rangle_0^A\langle z\rangle_1^A=e\times f+f\times \langle a\rangle^A_1+e\times\langle b\rangle^A_1+\langle c\rangle_1^A

    故有\langle z\rangle^A+\langle z\rangle^B=e\times f+f\times a+e\times b+c=x\times y

3. 生成三元组(a,b,c=a\times b)

(1). 通过同态加密实现

注释:Pailler同态加密指的是

Enc_0(a+b)=Enc_0(a) \times Enc_0(b)

初始状态:P_0,P_1分别随机\langle a\rangle_0^A,\langle a\rangle_1^A,\langle b\rangle_0^A,\langle b\rangle_1^AP_1随机一个随机数r

需要获得一个\langle c\rangle^A,\langle c\rangle^A_1,使得\langle c\rangle_0^A+\langle c\rangle_1^A=\langle c\rangle^A=\langle a\rangle^A\langle b\rangle^A=(\langle a\rangle^A_0+\langle a\rangle^A_1)(\langle b\rangle_0^A+\langle b\rangle^A_1)

方案如下:

1.P_0 发送给 P_1:

Enc_0(\langle a\rangle^A_0), Enc_0(\langle b\rangle^A_0)

于是情况变为:

P_0:\langle a\rangle^A_0,\langle b\rangle^A_0

P_1:\langle a\rangle^A_0,\langle b\rangle^A_1,r,Enc_0(\langle a\rangle^A_0),Enc_0(\langle b\rangle^A_0)

2.P_1发给P_0:

d=Enc_0(\langle a\rangle^A_0)^{\langle b\rangle^A_1}\times Enc_0(\langle b\rangle^A_0)^{\langle a\rangle^A_1}\times Enc_0(r)

3.P_0计算\langle c\rangle^A_0=\langle a\rangle^A_0 \langle b\rangle^A_0+Dec_0(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_0+r

4.P_1计算

\langle c\rangle^A_1=\langle a\rangle^A_1\langle b\rangle^A_1-r

(2).通过OT实现

暂时还不会 明天看!

留下回复