Paper 2016/137

Rate-1, Linear Time and Additively Homomorphic UC Commitments

Ignacio Cascudo, Ivan Damgård, Bernardo David, Nico Döttling, and Jesper Buus Nielsen

Abstract

We propose the first UC commitment scheme for binary strings with the optimal properties of rate approaching 1 and linear time (in the amortised sense, using a small number of seed OTs). On top of this, the scheme is additively homomorphic, which allows for applications to maliciously secure 2-party computation. As tools for obtaining this, we make three contributions of independent interest: we construct the first (binary) linear time encodable codes with non-trivial distance and rate approaching 1, we construct the first almost universal hash function with small seed that can be computed in linear time, and we introduce a new primitive called interactive proximity testing that can be used to verify whether a string is close to a given linear code.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in CRYPTO 2016
Keywords
commitmentasymptotic efficiencyuniversal composabilitycoding theory
Contact author(s)
bernardo @ cs au dk
History
2016-10-04: last of 2 revisions
2016-02-16: received
See all versions
Short URL
https://ia.cr/2016/137
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/137,
      author = {Ignacio Cascudo and Ivan Damgård and Bernardo David and Nico Döttling and Jesper Buus Nielsen},
      title = {Rate-1, Linear Time and Additively Homomorphic UC Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2016/137},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/137}},
      url = {https://eprint.iacr.org/2016/137}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.