Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2022

Abstract

Consider the scenario that the prover and the verifier perform the zero-knowledge (ZK) proof protocol for the same statement multiple times sequentially, where each proof is modeled as a session. We focus on the problem of how to resume a ZK proof efficiently in such scenario. We introduce a new primitive called resumable honest verifier zero-knowledge proof of knowledge (resumable HVZKPoK) and propose a general construction of the resumable HVZKPoK for circuits based on the “MPC-in-the-head" paradigm, where the complexity of the resumed session is less than that of the original ZK proofs. To ensure the knowledge soundness for the resumed session, we identify a property called extractable decomposition. Interestingly, most block ciphers satisfy this property and the cost of resuming session can be reduced dramatically when the underlying circuits are implemented with block ciphers. As a direct application of our resumable HVZKPoK, we construct a post quantum secure stateful signature scheme, which makes Picnic3 suitable for blockchain protocol. Using the same parameter setting of Picnic3, the sign/verify time of our subsequent signatures can be reduced to 3.1%/3.3% of Picnic3 and the corresponding signature size can be reduced to 36%. Moreover, by applying a parallel version of our method to the well known Cramer, Damgård and Schoenmakers (CDS) transformation, we get a compressed one-out-of-N proof for circuits, which can be further used to construct a ring signature from symmetric key primitives only. When the ring size is less than 24, the size of our ring signature scheme is only about 1/3 of Katz et al.’s construction.

Keywords

Resumable, Honest verifier zero-knowledge, MPC-in-the-head, Stateful signature, Ring signature, Blockchain

Discipline

Information Security

Research Areas

Cybersecurity

Areas of Excellence

Digital transformation

Publication

Proceedings of the 27th Australasian Conference, ACISP 2022 Wollongong, Australia, November 28-30

First Page

375

Last Page

398

ISBN

9783031223013

Identifier

10.1007/978-3-031-22301-3_19

Publisher

Springer

City or Country

Cham

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1007/978-3-031-22301-3_19

Download

Share

COinS