A Perfect Zero-Knowledge Proof System for the Discrete Root Problem

Abstract

This paper presents a perfect zero knowledge proof system for a decision problem which is computationally equivalent to the Discrete Root Problem,and its zero knowledge property does not rely on any assumptions.Thus we provide additional evidence to the belief that perfect zero knowledge proof systems exist in a non trivial manner (i.e.,for language not in BPP).