Adaptively Secure Primitives in the Random Oracle Model

Abstract

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.