data61
Questions about comparison with and without edabits
Hi! I am trying to benchmark different comparison protocols, to use in argmax.
I have some problems reproduce the cases where edabits preprocessing is more efficient.
I use the code posted in issue 1391. I run 3 parties in the same localhost.
I have manually edited the code to run for n=10322 comparison instances and n_threads=1 and I run this code block as it is
start_timer(1)
@multithread(n_threads, n)
def _(base, m):
@for_range(l)
def _(i):
(sint(0, size=m) < sint(1, size=m)).store_in_mem(base)
stop_timer(1)
From the results I get I see that without edabits the code is ~3 times faster which isn't aligned - from what I understand - with the speedup results in table 7 from CRYPTO 2020 (ingoring the actual numbers since I use only one thread and a less powerful machine).
I get similar results when I run this code block for n=103 argmax instances.
a = sint.get_random(size=100)
start_timer(8)
@for_range_opt(n)
def _(i):
ml.argmax(a)
stop_timer(8)
And also two more small questions..
- Is there a protocol in MP-SPDZ library which I can run in 2^k ring for honest majority and malicious parties?
- Do we expect a 10-party protcol with honest majority and malicious parties be faster with or without edabits (any references here)?
[Details]
I compile with ./compile.py -O bench_comp and run it as ./malicious-shamir-party.x -B 4 -b 10000 bench_comp -N 3 -p 2 -v with and without the edabits option. The bucket size and batch size I set it according to table 1 of CRYPTO 2020 paper.
with the edabits option I get:
Data sent = 996.045 MB in ~1336 rounds (party 1 only; rounds counted double due to multi-threading)
Communication details (rounds in parallel threads counted double):
Broadcasting 0.00712 MB in 313 rounds, taking 0.065262 seconds
Partial broadcasting 350.632 MB in 663 rounds, taking 0.541913 seconds
Sending/receiving 257.403 MB in 360 rounds, taking 1.04939 seconds
CPU time = 10.6531 (overall core time)
The following benchmarks are including preprocessing (offline phase).
Time = 10.4961 seconds
Time1 = 10.4393 seconds (958.521 MB, 1330 rounds)
Data sent = 958.681 MB in ~1336 rounds (party 2 only; rounds counted double due to multi-threading)
Global data sent = Global data sent = 2950.772950.77 MB (all parties) MB (all parties)Global data sent =
2950.77 MB (all parties)
Actual cost of program:
Type int
10322 daBits
100 Randoms
Type bit
1217996 Triples
edaBits
10322 of length 41 (strict)
10322 of length 63 (strict)
Actual cost of program:
Type int
10322 daBits
100 Randoms
Type bit
1217996 Triples
edaBits
10322 of length 41 (strict)
10322 of length 63 (strict)
Actual cost of program:
Type int
10322 daBits
100 Randoms
Type bit
Command line: 1217996 ./malicious-shamir-party.x -B 4 -b Triples10000
bench_comp edaBits
-N 103223 of length 41-p (strict)
0 -v 10322
of length 63 (strict)
and without the edabits option I get:
Time1 = 2.93971 seconds (348.546 MB, 1608 rounds)
Data sent = 348.706 MB in ~1614 rounds (party 2 only; rounds counted double due to multi-threading)
Global data sent = 1046.12 MB (all parties)
Global data sent = Global data sent = 1046.12 MB (all parties)1046.12
MB (all parties)
Actual cost of program:
Type int
1217996 Triples
1073488 Actual cost of program:
Type Bitsint
100 1217996 Randoms
Triples
1073488 This program might benefit from some protocol options.
Consider adding the following at the beginning of your code:
program.use_edabit(True)
Bits
100 Randoms
This program might benefit from some protocol options.
Consider adding the following at the beginning of your code:
program.use_edabit(True)
Command line: ./malicious-shamir-party.x -B 4 -b 10000 bench_comp -N 3 -p 1 -v
Command line: ./malicious-shamir-party.x -B 4 -b 10000 bench_comp -N 3 -p 0 -v
Actual cost of program:
Type int
1217996 Triples
1073488 Bits
100 Randoms
This program might benefit from some protocol options.
Consider adding the following at the beginning of your code:
program.use_edabit(True)
Command line: ./malicious-shamir-party.x -B 4 -b 10000 bench_comp -N 3 -p 2 -v
All parties finished execution.
Shamir-based protocols have to use GF(2^n) embeddings for binary computation, which makes edaBits less useful than in other settings.
- Is there a protocol in MP-SPDZ library which I can run in 2^k ring for honest majority and malicious parties?
The most efficient protocol in this setting is SPDZ-wise Rep3 (sy-rep-ring).
- Do we expect a 10-party protcol with honest majority and malicious parties be faster with or without edabits (any references here)?
I'm not aware of any work exploring that. Generally, edaBits don't scale well in the number of parties as the require O(n) basic operations, which require O(n) cost in themselves in malicious Shamir. The ATLAS paper has a variant with malicious security, but MP-SPDZ only implements the semi-honest variant. I'm not aware of any implementation of malicious ATLAS let alone edaBits therein.
thank you for the reply!
Shamir-based protocols have to use GF(2^n) embeddings for binary computation, which makes edaBits less useful than in other settings.
what is n in this context?
The most efficient protocol in this setting is SPDZ-wise Rep3 (sy-rep-ring).
The results for CRYPTO 2020 were obtained using this protocol? if not, which was the setting used?
Also, would that be possible to use in MP-SPDZ replicated secret sharing based protocols with more than 4 parties, in a way that is efficient?
Shamir-based protocols have to use GF(2^n) embeddings for binary computation, which makes edaBits less useful than in other settings.
what is n in this context?
n must be larger than the logarithm of the number of parties. The default is to use 8.
The most efficient protocol in this setting is SPDZ-wise Rep3 (sy-rep-ring).
The results for CRYPTO 2020 were obtained using this protocol? if not, which was the setting used?
No, the results in the paper were obtained using post-sacrifice Rep3 as SPDZ-wise was only implemented later.
Also, would that be possible to use in MP-SPDZ replicated secret sharing based protocols with more than 4 parties, in a way that is efficient?
This isn't implemented. Replicated secret sharing doesn't scale well if the threshold is just under half the number of parties, in which Shamir-based protocols quickly become more efficient. It probably wouldn't be too hard to extend the current implementation keeping a low threshold, however.