Amortized complexity of information-theoretically secure MPC revisited

Ignacio Cascudo, Ronald Cramer, Chaoping Xing, Chen Yuan

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

8 Citationer (Scopus)


A fundamental and widely-applied paradigm due to Franklin and Yung (STOC 1992) on Shamir-secret-sharing based general n-player MPC shows how one may trade the adversary threshold t 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 t+ 2 k- 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 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 ⌊ (n- 1)/ 3 ⌋ 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 ⌊ (n-1)/ 3 ⌋, it is possible to securely compute a binary circuit with amortized complexity O(n) of bits per gate per instance. Known results would give nlog n bits instead. By combining our result with the Franklin-Yung paradigm, and assuming a sub-optimal adversary (i.e., an arbitrarily small ϵ> 0 fraction below 1/3), this is improved to O(1) bits instead of O(n).

TitelAdvances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings : 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part III
RedaktørerHovav Shacham, Alexandra Boldyreva
Antal sider32
Publikationsdato1 jan. 2018
ISBN (Trykt)978-3-319-96877-3
ISBN (Elektronisk)978-3-319-96878-0
StatusUdgivet - 1 jan. 2018
Begivenhed38th Annual International Cryptology Conference - Santa Barbara, USA
Varighed: 19 aug. 201823 aug. 2018
Konferencens nummer: 38


Konference38th Annual International Cryptology Conference
BySanta Barbara
NavnLecture Notes in Computer Science

Fingeraftryk Dyk ned i forskningsemnerne om 'Amortized complexity of information-theoretically secure MPC revisited'. Sammen danner de et unikt fingeraftryk.