[Resource Topic] 2016/137: Rate-1, Linear Time and Additively Homomorphic UC Commitments

Welcome to the resource topic for 2016/137

Rate-1, Linear Time and Additively Homomorphic UC Commitments

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


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.

ePrint: https://eprint.iacr.org/2016/137

Talk: https://www.youtube.com/watch?v=w1js8QfIRGE

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .