International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Resettable Statistical Zero-Knowledge for NP

Authors:
Susumu Kiyoshima , NTT Social Informatics Laboratories
Download:
DOI: 10.1007/978-3-031-68400-5_9 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
Abstract: 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.
BibTeX
@inproceedings{crypto-2024-34142,
  title={Resettable Statistical Zero-Knowledge for NP},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68400-5_9},
  author={Susumu Kiyoshima},
  year=2024
}