Paper 2017/1041

Compact Zero-Knowledge Proofs of Small Hamming Weight

Ivan Damgård, Ji Luo, Sabine Oechsner, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in Pkc 2018
Keywords
zero-knowledgeoblivious transferring signatures
Contact author(s)
oechsner @ cs au dk
History
2018-01-05: revised
2017-10-28: received
See all versions
Short URL
https://ia.cr/2017/1041
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1041,
      author = {Ivan Damgård and Ji Luo and Sabine Oechsner and Peter Scholl and Mark Simkin},
      title = {Compact Zero-Knowledge Proofs of Small Hamming Weight},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1041},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1041}},
      url = {https://eprint.iacr.org/2017/1041}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.