CAREER: Towards Efficient and Scalable Zero-Knowledge Proofs

云计算、区块链和机器学习服务等数字平台的兴起正在催生众多新应用，并改变着日常生活。然而，用户缺乏对其他参与者的了解，在这些平台上建立信任具有挑战性。一个关键的研究问题是确定用户如何保护其数据的隐私，并确保其他人执行的计算是有效的。该项目的重点是开发高效和可扩展的零知识证明方案，这是同时确保数据隐私和计算完整性的重要密码原语。本课题从理论、应用和系统三个方面对零知识证明方案进行了研究。在理论方面，基于纠错码和扩展图，构造了新的具有线性运行时间的计算量的实用方案。在应用方面，该项目研究了机器学习算法和图算法，并为这些应用开发了高效的零知识证明。在系统方面，该项目启动了零知识证明的内存效率和分布式算法的研究。该项目将把零知识证明的效率和可扩展性提升到一个新的水平，使其适用于更广泛的行业工程师和开发人员社区。研究结果将使数字平台上的隐私保护和可验证数据挖掘的新应用成为可能，以保护用户的数据隐私。该项目还为本科生和研究生的网络安全教育开发了新的课程材料，并扩大了代表性不足的群体和K-12学生对计算的参与。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

The rise of digital platforms, such as cloud computing, blockchains, and machine learning services, is leading to numerous new applications and transforming daily life. However, users lack knowledge of other participants and it is challenging to establish trust on these platforms. A key research question is determining how users can protect the privacy of their data, and ensure that the computations performed by others are valid. The focus of this project is on developing efficient and scalable zero-knowledge proof schemes, an important cryptographic primitive to ensure data privacy and computation integrity simultaneously. The project advances three aspects of the zero-knowledge proof schemes: theory, application and system level. On the theory side, new practical schemes with linear running time in the size of the computation are constructed based on error-correcting codes and expander graphs. On the application side, the project investigates machine learning algorithms and graph algorithms and develops efficient zero-knowledge proofs tailored for these applications. On the system side, the project initiates the study of memory-efficient and distributed algorithms for zero-knowledge proofs. The project will bring the efficiency and scalability of zero-knowledge proof to the next level, making it applicable and accessible to the broader community of engineers and developers in the industry. The results will enable new applications of privacy-preserving and verifiable data mining on digital platforms to protect users’ data privacy. The project also develops new course materials for undergraduate and graduate cybersecurity education, and for broadening the participation in computing of underrepresented groups and K-12 students.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.