Paper 2024/806

Resettable Statistical Zero-Knowledge for NP

Susumu Kiyoshima, NTT Social Informatics Laboratories

Resettable statistical zero-knowledge [Garg--Ostrovsky--Visconti--Wadia, TCC 2012] is a strong privacy notion that guarantees statistical zero-knowledge even when the prover uses the same randomness in multiple proofs. In this paper, we show an equivalence of resettable statistical zero-knowledge arguments for $NP$ and witness encryption schemes for $NP$. - Positive result: For any $NP$ language $L$, a resettable statistical zero-knowledge argument for $L$ can be constructed from a witness encryption scheme for $L$ under the assumption of the existence of one-way functions. - Negative result: The existence of even resettable statistical witness-indistinguishable arguments for $NP$ imply the existence of witness encryption schemes for $NP$ under the assumption of the existence of one-way functions. The positive result is obtained by naturally extending existing techniques (and is likely to be already well-known among experts). The negative result is our main technical contribution. To explore workarounds for the negative result, we also consider resettable security in a model where the honest party's randomness is only reused with fixed inputs. We show that resettable statistically hiding commitment schemes are impossible even in this model.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2024
Contact author(s)
susumu kiyoshima @ ntt com
2024-05-27: approved
2024-05-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Susumu Kiyoshima},
      title = {Resettable Statistical Zero-Knowledge for {NP}},
      howpublished = {Cryptology ePrint Archive, Paper 2024/806},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.