Efficient Constructions of Composable Commitments and Zero-Knowledge Proofs

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

.