Paper 2018/168

Statistical Witness Indistinguishability (and more) in Two Messages

Yael Tauman Kalai, Dakshita Khurana, and Amit Sahai


Two-message witness indistinguishable protocols were first constructed by Dwork and Naor (FOCS 00). They have since proven extremely useful in the design of several cryptographic primitives. However, so far no two-message arguments for NP provided statistical privacy against malicious verifiers. In this paper, we construct the first: - Two-message statistical witness indistinguishable (SWI) arguments for NP. - Two-message statistical zero-knowledge arguments for NP with super-polynomial simulation (Statistical SPS-ZK). These were previously believed to be impossible to construct via black-box reductions (Chung et al., ePrint 2012). - Two-message statistical distributional weak zero-knowledge (SwZK) arguments for NP with polynomial simulation, where the instance is sampled by the prover in the second round. These protocols are based on quasi-polynomial hardness of two-message oblivious transfer (OT) with game-based security, which can in turn be based on quasi-polynomial DDH or QR or N'th residuosity. We also demonstrate simple applications of these arguments to constructing more secure forms of oblivious transfer. Along the way, we show that the Kalai and Raz (Crypto 09) transform compressing interactive proofs to two-message arguments can be generalized to compress certain types of interactive arguments. We introduce and construct a new technical tool, which is a variant of extractable two-message statistically hiding commitments, by extending the work of Khurana and Sahai (FOCS 17). These techniques may be of independent interest.

Available format(s)
Publication info
Published by the IACR in EUROCRYPT 2018
statistical witness indistinguishabilitysuper-polynomial simulation statistical ZKcompressing interactive argumentsoblivious transfer
Contact author(s)
yaelism @ gmail com
dakshita @ cs ucla edu
amitsahai @ gmail com
2018-02-11: received
Short URL
Creative Commons Attribution


      author = {Yael Tauman Kalai and Dakshita Khurana and Amit Sahai},
      title = {Statistical Witness Indistinguishability (and more) in Two Messages},
      howpublished = {Cryptology ePrint Archive, Paper 2018/168},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.