[SIRNN] Questions about the mixed bit-width

[llCurious]

Hey, @bhatuzdaname ✋🏻. I recently read the paper SIRNN and the work is particularly interesting. However, I just have several questions about the paper and the code implementation. Look forward to receiving your answers~

• I understand the motivation to use mixed bit-width to decrease the communication, while i think the zero(signed)-extension implies more communication rounds, which means more latency in the WAN environment. Could you please discuss the trade-off here?
• In the code implementation, i check the BuildingBlocks/extension.cpp, truncation.cpp, the data types to store all the values are uint64_t. I am a little confused here, since the uint64_t implies a ring Z_2^64. This is contradict with the claim in the paper.
• By the way, did you compare with the 3-party works like Falcon or ABY3, despite use of uniform bit-width, the truncation and multiplication use significant fewer rounds. While the extension and non-uniform multiplication seems to incur more rounds and more communication bits compared to these works.

Thanks a lot anyway, really hope you can answer these questions

[deevashwer]

Hi,

Thanks for your interest in our work. The answers to your questions are as follows:

1. It is correct that mixed-bitwidth protocols from SIRNN reduce communication at the expense of more rounds of communication. This makes sense for SIRNN as in the inference of ML models, the computation is wide enough that the cost of rounds is easily amortized and communication is the bottleneck. In a WAN environment, the cost of rounds will be higher, but at the same time, the bandwidth will also be constrained. Even if you have a WAN which has very high latency (and cost of rounds) and moderate bandwidth (and cost of communication), you can always batch multiple inference tasks, which will linearly increase the communication, but the cost of rounds will remain the same. Overall, it depends on your computation. If it is wide enough for your network or can be made wide enough (example, through batching), mixed-bitwidth protocols from SIRNN work great. If rounds are the bottleneck, you might be better off with garbled circuits and its constant rounds.
2. We're using uint64t for all rings Z{2^ell} with ell <= 64. You'll see additional parameters in each function specifying the bitwidth ell. This works because x mod 2^{ell} is equivalent to (x mod 2^{64}) mod 2^{ell} for ell <= 64.
3. No, we didn't compare with (honest-majority) 3PC works as they provide weaker security guarantees than 2PC.

[llCurious]

Hey, happy to receive your reply. Thank a lot and this greatly answers many of my questions.

• I still have a confusion as to the second point, i currently understand how you implement the functionality. However, i saw that you directly use (inA[i] & mask_bwA) to mask the least significant several bits to somehow simulate the mod operation over a smaller ring 2^{ell}. I think this might introduce some error since there might be a carry bit which can be ignored in such implementation (similar to SecureML?). If i am wrong, could you please correct misunderstandings?

• By the way, i note that you compare with the MP-SPDZ and MiniONN mainly focus on non-linear functions including Sigmoid and Tanh. Your idea of using LUT to compute these functions is interesting, do you have a theoretically comparison concerning round / communication complexity against above two works.

Great work deserves more thinkings. Looking forward to your answers~~

[llCurious]

Sry, i idiot. The second point is my misunderstanding and forget about it. SecureML truncates to take the most significant several bits, while you here use mask to take the least significant several bits. The carry bit does not have negative effects indeed.