close
Skip to main content
Springer Nature Link
Log in

Functional commitments for arbitrary circuits of bounded sizes

  • Published:
Save article
View saved research
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

A functional commitment (FC) scheme enables committing to a vector \({\textbf{x}}\) and later producing an opening proof \(\pi \) for a function value \(y=f({\textbf{x}})\) with function f in some function set \({\mathcal {F}}\). Everyone can verify the validity of the opening proof \(\pi \) w.r.t. the function f and the function value y. Up to now, the largest function set is the bounded-depth circuits and achieved by FC schemes in [Peikeit et al. TCC 2021, De Castro et al. TCC 2023, Wee et al. Eurocrypt 2023, Wee et al. Asiacrypt 2023] with the help of the homomorphic encoding and evaluation techniques from lattices. In fact, these FC schemes can hardly support circuits of large depth, due to the fast accumulation of noises in the homomorphic evaluations. For example, if the depth of the circuit is linear to the security parameter \(\lambda \), then the underlying \(\textsf {GapSVP}_{\gamma }\) problem will be accompanied with a super-exponentially large parameter \(\gamma >(\lambda \log \lambda )^{\Theta (\lambda )}\) and can be easily solved by the LLL algorithm. In this work, we propose a new FC scheme supporting arbitrary circuits of bounded sizes. We make use of homomorphic encoding and evaluation as well, but we disassemble the circuit gate by gate, process the gates, and reassemble the processed gates to a flattened circuit of logarithm depth \(O(\log \lambda )\). This makes possible for our FC scheme to support arbitrary polynomial-size circuits. Our FC scheme has the common reference string (CRS) growing linear to the size of the circuit. So CRSs of different sizes allow our FC scheme to support circuits of different (bounded) sizes. Just like the recent work on FC schemes [Wee et al. Eurocrypt 2023, Asiacrypt 2023], our FC scheme achieves private opening and target binding based on a falsifiable family of “basis-augmented” SIS assumptions. Our FC scheme has succinct commitment but not succinct opening proof which of course does not support fast verification. To improve the running time of verification, we resort to the non-interactive GKR protocol to outsource the main computation in verification to the proof generation algorithm. As a result, we obtain an improved FC scheme which decreases the computational complexity of verification with a factor \(O(\lambda )\).

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+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

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

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Data availability

Not applicable.

Code availability

Not applicable.

References

  1. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Vitter, J.S., Spirakis, P.G., Yannakakis, M. (eds.) Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pp. 601–610. ACM, ??? (2001). https://doi.org/10.1145/380752.380857 .

  2. 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).

  3. Albrecht, M.R., Cini, V., Lai, R.W., Malavolta, G., Thyagarajan, S.A.: Lattice-based snarks: Publicly verifiable, preprocessing, and recursively composable. In: Annual International Cryptology Conference, pp. 102–132 (2022). Springer

  4. Balbás, D., Catalano, D., Fiore, D., Lai, R.W.: Functional commitments for circuits from falsifiable assumptions. Cryptology ePrint Archive (2022)

  5. Boneh, D., Drake, J., Fisch, B., Gabizon, A.: Halo infinite: Proof-carrying data from additive polynomial commitments. In: Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part I 41, pp. 649–680 (2021). Springer

  6. Boneh, D., Gentry, C., Gorbunov, S., Halevi, S., Nikolaenko, V., Segev, G., Vaikuntanathan, V., Vinayagamurthy, D.: Fully key-homomorphic encryption, arithmetic circuit abe and compact garbled circuits. In: Advances in Cryptology–EUROCRYPT 2014: 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings 33, pp. 533–556 (2014). Springer

  7. Bünz, B., Fisch, B., Szepieniec, A.: Transparent snarks from dark compilers. In: Advances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part I 39, pp. 677–706 (2020). Springer

  8. Campanelli, M., Fiore, D., Greco, N., Kolonelos, D., Nizzardo, L.: Incrementally aggregatable vector commitments and applications to verifiable decentralized storage. In: Advances in Cryptology–ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part II 26, pp. 3–35 (2020). Springer

  9. Castro, L., Peikert, C.: Functional commitments for all functions, with transparent setup and from sis. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 287–320 (2023). Springer

  10. Catalano, D., Fiore, D., Tucker, I.: Additive-homomorphic functional commitments and applications to homomorphic signatures. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 159–188 (2022). Springer

  11. Catalano, D., Fiore, D.: Vector commitments and their applications. In: Public-Key Cryptography–PKC 2013: 16th International Conference on Practice and Theory in Public-Key Cryptography, Nara, Japan, February 26–March 1, 2013. Proceedings 16, pp. 55–72 (2013). Springer

  12. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Conference on the Theory and Application of Cryptographic Techniques, pp. 186–194 (1986). Springer

  13. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 197–206 (2008)

  14. Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In: Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, pp. 75–92 (2013). Springer

  15. Goldwasser S., Kalai Y.T., Rothblum G.N.: Delegating computation: interactive proofs for muggles. Journal of the ACM (JACM) 62(4), 1–64 (2015).

    Article  MathSciNet  Google Scholar 

  16. Gorbunov, S., Reyzin, L., Wee, H., Zhang, Z.: Pointproofs: Aggregating proofs for multiple vector commitments. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 2007–2023 (2020)

  17. Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, pp. 469–477 (2015)

  18. Håstad J., Impagliazzo R., Levin L.A., Luby M.: A pseudorandom generator from any one-way function. SIAM Journal on Computing 28(4), 1364–1396 (1999).

    Article  MathSciNet  Google Scholar 

  19. Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16, pp. 177–194 (2010). Springer

  20. Lai, R.W., Malavolta, G.: Subvector commitments with application to succinct arguments. In: Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part I 39, pp. 530–560 (2019). Springer

  21. Lenstra A.K., Lenstra H.W., Lovász L.: Factoring polynomials with rational coefficients. Mathematische annalen 261, 515–534 (1982).

    Article  MathSciNet  Google Scholar 

  22. Libert, B., Ramanna, S.C., et al.: Functional commitment schemes: From polynomial commitments to pairing-based accumulators from simple assumptions. In: 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016) (2016)

  23. Libert, B., Yung, M.: Concise mercurial vector commitments and independent zero-knowledge sets with short proofs. In: Theory of Cryptography Conference, pp. 499–517 (2010). Springer

  24. Lipmaa, H., Pavlyk, K.: Succinct functional commitment for a large class of arithmetic circuits. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 686–716 (2020). Springer

  25. Lund C., Fortnow L., Karloff H., Nisan N.: Algebraic methods for interactive proof systems. Journal of the ACM (JACM) 39(4), 859–868 (1992).

    Article  MathSciNet  Google Scholar 

  26. Micciancio, D., Peikert, C.: Trapdoors for lattices: Simpler, tighter, faster, smaller. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 700–718 (2012). Springer

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

    Article  MathSciNet  Google Scholar 

  28. Papamanthou, C., Shi, E., Tamassia, R.: Signatures of correct computation. In: Theory of Cryptography Conference, pp. 222–242 (2013). Springer

  29. Peikert, C., Pepin, Z., Sharp, C.: Vector and functional commitments from lattices. In: Theory of Cryptography: 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part III 19, pp. 480–511 (2021). Springer

  30. Schnorr C.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53, 201–224 (1987). https://doi.org/10.1016/0304-3975(87)90064-8.

    Article  MathSciNet  Google Scholar 

  31. Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zksnarks without trusted setup. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 926–943 (2018). IEEE

  32. Wee, H., Wu, D.J.: Lattice-based functional commitments: Fast verification and cryptanalysis. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 201–235 (2023). Springer

  33. Wee, H., Wu, D.J.: Succinct vector, polynomial, and functional commitments from lattices. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 385–416 (2023). Springer

Download references

Acknowledgements

This work is partially sponsored by National Natural Science Foundation of China under Grant No. 61925207, National Natural Science Foundation of China under Grant No. 62372292, Guangdong Major Project of Basic and Applied Basic Research under Grant No. 2019B030302008, and the National Key R &D Program of China under Grant No.2022YFB2701500.

Funding

Jinrui Sha and Shengli Liu were partially sponsored by Guangdong Major Project of Basic and Applied Basic Research under Grant No. 2019B030302008, National Natural Science Foundation of China under Grant No. 61925207 and the National Key R &D Program of China under Grant No. 2022YFB2701500. Shuai Han was partially supported by National Natural Science Foundation of China under Grant No. 62372292.

Author information

Authors and Affiliations

  1. School of Cyber Science and Engineering, Shanghai Jiao Tong University, Shanghai, 200240, China

    Jinrui Sha & Shuai Han

  2. State Key Laboratory of Cryptology, P.O. Box 5159, Beijing, 100878, China

    Jinrui Sha, Shengli Liu & Shuai Han

  3. Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, 200240, China

    Shengli Liu

Authors
  1. Jinrui Sha
    View author publications

    Search author on:PubMed Google Scholar

  2. Shengli Liu
    View author publications

    Search author on:PubMed Google Scholar

  3. Shuai Han
    View author publications

    Search author on:PubMed Google Scholar

Contributions

Not applicable.

Corresponding authors

Correspondence to Shengli Liu or Shuai Han.

Ethics declarations

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Ethical approval

Not applicable.

Consent to participate

Not applicable.

Consent for publication

Not applicable.

Additional information

Communicated by X. Wang.

Publisher's Note

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

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sha, J., Liu, S. & Han, S. Functional commitments for arbitrary circuits of bounded sizes. Des. Codes Cryptogr. 92, 3919–3953 (2024). https://doi.org/10.1007/s10623-024-01468-w

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Version of record:

  • Issue date:

  • DOI: https://doi.org/10.1007/s10623-024-01468-w

Keywords

Mathematics Subject Classification

Profiles

  1. Shengli Liu View author profile
  2. Shuai Han View author profile