Gotowa bibliografia na temat „Adaptively-secure multiparty computation”

We consider verifiable secret sharing (VSS) and multiparty computation (MPC) in the secure channels model, where a broadcast channel is given and a non-zero error probability is allowed. In this model Rabin and Ben-Or proposed VSS and MPC protocols, secure against an adversary that can corrupt any minority of the players. In this paper, we rst observe that a subprotocol of theirs, known as weak secret sharing (WSS), is not secure against an adaptive adversary, contrary to what was believed earlier. We then propose new and adaptively secure protocols for WSS, VSS and MPC that are substantially more efficient than the original ones. Our protocols generalize easily to provide security against general Q2 adversaries.

Despite being a relatively young field, cryptography taught us how to perform seemingly-impossible tasks, which now became part of our everyday life. One of them is secure multiparty computation (MPC), which allows mutually distrustful parties to jointly perform a computation on their private inputs, so that each party only learns its prescribed output, but nothing else. In this work we deal with two longstanding challenges of MPC: adaptive security and deniability (or, incoercibility). A protocol is said to be adaptively secure, if it still guarantees security for the remaining honest parties, even if some parties turn dishonest during the execution of the protocol, or even after the execution. (In contrast, statically secure protocols give security guarantees only when the set of dishonest parties is fixed before the execution starts.) While adaptive security threat model is often more realistic than the static one, there is a huge gap between efficiency of statically and adaptively secure protocols: adaptively secure protocols often require more complicated constructions, stronger assumptions, and more rounds of interaction. We improve in efficiency over the state of the art in adaptive security for a number of settings, including the first adaptively secure MPC protocol in constant number of rounds, under assumptions comparable to those of static protocols (previously known protocols required as many rounds of interaction as the depth of the circuit being computed). The second challenge we deal with is providing resilience in the situation where an external coercer demands that participants disclose their private inputs and all their secret keys - e.g. via threats, bribe, or court order. Deniable (or, incoercible) protocols allow coerced participants to convincingly lie about their inputs and secret keys, thereby still maintaining their privacy. While the concept was proposed more than twenty years ago, to date secure protocols withstanding coercion of all participants were not known, even for the simple case of encryption. We present the first construction of such an encryption scheme, and then show how to combine it with adaptively secure protocols to obtain the first incoercible MPC which withstands coercion of all parties.

Adaptive security embodies one of the strongest notions of security that allows an adversary to corrupt parties at any point during protocol execution and gain access to its internal state. Since it models reallife situations such as “hacking”, efficient adaptively-secure multiparty computation (MPC) protocols are desirable. Such protocols demand primitives such as zero knowledge (ZK), oblivious transfer (OT) and commitment schemes that are adaptively-secure as building blocks. Efficient realizations of these primitives have been found to be challenging, especially in the no erasure model. We make progress in this direction and provide efficient constructions that are Universally-Composable in the random oracle model. The study of efficient ZK protocols for non-algebraic statements has seen rapid progress in recent times, relying on the techniques from secure computation. Our primary contribution in ZK lies in constructing efficient constant round ZK protocols from garbled circuits that are adaptively-secure, with communication linear in the size of the statement. We begin by showing that the practically efficient ZK protocol of Jawurek et al. (CCS 2013) is adaptively-secure when the underlying OT satisfies a mild adaptive security guarantee. We gain adaptive security with little to no overhead over the static case. A conditional verification technique is then used to obtain a three-round adaptively secure zero-knowledge argument in the non-programmable non-observable random oracle model. We present the first round optimal framework for building adaptively-secure OT in the programmable random oracle (PRO) model, relying upon the framework of Peikert et al. (Crypto 2008). When instantiated with Decisional Diffie Hellman assumption, it incurs a minimal communication overhead of one bit string and computational overhead of 5 random oracle queries over its static counterpart, where is the security parameter. Additionally, we obtain a construction of adaptively-secure 1-out-of-N OT by extending the result of Naor et al. (Journal of Cryptology 2005) that transforms log N copies of 1-out-of-2 OTs to one 1-out-of-N OT in the PRO model. We complete the picture of efficient OT constructions by presenting the first adaptively secure OT Extension, extending the protocol of Asharov et al. (Eurocrypt 2015) for the adaptive setting using PRO. Our OT extension enables us to obtain adaptive OTs at an amortized cost of 3 symmetric key operations and communication of 3 bit strings. We present an adaptively secure commitment scheme solely relying on observable random oracle (ORO). Our commitment scheme has a one-time offline setup phase, where a common reference string (crs) is generated between the parties using an ORO. In the online phase, the parties use the crs and ORO to generate commitments in a non-interactive fashion. Our construction incurs communication of 4 bit strings and computation of 8 exponentiations and 4 random oracle queries for committing to an arbitrary length message. It finds applications in secure two-party computation (2PC) protocols that adopt offline-online paradigm, where the crs can be generated in the offline phase and the scheme can be used in the online phase.