Welcome to the resource topic for 2014/370
Title:
Compact VSS and Efficient Homomorphic UC Commitments
Authors: Ivan Damgård, Bernardo David, Irene Giacomelli, 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.
ePrint: https://eprint.iacr.org/2014/370
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .