Cryptology ePrint Archive: Report 2012/379

A Framework for Efficient Fully-Equipped UC Commitments

Eiichiro Fujisaki

Abstract: We present a general framework for constructing non-interactive universally composable (UC) commitment schemes that are secure against adaptive adversaries in the non-erasure setting under a single re-usable common reference string. Previously, such ``fully-equipped'' UC commitment schemes are only known in \cite{CF01,CLOS02}, with an unavoidable overhead of $O(\spar)$ in the sense of communication and computational complexities; meaning that to commit $\lambda$ bits, the communication and computational costs require $O(\lambda\spar)$, where $\spar$ denotes the security parameter. Efficient construction of a fully-equipped UC commitment scheme was a long-standing open problem. We introduce a cryptographic primitive, called all-but-many encryptions (ABMEs), and prove that it is a translation of fully-equipped UC commitment in the primitive level. We then construct ABMEs from cryptographic primitives that we call a probabilistic pseudo random function family and extractable sigma protocols -- the former is a probabilistic version of a pseudo random function family and the latter is a special kind of sigma (i.e., canonical 3-round public-coin HVSZK) protocols with some extractability. We provide fully-equipped UC commitment schemes from ABMEs under DDH and DCR-based assumptions, respectively. In particular, the DCR-based scheme is the first fully-equipped UC commitment scheme with optimal expansion factor $\Omega(1)$; to commit $\spar$ bits, the communication and computational costs are $\Omega(\spar)$. We further construct a fully-equipped UC commitment scheme from a general assumption (in which trap-door permutations exist), which is far more efficient than the previous construction~\cite{CLOS02}, because, unlike \cite{CLOS02}, our construction does not require non-interactive zero-knowledge proof systems.

Category / Keywords: cryptographic protocols / Universal composability, UC commitment,

Date: received 5 Jul 2012, last revised 20 Dec 2012

Contact author: fujisaki eiichiro at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Note: Fixed a description error of the schemes in Section 8.

Version: 20121221:062714 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]