Paper 2011/180

Highly-Efficient Universally-Composable Commitments based on the DDH Assumption

Yehuda Lindell

Abstract

Universal composability (or UC security) provides very strong security guarantees for protocols that run in complex real-world environments. In particular, security is guaranteed to hold when the protocol is run concurrently many times with other secure and possibly insecure protocols. Commitment schemes are a basic building block in many cryptographic constructions, and as such universally composable commitments are of great importance in constructing UC-secure protocols. In this paper, we construct highly efficient UC-secure commitments from the standard DDH assumption, in the common reference string model. Our commitment stage is non-interactive, has a common reference string with $O(1)$ group elements, and has complexity of $O(1)$ exponentiations for committing to a group element (to be more exact, the effective cost is that of $23\frac{1}{3}$ exponentiations overall, for both the commit and decommit stages). Our scheme is secure in the presence of static adversaries.

Note: The original version of this paper also contained a version of the protocol that was claimed to be secure under adaptive corruptions with erasures. The construction was not secure and this was discovered and fixed by Blazy et al. in ePrint report 2013/123. We have removed the construction from this paper and refer to their paper for a correct construction and proof.