基于离散对数的多项式函数根零知识证明协议

本文主要探讨了"多项式函数根的零知识证明协议"这一主题，它针对的是在信息技术领域中的一个重要问题——如何设计一个安全、高效的协议，使得证明者可以向验证者展示他们知道某个多项式函数的根，而无需透露实际根的具体值，同时保证验证者不能通过这个过程获取额外的信息，即实现零知识证明。这项工作建立在离散对数问题的困难性基础上，离散对数问题是一种在数学上被认为难以解决的问题，这对于密码学的安全性至关重要。 在该协议中，首先提出了多重离散对数问题，这是一种扩展的概念，涉及到对多项式多项式多项式每一项的离散对数计算。证明者会计算出多项式各项对应的离散对数A1, A2, ..., An，并将这些离散对数提供给验证者。验证者则通过对这些离散对数进行模运算(A1A2...An) mod p，来判断证明者是否确实知道多项式的根。值得注意的是，为了确保协议的安全性，这个过程需要双方进行多次交互式证明，通过这种方式，证明者试图欺骗的成功概率会随着证明次数的增加而快速降低，从而保证协议的可靠性。 文章作者李曦和王道顺来自清华大学计算机科学与技术系，他们在2009年发表在《清华大学学报(自然科学版)》的一篇文章中详细阐述了这一创新性的零知识证明协议。他们的研究得到了国家自然科学基金的资助，显示出该领域的学术认可。该论文被归类于计算机科学和技术领域，特别是离散数学和密码学方向，其关键词包括零知识证明、离散对数、多项式函数以及根的计算。 总结来说，这篇文章的核心贡献在于提出了一种利用离散对数难题构造的多项式函数根的零知识证明方法，该协议在保护隐私的同时，确保了验证过程的有效性和安全性。这对于许多依赖于多方信任但又需要保密的应用场景，如电子投票系统、金融交易等具有重要意义。