Different timings for operations on sfix and sint

[aniajj9]

Hi Marcell
I am trying to understand the implementation of many operations in MP-SPDZ.

• Questions about comparisons

1. How are the comparisons (>, <, >=, ==, != etc) implemented? Is it based on some paper?
2. I have also run some experiments involving timing comparisons on different datatypes, namely sfix and sint. I have noticed that for sfix==sfix and sfix==sint the performance was similar (approx. 115 seconds for 10k comparisons). However, for sint==sint, the computations took 191 seconds (those are the results from the last run, but in the previous runs the difference was also visible). Similar situation for "<". When comparing sfix<sfix and sfix<sint, I timed 145seconds for both, but sint<sint took 256 seconds. Is there a specific reason for that?

• Questions about sfix

1. When operating on cfix or sfix, is the truncation operation always applied? How is it applied?
2. As a part of my timing tests, I tested multiplication. I was running 10k multiply operations for sfixsint and sintsint (the values were 4.0 and 2.0, so no truncation would have been needed). They run really fast, approx. 1.17 seconds. However, for sfix*sfix (sfix(4.0)*sfix(2.0)), I timed 101.76 seconds. This seems like kind of the opposite of the difference I noticed with comparisons (there the presence of sfix made the comparisons faster, here is the presence of sint). However, here it is much more visible.

Is there a clear explanation to the behaviours? I tried to find answers in the code, but I still don't understand why the time diverges.
I would appreciate an explanation for the time difference, which algorithms were applied and/or code snippets from the implementation. Anything that would help me solve this problem really :)

All of the experiments were structed like this:
@for_range_opt(10000)
def _(i):
result = (sfix(4.0) < sfix(2.0)),
where the sfix(4.0) could have been exchanged with sint(4), < with == or * etc.

Thank you :)

[mkskeller]

1. How are the comparisons (>, <, >=, ==, != etc) implemented? Is it based on some paper?

It's not based on one particular paper, but a raft of works depending on the protocol and the options you chose. The following section in the documentation has pointers to the most important ones: https://mp-spdz.readthedocs.io/en/latest/non-linear.html

2. I have also run some experiments involving timing comparisons on different datatypes, namely sfix and sint. I have noticed that for sfix==sfix and sfix==sint the performance was similar (approx. 115 seconds for 10k comparisons). However, for sint==sint, the computations took 191 seconds (those are the results from the last run, but in the previous runs the difference was also visible). Similar situation for "<". When comparing sfix<sfix and sfix<sint, I timed 145seconds for both, but sint<sint took 256 seconds. Is there a specific reason for that?

sfix uses 31-bit numbers by default whereas the default for sint is 63 or 64 depending on the domain.

1. When operating on cfix or sfix, is the truncation operation always applied? How is it applied?

Truncation is applied after every multiplication. The generic operation is based on https://www.ifca.ai/pub/fc10/31_47.pdf but there are also specific operations for certain settings like https://eprint.iacr.org/2019/131 or https://eprint.iacr.org/2020/1330.

2. As a part of my timing tests, I tested multiplication. I was running 10k multiply operations for sfix_sint and sint_sint (the values were 4.0 and 2.0, so no truncation would have been needed). They run really fast, approx. 1.17 seconds. However, for sfix*sfix (sfix(4.0)*sfix(2.0)), I timed 101.76 seconds. This seems like kind of the opposite of the difference I noticed with comparisons (there the presence of sfix made the comparisons faster, here is the presence of sint). However, here it is much more visible.

Truncation is more expensive than the multiplication, so sfix-sfix multiplication is more expensive than sfix-sint or sint-sint.

[aniajj9]

Thanks for the comprehensive answer! I have one last question: What is the reason for division to be so significantly slower than other operations?

[mkskeller]

Division is much more intricate, which is also reflected in the fact that even CPUs usually take several clock cycles for it. You can look at Protocol 3.3 in the paper by Catrina and Saxena for more details on how division works.