International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Dakshita Khurana , UIUC
Download:
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).
BibTeX
@inproceedings{eurocrypt-2021-30915,
  title={Non-interactive Distributional Indistinguishability (NIDI) and Non-Malleable Commitments},
  publisher={Springer-Verlag},
  author={Dakshita Khurana},
  year=2021
}