Online cost of Crypto 2020 (edabits)

[kanav99]

I wish to calculate the experimental and theoretical online communication of the protocol for comparison from the "Improved Primitives for MPC over Mixed Arithmetic-Binary Circuits" paper.

1. Experimental Cost: I ran the code provided in Code for Crypto 2020 paper (edaBits) #1391 for 2^16, 2^15 and 2^14 comparisons, using -F flag and spdz2k. I get around 766 bits of communication (total communication, both side)

2. Theoretical cost: I understand that the protocol requires 2 opens and 2m = 126 online ANDs (for LT circuit). Roughly, if we consider just semi-honest security, we 2* 2* 64 (for opens) + 126 * 4 = 760 bits. But this is just semi-honest security.

I wish to understand what's wrong with above analysis. How is the implementation achieving malicious security at the cost of semi-honest protocol?

[mkskeller]

I'm getting slightly different figures, namely 1 integer open, 1 bit open, and 118 ANDs. The integer open costs 128 bits per party because SPDZ2k operates on 128 bits, the bit open costs 1 bit per party, and an AND costs 2 bits per party. Overall, I'm getting 2*(128+1+2*118)=730, which exactly matches the reported communication from around 100,000 comparisons.

[kanav99]

Thanks for the prompt response! I have two follow ups:

1. I see that you have 1 integer and 1 bit open. But in the paper, figure 9, statements 1a and 2b - both of them seem to be integer opens. I understand that to calculate the MSB required in comparison, we calculate LRS by setting m=l-1 (section 5.2). Is this some optimisation which I don't see in the paper but is implemented?

2. I see that you have assigned ANDs a cost 2 bit per party. What protocol is being used to achieve this cost with malicious security? Is there a reference for this?

[mkskeller]

1. Figure 9 is for full truncation, not comparison. Comparison only requires parts thereof.
2. The 2 bits comes from using Beaver multiplication. The communication cost of malicious security for the opening is amortized over many operations, so there is no additional communication per multiplication. Most of the cost of malicious security lies in the offline phase. The protocol is explained in the following paper: https://eprint.iacr.org/2015/901

[kanav99]

Thank you so much! I will look up the reference to understand the cost of OT/ANDs.

[waamm]

In case this is useful, the difference in your bitwise LT circuit costs (126 = 2*64 - 2 and 118 = 2*64 - log(64) - 2) can be explained as follows:

This is a circuit which in the literature is usually stated to cost 2m - 2 ANDs in log(m) rounds, but actually in each round one multiplication can be skipped. This is explicitly done in MP-SPDZ code's here (although I believe the current compiler would do it regardless).

[kanav99]

Thanks @waamm for the helpful pointer!

@mkskeller I have some more questions (or clarifications), this time about implementing relu(x) = max(x, 0).

1. Is (x > 0).if_else(x, 0) the right implementation? or can there be a better implementation using MPSPDZ?
2. Using the above expression, I am getting 1300 bits of communication, which is an additional 534 bits. Is this the expected communication?
3. When we calculate the above expression, is the intermediate comparison result x > 0 stored as a single bit share or a ring element? My hypothesis is that it stores as a ring element (i.e. 128 bit) and then it calculates the final relu using single multiplication, which should require 2*128 bits communication per party, 512 total, which is close to what I observe.

[mkskeller]

1. I'm not aware of any better approach.
2. Again I'm getting slightly lower figures, namely 1242 bits, 730 for the comparison and 512 for the multiplication.
3. As a ring element. Your hypothesis is correct.

[kanav99]

Thanks!

Figure 9 is for full truncation, not comparison. Comparison only requires parts thereof.

Do you have the exact/entire protocol for comparison written down somewhere? The paper only says that it's similar to truncation but doesn't provide any details

[mkskeller]

Not in the paper but the relevant code in MP-SPDZ is here: https://github.com/data61/MP-SPDZ/blob/a44132e5095f84ed5fda3e27c100bf2d6e462243/Compiler/comparison.py#L98C1-L106C68