8 results sorted by ID
Possible spell-corrected query: gap
A Unified Framework for Non-Universal SNARKs
Helger Lipmaa
Cryptographic protocols
We propose a general framework for non-universal SNARKs. It contains (1) knowledge-sound and non-black-box any-simulation-extractable (ASE), (2) zero-knowledge and subversion-zero knowledge SNARKs for the well-known QAP, SAP, QSP, and QSP constraint languages that all by design have \emph{relatively} simple security proofs. The knowledge-sound zero-knowledge SNARK is similar to Groth's SNARK from EUROCRYPT 2016, except having fewer trapdoors, while the ASE subversion-zero knowledge SNARK...
Another Look at Extraction and Randomization of Groth's zk-SNARK
Karim Baghery, Markulf Kohlweiss, Janno Siim, Mikhail Volkhov
Cryptographic protocols
Due to the simplicity and performance of zk-SNARKs they are widely used in real-world cryptographic protocols, including blockchain and smart contract systems. Simulation Extractability (SE) is a necessary security property for a NIZK argument to achieve Universal Composability (UC), a common requirement for such protocols. Most of the works that investigated SE focus on its strong variant which implies proof non-malleability. In this work we investigate a relaxed weaker notion, that allows...
2019/612
Last updated: 2023-05-16
Simulation-Extractable SNARKs Revisited
Helger Lipmaa
Cryptographic protocols
The most efficient SNARKs (e.g., Groth, 2016) have a brittle and difficult-to-verify knowledge-soundness proof in the generic model, which makes it nontrivial to modify such SNARKs to, e.g., satisfy simulation-extractability or to implement some other language instead of QAP (Quadratic Arithmetic Program). We propose knowledge-sound and non-black-box tag-based strong any-simulation-extractable ($\tagSASE$) subversion-zero knowledge SNARKs for QAP that by design have a relatively simple...
Simulation-Extractable zk-SNARK with a Single Verification
Jihye Kim, Jiwon Lee, Hyunok Oh
Cryptographic protocols
This revised paper improves the previous simulation-extractable zk-SNARK (SE-SNARK) in terms of performance efficiency and the security.
It removes the G_2 operation in verification, without degrading performance and size, and analyze the security of the nested hash collision more deeply to strengthen the security.
The simulation-extractable zk-SNARK (SE-SNARK) introduces a security notion of non-malleability. The existing pairing-based zk-SNARKs designed from linear encoding are known...
LegoSNARK: Modular Design and Composition of Succinct Zero-Knowledge Proofs
Matteo Campanelli, Dario Fiore, Anaïs Querol
Cryptographic protocols
We study the problem of building SNARKs modularly by linking small specialized “proof gadgets" SNARKs in a lightweight manner.
Our motivation is both theoretical and practical. On the theoretical side, modular SNARK designs would be flexible and reusable.
In practice, specialized SNARKs have the potential to be more efficient than general-purpose schemes, on which most existing works have focused. If a computation naturally presents different “components" (e.g. one arithmetic circuit and...
On the security of the BCTV Pinocchio zk-SNARK variant
Ariel Gabizon
Cryptographic protocols
The main result of this note is a severe flaw in the description of the zk-SNARK in [BCTV14].
The flaw stems from including redundant elements in the CRS, as compared to that of the original Pinocchio protocol [PHGR16], which are vital not to expose.
The flaw enables creating a proof of knowledge for *any* public input given a valid proof for *some* public input.
We also provide a proof of security for the [BCTV14] zk-SNARK in the generic group model, when these elements are excluded from...
Non-Interactive Zero-Knowledge Proofs for Composite Statements
Shashank Agrawal, Chaya Ganesh, Payman Mohassel
The two most common ways to design non-interactive zero-knowledge (NIZK) proofs are based on Sigma protocols and QAP-based SNARKs. The former is highly efficient for proving algebraic statements while the latter is superior for arithmetic representations.
Motivated by applications such as privacy-preserving credentials and privacy-preserving audits in cryptocurrencies, we study the design of NIZKs for composite statements that compose algebraic and arithmetic statements in arbitrary ways....
Prover-Efficient Commit-And-Prove Zero-Knowledge SNARKs
Helger Lipmaa
Cryptographic protocols
Zk-SNARKs (succinct non-interactive zero-knowledge arguments of knowledge) are needed in many applications. Unfortunately, all previous zk-SNARKs for interesting languages are either inefficient for the prover, or are non-adaptive and based on a commitment scheme that depends both on the prover's input and on the language, i.e., they are not commit-and-prove (CaP) SNARKs. We propose a proof-friendly extractable commitment scheme, and use it to construct prover-efficient adaptive CaP...
We propose a general framework for non-universal SNARKs. It contains (1) knowledge-sound and non-black-box any-simulation-extractable (ASE), (2) zero-knowledge and subversion-zero knowledge SNARKs for the well-known QAP, SAP, QSP, and QSP constraint languages that all by design have \emph{relatively} simple security proofs. The knowledge-sound zero-knowledge SNARK is similar to Groth's SNARK from EUROCRYPT 2016, except having fewer trapdoors, while the ASE subversion-zero knowledge SNARK...
Due to the simplicity and performance of zk-SNARKs they are widely used in real-world cryptographic protocols, including blockchain and smart contract systems. Simulation Extractability (SE) is a necessary security property for a NIZK argument to achieve Universal Composability (UC), a common requirement for such protocols. Most of the works that investigated SE focus on its strong variant which implies proof non-malleability. In this work we investigate a relaxed weaker notion, that allows...
The most efficient SNARKs (e.g., Groth, 2016) have a brittle and difficult-to-verify knowledge-soundness proof in the generic model, which makes it nontrivial to modify such SNARKs to, e.g., satisfy simulation-extractability or to implement some other language instead of QAP (Quadratic Arithmetic Program). We propose knowledge-sound and non-black-box tag-based strong any-simulation-extractable ($\tagSASE$) subversion-zero knowledge SNARKs for QAP that by design have a relatively simple...
This revised paper improves the previous simulation-extractable zk-SNARK (SE-SNARK) in terms of performance efficiency and the security. It removes the G_2 operation in verification, without degrading performance and size, and analyze the security of the nested hash collision more deeply to strengthen the security. The simulation-extractable zk-SNARK (SE-SNARK) introduces a security notion of non-malleability. The existing pairing-based zk-SNARKs designed from linear encoding are known...
We study the problem of building SNARKs modularly by linking small specialized “proof gadgets" SNARKs in a lightweight manner. Our motivation is both theoretical and practical. On the theoretical side, modular SNARK designs would be flexible and reusable. In practice, specialized SNARKs have the potential to be more efficient than general-purpose schemes, on which most existing works have focused. If a computation naturally presents different “components" (e.g. one arithmetic circuit and...
The main result of this note is a severe flaw in the description of the zk-SNARK in [BCTV14]. The flaw stems from including redundant elements in the CRS, as compared to that of the original Pinocchio protocol [PHGR16], which are vital not to expose. The flaw enables creating a proof of knowledge for *any* public input given a valid proof for *some* public input. We also provide a proof of security for the [BCTV14] zk-SNARK in the generic group model, when these elements are excluded from...
The two most common ways to design non-interactive zero-knowledge (NIZK) proofs are based on Sigma protocols and QAP-based SNARKs. The former is highly efficient for proving algebraic statements while the latter is superior for arithmetic representations. Motivated by applications such as privacy-preserving credentials and privacy-preserving audits in cryptocurrencies, we study the design of NIZKs for composite statements that compose algebraic and arithmetic statements in arbitrary ways....
Zk-SNARKs (succinct non-interactive zero-knowledge arguments of knowledge) are needed in many applications. Unfortunately, all previous zk-SNARKs for interesting languages are either inefficient for the prover, or are non-adaptive and based on a commitment scheme that depends both on the prover's input and on the language, i.e., they are not commit-and-prove (CaP) SNARKs. We propose a proof-friendly extractable commitment scheme, and use it to construct prover-efficient adaptive CaP...