Inquiry on A2B Protocol in ABY3

[o7s4]

Issue Type

Others

Modules Involved

MPC protocol

Have you reproduced the bug with SPU HEAD?

No

Have you searched existing issues?

Yes

SPU Version

none

OS Platform and Distribution

none

Python Version

none

Compiler Version

No response

Current Behavior?

hi, I have been studying the ABY3 paper, which I find both insightful and foundational to my work. I have a question regarding the A2B protocol described in the paper. Specifically, I am trying to understand whether the protocol converts an arithmetic sharing [x]=(x1,x2,x3) into a boolean sharing [x[1],x[2],x[3]]=((x1[1],x1[2],x1[3]),x2[1],x2[2],x2[3],x3[1],x3[2],x3[3]) , where the following conditions hold: x1[1]⊕x2[1]⊕x3[1]=x[1], x1[2]⊕x2[2]⊕x3[2]=x[2], x1[1]⊕x2[2]⊕x3[2]=x[2], assuming k=3. The paper mentions using a ripple-carry full adder circuit to achieve this transformation. However, I am struggling to understand how the full adder accomplishes this conversion. Could you kindly provide some insight or reference additional resources that explain this mechanism in more detail? Thank you very much for your time, and I look forward to any guidance you can provide. Warm regards

Standalone code to reproduce the issue

none

Relevant log output

No response

[tpppppub]

Suppose you have bit-level binary representations of x1, x2, and x3 (ignore they are shares). Obviously you can get the binary representations of (x1 + x2 + x3) using RCFA circuits.

[o7s4]

Suppose you have bit-level binary representations of x1, x2, and x3 (ignore they are shares). Obviously you can get the binary representations of (x1 + x2 + x3) using RCFA circuits.↳

Thank you for your previous response but i still have some questions regarding the specifics. After using the Ripple-Carry Full Adder (RCFA), we obtain the binary representation of the sum 𝑥=𝑥1+𝑥2+𝑥3​ . I am trying to understand how this binary result is shared among the three parties to meet the condition 𝑥1⊕𝑥2⊕𝑥3=x (bitwise XOR). For example, if 𝑥=10 and we have arithmetic shares 𝑥1=2x，𝑥2=5, and 𝑥3=3, the binary representations would be 𝑥1=0010,𝑥2=0101, and 𝑥3=0011. Using the RCFA circuit, the computed binary output would be 𝑥=1010My questions are: Which party receives this circuit output initially? Is there a specific mechanism to further distribute or convert this output into Boolean shares so that 𝑥1⊕𝑥2⊕𝑥3=𝑥(bitwise XOR, if the A2B protocol wants to do that)? I would greatly appreciate any clarification on this.

[tpppppub]

x1, x2, x3 are boolean shares, after the RCFA circuits, x is also boolean shares, that's exactly what you want.

[o7s4]

My understanding of the A2B protocol is that, throughout the entire process, none of the parties (party 1, party 2, or party 3) should know the arithmetic or binary representation of x. Each party should convert their arithmetic share of x into a Boolean share. Is this correct?

[o7s4]

x1, x2, x3 are boolean shares, after the RCFA circuits, x is also boolean shares, that's exactly what you want.↳

So, does A2B only convert 𝑥 into a bitwise form?

[tpppppub]

Sorry, I don't get your point. A2B converts arithmetic shares of X to bitwise boolean shares of X. The first paragraph of ABY3's paper is already clear enough. First, we can get the BShares of X1, X2, X3 from the AShare of X. Then we can get BShare of X using RCFA circuits on BShares of X1, X2, X3. The left of the paper are optimizations. So what's the problem?

[o7s4]

x1, x2, x3 are boolean shares, after the RCFA circuits, x is also boolean shares, that's exactly what you want.↳

But the x of the circuit output is a secret(plaintext). How do I secretly share this plaintext? I thought the situation was that after running the A2B(Bit Decomposition) protocol, P1, P2 and P3 would all get a partial boolean share of x.It's like in the end, P1 has 𝑥1 and 𝑥2 , P2 has 𝑥2 and 𝑥3 , and P3 has 𝑥3 and 𝑥1 , where any two parties can reconstruct 𝑥 by bitwise XOR of 𝑥1 , 𝑥2 , and 𝑥3 . (If it were arithmetic secret sharing, it would be 𝑥=𝑥1+𝑥2+𝑥3 ).According to the paper and what you explained, doesn’t this ultimately just compute the Boolean representation of the secret 𝑥? This seems a bit different from the kind of sharing conversion I had in mind.

[o7s4]

[o7s4]

I'm sorry to take up your time. I'm a beginner in MPC, and while this might be a simple and basic question for you, it is quite challenging for me, and I may have misunderstood some concepts. I would greatly appreciate your patience in answering my question, as it would be incredibly helpful to me. Thank you very much

[tpppppub]

the input X1, X2, X3 are shares, the RCFA circuits are XOR/AND gates with inputs and outputs are shares, and the final X is also shares.

[o7s4]

the input X1, X2, X3 are shares, the RCFA circuits are XOR/AND gates with inputs and outputs are shares, and the final X is also shares.↳

I'm still having difficulty understanding this. Could you please provide an example? Suppose we have a secret 𝑥=6, which is arithmetically secret-shared among 𝑃1, 𝑃2, and 𝑃3, with shares 𝑥1=2, 𝑥2=3, and 𝑥3=1, such that 𝑥1+𝑥2+𝑥3=6. In this case,none of 𝑃1, 𝑃2, or 𝑃3 know the value of 𝑥. Could you please explain how to perform A2B conversion using an adder circuit in this example? I would greatly appreciate it.

[o7s4]

the input X1, X2, X3 are shares, the RCFA circuits are XOR/AND gates with inputs and outputs are shares, and the final X is also shares.↳↳

I'm still having difficulty understanding this. Could you please provide an example? Suppose we have a secret 𝑥=6, which is arithmetically secret-shared among 𝑃1, 𝑃2, and 𝑃3, with shares 𝑥1=2, 𝑥2=3, and 𝑥3=1, such that 𝑥1+𝑥2+𝑥3=6. In this case,none of 𝑃1, 𝑃2, or 𝑃3 know the value of 𝑥. Could you please explain how to perform A2B conversion using an adder circuit in this example? I would greatly appreciate it.↳

According to your explanation, 𝑃1,𝑃2, and 𝑃3 each convert their arithmetic share of 𝑥 into binary form, meaning 𝑃1 gets 𝑥1=010, 𝑃2 gets 𝑥2=011, and 𝑃3 gets 𝑥3=001. Then, they use an adder circuit to compute the sum, which is essentially RCFA(RCFA(𝑥1,𝑥2),𝑥3)=RCFA(101,𝑥3)=110=𝑥(The final X). But doesn’t 110 just represent the value 6 ?

[o7s4]

I may have misunderstood; I apologize for taking up your time.

[deadlywing]

Please first clarify the inputs and outputs of the A2B protocol. Input: (x0, x1), (x1, x2), (x2, x0) , the Ashare of x, i.e. x0+x1+x2 = x Output: (y0, y1), (y1, y2), (y2, y0), the Bshare of x, i.e. y0^y1^y2 = x

Then, implementing A2B is straightforward, for simplicity, let's take semi-honest as an example. Just re-construct Bshare of x by [x0+x1]_B and [x2]_B, which is we have done in SPU:

Then, invoking any Adder (In SPU, it is KoggeStone Adder, which calls other Boolean ops like AND, XOR) to compute Bshare of [x0+x1]_B+ [x2]_B, which finishes the protocol.

[o7s4]

Please first clarify the inputs and outputs of the A2B protocol. Input: (x0, x1), (x1, x2), (x2, x0) , the Ashare of x, i.e. x0+x1+x2 = x Output: (y0, y1), (y1, y2), (y2, y0), the Bshare of x, i.e. y0^y1^y2 = x↳

Then, implementing A2B is straightforward, for simplicity, let's take semi-honest as an example. Just re-construct Bshare of x by [x0+x1]_B and [x2]_B, which is we have done in SPU: ↳

Then, invoking any Adder (In SPU, it is KoggeStone Adder, which calls other Boolean ops like AND, XOR) to compute Bshare of [x0+x1]_B+ [x2]_B, which finishes the protocol.↳

Thank you for your response; I feel like I understand a bit more, but I still have some questions. Following your explanation, it seems that the final result Y=PPA(M,N)=[((x0+x1)^z0, z1), (z1, x2+z2), (x2+z2, (x0+x1)^z0)], However, with this structure, we get Y1^Y2^Y3=(x0+x1)^z0^z1^(x2+z2), which does not equal X as intended. Could you clarify how this maintains the correct relationship, Y1⊕Y2⊕Y3=X? Thank you!

[deadlywing]

M, N is now Bshare; you can't add these as Ashare does, which has to be done by Adder.

[o7s4]

M, N is now Bshare; you can't add these as Ashare does, which has to be done by Adder.↳

Yes, I understand that an adder is needed. My main question is whether the final result y1⊕y2⊕y3 is equal to x

[o7s4]

[tpppppub]

The adder works on boolean shares, which means you need to use boolean share XOR/AND protocols to evaluate its each XOR/AND gate in this circuit, not just simply run the adder locally on each party. As I have explained earlier, you have complete computations XOR/AND (for bshares) and the bit string of X1, X2, X3 (as bshares). Using an adder to compute the X (as bshares) is straightforward.

[o7s4]

The adder works on boolean shares, which means you need to use boolean share XOR/AND protocols to evaluate its each XOR/AND gate in this circuit, not just simply run the adder locally on each party. As I have explained earlier, you have complete computations XOR/AND (for bshares) and the bit string of X1, X2, X3 (as bshares). Using an adder to compute the X (as bshares) is straightforward.↳

So, according to what you're saying, is the purpose of using the adder to reconstruct X?

[o7s4]

The adder works on boolean shares, which means you need to use boolean share XOR/AND protocols to evaluate its each XOR/AND gate in this circuit, not just simply run the adder locally on each party. As I have explained earlier, you have complete computations XOR/AND (for bshares) and the bit string of X1, X2, X3 (as bshares). Using an adder to compute the X (as bshares) is straightforward.↳

Or, does this 3PC adder circuit automatically distribute the Boolean shares of X to P1, P2, and P3 after computing the sum of x1, x2, and x3?