Improved non-interactive zero knowledge with applications to post-quantum signatures

Jonathan Katz, Vladimir Kolesnikov, Xiao Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Citations (Scopus)

Abstract

Recent work, including ZKBoo, ZKB++, and Ligero, has developed efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoKs) for Boolean circuits based on symmetric-key primitives alone, using the “MPC-in-the-head” paradigm of Ishai et al. We show how to instantiate this paradigm with MPC protocols in the preprocessing model; once optimized, this results in an NIZKPoK with shorter proofs (and comparable computation) as in prior work for circuits containing roughly 300-100,000 AND gates. In contrast to prior work, our NIZKPoK also supports witness-independent preprocessing, which allows the prover to shift most of its work to an offline phase before the witness is known. We use our NIZKPoK to construct a signature scheme based only on symmetric-key primitives (and hence with “post-quantum” security). The resulting scheme has shorter signatures than the scheme built using ZKB++ (and comparable signing/verification time), and is even competitive with hash-based signature schemes. To further highlight the flexibility and power of our NIZKPoK, we also use it to build efficient ring and group signatures based on symmetric-key primitives alone. To our knowledge, the resulting schemes are the most efficient constructions of these primitives that offer post-quantum security.

Original languageEnglish (US)
Title of host publicationCCS 2018 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Pages525-537
Number of pages13
ISBN (Electronic)9781450356930
DOIs
StatePublished - Oct 15 2018
Event25th ACM Conference on Computer and Communications Security, CCS 2018 - Toronto, Canada
Duration: Oct 15 2018 → …

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Conference

Conference25th ACM Conference on Computer and Communications Security, CCS 2018
CountryCanada
CityToronto
Period10/15/18 → …

Fingerprint

Networks (circuits)
Network protocols

Keywords

  • Zero-knowledge proof; Post-quantum signature

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Cite this

Katz, J., Kolesnikov, V., & Wang, X. (2018). Improved non-interactive zero knowledge with applications to post-quantum signatures. In CCS 2018 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (pp. 525-537). (Proceedings of the ACM Conference on Computer and Communications Security). Association for Computing Machinery. https://doi.org/10.1145/3243734.3243805
Katz, Jonathan ; Kolesnikov, Vladimir ; Wang, Xiao. / Improved non-interactive zero knowledge with applications to post-quantum signatures. CCS 2018 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 2018. pp. 525-537 (Proceedings of the ACM Conference on Computer and Communications Security).
@inproceedings{d04fb951cb5e4aed904230538e1e3bfb,
title = "Improved non-interactive zero knowledge with applications to post-quantum signatures",
abstract = "Recent work, including ZKBoo, ZKB++, and Ligero, has developed efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoKs) for Boolean circuits based on symmetric-key primitives alone, using the “MPC-in-the-head” paradigm of Ishai et al. We show how to instantiate this paradigm with MPC protocols in the preprocessing model; once optimized, this results in an NIZKPoK with shorter proofs (and comparable computation) as in prior work for circuits containing roughly 300-100,000 AND gates. In contrast to prior work, our NIZKPoK also supports witness-independent preprocessing, which allows the prover to shift most of its work to an offline phase before the witness is known. We use our NIZKPoK to construct a signature scheme based only on symmetric-key primitives (and hence with “post-quantum” security). The resulting scheme has shorter signatures than the scheme built using ZKB++ (and comparable signing/verification time), and is even competitive with hash-based signature schemes. To further highlight the flexibility and power of our NIZKPoK, we also use it to build efficient ring and group signatures based on symmetric-key primitives alone. To our knowledge, the resulting schemes are the most efficient constructions of these primitives that offer post-quantum security.",
keywords = "Zero-knowledge proof; Post-quantum signature",
author = "Jonathan Katz and Vladimir Kolesnikov and Xiao Wang",
year = "2018",
month = "10",
day = "15",
doi = "10.1145/3243734.3243805",
language = "English (US)",
series = "Proceedings of the ACM Conference on Computer and Communications Security",
publisher = "Association for Computing Machinery",
pages = "525--537",
booktitle = "CCS 2018 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security",

}

Katz, J, Kolesnikov, V & Wang, X 2018, Improved non-interactive zero knowledge with applications to post-quantum signatures. in CCS 2018 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. Proceedings of the ACM Conference on Computer and Communications Security, Association for Computing Machinery, pp. 525-537, 25th ACM Conference on Computer and Communications Security, CCS 2018, Toronto, Canada, 10/15/18. https://doi.org/10.1145/3243734.3243805

Improved non-interactive zero knowledge with applications to post-quantum signatures. / Katz, Jonathan; Kolesnikov, Vladimir; Wang, Xiao.

CCS 2018 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 2018. p. 525-537 (Proceedings of the ACM Conference on Computer and Communications Security).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Improved non-interactive zero knowledge with applications to post-quantum signatures

AU - Katz, Jonathan

AU - Kolesnikov, Vladimir

AU - Wang, Xiao

PY - 2018/10/15

Y1 - 2018/10/15

N2 - Recent work, including ZKBoo, ZKB++, and Ligero, has developed efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoKs) for Boolean circuits based on symmetric-key primitives alone, using the “MPC-in-the-head” paradigm of Ishai et al. We show how to instantiate this paradigm with MPC protocols in the preprocessing model; once optimized, this results in an NIZKPoK with shorter proofs (and comparable computation) as in prior work for circuits containing roughly 300-100,000 AND gates. In contrast to prior work, our NIZKPoK also supports witness-independent preprocessing, which allows the prover to shift most of its work to an offline phase before the witness is known. We use our NIZKPoK to construct a signature scheme based only on symmetric-key primitives (and hence with “post-quantum” security). The resulting scheme has shorter signatures than the scheme built using ZKB++ (and comparable signing/verification time), and is even competitive with hash-based signature schemes. To further highlight the flexibility and power of our NIZKPoK, we also use it to build efficient ring and group signatures based on symmetric-key primitives alone. To our knowledge, the resulting schemes are the most efficient constructions of these primitives that offer post-quantum security.

AB - Recent work, including ZKBoo, ZKB++, and Ligero, has developed efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoKs) for Boolean circuits based on symmetric-key primitives alone, using the “MPC-in-the-head” paradigm of Ishai et al. We show how to instantiate this paradigm with MPC protocols in the preprocessing model; once optimized, this results in an NIZKPoK with shorter proofs (and comparable computation) as in prior work for circuits containing roughly 300-100,000 AND gates. In contrast to prior work, our NIZKPoK also supports witness-independent preprocessing, which allows the prover to shift most of its work to an offline phase before the witness is known. We use our NIZKPoK to construct a signature scheme based only on symmetric-key primitives (and hence with “post-quantum” security). The resulting scheme has shorter signatures than the scheme built using ZKB++ (and comparable signing/verification time), and is even competitive with hash-based signature schemes. To further highlight the flexibility and power of our NIZKPoK, we also use it to build efficient ring and group signatures based on symmetric-key primitives alone. To our knowledge, the resulting schemes are the most efficient constructions of these primitives that offer post-quantum security.

KW - Zero-knowledge proof; Post-quantum signature

UR - http://www.scopus.com/inward/record.url?scp=85056886844&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85056886844&partnerID=8YFLogxK

U2 - 10.1145/3243734.3243805

DO - 10.1145/3243734.3243805

M3 - Conference contribution

AN - SCOPUS:85056886844

T3 - Proceedings of the ACM Conference on Computer and Communications Security

SP - 525

EP - 537

BT - CCS 2018 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security

PB - Association for Computing Machinery

ER -

Katz J, Kolesnikov V, Wang X. Improved non-interactive zero knowledge with applications to post-quantum signatures. In CCS 2018 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery. 2018. p. 525-537. (Proceedings of the ACM Conference on Computer and Communications Security). https://doi.org/10.1145/3243734.3243805