Concretely Efficient Lattice-Based Polynomial Commitment from Standard Assumptions | SpringerLink
Skip to main content
Springer Nature Link
Log in

Concretely Efficient Lattice-Based Polynomial Commitment from Standard Assumptions

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2024 (CRYPTO 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14929))

Included in the following conference series:

  • 647 Accesses

Abstract

Polynomial commitment is a crucial cryptographic primitive in constructing zkSNARKs. Most practical constructions to date are either vulnerable against quantum adversaries or lack homomorphic properties, which are essential for recursive proof composition and proof batching. Recently, lattice-based constructions have drawn attention for their potential to achieve all the desirable properties, though they often suffer from concrete inefficiency or rely on newly introduced assumptions requiring further cryptanalysis.

In this paper, we propose a novel construction of a polynomial commitment scheme based on standard lattice-based assumptions. Our scheme achieves a square-root proof size and verification complexity, ensuring concrete efficiency in proof size, proof generation, and verification. Additionally, it features a transparent setup and publicly verifiability.

When compared with Brakedown (CRYPTO 2023), a recent code-based construction, our scheme offers comparable performance across all metrics. Furthermore, its proof size is approximately 4.1 times smaller than SLAP (EUROCRYPT 2024), a recent lattice-based construction.

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

Access this chapter

Log in via an institution

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 14871
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10581
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

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    In this context, we only consider the extractable versions of [2, 21].

  2. 2.

    Baum et al. [7] presented an effective encoding method for a finite field \(GF(p^k)\) with a small prime p, but it does not cover large primes.

  3. 3.

    https://eprint.iacr.org/2024/306.

  4. 4.

    In our benchmark for the non-zero knowledge version, we exclude all random sampling procedures.

References

  1. Ajtai, M.: Generating hard instances of lattice problems. In: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, pp. 99–108 (1996)

    Google Scholar 

  2. Albrecht, M.R., Cini, V., Lai, R.W., Malavolta, G., Thyagarajan, S.A.: Lattice-based snarks: publicly verifiable, preprocessing, and recursively composable. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13508, pp. 102–132. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_4

    Chapter  Google Scholar 

  3. Albrecht, M.R., Fenzi, G., Lapiha, O., Nguyen, N.K.: SLAP: succinct lattice-based polynomial commitments from standard assumptions. In: Joye, M., Leander, G. (eds.) EUROCRYPT 2024. LNCS, vol. 14657, pp. 90–119. Springer, Cham (2024). https://doi.org/10.1007/978-3-031-58754-2_4

    Chapter  Google Scholar 

  4. Attema, T., Lyubashevsky, V., Seiler, G.: Practical product proofs for lattice commitments. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 470–499. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_17

    Chapter  Google Scholar 

  5. Bai, S., Galbraith, S.D.: An improved compression technique for signatures based on learning with errors. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 28–47. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-04852-9_2

    Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  7. Baum, C., Bootle, J., Cerulli, A., Del Pino, R., Groth, J., Lyubashevsky, V.: Sub-linear lattice-based zero-knowledge arguments for arithmetic circuits. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 669–699. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_23

    Chapter  Google Scholar 

  8. Baum, C., Damgård, I., Lyubashevsky, V., Oechsner, S., Peikert, C.: More efficient commitments from structured lattice assumptions. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 368–385. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_20

    Chapter  Google Scholar 

  9. Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast Reed-Solomon interactive oracle proofs of proximity. In: 45th International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)

    Google Scholar 

  10. Benhamouda, F., Camenisch, J., Krenn, S., Lyubashevsky, V., Neven, G.: Better zero-knowledge proofs for lattice encryption and their application to group signatures. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 551–572. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_29

    Chapter  Google Scholar 

  11. Beullens, W., Seiler, G.: LaBRADOR: compact proofs for R1CS from module-SIS. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14085, pp. 518–548. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38554-4_17

    Chapter  Google Scholar 

  12. Boneh, D., Drake, J., Fisch, B., Gabizon, A.: Halo infinite: proof-carrying data from additive polynomial commitments. In: Annual International Cryptology Conference, pp. 649–680 (2021)

    Google Scholar 

  13. Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In: Fischlin, M., Coron, J.S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 327–357. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_12

    Chapter  Google Scholar 

  14. Bootle, J., Groth, J.: Efficient batch zero-knowledge arguments for low degree polynomials. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10770, pp. 561–588. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76581-5_19

    Chapter  Google Scholar 

  15. Bootle, J., Lyubashevsky, V., Nguyen, N.K., Seiler, G.: A non-PCP approach to succinct quantum-safe zero-knowledge. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 441–469. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_16

    Chapter  Google Scholar 

  16. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 315–334. IEEE (2018)

    Google Scholar 

  17. Bünz, B., Chiesa, A., Lin, W., Mishra, P., Spooner, N.: Proof-carrying data without succinct arguments. In: Annual International Cryptology Conference, pp. 681–710 (2021)

    Google Scholar 

  18. Bünz, B., Fisch, B., Szepieniec, A.: Transparent snarks from dark compilers. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 677–706 (2020)

    Google Scholar 

  19. Chen, H., Iliashenko, I., Laine, K.: When HEAAN meets FV: a new somewhat homomorphic encryption with reduced memory overhead. In: Paterson, M.B. (ed.) IMACC 2021. LNCS, vol. 13129, pp. 265–285. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92641-0_13

    Chapter  Google Scholar 

  20. Chen, H., Laine, K., Player, R., Xia, Y.: High-precision arithmetic in homomorphic encryption. In: Smart, N. (ed.) CT-RSA 2018. LNCS, vol. 10808, pp. 116–136. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76953-0_7

    Chapter  Google Scholar 

  21. Cini, V., Lai, R.W., Malavolta, G.: Lattice-based succinct arguments from vanishing polynomials. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14082, pp. 72–105. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38545-2_3

    Chapter  Google Scholar 

  22. 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 

  23. Fisch, B., Liu, Z., Vesely, P.: Orbweaver: succinct linear functional commitments from lattices. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14082, pp. 106–131. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38545-2_4

    Chapter  Google Scholar 

  24. Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_3

    Chapter  Google Scholar 

  25. Golovnev, A., Lee, J., Setty, S., Thaler, J., Wahby, R.S.: Brakedown: linear-time and field-agnostic snarks for R1CS. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14082, pp. 193–226. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38545-2_7

    Chapter  Google Scholar 

  26. Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 177–194. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_11

    Chapter  Google Scholar 

  27. Kim, D., Lee, D., Seo, J., Song, Y.: Toward practical lattice-based proof of knowledge from hint-MLWE. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14085, pp. 549–580. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38554-4_18

    Chapter  Google Scholar 

  28. Kothapalli, A., Setty, S., Tzialla, I.: Nova: recursive zero-knowledge arguments from folding schemes. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13510, pp. 359–388. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15985-5_13

    Chapter  Google Scholar 

  29. Kuchta, V., Sakzad, A., Steinfeld, R., Liu, J.K.: Efficient lattice-based polynomial evaluation and batch ZK arguments. In: Dunkelman, O., Jacobson, M.J., Jr., O’Flynn, C. (eds.) SAC 2020. LNCS, vol. 12804, pp. 3–33. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81652-0_1

    Chapter  Google Scholar 

  30. Lee, J.: Dory: efficient, transparent arguments for generalised inner products and polynomial commitments. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13043, pp. 1–34. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90453-1_1

    Chapter  Google Scholar 

  31. Lyubashevsky, V.: Lattice signatures without trapdoors. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 738–755. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_43

    Chapter  Google Scholar 

  32. Lyubashevsky, V., Nguyen, N.K., Seiler, G.: Practical lattice-based zero-knowledge proofs for integer relations. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 1051–1070 (2020)

    Google Scholar 

  33. Mera, J.M.B., Karmakar, A., Marc, T., Soleimanian, A.: Efficient lattice-based inner-product functional encryption. In: Hanaoka, G., Shikata, J., Watanabe, Y. (eds.) PKC 2022. LNCS, vol. 13178, pp. 163–193. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-97131-1_6

    Chapter  Google Scholar 

  34. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007)

    Article  MathSciNet  Google Scholar 

  35. Micciancio, D., Walter, M.: Gaussian sampling over the integers: efficient, generic, constant-time. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 455–485. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_16

    Chapter  Google Scholar 

  36. Nguyen, N.K., Seiler, G.: Practical sublinear proofs for R1CS from lattices. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13508, pp. 133–162. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_5

    Chapter  Google Scholar 

  37. Peikert, C.: An efficient and parallel Gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 80–97. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_5

    Chapter  Google Scholar 

  38. Tomescu, A., et al.: Towards scalable threshold cryptosystems. In: 2020 IEEE Symposium on Security and Privacy (SP), pp. 877–893. IEEE (2020)

    Google Scholar 

  39. Wee, H., Wu, D.J.: Lattice-based functional commitments: fast verification and cryptanalysis. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023. LNCS, vol. 14442, pp. 201–235. Springer, Singapore (2023). https://doi.org/10.1007/978-981-99-8733-7_7

    Chapter  Google Scholar 

  40. Wee, H., Wu, D.J.: Succinct vector, polynomial, and functional commitments from lattices. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14006, pp. 385–416. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30620-4_13

    Chapter  Google Scholar 

  41. Zhang, J., Xie, T., Hoang, T., Shi, E., Zhang, Y.: Polynomial commitment with a One-to-Many prover and applications. In: 31st USENIX Security Symposium (USENIX Security 2022), pp. 2965–2982 (2022)

    Google Scholar 

Download references

Acknowledgement

This work was supported by Samsung Research Funding & Incubation Center of Samsung Electronics under Project Number SRFC-TB2103-01.

Author information

Authors and Affiliations

  1. Seoul National University, Seoul, South Korea

    Intak Hwang, Jinyeong Seo & Yongsoo Song

Authors
  1. Intak Hwang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jinyeong Seo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yongsoo Song
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yongsoo Song .

Editor information

Editors and Affiliations

  1. Boston University, Boston, MA, USA

    Leonid Reyzin

  2. University of Waterloo, Waterloo, ON, Canada

    Douglas Stebila

Rights and permissions

Reprints and permissions

Copyright information

© 2024 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Hwang, I., Seo, J., Song, Y. (2024). Concretely Efficient Lattice-Based Polynomial Commitment from Standard Assumptions. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology – CRYPTO 2024. CRYPTO 2024. Lecture Notes in Computer Science, vol 14929. Springer, Cham. https://doi.org/10.1007/978-3-031-68403-6_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-68403-6_13

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-68402-9

  • Online ISBN: 978-3-031-68403-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation