TY - GEN
T1 - Compact Zero-Knowledge Proofs of Small Hamming Weight
AU - Damgård, Ivan
AU - Luo, Ji
AU - Oechsner, Sabine
AU - Scholl, Peter
AU - Simkin, Mark
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85044005480&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-76581-5_18
DO - 10.1007/978-3-319-76581-5_18
M3 - Conference contribution
SN - 9783319765778
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 530
EP - 560
BT - Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
A2 - Abdalla, M.
A2 - Dahab, R.
PB - Springer Verlag
T2 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2018
Y2 - 25 March 2018 through 29 March 2018
ER -