Statistical witness indistinguishability (and more) in two messages

Yael Tauman Kalai, Dakshita Khurana, Amit Sahai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Two-message witness indistinguishable protocols were first constructed by Dwork and Naor (FOCS 2000). 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:$$\circ $$ Two-message statistical witness indistinguishable (SWI) arguments for NP.$$\circ $$ Two-message statistical zero-knowledge arguments for NP with super-polynomial simulation (Statistical SPS-ZK).$$\circ $$ Two-message statistical distributional weak zero-knowledge (SwZK) arguments for NP, where the simulator is a probabilistic polynomial time machine with oracle access to the distinguisher, and 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), which in turn can be based on quasi-polynomial hardness of DDH or QR or$$N^{th}$$ residuosity. We also show how such protocols can be used to build 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, building on the recent work of Khurana and Sahai (FOCS 17). These techniques may be of independent interest.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018 Proceedings
EditorsJesper Buus Nielsen, Vincent Rijmen
PublisherSpringer
Pages34-65
Number of pages32
ISBN (Print)9783319783710
DOIs
StatePublished - Jan 1 2018
Externally publishedYes
Event37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2018 - Tel Aviv, Israel
Duration: Apr 29 2018May 3 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10822 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2018
CountryIsrael
CityTel Aviv
Period4/29/185/3/18

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Statistical witness indistinguishability (and more) in two messages'. Together they form a unique fingerprint.

Cite this