An almost-constant round interactive zero-knowledge proof (Q1198029)

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.