On the 13th of August Karim Baghery defended his PhD thesis „Reducing trust and improving security in zk-SNARKs and commitments„ in which he studied the zk-SNARKs from two different perspectives, namely reducing trust in their setup phase and improving their security in different applications.
On the need for proof systems
People frequently are asked to provide their reasons and authorized documents to validate their opinion and statements. Most likely, these happen when they want to receive a service, or they need to prove that they have the right to be in a particular place, or more official situations they need to prove that they have done everything correctly! Such inquiries are more satisfying when they can be done as fast as possible and require the least amount of personal information leakage.
Zero-knowledge proof systems
Such practical scenarios open up a huge can of
worms, which is what different approaches of Zero-Knowledge (ZK)
proofs deal with. Zero-knowledge proofs are one of the essential tools in cryptography
that allow a person to prove the validity of a statement without revealing
secret information about them. For instance, they allow a person to convince another
person that he is +18 years old, or he has a valid driving license, ticket, or
visa, without (frequently) showing her personal documents and revealing secret
information about herself.
Construction of Zero-knowledge proofs
Generating such kind of proofs usually is done using a several-round interactive protocol (called Interactive Proof Systems) between the person who gives the proof (a.k.a. Prover), and the person who verifies the proof (a.k.a. Verifier). But such sort of proof generation requires the Verifier to be available (online) and have an interaction with the Prover to complete the proof generation. But, in practice, usually, interaction is difficult and brings overhead to the system. So, it would be great if we can construct such proof systems non-interactively, such that the Prover can generate the proof once and send it in one round to the Verifier. This actually exists! Currently, various constructions allow generating a ZK proof non-interactively and the Prover can publish the proof on a public bulletin board or can send directly to the Verifier in a single round. Such sort of proof systems are called Non-Interactive Zero-Knowledge (NIZK) proofs and are usually built in two main models, known as Random Oracle (RO) or Common Reference String (CRS). Roughly speaking, in the RO model one assumes that all parties of the protocol have access to a one-way function that given distinct inputs , returns unique (uniformly) random outputs, while in the CRS model there exists a trusted party who generates some public parameters and shares with the parties for proof generation and proof verification. In practice, it is shown that NIZK proof systems with CRS are more efficient than the constructions that are built in the RO model.
ZK-SNARKs
By now, zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs) are the most efficient family of ZK proof systems that are built in the CRS model. They allow proving different statements with constant and very short proofs (e.g. less than 128 bytes) and very efficient verification (e.g. in less than 0.1 seconds on current smartphones). However, constructions of zk-SNARKs rely on a setup phase and the users should trust the output of the setup phase that is supposed to be done by a trusted third party or distributed authority. Above all, in some applications, their default security is not sufficient to directly deploy in larger protocols that aim to achieve a stronger notion of security.
The thesis results
In this thesis, we mainly study zk-SNARKs from
two different perspectives.
- Reducing trust in their setup phase
- Amplifying their security in different applications.
In the first direction, we investigate how much one can mitigate trust in a third party without sacrificing the protocol’s efficiency. In such constructions, the parties of the protocol will obtain a certain level of security even if the setup phase was done maliciously or the secret information of the setup phase was revealed (e.g. with a hack). As a result of this direction, we present some efficient constructions that can resist against subverting of the setup phase of zk-SNARKs and achieve a certain level of security which is stronger than before. We also show that similar techniques will allow us to mitigate the trust in the CRS-based equivocal commitment schemes that are another prominent family of cryptographic primitives used in building ZK proof systems. Commitment schemes allow a person to commit to a particular message or value (e.g. a name of the candidate in voting) while keeping it hidden to other parties, but with the ability to reveal the committed message or value later. The results in the first direction are published in the following three papers:
- Karim Baghery with Behzad Abdolmaleki, Helger Lipmaa, and Michal Zajac. A Subversion-Resistant SNARK. In 23rd Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT, Hong Kong, 2017. Ranked in top 3 papers, and was invited to Journal of Cryptology. Available on ia.cr/2017/599.
- Karim Baghery. Subversion-Resistant Simulation (Knowledge) Sound NIZKs. In 17th IMA Conference on Cryptography and Coding Theory, Oxford, UK, 2019. Available on ia.cr/2019/1162.
- Karim Baghery. Subversion-Resistant Commitment Schemes: Definitions and Constructions. In 16th Workshop on Security and Trust Management at ESORICS 2020, Guildford, UK, 2020. Available on ia.cr/2019/1065.
In the second direction studied in the thesis, we present some efficient constructions that achieve stronger security with minimal overhead. Some of the presented constructions allow simplifying the construction and improving the efficiency of some sophisticated cryptographic protocols, e.g. privacy-preserving smart contracts systems. Our proposed constructions can be directly deployed in any novel protocols that aim to use efficient proof systems while guaranteeing users’ privacy and security. The results in the second direction are published in the following two papers:
- Karim Baghery. On the Efficiency of Privacy-Preserving Smart Contract Systems. In Progress in Cryptography – AFRICACRYPT 2019, Rabat, Morocco, 2019. Available on ia.cr/2019/480.
- Karim Baghery with Shahla Atapoor. Simulation Extractability in Groth’s zk-SNARK. In 3rd workshop on Cryptocurrencies, and Blockchain Technology at ESORICS 2019, Luxembourg, 2019. Available on ia.cr/2019/641.
Some of the proposed constructions in the thesis are implemented in Libsnark, the state-of-the-art library for zk-SNARKs, and empirical experiences confirm that the computational cost to mitigate the trust or to achieve more security is practical on current laptops or smartphones.
