Some questions about the implementation of ABY3 and it's Truncation protocol about spu HOT 8 CLOSED

Hey @BeStrongok , this is a good question.

The problem you mentioned is discussed in the ABY3 paper already. To be specific, the truncation in ABY3, i.e. TruncA here may incur two error: 1) the 1-bit error in the MSB and 2) the 1-bit error in the LSB.

The 1-bit MSB error happens with probability that is discussed in ABY3 paper. This shall cause significant error. Therefore we have another implementation TruncAPr to fix this problem.

We note that TruncAPr (known as probabilistic truncation) fixs (1) and does not consider (2). That said, (x1'+x2'+x3')/2^d = (x1'+x2')/2^d+(x3'/2^d) +- 1. This error is actually negligible.

from spu.

Hey @BeStrongok , this is a good question.

The problem you mentioned is discussed in the ABY3 paper already. To be specific, the truncation in ABY3, i.e. TruncA here may incur two error: 1) the 1-bit error in the MSB and 2) the 1-bit error in the LSB.

The 1-bit MSB error happens with probability that is discussed in ABY3 paper. This shall cause significant error. Therefore we have another implementation TruncAPr to fix this problem.

We note that TruncAPr (known as probabilistic truncation) fixs (1) and does not consider (2). That said, (x1'+x2'+x3')/2^d = (x1'+x2')/2^d+(x3'/2^d) +- 1. This error is actually negligible.

Thanks for your quickly reply.
I'm curious about the arithmetic operations of ring2k_t, does it contains modulo operation?
That is, when x1'+x2'+x3' exceeds modulus, the result of (x1'+x2'+x3)/2^d is completely different with the result of x1'+x2')/2^d+(x3'/2^d).

from spu.

Thanks for your quickly reply. I'm curious about the arithmetic operations of ring2k_t, does it contains modulo operation?

Yes. We do modulo 2^k implicitly.

That is, when x1'+x2'+x3' exceeds modulus, the result of (x1'+x2'+x3)/2^d is completely different with the result of x1'+x2')/2^d+(x3'/2^d).

You are right. This is the root cause of the 1-bit MSB error i mentioned above. To be specific, if the wrap happens, (x1'+x2'+x3)/2^d = (x1'+x2')/2^d+(x3'/2^d) - 2^{k-d}

from spu.

Thanks, the reason i mentioned this protocol is that TruncAPr needs 3 rounds which is relatively high in high latency circumstance, so i'm thinking a better way and meet some problem, what you told me is very helpful. :)

Yes. We do modulo 2^k implicitly.

Could you point out the detailed implementation of ring2k_t?

You are right. This is the root cause of the 1-bit MSB error i mentioned above. To be specific, if the wrap happens, (x1'+x2'+x3)/2^d = (x1'+x2')/2^d+(x3'/2^d) - 2^{k-d}

Has - 2^{k-d} been already implemented in the SPU?

from spu.

Could you point out the detailed implementation of ring2k_t?

You can refer to type_utils.h. code is here. It dynamically casts data type like uint32 or uint64.

Has - 2^{k-d} been already implemented in the SPU?

Currently, we support TruncAPr which calculates this part (refer to code). It indeed incurs 3 rounds and you can find the original paper for detailed description.

from spu.

Could you point out the detailed implementation of ring2k_t?

You can refer to type_utils.h. code is here. It dynamically casts data type like uint32 or uint64.

Has - 2^{k-d} been already implemented in the SPU?

Currently, we support TruncAPr which calculates this part (refer to code). It indeed incurs 3 rounds and you can find the original paper for detailed description.

Thanks, your reply is very helpful. I have solved my problem.
In 3PC circumstance, do you think a more efficient truncation protocol compared to TruncAPr could be implemented?
I'm wondering that whether there exists a way to solve the MSB error without communication.

from spu.

Yep. This is a open question indeed. If you have any idea, feel free to open a PR request :).

from spu.

Yep. This is a open question indeed. If you have any idea, feel free to open a PR request :).

Thanks, an initial idea may works but needs more tests. That is, a mixed truncation protocol may be useful, rather than an specific protocol such as TruncA or TruncPRA.
I will see if it can help to improve the truncation performance of ABY3 in SPU.

from spu.