Efficient constructions of composable commitments and zero-knowledge proofs

Yevgeniy Dodis, Victor Shoup, Shabsi Walfish

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Canetti et al. [7] recently proposed a new framework - termed Generalized Universal Composability (GUC) - for properly analyzing concurrent execution of cryptographic protocols in the presence of a global setup, and constructed the first known GUC-secure implementations of commitment (GUCC) and zero-knowledge (GUC ZK), which suffice to implement any two-party or multi-party functionality under several natural and relatively mild setup assumptions. Unfortunately, the feasibility results of [7] used rather inefficient constructions. In this paper, we dramatically improve the efficiency of (adaptively-secure) GUCC and GUC ZK assuming data erasures are allowed. Namely, using the same minimal setup assumptions as those used by [7], we build a direct and efficient constant-round GUC ZK for R from any "dense" Ω-protocol [21] for R. As a corollary, we get a semi-efficient construction from any ∑-protocol for R (without doing the Cook-Levin reduction), and a very efficient GUC ZK for proving knowledge of a discrete log representation. the first constant-rate (and constant-round) GUCC scheme. Additionally, we show how to properly model a random oracle in the GUC framework without losing deniability, which is one of the attractive features of the GUC framework. In particular, by adding the random oracle to the setup assumptions used by [7], we build the first two-round (which we show is optimal), deniable, straight-line extractable and simulatable ZK proof for any NP relation R.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2008 - 28th Annual International Cryptology Conference, Proceedings
Number of pages21
StatePublished - 2008
Event28th Annual International Cryptology Conference, CRYPTO 2008 - Santa Barbara, CA, United States
Duration: Aug 17 2008Aug 21 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5157 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other28th Annual International Cryptology Conference, CRYPTO 2008
Country/TerritoryUnited States
CitySanta Barbara, CA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Efficient constructions of composable commitments and zero-knowledge proofs'. Together they form a unique fingerprint.

Cite this