On constant-round concurrent zero-knowledge from a knowledge assumption
From MaRDI portal
Abstract: In this work, we consider the long-standing open question of constructing constant-round concurrent zero-knowledge protocols in the plain model. Resolving this question is known to require non-black-box techniques. We consider non-black-box techniques for zero-knowledge based on knowledge assumptions, a line of thinking initiated by the work of Hada and Tanaka (CRYPTO 1998). Prior to our work, it was not known whether knowledge assumptions could be used for achieving security in the concurrent setting, due to a number of significant limitations that we discuss here. Nevertheless, we obtain the following results: 1. We obtain the first constant round concurrent zero-knowledge argument for extbf{NP} in the plain model based on a new variant of knowledge of exponent assumption. Furthermore, our construction avoids the inefficiency inherent in previous non-black-box techniques such that those of Barak (FOCS 2001); we obtain our result through an efficient protocol compiler. 2. Unlike Hada and Tanaka, we do not require a knowledge assumption to argue the soundness of our protocol. Instead, we use a discrete log like assumption, which we call Diffie-Hellman Logarithm Assumption, to prove the soundness of our protocol. 3. We give evidence that our new variant of knowledge of exponent assumption is in fact plausible. In particular, we show that our assumption holds in the generic group model. 4. Knowledge assumptions are especially delicate assumptions whose plausibility may be hard to gauge. We give a novel framework to express knowledge assumptions in a more flexible way, which may allow for formulation of plausible assumptions and exploration of their impact and application in cryptography.
Recommendations
Cites work
- scientific article; zbMATH DE number 176566 (Why is no real title available?)
- scientific article; zbMATH DE number 1302862 (Why is no real title available?)
- scientific article; zbMATH DE number 2009954 (Why is no real title available?)
- scientific article; zbMATH DE number 1759795 (Why is no real title available?)
- scientific article; zbMATH DE number 1775426 (Why is no real title available?)
- scientific article; zbMATH DE number 1842484 (Why is no real title available?)
- Advances in Cryptology - CRYPTO 2003
- Advances in Cryptology – CRYPTO 2004
- Black-box concurrent zero-knowledge requires \(\tilde{\omega}(\log n)\) rounds
- Composition of secure multi-party protocols. A comprehensive study.
- Extractable Perfectly One-Way Functions
- From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
- Impossibility results for static input secure computation
- Information-theoretically secure protocols and security under composition
- Lower bounds for concurrent zero knowledge
- New impossibility results for concurrent composition and a non-interactive completeness theorem for secure computation
- Okamoto-Tanaka Revisited: Fully Authenticated Diffie-Hellman with Minimal Overhead
- On Invertible Sampling and Adaptive Security
- On constant-round concurrent zero-knowledge from a knowledge assumption
- On the existence of extractable one-way functions
- Perfect NIZK with Adaptive Soundness
- Secure two-party computation with low communication
- Short pairing-based non-interactive zero-knowledge arguments
- Statistically Hiding Sets
- Succinct NP Proofs from an Extractability Assumption
- The Knowledge Complexity of Interactive Proof Systems
- Theory of Cryptography
- Towards a Theory of Extractable Functions
Cited in
(15)- Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds
- Advances in Cryptology – CRYPTO 2004
- scientific article; zbMATH DE number 1418313 (Why is no real title available?)
- Random walks and concurrent zero-knowledge
- Constant-round concurrent zero-knowledge from indistinguishability obfuscation
- Composition with knowledge assumptions
- Constant-round concurrent zero knowledge in the bounded player model
- The bottleneck complexity of secure multiparty computation
- Constant-round leakage-resilient zero-knowledge argument for NP from the knowledge-of-exponent assumption
- Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party
- Toward RSA-OAEP without random oracles
- On the classification of knowledge-of-exponent assumptions in cyclic groups
- The hunting of the SNARK
- On constant-round concurrent zero-knowledge from a knowledge assumption
- On Constant-Round Concurrent Zero-Knowledge
This page was built for publication: On constant-round concurrent zero-knowledge from a knowledge assumption
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945373)
