How did you perform the comparison protocol in SPU

[BeStrongok]

Dear authors:
Thank you for the wonderful code. I was wondering how you implemented the comparison protocol in the SPU, i haven't found the corresponding code. The protocol for comparison is LTZ, did you used this prototol? Looking for your reply!

[6fj]

Hi @BeStrongok ,

Yes, we are using the same idea here, please check https://github.com/secretflow/spu/blob/beta/spu/hal/ring.cc#L141-L146.

[BeStrongok]

Thanks for your reply, but i haven't find the implementation code of the function _msb, dose you directly reveal the difference x - y and get the msb of the revealed result?

[icavan]

Thanks for your reply, but i haven't find the implementation code of the function _msb, dose you directly reveal the difference x - y and get the msb of the revealed result?

We should not reveal any value here.

Currently, some protocols adopt the arithmetic shares to boolean shares (A2B) procedure. Thus you could get any bit, including the MSB. Some protocol, say cheetah, has a dedicated MSB implementation. Check here.

A more wise way is to directly perform a carry-out circuit calculation which has a similar procedure as the A2B routine. The carry-out circuit will be supported soon.

[BeStrongok]

Cool!! I will learn this code. I'm confused that the shares is generated randomly, so it cannot be used for comparison locally, after A2B procedure, we need to reveal the MSB bit, is my understanding correct?

[icavan]

Cool!! I will learn this code. I'm confused that the shares is generated randomly, so it cannot be used for comparison locally, after A2B procedure, we need to reveal the MSB bit, is my understanding correct?

The MSB is also kept in secret sharing form, either boolean or arithmetic. Everything has to be confidential inside a generic secure multiparty computation protocol. Once you've decided to open the secret, you need to reveal it explicitly.

[BeStrongok]

Cool!! I will learn this code. I'm confused that the shares is generated randomly, so it cannot be used for comparison locally, after A2B procedure, we need to reveal the MSB bit, is my understanding correct?

The MSB is also kept in secret sharing form, either boolean or arithmetic. Everything has to be confidential inside a generic secure multiparty computation protocol. Once you've decided to open the secret, you need to reveal it explicitly.

Thanks for your guidance, i understand. After A2B procedure, parties can get the secret shares of MSB locally, once we want to open this secret, we need to reveal it explicitly, we can't directly reveal it in the source code implicitly.

[BeStrongok]

Thanks for your reply, but i haven't find the implementation code of the function _msb, dose you directly reveal the difference x - y and get the msb of the revealed result?

We should not reveal any value here.

Currently, some protocols adopt the arithmetic shares to boolean shares (A2B) procedure. Thus you could get any bit, including the MSB. Some protocol, say cheetah, has a dedicated MSB implementation. Check here.

A more wise way is to directly perform a carry-out circuit calculation which has a similar procedure as the A2B routine. The carry-out circuit will be supported soon.

Hi~
I noticed that you will implement carry-out circuit calculation, i read the corresponding paper and find that the protocol BitLTL needs log(k) communication rounds, which is not effecient enough, especially handling larger amount of data.
I'm wondering that is there any protocol can be implemented with constant round complexity?
The paper is Improved Primitives for Secure Multiparty Integer Computation.

[rivertalk]

Hi @BeStrongok

Carry-out circuit is supported in the latest SPU implementation (for ABY3 protocol), but it's only helps to reduce the total number of communication data, not communication rounds, the rounds is still log(k).

AFAIK, at least log(k) rounds is required :(