An almost-constant round interactive zero-knowledge proof
We consider an Arthur-Merlin black-box IZKP for which \(t(| x|)\succ1\), that is, \(t\) is any unbounded function of \(| x|\). We are concerned with functions which grow very slowly, significantly slower than any iterated logarithm. For example, we can take \(t=\log\ast| x|\) [\textit{G. Brassard} and \textit{P. GiLLES}, Algorithmics. Theory and practice, London etc.: Prentice-Hall (1988)]. We call such functions almost-constant. From our earlier remarks it follows that \(t\) cannot be constant unless the corresponding problem is feasible. We shall see that in particular cases, both the running time and the communication complexity are less than those of comparable schemes by a factor of \(\log| x|\) (for the same security level). This applies even if the probabilities \(1-| x|^{-k}\) and \(| x|^{- k}\) mentioned earlier are replaced by \(1-2^{-| x|}\) and \(2^{- | x|}\) respectively.
- Computational Complexity of Probabilistic Turing Machines
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems
- scientific article; zbMATH DE number 4172376 (Why is no real title available?)
- scientific article; zbMATH DE number 4211486 (Why is no real title available?)
- scientific article; zbMATH DE number 177820 (Why is no real title available?)
- scientific article; zbMATH DE number 193197 (Why is no real title available?)
- Minimum disclosure proofs of knowledge
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- The Knowledge Complexity of Interactive Proof Systems
- Zero-knowledge proofs of identity
This page was built for publication: An almost-constant round interactive zero-knowledge proof
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198029)
