emp-toolkit / emp-agmpc Goto Github PK
View Code? Open in Web Editor NEWGlobal-Scale Secure Multiparty Computation
License: Other
Global-Scale Secure Multiparty Computation
License: Other
In fpremp.h
, each party generates random AND triplets. To do that, each party has authenticated shares of [x] and [y] (the 3*i
and 3*i+1
bits in the tr
array in fpremp.h
), and they engage in a garbled-circuit like protocol to compute a tiny AND gate to then compute the shares of [v]/[z] (will be 3*i+2
bits in the tr
array in fpremp.h
).
Currently, fpremp.h
has every party generate a random tr
, and then make the tr
zero:
prg.random_bool(tr, length*bucket_size*3+3*ssp);
memset(tr, false, length*bucket_size*3+3*ssp);
I kind of feel that the second line is unnecessary and should be removed?
An experiment shows that if the second line makes the evaluate function in fpremp.h
always deals with the first column of the garbled table. If we remove the second line, then other columns have the hope of being touched.
Removing the second line still preserves all MACes are correct, as confirmed by running AG-MPC with debug
on.
It is known that AG-MPC has similar performance with the prior work in semi-honest MPC; however, AG-MPC achieves malicious security.
One who wants the fastest semi-honest MPC may want to start from AG-MPC and turn AG-MPC into semi-honest.
The shortcut is thus to find invocations to SHA256 that are unnecessary for the semi-honest setting.
My observation is that:
Any thoughts or advice?
One desired property in malicious MPC is identifiable abort, in which if some servers cause the protocol to abort, these servers will be identified. Attempts to make SPDZ with such properties have led to significant overhead.
The AG-MPC protocol, in principle, is authenticated, which is somehow close to identifiability.
Thus, this is a short question: Does AG-MPC have identifiable abort? If not, any high-level idea where it is not identifiable?
Not really an issue, but likely a direction. The offline-online model allows us to reduce online latency, but it also means that the servers must store the offline preprocessed result (e.g., the many garbled circuits in AG-MPC).
This result is still a little bit big. For 10 parties, the first server stores ~400MB per SHA-256 circuit, mostly the garbled circuits. Other servers only need to store little data, such as the MAC keys for the input/output wires.
So it seems that applications might desire a way to "compress" the offline preprocessed result somehow, such as an alternative offline phase that has fewer copies of circuits, since it seems unavoidable but also kind of unideal for the first party to keep
This is likely left as a future TODO.
To obtain maliciously secure n-party authenticated bits, the parties, in a pairwise manner, run COT. This is followed by a random validity check.
In practice, this linear combination has to be generated online, which requires a coin-tossing functionality.
This can be implemented by having each party commit to the random numbers (or a PRNG seed), broadcast the commitments, and open the commitments. See Appendix A.1 in https://eprint.iacr.org/2019/1104.pdf for more details.
It seems that FerretCOT architecture has been stabilized. Would AG-MPC use FerretCOT by default? Any suggestions on the number of threads to be used? (How major the computation cost is in FerretCOT?)
I would cc @carlweng here!
Ryan Deng (@ryandeng1) and I implemented a fork of EMP-AGMPC that supports flexible input/output, which suffices for reactive computation.
Fork: https://github.com/n-for-1-auth/emp-agmpc-flex-in-out
Basically, inputs and outputs are flexible in the following ways.
Each bit of the input can be in one of four modes:
Each bit of the output can be in one of three modes:
The input array is replaced by FlexIn<nP>
. Parties first agree on the mode (here, "party") of each bit.
FlexIn<nP> in(cf.n1 + cf.n2, party);
for(int i = 0; i < 64; i++) {
in.assign_party(i, ALICE);
}
for(int i = 64; i < cf.n1; i++) {
in.assign_party(i, BOB);
}
And the party can feed a bit or an authenticated bit into it.
for(int i = 0; i < cf.n1; i++){
in.assign_plaintext_bit(i, i % 2 == 0);
}
for(int i = 0; i < cf.n2; i++) {
AuthBitShare<nP> mabit = out.get_authenticated_bitshare(i);
in.assign_authenticated_bitshare(cf.n1 + i, &mabit);
}
The output array is replaced by FlexOut<nP>
, which works in a similar fashion.
FlexOut<nP> out(cf.n3, party);
for(int i = 0; i < 32; i++) {
out.assign_party(i, ALICE);
}
for(int i = 32; i < 64; i++) {
out.assign_party(i, BOB);
}
for(int i = 64; i < cf.n3; i++) {
out.assign_party(i, 0);
}
One can get an authenticated bit like this, after the online phase.
out.get_authenticated_bitshare(i);
Or, if the party is allowed to see the plaintext value, it can do:
if(party == ALICE) {
for (int i = 0; i < 32; i++) {
cout << out.get_plaintext_bit(i) << " ";
}
for (int i = 32; i < 64; i++) {
cout << "x" << " ";
}
for (int i = 64; i < cf.n3; i++) {
cout << out.get_plaintext_bit(i) << " ";
}
}
The code has been tested for 2 parties over the AES circuit. This test script tries all the functionalities and compares them with the original input/output framework.
https://github.com/n-for-1-auth/emp-agmpc-flex-in-out/blob/master/test/test_in_out.cpp
There are two potential improvements to the code.
We feel this should be fine since input/output is often small, compared with the circuit size. But this may not always be the case.
Though the commit is small, there are two obstacles.
CMPC
objects requires the same delta key. Our fork hardcodes this delta key, which is insecure. We might need a way to generate and use the same delta key across a number of instances that require such reactive computation (and not do so when not needed). Ferret's COT has a setup phase that seems relevant.So, the code is currently left as a fork.
Note that EMP-AGMPC currently only supports BristolFormat, but, especially given this framework, BristolFashion should work as well. A possible direction is to allow easy conversion from BristolFormat to BristolFashion or merge their API.
This implementation is made when working on https://eprint.iacr.org/2021/342.
We also leveraged some code snippets of Senate by @podcastinator and @sukritkalra.
It seems that the implementation does not check the MAC of the outputs (even with __debug
turned on). I feel that it is okay for benchmark purposes since the overhead is comparably small.
But, should the code for output MAC check be added (which would be invoking check_MAC)? Or should we leave as it is?
My local test, which tampers party 2's value
before https://github.com/emp-toolkit/emp-agmpc/blob/master/emp-agmpc/mpc.h#L416, suggests that one malicious party can, however, tamper with the output since the party 1 does not check the MAC.
cmake -DENABLE_FLOAT=False .
as seen in the install script does not work on a clean Ubuntu 18.04 install.
CMake Error at cmake_install.cmake:41 (file):
file INSTALL cannot find "/root/emp-agmpc/cmake".
All you need to do is remove
the line
install(DIRECTORY cmake/ DESTINATION cmake)
from the CMakeLists.txt
file
This is likely a note for reference of performance evaluation: amortized cost can be significantly smaller than the non-amortized cost for the function-independent phase.
Example: If parties are going to run a lot of small circuits (e.g., run AES circuits for one million times), they can:
The latter will show performance numbers that are suboptimal.
Benefits of amortization: Based on some evaluations, it seems that amortization affects the evaluation in many ways.
First, and most obviously and severely, the network latency, as already noted in [WRK17].
The function-independent phase has a lot of rounds. To generate 10k AND triples, using this repo (aka IKNP) and 2Gbit/s network, with two parties,
If one instead generates 10^7 AND triple, then one can get similar numbers that are insensitive to network latency: 3.9 us.
Second, also obviously and severely when bandwidth is limited, the authenticated bit cost if using Ferret.
This one goes without saying. Ferret generates a large batch of AND triples at the same time. And one would miss the opportunities if not all AND triples are consumed. Ferret's benefits are more obvious when machines are powerful and when the network is slow.
Third, the bucket size needed for removing the leakage in leaky AND triples.
Most common circuits would use more than 3100 AND gates, so bucket_size = 4. But for a bucket with size 280000 or more, bucket_size = 3, and this is indeed a non-negligible saving (if network latency is handled).
This means that if one can do a batch function-independent phase, which does not need to be large---10^7 AND gates are not that expensive---then one could always enjoy the bucket size of 3.
Implications for benchmark: This may suggest that benchmarks on one invocation of small circuits would need significant cautions, as network latency may dominate.
Furthermore, the function-dependent phase shows a similar situation---if the circuit is very small, the network latency may dominate.
Implications for the platform: This may suggest that for benchmark purposes, people may want to get good numbers, and reasonable amortization would be considered.
Currently, emp-agmpc does not provide a separation between online/offline, nor a useful tool for benchmarking that considers amortization at heart. In the future, this may be an interesting topic on its own, as it benefits paper writers. E.g., how to store the offline phase result efficiently is another problem (#11).
This is related to the inProd
function in this repo.
https://github.com/emp-toolkit/emp-agmpc/blob/master/emp-agmpc/helper.h#L15
It uses the following selection pad:
const static block inProdTableBlock[] = {zero_block, makeBlock(0xFFFFFFFFULL, 0xFFFFFFFFULL)};
However, the one pad here is not fully one. In fact, a fully one pad should be:
const block all_one_block = makeBlock(0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF);
Note that emp-tool
's 'block.h
offered const block select_mask[2] = {zero_block, all_one_block};
, which could be a drop-in replacement here.
The following installation command worked for me as opposed to single-dash parameters provided in the README.md
.
python install.py -install --tool --ot --agmpc
It seems that emp-toolkit is replacing double_block
with sigma
.
The double_block
is removed from emp-tool
in this commit emp-toolkit/emp-tool@d707eac
However, emp-agmpc
still uses double_block
, as in here: https://github.com/emp-toolkit/emp-agmpc/blob/master/emp-agmpc/mpc.h#L443
Are we going to see a new version of emp-agmpc
recently, which would use sigma
?
AG-MPC is full-threshold, meaning that one honest party is sufficient for security.
In some settings, one may desire threshold security in exchange for better performance, e.g., assuming 20 out of 100 parties are honest, while the rest are malicious.
For arithmetic settings, SCALE-MAMBA provides such a threshold option, using Shamir secret sharing.
But for Boolean circuit settings, a very flexible threshold setting seems missing. However, circuit representations matter, such as AES is commonly expressed in Boolean circuits.
Are any ongoing projects over emp-toolkit aimed for such a threshold setting? Any recommended readings over the malicious + threshold setting for Boolean circuits?
Thanks!
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.