We present new universally composable commitment schemes based on the Paillier cryptosystem and the Okamoto-Uchiyama cryptosystem. The schemes are efficient: to commit to $k$ bits, they use a constant number of modular exponentiations and communicates $O(k)$ bits. Further more the scheme can be instantiated in either perfectly hiding or perfectly binding versions. These are the first schemes to show that constant expansion factor, perfect hiding, and perfect binding can be obtained for universally composable commitments.
We also show how the schemes can be applied to do efficient zero-knowledge proofs of knowledge that are universally composable.Category / Keywords: cryptographic protocols / bit commitment Date: received 5 Nov 2001 Contact author: buus at brics dk Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20011105:182345 (All versions of this report) Short URL: ia.cr/2001/091 Discussion forum: Show discussion | Start new discussion