Resumable Zero-Knowledge for Circuits from Symmetric Key Primitives

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

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, 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)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Resumablehonest verifier zero-knowledgeMPC-in-the-headstateful signaturering signatureblockchain.
Contact author(s)
hdzhang @ mail sdu edu cn
pwei @ sdu edu cn
History
2022-05-11: revised
See all versions
Short URL
https://ia.cr/2022/556

CC BY

BibTeX

@misc{cryptoeprint:2022/556,
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{https://eprint.iacr.org/2022/556}},
url = {https://eprint.iacr.org/2022/556}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.