Zero-knowledge proof protocol of the roots of polynomial functions

Abstract

The multi discrete logarithm problem and the zero-knowledge proolf protocol were proposed to efficiently solve the zero-knowledge proof of the roots of polynomials,based on the hardness of computing the discrete logarithms.In the protocol,the prover computes the discrete logarithms of each term of the polynomial and obtains A1,A2,…,An,which are sent to the verifier.Based on the value of(A1A2…An)modp,the verifier verifies the prover's ownership of the root.The protocol needs to be executed several rounds to reduce the possibility of cheating.Theoretical analyses show that the chance of successfully cheating decays exponentially with increasing number of rounds,so the protocol is secure and reliable.