**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 ]