Paper 2018/429
Amortized Complexity of InformationTheoretically Secure MPC Revisited
Ignacio Cascudo, Ronald Cramer, Chaoping Xing, and Chen Yuan
Abstract
A fundamental and widelyapplied paradigm due to Franklin and Yung (STOC 1992) on Shamirsecretsharing based general $n$player MPC shows how one may trade the adversary threshold $t$ against amortized communication complexity, by using a socalled packed version of Shamir's scheme. For e.g.~the BGWprotocol (with active security), this tradeoff means that if $t + 2k 2 < n/3$, then $k$ parallel evaluations of the same arithmetic circuit on different inputs can be performed at the overall cost corresponding to a single BGWexecution. In this paper we propose a novel paradigm for amortized MPC that offers a different tradeoff, namely with the size of the field of the circuit which is securely computed, instead of the adversary threshold. Thus, unlike the FranklinYung paradigm, this leaves the adversary threshold unchanged. Therefore, for instance, this paradigm may yield constructions enjoying the maximal adversary threshold $\lfloor (n1)/3 \rfloor$ in the BGWmodel (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 multiplicationfriendly embeddings (RMFE) and our proof, by algebraicgeometric means, that these are constantrate, as well as efficient auxiliary protocols for creating ``subspacerandomness'' with good amortized complexity. In the BGWmodel, we show that the latter can be constructed by combining our tensoredup linear secret sharing with protocols based on hyperinvertible matrices á la BeerliovaHirt (or variations thereof). Along the way, we suggest alternatives for hyperinvertible 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 BGWmodel and with an optimal adversary threshold $\lfloor (n1)/3 \rfloor$, it is possible to securely compute a binary circuit with amortized complexity $O(n)$ of bits per gate per instance. Known results would give $n \log n$ bits instead. By combining our result with the FranklinYung paradigm, and assuming a suboptimal adversary (i.e., an arbitrarily small $\epsilon>0$ fraction below 1/3), this is improved to $O(1)$ bits instead of $O(n)$.
Note: Accepted to CRYPTO 2018. This is the final version submitted by the authors to the IACR and to SpringerVerlag on the 3rd June 2018.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in CRYPTO 2018
 Keywords
 multiparty computationamortizationinformationtheoretical securitymultiplicationfriendly embeddings
 Contact author(s)
 ignacio @ math aau dk
 History
 20180606: revised
 20180511: received
 See all versions
 Short URL
 https://ia.cr/2018/429
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/429, author = {Ignacio Cascudo and Ronald Cramer and Chaoping Xing and Chen Yuan}, title = {Amortized Complexity of InformationTheoretically Secure MPC Revisited}, howpublished = {Cryptology ePrint Archive, Paper 2018/429}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/429}}, url = {https://eprint.iacr.org/2018/429} }