Paper 2021/1404

Non-interactive Distributional Indistinguishability (NIDI) and Non-Malleable Commitments

Dakshita Khurana

Abstract

We introduce non-interactive distributionally indistinguishable arguments (NIDI) to address a significant weakness of NIWI proofs: namely, the lack of meaningful secrecy when proving statements about $\mathsf{NP}$ languages with unique witnesses. NIDI arguments allow a prover P to send a single message to verifier V, given which V obtains a sample d from a (secret) distribution D, together with a proof of membership of d in an NP language L. The soundness guarantee is that if the sample d obtained by the verifier V is not in L, then V outputs $\bot$. The privacy guarantee is that secrets about the distribution remain hidden: for every pair of distributions $D_0$ and $D_1$ of instance-witness pairs in L such that instances sampled according to $D_0$ or $D_1$ are (sufficiently) hard-to-distinguish, a NIDI that outputs instances according to $D_0$ with proofs of membership in L is indistinguishable from one that outputs instances according to $D_1$ with proofs of membership in L. - We build NIDI arguments for sufficiently hard-to-distinguish distributions assuming sub-exponential indistinguishability obfuscation and sub-exponential one-way functions. - We demonstrate preliminary applications of NIDI and of our techniques to obtaining the first (relaxed) non-interactive constructions in the plain model, from well-founded assumptions, of: 1. Commit-and-prove that provably hides the committed message 2. CCA-secure commitments against non-uniform adversaries. The commit phase of our commitment schemes consists of a single message from the committer to the receiver, followed by a randomized output by the receiver (that need not necessarily be returned to the committer).

Note: Full version of the Eurocrypt 2021 paper.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
Keywords
zero knowledge
Contact author(s)
dakshita @ illinois edu
History
2021-10-18: received
Short URL
https://ia.cr/2021/1404
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1404,
      author = {Dakshita Khurana},
      title = {Non-interactive Distributional Indistinguishability ({NIDI}) and Non-Malleable Commitments},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1404},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1404}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.