Paper 2018/429
Amortized Complexity of Information-Theoretically Secure MPC Revisited
Ignacio Cascudo, Ronald Cramer, Chaoping Xing, and Chen Yuan
Abstract
A fundamental and widely-applied paradigm due to Franklin and Yung (STOC 1992) on Shamir-secret-sharing based general -player MPC shows how one may trade the adversary threshold against amortized communication complexity, by using a so-called packed version of Shamir's scheme. For e.g.~the BGW-protocol (with active security), this trade-off means that if , then parallel evaluations of the same arithmetic circuit on different inputs can be performed at the overall cost corresponding to a single BGW-execution.
In this paper we propose a novel paradigm for amortized MPC that offers a different trade-off, namely
with the size of the field
of the circuit which is securely computed, instead of the adversary threshold.
Thus, unlike the Franklin-Yung paradigm, this leaves
the adversary threshold unchanged. Therefore, for instance, this paradigm may yield
constructions enjoying the maximal adversary threshold in the BGW-model
(secure channels, perfect security, active adversary, synchronous communication).
Our idea is to compile an MPC for a circuit over an extension field to a
parallel MPC of the same circuit but with inputs defined over its base field and with the same adversary threshold. Key technical handles are
our notion of reverse multiplication-friendly embeddings (RMFE)
and our proof, by algebraic-geometric means, that these are constant-rate, as well as
efficient auxiliary protocols for creating ``subspace-randomness'' with good amortized complexity.
In the BGW-model, we show that the latter can be constructed by combining our tensored-up linear secret sharing
with protocols based on hyper-invertible matrices á la Beerliova-Hirt (or variations thereof). Along the way, we suggest alternatives for hyper-invertible matrices with the same functionality but which can be defined over a large enough constant size field, which we believe is of independent interest.
As a demonstration of the merits of the novel paradigm, we show that, in the BGW-model
and with an optimal adversary threshold , it is possible to securely compute a binary circuit with amortized complexity of bits per gate per instance. Known results would give bits instead. By combining our result with the Franklin-Yung paradigm, and assuming a sub-optimal adversary (i.e., an arbitrarily small fraction
below 1/3), this is improved to bits instead of .
Note: Accepted to CRYPTO 2018. This is the final version submitted by the authors to the IACR and to Springer-Verlag on the 3rd June 2018.