Cryptology ePrint Archive: Report 2014/370

Compact VSS and Efficient Homomorphic UC Commitments

Ivan Damgård and Bernardo David and Irene Giacomelli and Jesper Buus Nielsen

Abstract: We present a new compact verifiable secret sharing scheme, based on this we present the first construction of a homomorphic UC commitment scheme that requires only cheap symmetric cryptography, except for a small number of seed OTs. To commit to a $k$-bit string, the amortized communication cost is $O(k)$ bits. Assuming a sufficiently efficient pseudorandom generator, the computational complexity is $O(k)$ for the verifier and $O(k^{1+\epsilon})$ for the committer (where $\epsilon <1$ is a constant). In an alternative variant of the construction, all complexities are $O(k\cdot polylog(k))$. Our commitment scheme extends to vectors over any finite field and is additively homomorphic. By sending one extra message, the prover can allow the verifier to also check multiplicative relations on committed strings, as well as verifying that committed vectors $\vec{a}, \vec{b}$ satisfy $\vec{a}= \varphi( \vec{b})$ for a linear function $\varphi$. These properties allow us to non-interactively implement any one-sided functionality where only one party has input (this includes UC secure zero-knowledge proofs of knowledge). We also present a perfectly secure implementation of any multiparty functionality, based directly on our VSS. The communication required is proportional to a circuit implementing the functionality, up to a logarithmic factor. For a large natural class of circuits the overhead is even constant. We also improve earlier results by Ranellucci \emph{et al.} on the amount of correlated randomness required for string commitments with individual opening of bits.

Category / Keywords: cryptographic protocols / UC, commitment, homomorphic, constant overhead

Date: received 26 May 2014

Contact author: jbn at cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20140527:102044 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]