Cryptology ePrint Archive: Report 2017/1041

Compact Zero-Knowledge Proofs of Small Hamming Weight

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

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.

Category / Keywords: cryptographic protocols / zero-knowledge, oblivious transfer, ring signatures

Date: received 22 Oct 2017

Contact author: oechsner at cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20171028:204653 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]