TY - GEN
T1 - Non-interactive Distributional Indistinguishability (NIDI) and Non-malleable Commitments
AU - Khurana, Dakshita
N1 - Funding Information:
Work done in part during a visit to the Simons institute, Berkeley. This material is based upon work supported in part by DARPA under Contract No. HR001120C0024. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.
Publisher Copyright:
© 2021, International Association for Cryptologic Research.
PY - 2021
Y1 - 2021
N2 - 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 NP languages with unique witnesses. NIDI arguments allow a prover P to send a single message to verifier V, from 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 ⊥. The privacy guarantee is that secrets about the distribution remain hidden: for every pair of (sufficiently) hard-to-distinguish distributions D0 and D1 with support in NP language L, a NIDI that outputs samples from D0 with proofs of membership in L is indistinguishable from one that outputs samples from D1 with proofs of membership in L. We build NIDI arguments for superpolynomially hard-to-distinguish 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 returned to the committer).
AB - 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 NP languages with unique witnesses. NIDI arguments allow a prover P to send a single message to verifier V, from 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 ⊥. The privacy guarantee is that secrets about the distribution remain hidden: for every pair of (sufficiently) hard-to-distinguish distributions D0 and D1 with support in NP language L, a NIDI that outputs samples from D0 with proofs of membership in L is indistinguishable from one that outputs samples from D1 with proofs of membership in L. We build NIDI arguments for superpolynomially hard-to-distinguish 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 returned to the committer).
UR - http://www.scopus.com/inward/record.url?scp=85111464003&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85111464003&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-77883-5_7
DO - 10.1007/978-3-030-77883-5_7
M3 - Conference contribution
AN - SCOPUS:85111464003
SN - 9783030778828
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 186
EP - 215
BT - Advances in Cryptology – EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Canteaut, Anne
A2 - Standaert, François-Xavier
PB - Springer
T2 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2021
Y2 - 17 October 2021 through 21 October 2021
ER -