Paper 2014/370

Compact VSS and Efficient Homomorphic UC Commitments

Ivan Damgård, Bernardo David, 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.