Paper 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.
Note: Fixed a description error of the schemes in Section 8.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Universal composabilityUC commitment
- Contact author(s)
- fujisaki eiichiro @ lab ntt co jp
- History
- 2016-06-16: last of 6 revisions
- 2012-07-05: received
- See all versions
- Short URL
- https://ia.cr/2012/379
- License
-
CC BY