CAREER: Towards Efficient and Scalable Zero-Knowledge Proofs

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.