Journal of the Graduate School of the Chinese Academy of Sciences

An efficient compiler from Σ-protocol to deniable zero knowledge in CRS model

Wei‐Qing Huang

Published Jan 1, 2010• 0 citations

Abstract

In this paper,we present a positive result on deniable zero knowledge in the common reference string (CRS ) model: an efficient transformation from Σ-protocol to deniable zero knowledge in CRS model.According to the lower bound given by Pass,for deniable zero knowledge in CRS model,our compiler achieves optimal round efficiency.In addition,the transformation induces only a small additive overhead in communication complexity.

Related papers

On Deniability in the Common Reference String and Random Oracle Model

Rafael Pass

Abstract. We revisit the definitions of zero-knowledge in the Common Reference String (CRS) model and the Random Oracle (RO) model. We argue that even though these definitions syntactically mimic the standard zero-knowledge definition, they loose some of its spirit. In particular, we show that there exist a specific natural security property that is not captured by these definitions. This is the property of deniability. We formally define the notion of deniable zero-knowledge in these models and investigate the possibility of achieving it. Our results are different for the two models: – Concerning the CRS model, we rule out the possibility of achieving deniable zero-knowledge protocols in “natural ” settings where such protocols cannot already be achieved in plain model. – In the RO model, on the other hand, we construct an efficient 2-round deniable zero-knowledge argument of knowledge, that preserves both the zero-knowledge property and the proof of knowledge property under concurrent executions (concurrent zero-knowledge and concurrent proof-of knowledge). 1

Jan 1, 20030 citations

Generic construction of deniable group key establishment from group key establishment

Bao Li

A generic way to construct a deniable group key establishment protocol from an unauthenticated group key es-tablishment protocol was proposed.The construction could be seen as a compiler.By using Schnorr's zero-knowledge identification scheme,this compiler could transform an unauthenticated group key establishment to a deniable group key establishment protocol with only additional two round communications and one round verification.It is very efficient and practical.The security and deniability proof is in the Random Oracle model.A concrete transforming example of the con-struction was also presented.

Journal of CommunicationsJan 1, 20111 citation

Towards Accountability in CRS Generation

Prabhanjan Ananth, Gilad Asharov, Hila Dahari +1 more

Abstract It is well known that several cryptographic primitives cannot be achieved without a common reference string (CRS). Those include, for instance, non-interactive zero-knowledge for NP, or maliciously secure computation in fewer than four rounds. The security of those primitives heavily relies on the assumption that the trusted authority, who generates the CRS, does not misuse the randomness used in the CRS generation. However, we argue that there is no such thing as an unconditionally trusted authority and every authority must be held accountable for any trust to be well-founded. Indeed, a malicious authority can, for instance, recover private inputs of honest parties given transcripts of the protocols executed with respect to the CRS it has generated. While eliminating trust in the trusted authority may not be entirely feasible, can we at least move towards achieving some notion of accountability? We propose a new notion in which, if the CRS authority releases the private inputs of protocol executions to others, we can then provide a publicly-verifiable proof that certifies that the authority misbehaved. We study the feasibility of this notion in the context of non-interactive zero knowledge and two-round secure two-party computation.

Journal of CryptologyAug 12, 20250 citations

Efficient, Adaptively Secure, and Composable Oblivious Transfer with a Single, Global CRS.

Seung Geol Choi, Jonathan I. Katz, Hoeteck Wee +1 more

We present a general framework for efficient, universally composable oblivious transfer (OT) protocols in which a single, global, common reference string (CRS) can be used for multiple invocations of oblivious transfer by arbitrary pairs of parties. In addition: • Our framework is round-efficient. E.g., under the DLIN or SXDH assumptions we achieve round-optimal protocols with static security, or 3-round protocols with adaptive security (assuming erasure). • Our resulting protocols are more efficient than any known previously, and in particular yield protocols for string OT using O(1) exponentiations and communicating O(1) group elements. Our result improves on that of Peikert et al. (Crypto 2008), which uses a CRS whose length depends on the number of parties in the network and achieves only static security. Compared to Garay et al. (Crypto 2009), we achieve adaptive security with better round complexity and efficiency. ∗Columbia University. Email: sgchoi@cs.columbia.edu. Portions of this work were done at the University of Maryland. This work was supported in part by the Intelligence Advanced Research Project Activity (IARPA) via DoI/NBC contract Number D11PC20194. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of IARPA, DoI/NBC, or the U.S. Government. †Dept. of Computer Science, University of Maryland. Email: jkatz@cs.umd.edu. This work is supported in part by DARPA and by NSF awards #0447075, #1111599, and #1223623. ‡George Washington University. Email: hoeteck@alum.mit.edu. Supported by NSF CAREER award #1237429. §Dept. of Computer Science, Virginia Commonwealth University. Email: hszhou@vcu.edu. Work supported in part by an NSF CI postdoctoral fellowship, and done while at University of Maryland.

Jan 1, 20121 citation

An Efficient Compiler from Σ-Protocol to 2-Move Deniable Zero-Knowledge

Jun Furukawa, Kaoru Kurosawa, Hideki Imai

Lecture notes in computer scienceJan 1, 20065 citations

Impossibility Results for Leakage-Resilient Zero Knowledge and Multi-Party Computation.

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

In [AGP14] Ananth et al. showed that continual leakage-resilient non-transferable interactive proofs exist when a leak-free input-encoding phase is allowed and a common reference string is available. They left open the problem of removing the need of a common reference string. In [BGJK12] Boyle et al. showed that for some interesting functionalities continual leakage-resilient secure computation is possible when leak-free interactive preprocessing and input-encoding phases are allowed. They left open the problem of removing the interactive pre-processing. In this work we study the above questions. Our main contribution shows that leakage-resilient black-box zero-knowledge is impossible when relying on a leak-free input-encoding phase only (i.e., without CRS/preprocessing). Additionally, we also show that leakage-resilient multi-party computation for all functionalities is impossible (regardless of the number of players assuming just one corrupted player) when relying only on a leak-free input-encoding phase (i.e., without CRS/preprocessing). Our results are achieved by extending a technique of [NVZ13] to prove lower bounds for leakage-resilient security. Indeed as in [NVZ13] we use leakage queries to run an execution of a communication-efficient protocol in the head of the adversary. Moreover, to defeat the black-box simulator we connect the above technique for leakage resilience to security against reset attacks.

Jan 1, 20140 citations