Perfect zero-knowledge in constant rounds
Mihir Bellare, Silvio Micali, Rafail Ostrovsky · 1990
Quadratic residuosity and graph isomorphism are classic problems and the canonical examples of zero-knowledge languages.However, despite much research effort, all previous zero-knowledge proofs for them required either unproven complexity assumptions or an unbounded number of rounds of message exchange.For both (and similar) languages, we exhibit zeroknowledge proofs that require 5 rounds and no unproven assumptions.Our solution is essentially optimal, in this setting, due to a recent lower bound argument of Goldreich and Krawczyk.