Paper 2014/370

Compact VSS and Efficient Homomorphic UC Commitments

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


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.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2014
UCcommitmenthomomorphicconstant overhead
Contact author(s)
giacomelli @ cs au dk
2014-11-26: revised
2014-05-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ivan Damgård and Bernardo David and Irene Giacomelli and Jesper Buus Nielsen},
      title = {Compact {VSS} and Efficient Homomorphic {UC} Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2014/370},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.