Carnegie Mellon University PHD Statement of Purpose Essay Sample

Statement of Purpose Carnegie Mellon Computer Science Ph.D. Quang Vu Dao I am interested in zero-knowledge proofs, a powerful cryptographic primitive that allows anyone to prove statements about their private data without revealing it. State-of-the-art proof systems are used to secure billions of dollars in transactions on blockchains, yet many questions about their security and efficiency remain unanswered. In my Ph.D., I plan to advance our theoretical understanding of zero-knowledge proofs, and to build new privacy-preserving applications based on practical proof systems. In fact, I have been working on the same topics with Prof. Paul Grubbs at Michigan for the past six months. Before this, I was doing a Ph.D. in math at the same school. While I loved learning about deep and powerful ideas in mathematics, I was not satisfied with pursuing math for its own sake, and instead looked for a field where mathematical results have been translated to real-world applications. Cryptography turned out to be the perfect answer to what I was looking for, a subject that leverages math and complexity theory to build cryptosystems helping to secure our privacy in a digital world. My research with Prof. Grubbs has focused on proofs that are short and non-interactive, known as SNARKs. Many SNARKs today are constructed using the Fiat-Shamir transform, which removes interaction from an underlying interactive proof protocol. A variation of this transform, called weak Fiat-Shamir, does not explicitly hash the instance being proved, and hence is insecure when a malicious prover could adaptively choose the input. Indeed, [BPW12] showed that weak Fiat-Shamir could totally break the soundness of many three-round protocols, which led to breaking various aspects of the Helios voting system. However, no follow-up work has studied whether weak Fiat-Shamir is insecure for more complicated, multi-round protocols. I extended the same line of attack to break the soundness of the sumcheck protocol, and the knowledge soundness of Bulletproofs’ inner product argument [Bün+18] (assuming weak Fiat-Shamir is used). Prof. Grubbs and I are also surveying existing implementations of SNARKs to see whether our attacks translate to practice. For our second line of research, I explore constructions of more expressive signature schemes, called signatures of knowledge, from SNARKs. A signature of knowledge (SoK) generalizes traditional signatures by letting the public key be an instance in a NP relation, and signing can only be done if one knows a corresponding witness. Thanks to its generality, SoKs have been used in many privacy-preserving applications such as anonymous credentials, direct anonymous attestation, and private cryptocurrencies. The only existing SoK that is also succinct is given in [GM17], which requires large public parameters and a trusted setup. I give a construction of succinct SoKs from any SNARK that uses the Fiat-Shamir transform, simply by adding the message into the transcript to be hashed. While this idea is not new [Abd+02] and goes back to the original Schnorr signature, there has been no work evaluating the security of the resulting signature scheme for multi-round protocols. I fill this gap and show that the resulting SoK is indeed secure when the SNARK satisfies a strong notion of non-malleability. In particular, I obtain a succinct SoK with small public parameters by instantiating Bulletproofs as the proof system. As the next step, I am exploring how to construct blind SoKs, which allow one party to sign a message without knowing its content. While my switch to cryptography was recent, I would argue that my background and motivation have always been a natural match for the subject. My favorite mathematical problems are those that are simple and elegant, yet require deep and powerful ideas to solve. Such inclination informed my undergraduate research [Dao+19; Dao+20], where I proved concrete statements about combinatorial objects using tools from algebra and representation theory. Both papers have been submitted to journals, with the second nearing acceptance. At the same time, I care deeply about communicating concepts in math and computer science to a wider audience, getting people excited about profound ideas in both fields. For the past three semesters, I have been the primary instructor for Calculus I, teaching a class of around 18 students three times every week. I have also consistently engaged in outreach efforts outside school. Over the past summer, I mentored two groups of high school students in a math & computer science summer camp on Groebner bases and error-correcting codes. I plan to return to the camp this year to teach various topics in cryptography. I am drawn to Carnegie Mellon for its large and vibrant research groups in cryptography and security. In particular, I hope to work with Prof. Riad Wahby and Prof. Bryan Parno, who are both active in building practical proof systems. One of Prof. Wahby’s recent works that particularly excites me is [Gol+21], a concretely efficient post-quantum SNARK with a linear time prover. There are several concrete questions in line with Prof. Wahby’s research that I would like to tackle in my Ph.D. There is much we don’t fully understand about the security of current SNARKs. How can we improve the analysis of the Fiat-Shamir transform to give better security bounds, especially for logarithmic-round protocols or against quantum adversaries? Can we show that SNARKs are still secure when composed with other primitives? How do we put the heuristic security of proof recursion on firmer theoretical grounds? I believe that answering these questions will result in greater theoretical understanding of and better security guarantees for proof systems. I also wish to explore the applications of proof systems, both in the context of blockchains and beyond. In what ways can we use proof systems to improve the privacy of our digital lives? Which verifiability problems would require ideas beyond general zero-knowledge proofs to solve? Can we build fully succinct proof systems that are space-efficient as well as time-efficient? I hope to translate advances in proof systems into new verifiable primitives, and to deploy them in real-world privacy-preserving protocols. Cryptography is a beautiful subject, and I care about cryptographic problems that are both theoretically interesting and practically relevant. Getting a Ph.D. would allow me to continue working on those important problems, and to acquire the skills I need to become a Professor in Computer Science. Thank you for your consideration. References [Abd+02] Michel Abdalla et al. “From identification to signatures via the Fiat-Shamir transform: Minimizing assumptions for security and forward-security”. In: International Conference on the Theory and Applications of Cryptographic Techniques. Springer. 2002, pp. 418–433. [BPW12] David Bernhard, Olivier Pereira, and Bogdan Warinschi. “How not to prove yourself: Pitfalls of the fiat-shamir heuristic and applications to helios”. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer. 2012, pp. 626–643. [Bün+18] Benedikt Bünz et al. “Bulletproofs: Short proofs for confidential transactions and more”. In: 2018 IEEE Symposium on Security and Privacy (SP). IEEE. 2018, pp. 315–334. [Bün+20] Benedikt Bünz et al. “Zether: Towards privacy in a smart contract world”. In: International Conference on Financial Cryptography and Data Security. Springer. 2020, pp. 423–443. [Dao+19] Quang Dao et al. “Extended Nestohedra and their Face Numbers”. In: arXiv:1912.00273 (2019). [Dao+20] Quang Dao et al. “Rowmotion orbits of trapezoid posets”. In: arXiv:2002.04810 (2020). [GM17] Jens Groth and Mary Maller. “Snarky signatures: Minimal signatures of knowledge from simulation-extractable SNARKs”. In: Annual International Cryptology Conference. Springer. 2017, pp. 581–612. [Gol+21] Alexander Golovnev et al. “Brakedown: Linear-time and post-quantum SNARKs for R1CS”. In: Cryptology ePrint Archive (2021).