TY - GEN
T1 - Efficient constructions of composable commitments and zero-knowledge proofs
AU - Dodis, Yevgeniy
AU - Shoup, Victor
AU - Walfish, Shabsi
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=51849131499&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=51849131499&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-85174-5_29
DO - 10.1007/978-3-540-85174-5_29
M3 - Conference contribution
AN - SCOPUS:51849131499
SN - 3540851739
SN - 9783540851738
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 515
EP - 535
BT - Advances in Cryptology - CRYPTO 2008 - 28th Annual International Cryptology Conference, Proceedings
T2 - 28th Annual International Cryptology Conference, CRYPTO 2008
Y2 - 17 August 2008 through 21 August 2008
ER -