### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2016/137

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.