You are looking at a specific version 20121221:062714 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.