February 23, 2023: Comparing the Efficiency and Security of zk-SNARKs, zk-STARKs, and Bulletproofs for Privacy-Preserving Authentication

MAster assignment

Comparing the Efficiency and Security of zk-SNARKs, zk-STARKs, and Bulletproofs for Privacy-Preserving Authentication

TYPE : MASTER CS

Period: Start date: as soon as possible

Student: Unassigned

If you are interested please contact:

dr.ing. M. Elhajj (Mohammed) Lecturer

+31534893475

 m.elhajj@utwente.nl

Building: Zilverling 2031

Personal page

Introduction:

Privacy-preserving authentication is an important area of research in cryptography, with applications in anonymous credentials, secure voting protocols, and other areas where privacy is a concern. Zero-knowledge proofs are a powerful tool for privacy-preserving authentication, allowing one party to prove to another party that they know a certain piece of information without revealing the information itself. In recent years, several types of zero-knowledge proofs have emerged as leading contenders for practical use: zk-SNARKs, zk-STARKs, and bulletproofs. These protocols differ in their efficiency, security, and underlying mathematical techniques, making them suitable for different types of applications. The goal of this thesis is to compare the efficiency and security of these three protocols and provide recommendations for their use in different settings. 

Objectives:

1. To review the literature on zk-SNARKs, zk-STARKs, and bulletproofs, including their mathematical foundations, security assumptions, and practical implementations.
2. To implement and compare the efficiency and security of these three protocols in a practical setting, using a common benchmark and real-world use cases.
3. To evaluate the trade-offs between efficiency and security for each protocol, including the impact of parameters such as proof size, verification time, and prover time.
4. To provide recommendations for the use of these protocols in different settings, based on their strengths and weaknesses.

Methodology:

The research will begin with a thorough review of the literature on zk-SNARKs, zk-STARKs, and bulletproofs, including their mathematical foundations, security assumptions, and practical implementations. This will be followed by the implementation of these protocols in a practical setting, using a common benchmark and real-world use cases. The efficiency and security of each protocol will be evaluated using performance metrics such as proof size, verification time, and prover time. The trade-offs between efficiency and security will be evaluated and compared, and recommendations for the use of these protocols in different settings will be provided.

Expected outcomes:

The expected outcomes of this research are:

1. A comprehensive review of the literature on zk-SNARKs, zk-STARKs, and bulletproofs, including their mathematical foundations, security assumptions, and practical implementations.
2. An implementation and evaluation of these protocols in a practical setting, using a common benchmark and real-world use cases.
3. A comparison of the efficiency and security of these three protocols, including the trade-offs between efficiency and security.
4. Recommendations for the use of these protocols in different settings, based on their strengths and weaknesses.

Conclusion:

The research proposed in this thesis will provide a comprehensive evaluation of three leading protocols for privacy-preserving authentication: zk-SNARKs, zk-STARKs, and bulletproofs. By comparing the efficiency and security of these protocols, we will gain a better understanding of their strengths and weaknesses and provide recommendations for their use in different settings. This research will contribute to the growing body of knowledge on privacy-preserving authentication and may have practical implications for the design of secure voting protocols, anonymous credentials, and other applications where privacy is a concern.

Related reading and references:

1. Liu, H., Ning, H., Xiong, Q. and Yang, L.T., 2014. Shared authority-based privacy-preserving authentication protocol in cloud computing. IEEE Transactions on parallel and distributed systems, 26(1), pp.241-251.
2. Katz, J., & Lindell, Y. (2014). Introduction to modern cryptography (2nd ed.). Chapman and Hall/CRC.
3. Goldreich, O. (2001). Foundations of cryptography: Basic applications (Vol. 2). Cambridge University Press.
4. Boneh, D., & Shoup, V. (2003). Proofs of knowledge and their applications. In Advances in cryptology—CRYPTO 2003 (pp. 33-57). Springer.
5. Camenisch, J., & Lysyanskaya, A. (2001). A signature scheme with efficient protocols. In Advances in cryptology—CRYPTO 2001 (pp. 268-289). Springer.
6. Ben-Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., & Virza, M. A. (2018). Zero knowledge proofs and succinct non-interactive arguments of knowledge. Foundations and Trends in Theoretical Computer Science, 12(1-2), 1-286.
7. Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M., & Spooner, N. (2019). Scalable, transparent, and post-quantum secure computational integrity. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 1317-1334.
8. Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C., & Scaife, N. (2018). Efficient zero-knowledge arguments for arithmetic circuits in the discrete logarithm setting. In Advances in Cryptology – CRYPTO 2018 (pp. 327-357). Springer.