Paper 2018/168

Statistical Witness Indistinguishability (and more) in Two Messages

Yael Tauman Kalai, Dakshita Khurana, and Amit Sahai

Abstract

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.