Cryptology ePrint Archive: Report 2018/475

Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures

Jonathan Katz and Vladimir Kolesnikov and Xiao Wang

Abstract: Recent work, including ZKBoo, ZKB++, and Ligero, has developed efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoKs) for arbitrary 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 move 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++ (with 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.

Category / Keywords: cryptographic protocols / zero-knowledge proofs, signatures

Date: received 18 May 2018, last revised 20 Aug 2018

Contact author: wangxiao at cs umd edu

Available format(s): PDF | BibTeX Citation

Version: 20180820:210516 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]