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

16 Scopus citations

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

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