International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Dakshita Khurana , UIUC
DOI: 10.1007/978-3-030-77883-5_7 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Abstract: We introduce non-interactive distributionally indistinguishable arguments (NIDI) to remedy a significant weakness of NIWI proofs: namely, the lack of meaningful secrecy when proving statements about NP languages with unique witnesses. NIDI arguments allow a prover $\cP$ to send a single message to verifier $\cV$, given which $\cV$ can obtain a sample $d$ from a (secret) distribution $\cD$ together with a proof of membership of $d$ in an NP language. The soundness guarantee is that if the sample $d$ obtained by the verifier $\cV$ is not in the language, then $\cV$ outputs $\bot$. The secrecy guarantee is that secrets about the distribution remain hidden: for every pair of (sufficiently) hard-to-distinguish distributions $\cD_0$ and $\cD_1$, a NIDI that outputs samples from $\cD_0$ with proofs is indistinguishable from one that outputs samples from $\cD_1$ with proofs. We build NIDI arguments that satisfy secrecy for sufficiently hard distributions, assuming sub-exponential indistinguishability obfuscation and sub-exponentially secure (variants of) 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: -- Commit-and-prove that provably hides the committed message -- 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 be sent to the committer).
Video from EUROCRYPT 2021
  title={Non-interactive Distributional Indistinguishability (NIDI) and Non-Malleable Commitments},
  author={Dakshita Khurana},