Paper 2022/556

Resumable Zero-Knowledge for Circuits from Symmetric Key Primitives

Handong Zhang, Puwen Wei, Haiyang Xue, Yi Deng, Jinsong Li, Wei Wang, and Guoxiao Liu


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, Damgaard 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 $2^4$, the size of our ring signature scheme is only about 1/3 of Katz et al.'s construction.

Note: references typos

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Resumablehonest verifier zero-knowledgeMPC-in-the-headstateful signaturering signatureblockchain.
Contact author(s)
hdzhang @ mail sdu edu cn
pwei @ sdu edu cn
2022-05-11: revised
2022-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Handong Zhang and Puwen Wei and Haiyang Xue and Yi Deng and Jinsong Li and Wei Wang and Guoxiao Liu},
      title = {Resumable Zero-Knowledge for Circuits from Symmetric Key Primitives},
      howpublished = {Cryptology ePrint Archive, Paper 2022/556},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.