IACR News item: 06 July 2012
Eiichiro Fujisaki
ePrint ReportPreviously, such fully-equipped UC commitment schemes are
only known in \\cite{CF01,CLOS02}, with an unavoidable overhead of $O(\\spar)$; meaning that to commit $\\lambda$ bit, the communication and computational costs are $O(\\lambda\\spar)$. Efficient construction of a fully-equipped UC commitment scheme was a long-standing open problem. We introduce a new cryptographic primitive, called all-but-many encryptions (ABMEs), and prove that it is a translation of fully-equipped UC commitment in the algorithmic level. We implement ABMEs from two primitives, called probabilistic pseudo random functions
and extractable sigma protocols, where the former is a probabilistic version of pseudo random function and the latter is a special kind of sigma (i.e., canonical 3-round public-coin HVSZK) protocols with some extractability.
Interestingly, ABEs are not chosen-ciphertext secure, but still suffice to construct UC commitments without an additional zero-knowledge protocol.
We provide efficient fully-equipped UC commitment schemes
from ABMEs under DDH and DCR-based assumptions. The former is at least as efficient as the arguably most efficient UC commitment scheme~\\cite{Lin11:UCCom} (which is interactive and not erasure-free) in reasonable security parameters.
The latter is the first fully-equipped UC commitment scheme
with optimal expansion factor $O(1)$.
We also construct a fully-equipped UC commitment scheme from
a general assumption (that trap-door permutations exist), converted from a weak ABME in an non-black-box manner, which is far more efficient than the previous general construction~\\cite{CLOS02}, because it does not require any non-interactive zero knowledge protocol.
Additional news items may be found on the IACR news page.