Compact Zero-Knowledge Proofs of Small Hamming Weight

Ivan Damgård, Ji Luo, Sabine Oechsner, Peter Scholl, Mark Simkin

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We introduce a new technique that allows to give a zero-knowledge proof that a committed vector has Hamming weight bounded by a given constant. The proof has unconditional soundness and is very compact: It has size independent of the length of the committed string, and for large fields, it has size corresponding to a constant number of commitments. We show five applications of the technique that play on a common theme, namely that our proof allows us to get malicious security at small overhead compared to semi-honest security: (1) actively secure k-out-of-n OT from black-box use of 1-out-of-2 OT, (2) separable accountable ring signatures, (3) more efficient preprocessing for the TinyTable secure two-party computation protocol, (4) mixing with public verifiability, and (5) PIR with security against a malicious client.
Original languageEnglish
Title of host publicationPublic-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
EditorsM. Abdalla, R. Dahab
PublisherSpringer Verlag
Pages530-560
ISBN (Print)9783319765778
DOIs
Publication statusPublished - 2018
Externally publishedYes
Event21st IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2018 - Rio de Janeiro, Brazil
Duration: 25 Mar 201829 Mar 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2018
Country/TerritoryBrazil
CityRio de Janeiro
Period25/03/1829/03/18

Funding

Acknowledgements. This work has been supported by the European Research Council (ERC) under the European Unions’s Horizon 2020 research and innovation programme under grant agreement No. 669255 (MPCPRO); the European Union’s Horizon 2020 research and innovation programme under grant agreement No. 731583 (SODA); and the Danish Independent Research Council under Grant-ID DFF–6108-00169 (FoCC).

FundersFunder number
Danish Independent Research CouncilDFF–6108-00169
European Research Council
European Union’s Horizon 2020
Horizon 2020
Horizon 2020 Framework Programme669255, 731583

    Fingerprint

    Dive into the research topics of 'Compact Zero-Knowledge Proofs of Small Hamming Weight'. Together they form a unique fingerprint.

    Cite this