Passer à la navigation principale Passer à la recherche Passer au contenu principal

Constant-round perfect zero-knowledge computationally convincing protocols

  • University of Montreal
  • Université Paris-Sud
  • IBM

Résultats de recherche: Contribution à un journal › Article publié dans une revue, révisé par les pairs › Revue par des pairs

36 Citations (Scopus)

Résumé

A perfect zero-knowledge interactive protocol allows a prover to convince a verifier of the validity of a statement in a way that does not give the verifier any additional information. Such protocols take place by the exchange of messages back and forth between the prover and the verifier. An important measure of efficiency for these protocols is the number of rounds in the interaction. In previously known perfect zero-knowledge protocols for statements concerning NP-complete problems, at least k rounds were necessary in order to prevent one party from having a probability of undetected cheating greater than 2-k. In this paper, we give the first perfect zero-knowledge protocol that offers arbitrarily high security for any statement in NP with a constant number of rounds. The protocol is computationally convincing (rather than statistically convincing as would have been an interactive proof-system in the sense of Goldwasser, Micali and Rackoff) because the verifier's belief in the prover's claim is partly based on the assumption that it is feasible to find a prime p with known factorization of p - 1 such that it is infeasible to compute discrete logarithms modulo p even for someone who knows the factors of p - 1. Our protocol can also be based on the more general assumption that one-way certified group actions exist. It is still open whether it would be sufficient to assume the existence of one-way functions in order to obtain perfect zero-knowledge computationally convincing interactive protocols for all statements in NP.

Langue originaleAnglais
Pages (de - à)23-52
Nombre de pages30
RevueTheoretical Computer Science
Volume84
Numéro de publication1
Les DOIs
ÉtatPublié - 22 juil. 1991
Modification externeOui

Classification disciplinaire ASJC Scopus

  • Informatique théorique
  • Informatique générale

Empreinte digitale

Voici les principaux termes ou expressions associés à « Constant-round perfect zero-knowledge computationally convincing protocols ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.

Citer cette ressource