Paper 2015/694

On the Complexity of Additively Homomorphic UC Commitments

Tore Kasper Frederiksen, Thomas P. Jakobsen, Jesper Buus Nielsen, and Roberto Trifiletti


We present a new constant round additively homomorphic commitment scheme with (amortized) computational and communication complexity linear in the size of the string committed to. Our scheme is based on the non-homomorphic commitment scheme of Cascudo \emph{et al.} presented at PKC 2015. However, we manage to add the additive homo- morphic property, while at the same time reducing the constants. In fact, when opening a large enough batch of commitments we achieve an amor- tized communication complexity converging to the length of the message committed to, i.e., we achieve close to rate 1 as the commitment protocol by Garay \emph{et al.} from Eurocrypt 2014. A main technical improvement over the scheme mentioned above, and other schemes based on using error correcting codes for UC commitment, we develop a new technique which allows to based the extraction property on erasure decoding as opposed to error correction. This allows to use a code with significantly smaller minimal distance and allows to use codes without efficient decoding. Our scheme only relies on standard assumptions. Specifically we require a pseudorandom number generator, a linear error correcting code and an ideal oblivious transfer functionality. Based on this we prove our scheme secure in the Universal Composability (UC) framework against a static and malicious adversary corrupting any number of parties. On a practical note, our scheme improves significantly on the non- homomorphic scheme of Cascudo \emph{et al.} Based on their observations in regards to efficiency of using linear error correcting codes for commit- ments we conjecture that our commitment scheme might in practice be more efficient than all existing constructions of UC commitment, even non-homomorphic constructions and even constructions in the random oracle model. In particular, the amortized price of computing one of our commitments is less than that of evaluating a hash function once.

Note: Added clarification on an error appearing in a previous version of this work. We use the recent notion of interactive proximity testing introduced by Cascudo et al. [CDDDN16] to correct our proof of security.

Available format(s)
Publication info
Published by the IACR in TCC 2016
CommitmentsUCHomomorphicMinimal AssumptionsLinear Error Correcting CodesErasure Codes.
Contact author(s)
roberto @ cs au dk
2017-05-16: last of 5 revisions
2015-07-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tore Kasper Frederiksen and Thomas P.  Jakobsen and Jesper Buus Nielsen and Roberto Trifiletti},
      title = {On the Complexity of Additively Homomorphic {UC} Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2015/694},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.