An almost-constant round interactive zero-knowledge proof
type: Item
instance of: scholarly article
title: An almost-constant round interactive zero-knowledge proof
zbMATH Open document ID: 0753.68038
DOI: 10.1016/0020-0190(92)90094-C
published in: Information Processing Letters
publication date: 1993-01-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P25
Mathematics Subject Classification ID: 94A15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P15
zbMATH DE Number: 92097
zbMATH Keywords: zero-knowledge proofs
zbMATH Keywords: Arthur-Merlin black-box IZKP
author: M. V. D. Burmester
MaRDI profile type: Publication
cites work: Q4040055
cites work: Minimum disclosure proofs of knowledge
cites work: Q3358225
cites work: Zero-knowledge proofs of identity
cites work: How To Prove Yourself: Practical Solutions to Identification and Signature Problems
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Q4038698
cites work: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: Q3197311
full work available at URL: 0020-0190(92)90094-c
OpenAlex ID: W1999954816
description: scientific article; zbMATH DE number 92097