Question about comparison protocols

[Poppy22]

Hello Marcel,

I wanted to clarify my understanding about the comparison protocols available in MP-SPDZ. I was wondering how the computation changes if I enable dabits, edabits, or none at all, in particular for the online phase (not so interested in pre-processing).

Here's my current understanding summarized:

Protocol	no (e)dabits	dabits enabled	edabits enabled
with bit decomposition	as in Damgard et al., but with bit decomposition improved from Nishide et al.	replaces the bit decomposition from before with k dabits which also help split a secret share into secret bits	no change in the online phase, similar to dabits enabled (because it uses k dabits)
with truncation	as described in Catrina et al.	no influence (?)	as described in Daniel Escudero's PhD thesis (page 225, MSB extraction)

Could you confirm, or help point what is different when I use dabits / edabits in comparisons?

[mkskeller]

You're right about the base protocols. However, I don't think dabits are used in the BD solution but they can be used in the Catrina et al. protocol (otherwise the edaBits paper) wouldn't show any changes. In addition, edaBits are used with bit decomposition if the prime fulfils the conditions in the Rabbit paper.

[Poppy22]

Hm, I'll look more into this and probably have follow-up questions. But until then, I was trying to check how to run comparisons with bit decomposition and with truncation.

For truncation, the docs mention "If you want to use this approach with a given prime, do not specify the prime during compilation but during execution." How can I specify the prime during execution? From the list of command line arguments accepted by dealer-ring-party.x, none of them seem to be used to specify the prime.

My script looks like this for BD:

/benchmarks/MP-SPDZ/compile.py -X -P 1031 bench_mcomp.mpc $1
/benchmarks/MP-SPDZ/dealer-ring-party.x $2 bench_mcomp-$1 -h 172.18.0.2 -N 3 -v

How can I adapt the script for truncation (Catrina et al.)?

Thanks for the answers!

[mkskeller]

This script shouldn't work if there are non-linear operations the MPC program because dealer-ring-party.x doesn't support prime moduli. Generally, execution would mean that you use <protocol>-party.x -P <prime> but the protocol has to be one supporting primes.

[Poppy22]

Ok, follow-up question!

So I'm comparing comparison with BD and Truncation to figure out if they have some optimised implementation in MP-SPDZ. I thought that if I use mixed-circuits (by enabling edabits), the result would be faster. But my quick experiments in MP-SPDZ showed the same online-phase time if I enable edabits.

Online-phase time to execute N=10k comparisons sequentially with shamir-party.x with 3 parties:	Protocol	no (e)dabits	edabits enabled
with bit decomposition	26-27s online phase	26-27s online phase
with truncation	6-7s online phase	6-7s online phase

My code is as follows:

program.use_dabit = bool(int(program.args[1]))
program.use_edabit(int(program.args[1]) == 2)

print(program.use_dabit, program.use_edabit())

program.set_security(40)
program.set_bit_length(8)

n = 10000
@for_range(n)
def _(i):
    (sint(10) < sint(20))

The run script looks like this (I use either compilation with -P, or execution with -lgp:

/benchmarks/MP-SPDZ/compile.py -X bench_mcomp.mpc $1  # use -P 1031 here for bit dec

/benchmarks/MP-SPDZ/shamir-party.x -lgp 50 $2 bench_mcomp-$1 -h 172.18.0.2 -N 3 -v  # use -lgp here for truncation

I just wanted to check if I'm doing anything wrong? I was expecting some online-phase improvements when using mixed-circuits (or does it improve mainly the pre-processing phase?).

Thanks in advance!