Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Batch Lattice-Based Designated-Verifier ZK-SNARKs for R1CS

  • Conference paper
  • First Online:

Abstract

Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK) is a crucial cryptographic tool to achieve privacy protection and has drawn considerable attention for its appealing applications, e.g., anonymous transactions, confidential smart contracts, and scalable consensus mechanisms. Compared with the pre-quantum case, the practicability of this primitive in the post-quantum setting is still unsatisfactory, especially for the space complexity.

In this work, we generalize the LPCP-based SNARK schemes for general cyclotomic rings and propose a tighter bound in the noise analysis for non-power-of-two cyclotomic rings using the powerful basis. Secondly, we introduce the first batch SNARK scheme for rank-1 constraint system (R1CS) in\({\mathbb {F}}_{p^n}\) for any primep. Then, we apply our batch SNARK schemes for R1CS in\({\mathbb {F}}_{2^n}\) and implement it. Using the batch technique, we can process multiple relations at the same time, thereby yielding nice amortized results. The amortized proof size is around 3KB for moderate-size circuits (the circuit size ranges from\(2^{10}\) to\(2^{14}\)).

To exemplify the efficiency, we present some practical examples. Initially, we integrate a rank-1 constraint system in\({\mathbb {F}}_{2^8}\) for the AES algorithm, which is 3.95x smaller than xJsnark (Kosba et al., 2018) in terms of the number of constraints. Subsequently, we proceed to instantiate our batch SNARK scheme for AES, MiMC, and LowMC.

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

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8007
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 12869
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

References

  1. Albrecht, M., Grassi, L., Rechberger, C., Roy, A., Tiessen, T.: MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 191–219. Springer, Heidelberg (2016).https://doi.org/10.1007/978-3-662-53887-6_7

    Chapter  Google Scholar 

  2. Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol.9(3), 169–203 (2015)

    Article MathSciNet  Google Scholar 

  3. Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 430–454. Springer, Heidelberg (2015).https://doi.org/10.1007/978-3-662-46800-5_17

    Chapter  Google Scholar 

  4. Banaszczyk, W.: Inequalities for convex bodies and polar reciprocal lattices in\(R^{n}\). Discret. Comput. Geom.13, 217–231 (1995)

    Article  Google Scholar 

  5. Ben-Sasson, E., et al.: Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 459–474 (2014)

    Google Scholar 

  6. Bonneau, J., Meckler, I., Rao, V., Shapiro, E.: Coda: Decentralized cryptocurrency at scale. Cryptology ePrint Archive, Paper 2020/352 (2020).https://eprint.iacr.org/2020/352

  7. Bouvier, C., et al.: New design techniques for efficient arithmetization-oriented hash functions: anemoi permutations and jive compression mode. Cryptology ePrint Archive (2022)

    Google Scholar 

  8. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory (TOCT)6(3), 1–36 (2014)

    Article MathSciNet  Google Scholar 

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

    Chapter  Google Scholar 

  10. Esgin, M.F., Nguyen, N.K., Seiler, G.: Practical exact proofs from lattices: new techniques to exploit fully-splitting rings. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 259–288. Springer, Cham (2020).https://doi.org/10.1007/978-3-030-64834-3_9

    Chapter  Google Scholar 

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

    Chapter  Google Scholar 

  12. Gennaro, R., Minelli, M., Nitulescu, A., Orrù, M.: Lattice-based zk-snarks from square span programs. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 556–573 (2018)

    Google Scholar 

  13. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, pp. 169–178 (2009)

    Google Scholar 

  14. Gentry, C., Halevi, S., Smart, N.P.: Homomorphic evaluation of the AES circuit. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 850–867. Springer, Heidelberg (2012).https://doi.org/10.1007/978-3-642-32009-5_49

    Chapter  Google Scholar 

  15. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput.18(1), 186–208 (1989).https://doi.org/10.1137/0218012

    Article MathSciNet  Google Scholar 

  16. Grassi, L., Hao, Y., Rechberger, C., Schofnegger, M., Walch, R., Wang, Q.: Horst meets fluid-spn: griffin for zero-knowledge applications. Cryptology ePrint Archive (2022)

    Google Scholar 

  17. Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: Poseidon: a new hash function for zero-knowledge proof systems. In: USENIX Security Symposium, vol. 2021 (2021)

    Google Scholar 

  18. Grassi, L., Onofri, S., Pedicini, M., Sozzi, L.: Invertible quadratic non-linear layers for MPC-/FHE-/ZK-friendly schemes over fnp: application to Poseidon. IACR Transactions on Symmetric Cryptology, pp. 20–72 (2022)

    Google Scholar 

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

    Chapter  Google Scholar 

  20. Halevi, S., Shoup, V.: Design and implementation of HElib: a homomorphic encryption library. Cryptology ePrint Archive, Paper 2020/1481 (2020).https://eprint.iacr.org/2020/1481

  21. Ishai, Y., Su, H., Wu, D.J.: Shorter and faster post-quantum designated-verifier zkSNARKS from lattices. In: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (2021)

    Google Scholar 

  22. Kosba, A., Papamanthou, C., Shi, E.: xJsnark: a framework for efficient verifiable computation. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 944–961. IEEE (2018)

    Google Scholar 

  23. Liu, F.H., Wang, H.: Batch bootstrapping i: a new framework for SIMD bootstrapping in polynomial modulus. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. LNCS, vol. 14006, pp. 321–352. Springer, Cham (2023).https://doi.org/10.1007/978-3-031-30620-4_11

  24. Lüftenegger, R., Rechberger, C., Grassi, L., Schofnegger, M., Walch, R., Khovratovich, D.: Reinforced concrete: a fast hash function for verifiable computation. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS’22) (2022)

    Google Scholar 

  25. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM (JACM)56(6), 1–40 (2009)

    Article MathSciNet  Google Scholar 

  26. Songhori, E.M., Hussain, S.U., Sadeghi, A.R., Schneider, T., Koushanfar, F.: TinyGarble: highly compressed and scalable sequential garbled circuits. In: 2015 IEEE Symposium on Security and Privacy, pp. 411–428. IEEE (2015)

    Google Scholar 

  27. Yang, R., Au, M.H., Zhang, Z., Xu, Q., Yu, Z., Whyte, W.: Efficient lattice-based zero-knowledge arguments with standard soundness: construction and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 147–175. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-26948-7_6

    Chapter  Google Scholar 

Download references

Acknowledgements

We thank the reviewers of SecureComm 2023 for providing insightful comments to improve the clarity of this paper and pointing out some typos. This work is supported by the National Natural Science Foundation of China (No. 12371525).

Author information

Authors and Affiliations

  1. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

    Xi Lin, Han Xia, Yongqiang Li & Mingsheng Wang

  2. School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

    Xi Lin, Han Xia, Yongqiang Li & Mingsheng Wang

Authors
  1. Xi Lin

    You can also search for this author inPubMed Google Scholar

  2. Han Xia

    You can also search for this author inPubMed Google Scholar

  3. Yongqiang Li

    You can also search for this author inPubMed Google Scholar

  4. Mingsheng Wang

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toYongqiang Li.

Editor information

Editors and Affiliations

  1. Tsinghua University, Beijing, China

    Haixin Duan

  2. Concordia University, Montreal, QC, Canada

    Mourad Debbabi

  3. Hong Kong Polytechnic University, Kowloon, Hong Kong

    Xavier de Carné de Carnavalet

  4. Hong Kong Polytechnic University, Kowloon, Hong Kong

    Xiapu Luo

  5. Stevens Institute of Technology, Hoboken, USA

    Xiaojiang Du

  6. Hong Kong Polytechnic University, Kowloon, Hong Kong

    Man Ho Allen Au

Rights and permissions

Copyright information

© 2025 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Lin, X., Xia, H., Li, Y., Wang, M. (2025). Batch Lattice-Based Designated-Verifier ZK-SNARKs for R1CS. In: Duan, H., Debbabi, M., de Carné de Carnavalet, X., Luo, X., Du, X., Au, M.H.A. (eds) Security and Privacy in Communication Networks. SecureComm 2023. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 567. Springer, Cham. https://doi.org/10.1007/978-3-031-64948-6_17

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8007
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 12869
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp