Cryptology ePrint Archive: Report 2016/137
Rate-1, Linear Time and Additively Homomorphic UC Commitments
Ignacio Cascudo and Ivan Damgård and Bernardo David and 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.
Category / Keywords: commitment, asymptotic efficiency, universal composability, coding theory
Original Publication (with minor differences): IACR-CRYPTO-2016
Date: received 15 Feb 2016, last revised 4 Oct 2016
Contact author: bernardo at cs au dk
Available format(s): PDF | BibTeX Citation
Version: 20161004:141206 (All versions of this report)
Short URL: ia.cr/2016/137
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]