| Consider the scenario that the prover and the verifier run the zero-knowledge(ZK)proof for the same statement repeatedly multiple times,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 HVZK PoK)and propose a general construction of the resumable HVZK PoK 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 proof.To ensure the knowledge soundness for the resumed session,we identify a property called extractable decomposition.Fortunately,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 HVZK PoK,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 size of our subsequent signatures can be reduced to 36%.Moreover,by applying a parallel version of our proof to the well known Cramer,Damagard and Schoenmakers(CDS)transformation,we get a compressed oneout-of-N proof for circuits,which can remove most of the simulation transcripts for the N-1 statements.Combining the straightforward construction of ring signature with our compressed one-out-of-N proof,we propose a ring signature from symmetric key primitives only.When the ring size is less than 24,the size of our scheme is only about 1/3 of the state-of-the-art construction. |
