Aktiviteter pr. år
Abstrakt
A fundamental and widelyapplied paradigm due to Franklin and Yung (STOC 1992) on Shamirsecretsharing based general nplayer 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+ 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 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 ⌊ (n 1)/ 3 ⌋ 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 ⌊ (n1)/ 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 FranklinYung paradigm, and assuming a suboptimal adversary (i.e., an arbitrarily small ϵ> 0 fraction below 1/3), this is improved to O(1) bits instead of O(n).
Originalsprog  Engelsk 

Titel  Advances 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ører  Hovav Shacham, Alexandra Boldyreva 
Antal sider  32 
Forlag  Springer 
Publikationsdato  1 jan. 2018 
Sider  395426 
ISBN (Trykt)  9783319968773 
ISBN (Elektronisk)  9783319968780 
DOI  
Status  Udgivet  1 jan. 2018 
Begivenhed  38th Annual International Cryptology Conference  Santa Barbara, USA Varighed: 19 aug. 2018 → 23 aug. 2018 Konferencens nummer: 38 
Konference
Konference  38th Annual International Cryptology Conference 

Nummer  38 
Land  USA 
By  Santa Barbara 
Periode  19/08/2018 → 23/08/2018 
Navn  Lecture Notes in Computer Science 

Vol/bind  10993 
ISSN  03029743 
Fingeraftryk Dyk ned i forskningsemnerne om 'Amortized complexity of informationtheoretically secure MPC revisited'. Sammen danner de et unikt fingeraftryk.
Aktiviteter
 1 Konferenceoplæg

Amortized Complexity of Information Theoretically Secure MPC Revisited
Ignacio Cascudo Pueyo (Foredragsholder)
22 aug. 2018Aktivitet: Foredrag og mundtlige bidrag › Konferenceoplæg