- Two-round witness indistinguishable (WI) arguments for $\NP$ from different assumptions than previously known.
- Two-round arguments and three-round proofs 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 N^th 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.
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 more applications in the future.Category / Keywords: cryptographic protocols / input-delayed, weak zero knowledge, strong witness indistinguishability, witness hiding, two rounds, input indistinguishable computation Date: received 13 Apr 2017, last revised 13 Apr 2017 Contact author: dakshita at cs ucla edu Available format(s): PDF | BibTeX Citation Version: 20170417:154329 (All versions of this report) Short URL: ia.cr/2017/330 Discussion forum: Show discussion | Start new discussion