Post-quantum Resettably-Sound Zero Knowledge

Joshua Baron, Rafail Ostrovsky, Ivan Visconti

Steven Goldfeder, Melissa Chase, Greg Zaverucha

Tao Shang

Wei Zhu, Yi Deng

Abstract In this paper, we construct a 6-round simultaneously resettable sound resettable $$(T, \epsilon )$$ ( T , ϵ ) -zero knowledge protocol for $$\mathsf {NP \cap coNP}$$ NP ∩ coNP in the Public Key model under standard assumptions, comparing with the 27-round simultaneously resettable zero knowledge protocol in the BPK model by Deng et al. in 2011, we have achieved a significant reduction in the round complexity. Our model assumes that both prover and verifier hold public keys, we call it the Public Key model. It is a variation of the traditional BPK model where only the verifier is assumed to hold public keys. In the original BPK model, under the sub-exponential hardness assumption of factoring, we construct a 2-round simultaneously resettable sound resettable $$(T,\epsilon )$$ ( T , ϵ ) -zero knowledge protocol for $$\textsf{NP}$$ NP .

Seiko Arita

In resetting attacks against a proof system, a prover or a verifier is reset and enforced to use the same random tape on various inputs as many times as an adversary may want. Recent deployment of cloud computing gives these attacks a new importance. This paper shows that argument systems for any NP language that are both resettably-sound and resettable zero-knowledge are possible by a constant-round protocol in the BPK model. For that sake, we define and construct a resettably-extractable conditional commitment scheme.

Karmela Padavic-Callaghan