iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s00145-021-09379-y
On Subversion-Resistant SNARKs | Journal of Cryptology Skip to main content
Springer Nature Link
Log in

On Subversion-Resistant SNARKs

  • Published:
Journal of Cryptology Aims and scope Submit manuscript

Abstract

While NIZK arguments in the CRS model are widely studied, the question of what happens when the CRS is subverted has received little attention. In ASIACRYPT 2016, Bellare, Fuchsbauer, and Scafuro showed the first negative and positive results, proving also that it is impossible to achieve subversion soundness and (even non-subversion) zero knowledge at the same time. On the positive side, they constructed a sound and subversion-zero knowledge (Sub-ZK) non-succinct NIZK argument for NP. We consider the practically very relevant case of zk-SNARKs. We make Groth’s zk-SNARK for Circuit-SAT from EUROCRYPT 2016 computationally knowledge-sound and perfectly composable Sub-ZK with minimal changes. We only require the CRS trapdoor to be extractable and the CRS to be publicly verifiable. To achieve the latter, we add some new elements to the CRS and construct an efficient CRS verification algorithm. We also provide a definitional framework for knowledge-sound and Sub-ZK SNARKs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. [3] investigates Sub-ZK QA-NIZKs, where languages are parameterized. Sub-ZK QA-NIZKs are out of the scope of this paper since one needs also consider the parameter subversion. However, their impossibility result works also in the case of Sub-ZK SNARKs.

  2. Lipmaa [41] has showed recently how to minimally modify Groth’s SNARK so that it only has two trapdoors.

References

  1. B. Abdolmaleki, K. Baghery, H. Lipmaa, and M. Zajac, A subversion-resistant SNARK, in T. Takagi and T. Peyrin, (eds.), ASIACRYPT 2017, Part III, vol. 10626 of LNCS, (Springer, Heidelberg, 2017), pp. 3–33. https://doi.org/10.1007/978-3-319-70700-6_1

  2. B. Abdolmaleki, K. Baghery, H. Lipmaa, and M. Zajac. A subversion-resistant SNARK. Cryptology ePrint Archive, Report 2017/599, (2017). http://eprint.iacr.org/2017/599

  3. B. Abdolmaleki, H. Lipmaa, J. Siim, and M. Zajac. On QA-NIZK in the BPK model, in A. Kiayias, M. Kohlweiss, P. Wallden, and V. Zikas, eds, PKC 2020, Part I, vol. 12110 of LNCS, (Springer, Heidelberg, 2020), pp. 590–620. https://doi.org/10.1007/978-3-030-45374-9_20

  4. D. Boneh, X. Boyen, and E.-J. Goh. Hierarchical identity based encryption with constant size ciphertext, in R. Cramer, (ed.), EUROCRYPT 2005, vol. 3494 of LNCS, (Springer, Heidelberg, 2005), pp. 440–456. https://doi.org/10.1007/11426639_26

  5. E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, and M. Virza. SNARKs for C: verifying program executions succinctly and in zero knowledge, in R. Canetti, J.A. Garay, (eds.), CRYPTO 2013, Part II, vol. 8043 of LNCS, (Springer, Heidelberg, 2013). https://doi.org/10.1007/978-3-642-40084-1_6

  6. E. Ben-Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza. Zerocash: Decentralized anonymous payments from bitcoin, in 2014 IEEE Symposium on Security and Privacy, (IEEE Computer Society Press, 2014), pp. 459–474. https://doi.org/10.1109/SP.2014.36

  7. N. Bitansky, R. Canetti, O. Paneth, and A. Rosen. On the existence of extractable one-way functions, in D.B. Shmoys, (ed.), 46th ACM STOC, (ACM Press, May/June 2014), pp. 505–514. https://doi.org/10.1145/2591796.2591859

  8. E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza. Succinct non-interactive zero knowledge for a von neumann architecture, in K. Fu and J. Jung, (eds.), USENIX Security 2014, (USENIX Association, 2014), pp. 781–796

  9. M. Blum, P. Feldman, and S. Micali. Non-interactive zero-knowledge and its applications (extended abstract), in 20th ACM STOC, (ACM Press, May 1988), pp. 103–112. https://doi.org/10.1145/62212.62222

  10. M. Bellare, G. Fuchsbauer, and A. Scafuro. NIZKs with an untrusted CRS: security in the face of parameter subversion, in J.H. Cheon and T. Takagi, (eds.), ASIACRYPT 2016, Part II, vol. 10032 of LNCS, (Springer, Heidelberg, 2016), pp. 777–804. https://doi.org/10.1007/978-3-662-53890-6_26

  11. M. Bellare, J.A. Garay, and T. Rabin. Batch verification with applications to cryptography and checking, in C.L. Lucchesi and A.V. Moura, (eds.), LATIN 1998, vol. 1380 of LNCS, (Springer, Heidelberg, 1998), pp. 170–191

  12. S. Bowe. BLS12-381: New zk-SNARK Elliptic Curve Construction. Blog post, https://blog.z.cash/new-snark-curve/, last accessed in July, 2018, March 11 (2017)

  13. D.R.L. Brown. The exact security of ECDSA. Contributions to IEEE P1363a, (2001). http://grouper.ieee.org/groups/1363/

  14. R. Canetti, O. Goldreich, S. Goldwasser, and S. Micali. Resettable zero-knowledge (extended abstract), in 32nd ACM STOC, (ACM Press, 2000), pp. 235–244. https://doi.org/10.1145/335305.335334

  15. I. Damgård. Towards practical public key systems secure against chosen ciphertext attacks, in J. Feigenbaum, (ed.), CRYPTO’91, volume 576 of LNCS, (Springer, Heidelberg, 1992), pp. 445–456. https://doi.org/10.1007/3-540-46766-1_36

  16. G. Danezis, C. Fournet, J. Groth, and M. Kohlweiss. Square span programs with applications to succinct NIZK arguments, in P. Sarkar and T. Iwata, (eds), ASIACRYPT 2014, Part I, volume 8873 of LNCS, (Springer, Heidelberg, 2014), pp. 532–550. https://doi.org/10.1007/978-3-662-45611-8_28

  17. G. Danezis, C. Fournet, M. Kohlweiss, and B. Parno. Pinocchio coin: building zerocoin from a succinct pairing-based proof system. pp. 27–30, Berlin, Germany, (2013). ACM

  18. G. Di Crescenzo and H. Lipmaa. Succinct NP proofs from an extractability assumption, in A. Beckmann, C. Dimitracopoulos, and B. Löwe, editors, Computability in Europe, CIE 2008, volume 5028 of LNCS, pp. 175–185, Athens, Greece, June 15–20, (2008). Springer, Heidelberg

  19. A. Escala, G. Herold, E. Kiltz, C. Ràfols, and J. Villar. An algebraic framework for Diffie-Hellman assumptions, in R. Canetti and J.A. Garay, (eds.), CRYPTO 2013, Part II, volume 8043 of LNCS, (Springer, Heidelberg, 2013), pp. 129–147. https://doi.org/10.1007/978-3-642-40084-1_8

  20. G. Fuchsbauer, E. Kiltz, and J. Loss. The algebraic group model and its applications, in H. Shacham and A. Boldyreva, (eds), CRYPTO 2018, Part II, volume 10992 of LNCS, (Springer, Heidelberg, 2018), pp. 33–62. https://doi.org/10.1007/978-3-319-96881-0_2

  21. P. Fauzi, H. Lipmaa, and M. Zajac. A shuffle argument secure in the generic model, in J.H. Cheon and T. Takagi, (eds.), ASIACRYPT 2016, Part II, volume 10032 of LNCS, (Springer, Heidelberg, 2016), pp. 841–872. https://doi.org/10.1007/978-3-662-53890-6_28

  22. G. Fuchsbauer and M. Orrù. Non-interactive zaps of knowledge, in B. Preneel and F. Vercauteren, (eds.), ACNS 18, volume 10892 of LNCS, (Springer, Heidelberg, 2018), pp. 44–62. https://doi.org/10.1007/978-3-319-93387-0_3

  23. G. Fuchsbauer. Subversion-zero-knowledge SNARKs, in M. Abdalla and R. Dahab, (eds.), PKC 2018, Part I, volume 10769 of LNCS, (Springer, Heidelberg, 2018), pp. 315–347. https://doi.org/10.1007/978-3-319-76578-5_11

  24. A. Gabizon. On the security of the BCTV pinocchio zk-SNARK variant. Cryptology ePrint Archive, Report 2019/119, (2019). https://eprint.iacr.org/2019/119

  25. R. Gennaro, C. Gentry, and B. Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers, in T. Rabin, (ed.), CRYPTO 2010, volume 6223 of LNCS, (Springer, Heidelberg, 2010), pp. 465–482. https://doi.org/10.1007/978-3-642-14623-7_25

  26. R. Gennaro, C. Gentry, B. Parno, and M. Raykova. Quadratic span programs and succinct NIZKs without PCPs, in T. Johansson and P.Q. Nguyen, (eds.), EUROCRYPT 2013, volume 7881 of LNCS, (Springer, Heidelberg, 2013), pp. 626–645. https://doi.org/10.1007/978-3-642-38348-9_37

  27. J. Groth, M. Kohlweiss, M. Maller, S. Meiklejohn, and I. Miers. Updatable and universal common reference strings with applications to zk-SNARKs, in H. Shacham and A. Boldyreva, (eds.), CRYPTO 2018, Part III, volume 10993 of LNCS, (Springer, Heidelberg, 2018), pp. 698–728. https://doi.org/10.1007/978-3-319-96878-0_24

  28. O. Goldreich and Y. Oren. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology, 7(1):1–32, 1994. https://doi.org/10.1007/BF00195207

  29. J. Groth, R. Ostrovsky, and A. Sahai. Non-interactive zaps and new techniques for NIZK, in C.a Dwork, (ed.), CRYPTO 2006, volume 4117 of LNCS, (Springer, Heidelberg, August 2006), pp. 97–111. https://doi.org/10.1007/11818175_6

  30. S.D. Galbraith, K.G. Paterson, and N.P. Smart. Pairings for cryptographers. Discrete Appl. Math., 156(16):3113–3121 (2008)

  31. J. Groth. Simulation-sound NIZK proofs for a practical language and constant size group signatures, in X. Lai and K. Chen, (eds.), ASIACRYPT 2006, volume 4284 of LNCS, (Springer, Heidelberg, 2006), pp. 444–459. https://doi.org/10.1007/11935230_29

  32. J. Groth. Short pairing-based non-interactive zero-knowledge arguments, in M. Abe, (ed.), ASIACRYPT 2010, volume 6477 of LNCS, (Springer, Heidelberg, 2010), pp. 321–340. https://doi.org/10.1007/978-3-642-17373-8_19

  33. J. Groth. On the size of pairing-based non-interactive arguments, in M. Fischlin and J.-S. Coron, (eds.), EUROCRYPT 2016, Part II, volume 9666 of LNCS, (Springer, Heidelberg, 2016), pp. 305–326. https://doi.org/10.1007/978-3-662-49896-5_11

  34. C. Gentry and D. Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions, in L. Fortnow and S.P. Vadhan, (eds.), 43rd ACM STOC, (ACM Press, 2011), pp. 99–108. https://doi.org/10.1145/1993636.1993651

  35. T. Icart. How to hash into elliptic curves, in S. Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, (Springer, Heidelberg, 2009), pp. 303–316. https://doi.org/10.1007/978-3-642-03356-8_18

  36. C.S. Jutla and A. Roy. Shorter quasi-adaptive NIZK proofs for linear subspaces, in K. Sako and P. Sarkar, (eds.), ASIACRYPT 2013, Part I, volume 8269 of LNCS, (Springer, Heidelberg, 2013), pp. 1–20. https://doi.org/10.1007/978-3-642-42033-7_1

  37. A.E. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou. Hawk: the blockchain model of cryptography and privacy-preserving smart contracts, in 2016 IEEE Symposium on Security and Privacy, (IEEE Computer Society Press, 2016), pp. 839–858. https://doi.org/10.1109/SP.2016.55

  38. H. Lipmaa. Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments, in R. Cramer, (ed.), TCC 2012, volume 7194 of LNCS, (Springer, Heidelberg, 2012), pp. 169–189. https://doi.org/10.1007/978-3-642-28914-9_10

  39. H. Lipmaa. Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes, in K. Sako and P. Sarkar, (eds.), ASIACRYPT 2013, Part I, volume 8269 of LNCS, (Springer, Heidelberg, 2013), pp. 41–60. https://doi.org/10.1007/978-3-642-42033-7_3

  40. H. Lipmaa. Prover-efficient commit-and-prove zero-knowledge SNARKs, in D. Pointcheval, A. Nitaj, and T. Rachidi, (eds.), AFRICACRYPT 16, volume 9646 of LNCS, (Springer, Heidelberg, 2016), pp. 185–206. https://doi.org/10.1007/978-3-319-31517-1_10

  41. H. Lipmaa. Simulation-Extractable ZK-SNARKs Revisited. Technical Report 2019/612, IACR, May 31, 2019. https://eprint.iacr.org/2019/612, updated on 8 Feb 2020

  42. U.M. Maurer. Abstract models of computation in cryptography (invited paper), in N.P. Smart, (ed.), 10th IMA International Conference on Cryptography and Coding, volume 3796 of LNCS, (Springer, Heidelberg, 2005), pp. 1–12

  43. S. Micali and L. Reyzin. Soundness in the public-key model, in J. Kilian, (ed.), CRYPTO 2001, volume 2139 of LNCS, (Springer, Heidelberg, August 2001), pp. 542–565. https://doi.org/10.1007/3-540-44647-8_32

  44. V. I. Nechaev. Complexity of a determinate algorithm for the discrete logarithm. Mathematical Notes, 55(2):165–172, 1994.

    Article  MathSciNet  Google Scholar 

  45. B. Parno, J. Howell, C. Gentry, and M. Raykova. Pinocchio: nearly practical verifiable computation, in 2013 IEEE Symposium on Security and Privacy, (IEEE Computer Society Press, May 2013), pp. 238–252. https://doi.org/10.1109/SP.2013.47

  46. J.T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–717, 1980.

  47. V. Shoup. Lower bounds for discrete logarithms and related problems, in W. Fumy, (ed.), EUROCRYPT’97, volume 1233 of LNCS, (Springer, Heidelberg, 1997), pp. 256–266. https://doi.org/10.1007/3-540-69053-0_18

  48. J. Stern, D. Pointcheval, J. Malone-Lee, and N.P. Smart. Flaws in applying proof methodologies to signature schemes, in M. Yung, (ed.), CRYPTO 2002, volume 2442 of LNCS, (Springer, Heidelberg, 2002), pp. 93–110. https://doi.org/10.1007/3-540-45708-9_7

  49. R. Zippel. Probabilistic Algorithms for Sparse Polynomials, in E.W. Ng, (ed.), EUROSM 1979, volume 72 of LNCS, (Marseille, France, 1979. Springer, Heidelberg), pp. 216–226

Download references

Acknowledgements

We thank Karim Baghery for his contribution to the conference version of the current paper. Most of this work was done while the authors were working at the University of Tartu, Estonia. This work was partially supported by the Estonian Research Council grant (PRG49) and by the European Union’s Horizon 2020 research and innovation program under grant agreement No. 780477 (project PRIViLEDGE).

Author information

Authors and Affiliations

  1. Max Planck Institute for Security and Privacy, Bochum, Germany

    Behzad Abdolmaleki

  2. University of Tartu, Tartu, Estonia

    Janno Siim

  3. Simula UiB, Bergen, Norway

    Helger Lipmaa

  4. Clearmatics, London, UK

    Michał Zając

Authors
  1. Behzad Abdolmaleki
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Helger Lipmaa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Janno Siim
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Michał Zając
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Helger Lipmaa.

Additional information

Communicated by Masayuki Abe.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

An earlier version of this paper, [1], was published at Asiacrypt 2017. The current version has been significantly modified.

Changes Compared to the Conference Version

Changes Compared to the Conference Version

This version of the paper contains several new results compared to the conference and fixes couple of small errors that occured in the conference version. We briefly list them below.

  1. 1.

    Improvements in the definitional framework:

    • Divided subversion-completeness into completeness and CRS verifiability.

    • In the composable Sub-ZK definition, we now allow the adversary to pick \((\mathsf {x}, \mathsf {w})\) adaptively based on the CRS.

    • Changed non-uniform adversary to uniform in the composable Sub-ZK definition (we provide a long discussion after the definition explaining this change).

    • The conference version contained an additional definition of Sub-ZK, which had a computationally unbounded extractor. We have omitted this definition in the current version since it is unclear whether it provides the correct privacy level. In general, the simulator should not be unbounded, and the extractor can be thought of as a part of the simulator.

    • Renamed Sub-GBGM to GBGM-H and statistical CRS trapdoor extractability to trapdoor extractability.

  2. 2.

    Section 5 contains new generic results for achieving composable Sub-ZK. Namely, we prove that if an argument is perfectly zero knowledge in the (trusted) CRS model and satisfies the notion of trapdoor extractability, then it has composable Sub-ZK.

  3. 3.

    We construct two versions of the Sub-ZK SNARK. The first version is trapdoor extractable and uses the general result from Sect. 5. The second version is more efficient but requires a different proof strategy. Compared to the construction in the conference version, CRS of the second argument is shorter by approximately n group elements, and the \({\mathsf {CV}}\) algorithm is also more efficient.

  4. 4.

    The full version [2] of the conference version contains details on implementation and performance. We removed it from the current version since the implementation is incompatible with the newest version of libsnark library.

  5. 5.

    Fixed several small errors and updated the related/subsequent work section (see Sect. 2) with some of the intermediate results.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Abdolmaleki, B., Lipmaa, H., Siim, J. et al. On Subversion-Resistant SNARKs. J Cryptol 34, 17 (2021). https://doi.org/10.1007/s00145-021-09379-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00145-021-09379-y

Keywords

Search

Navigation