CryptoDB
Compact Zero-Knowledge Proofs of Small Hamming Weight
| Authors: | |
|---|---|
| Download: | |
| Conference: | PKC 2018 |
| 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. |
BibTeX
@inproceedings{pkc-2018-28900,
title={Compact Zero-Knowledge Proofs of Small Hamming Weight},
booktitle={Public-Key Cryptography – PKC 2018},
series={Public-Key Cryptography – PKC 2018},
publisher={Springer},
volume={10770},
pages={530-560},
doi={10.1007/978-3-319-76581-5_18},
author={Ivan Damgård and Ji Luo and Sabine Oechsner and Peter Scholl and Mark Simkin},
year=2018
}