In this post I will feature two of the papers in the session on foundations of MPC, Efficient Multiparty Protocols via Log-Depth Threshold Formulae by Cohen et al. and A Dynamic Tradeoff Between Active and Passive Corruptions in Secure Multi-Party Computation by Hirt et al.
The first of those talks presented not a new MPC protocol but a way to construct an MPC protocol from one with less players. To do so, they employ the player emulation technique by Hirt and Maurer, which is best explained by the following example. Take an MPC protocol (like BGW) with three players v1,v2,v3 and passive security against one corrupted player. Now replace player v1 by the same protocol run with the players w1,w2,w3. With respect to corruptions, there are now two possible scenarios that maintain security. Either v1 or one of v2,v3 can be corrupted in the first protocol instance. The former case corresponds to any number of w1,w2,w3 being corrupted, even all of them. In the latter case, v1 must not be corrupted, which implies that at most one out of w1,w2,w3 can be corrupted. Generalizing this example, one can model one protocol instance as a MAJ3 logic gate that takes three inputs and outputs the majority of them.
It remains to find a formula with only such gates that outputs true if at most t inputs are false. Such a formula directly implies an MPC protocol for n parties with threshold t. It is proven that, in the information-theoretic setting, the threshold must be less than n/2. Another constraint is that the complexity of the constructed MPC protocol grows exponentially with the depth of the formula, so one wants to have a log-depth formula. The authors present two ways of constructing such a formula for any n, a randomized one for the maximal t < n/2 that is correct with high probability and a deterministic one that with only approximate t. The authors also present a similar approximate solution for the case of active security, where at most n/3 players can be corrupted. Here the base case is a four-party protocol with at most one corruption.
The other talk explored the space between purely active and purely passive corruption in multi-party computation. Classical work like BGW assumes that all corrupted parties are corrupted in the same way, and a recent work by Ishai et al. proposed a protocol that is secure against passive corruption of t < n or active corruption of t < n/2 parties. However, the latter does not allow a mixed case, say some active corruption and passive corruption such that the total number of corrupted parties is at least n/2.
The new work now allows k < n/2 active corruptions and n-k-1 passive corruptions for an unknown k. To achieve this, the authors propose a new variant of verifiable secret-sharing, gradual VSS. VSS is essentially secret-sharing with the reconstruction guaranteeing correctness. Traditional VSS provides secrecy against t corruptions and robustness against n-t-1 corruptions for a fixed t. Gradual VSS in addition uses additive secret sharing to produce k shares, which then are shared using traditional VSS for every t in 1,...,k. For reconstruction, the additive secret shares are reconstructed one after the other starting with t. If any of those reconstructions fail, the protocol is aborted, and if this happens before the reconstruction with k=1, the secret is protected by the additive shares that are not reconstructed yet. This guarantees secrecy and robustness for any combination of passive and active corruption in the permitted range.
No comments:
Post a Comment