You are looking at a specific version 20160502:103605 of this paper. See the latest version.

Paper 2015/694

On the Complexity of Additively Homomorphic UC Commitments

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

Abstract

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: Updated protocol and proof to address an issue found regarding the number of linear combinations needed. Tables and rest of the paper updated to reflect this.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2016
Keywords
CommitmentsUCHomomorphicMinimal AssumptionsLinear Error Correcting CodesErasure Codes.
Contact author(s)
roberto @ cs au dk
History
2017-05-16: last of 5 revisions
2015-07-13: received
See all versions
Short URL
https://ia.cr/2015/694
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.