Distinguisher-dependent simulation in two rounds and its applications

Abhishek Jain, Yael Tauman Kalai, Dakshita Khurana, Ron Rothblum

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

Abstract

We devise a novel simulation technique that makes black-box use of the adversary as well as the distinguisher. Using this technique we construct several round-optimal protocols, many of which were previously unknown even using non-black-box simulation techniques: – Two-round witness indistinguishable (WI) arguments for NP from different assumptions than previously known. – Two-round arguments and three-round arguments of knowledge for NP that achieve strong WI, witness hiding (WH) and distributional weak zero knowledge (WZK) properties in a setting where the instance is only determined by the prover in the last round of the interaction. The soundness of these protocols is guaranteed against adaptive provers. – Three-round two-party computation satisfying input-indistinguishable security as well as a weaker notion of simulation security against malicious adversaries. – Three-round extractable commitments with guaranteed correctness of extraction from polynomial hardness assumptions. Our three-round protocols can be based on DDH or QR or Nth residuosity and our two-round protocols require quasi-polynomial hardness of the same assumptions. In particular, prior to this work, two-round WI arguments for NP were only known based on assumptions such as the existence of trapdoor permutations, hardness assumptions on bilinear maps, or the existence of program obfuscation; we give the first construction based on (quasi-polynomial) DDH or QR or Nth residuosity. Our simulation technique bypasses known lower bounds on black-box simulation [Goldreich-Krawcyzk’96] by using the distinguisher’s output in a meaningful way. We believe that this technique is likely to find additional applications in the future.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings
EditorsJonathan Katz, Hovav Shacham
PublisherSpringer-Verlag
Pages158-189
Number of pages32
ISBN (Print)9783319637143
DOIs
StatePublished - Jan 1 2017
Externally publishedYes
Event37th Annual International Cryptology Conference, CRYPTO 2017 - Santa Barbara, United States
Duration: Aug 20 2017Aug 24 2017

Publication series

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

Conference

Conference37th Annual International Cryptology Conference, CRYPTO 2017
CountryUnited States
CitySanta Barbara
Period8/20/178/24/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Distinguisher-dependent simulation in two rounds and its applications'. Together they form a unique fingerprint.

Cite this