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 contribution


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
EditorsMichel Abdalla, Ricardo Dahab
Place of PublicationCham
PublisherSpringer International Publishing
Number of pages31
ISBN (Electronic)978-3-319-76581-5
ISBN (Print)978-3-319-76580-8
Publication statusPublished - 1 Mar 2018
Event21st edition of the International Conference on Practice and Theory of Public Key Cryptography - Rio De Janeiro, Brazil
Duration: 25 Mar 201829 Mar 2018

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st edition of the International Conference on Practice and Theory of Public Key Cryptography
Abbreviated titlePKC 2018
CityRio De Janeiro
Internet address

Cite this