多项式函数根的零知识证明协议

摘要

为有效解决多项式函数根的零知识证明问题,基于离散对数的困难性假设,提出了多重离散对数问题,给出了多项式函数根的零知识证明协议,即:通过对多项式的每一项计算对应的离散对数A1,A2,…,An,证明者向验证者提供这些项,验证者根据(A1A2…An)m odp的结论来判定证明者是否拥有该多项式的根。为了防止证明者的欺骗行为,双方需要进行多次交互式证明。理论分析结果表明:证明者欺骗成功的概率随交互式证明次数的增加呈指数衰减,该协议是安全和可靠的。