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
-
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} }