Rate-1, linear time and additively homomorphic UC commitments

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

We construct the first UC commitment scheme for binary strings with the optimal properties of rate approaching 1 and linear time complexity (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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - 36th Annual International Cryptology Conference, CRYPTO 2016, Proceedings
EditorsMatthew Robshaw, Jonathan Katz
Number of pages29
PublisherSpringer VS
Publication year2016
ISBN (print)9783662530146
ISBN (Electronic) 978-3-662-53015-3
Publication statusPublished - 2016
Event36th Annual International Cryptology Conference, CRYPTO 2016 - Santa Barbara, United States
Duration: 14 Aug 201618 Aug 2016


Conference36th Annual International Cryptology Conference, CRYPTO 2016
LandUnited States
BySanta Barbara
SeriesLecture Notes in Computer Science
Volume 9816

See relations at Aarhus University Citationformats

ID: 108281647