Paper 2018/983

Efficient UC Commitment Extension with Homomorphism for Free (and Applications)

Ignacio Cascudo, Ivan Damgård, Bernardo David, Nico Döttling, Rafael Dowsley, and Irene Giacomelli

Abstract

Homomorphic universally composable (UC) commitments allow for the sender to reveal the result of additions and multiplications of values contained in commitments without revealing the values themselves while assuring the receiver of the correctness of such computation on committed values. In this work, we construct essentially optimal additively homomorphic UC commitments from any (not necessarily UC or homomorphic) extractable commitment. We obtain amortized linear computational complexity in the length of the input messages and rate 1. Next, we show how to extend our scheme to also obtain multiplicative homomorphism at the cost of asymptotic optimality but retaining low concrete complexity for practical parameters. While the previously best constructions use UC oblivious transfer as the main building block, our constructions only require extractable commitments and PRGs, achieving better concrete efficiency and offering new insights into the sufficient conditions for obtaining homomorphic UC commitments. Moreover, our techniques yield public coin protocols, which are compatible with the Fiat-Shamir heuristic. These results come at the cost of realizing a restricted version of the homomorphic commitment functionality where the sender is allowed to perform any number of commitments and operations on committed messages but is only allowed to perform a single batch opening of a number of commitments. Although this functionality seems restrictive, we show that it can be used as a building block for more efficient instantiations of recent protocols for secure multiparty computation and zero knowledge non-interactive arguments of knowledge.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2019
Keywords
Commitmentsuniversal composabilitysecure multiparty computationzero knowledge
Contact author(s)
ignacio cascudo @ imdea org
History
2019-10-02: last of 2 revisions
2018-10-18: received
See all versions
Short URL
https://ia.cr/2018/983
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/983,
      author = {Ignacio Cascudo and Ivan Damgård and Bernardo David and Nico Döttling and Rafael Dowsley and Irene Giacomelli},
      title = {Efficient UC Commitment Extension with Homomorphism for Free (and Applications)},
      howpublished = {Cryptology ePrint Archive, Paper 2018/983},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/983}},
      url = {https://eprint.iacr.org/2018/983}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.