Dual functional commitments for arbitrary circuits of bounded sizes

Abstract

A functional commitment (FC) commits to a value x, and can later generate a proof for a function value y=f(x) with respect to some function f\in \mathcal{F}. In contrast, the dual functional commitment (dual FC) allows a committer to commit to a function f\in \mathcal{F}, and later produces an opening proof \pi for the function value y=f(x) given an input x. We propose a new construction of dual FC scheme from lattices. Our dual FC scheme can support arbitrary circuits of bounded sizes. Moreover, our dual FC scheme enjoys computational binding, and we prove the computational binding property of our dual FC based on the l-succinct \mathsf{\text{H}}-\mathsf{\text{SIS}} assumption, a falsifiable generalization of the l-succinct \mathsf{\text{SIS}} assumption, in the random oracle model. In addition, our dual FC scheme is quasi-succinct with a succinct commitment and a quasi-succinct opening proof.

Graphical abstract

Keywords

dual functional commitment / arbitrary circuits / lattice

References

[1] de Castro L, Peikert C. Functional commitments for all functions, with transparent setup and from sis. In: Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2023, 287−320

[2] Wee H, Wu D J. Lattice-based functional commitments: Fast verification and cryptanalysis. In: Proceedings of the 29th International Conference on the Theory and Application of Cryptology and Information Security. 2023, 201−235

[3] Catalano D, Fiore D, Tucker I. Additive-homomorphic functional commitments and applications to homomorphic signatures. In: Proceedings of the 28th International Conference on the Theory and Application of Cryptology and Information Security. 2022, 159−188

[4] Gorbunov S, Reyzin L, Wee H, Zhang Z. Pointproofs: aggregating proofs for multiple vector commitments. In: Proceedings of 2020 ACM SIGSAC Conference on Computer and Communications Security. 2020, 2007−2023

[5] Campanelli M, Fiore D, Greco N, Kolonelos D, Nizzardo L. Incrementally aggregatable vector commitments and applications to verifiable decentralized storage. In: Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security. 2020, 3−35

[6] Bünz B, Fisch B, Szepieniec A. Transparent SNARKs from DARK compilers. In: Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2020, 677−706

[7] Boneh D, Drake J, Fisch B, Gabizon A. Halo Infinite: Proof-carrying data from additive polynomial commitments. In: Proceedings of the 41st Annual International Cryptology Conference. 2021, 649−680

[8] Libert B, Ramanna S C, Yung M. Functional commitment schemes: from polynomial commitments to pairing-based accumulators from simple assumptions. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming. 2016

[9] Lai R W F, Malavolta G. Subvector commitments with application to succinct arguments. In: Proceedings of the 39th Annual International Cryptology Conference. 2019, 530−560

[10] Lipmaa H, Pavlyk K. Succinct functional commitment for a large class of arithmetic circuits. In: Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security. 2020, 686−716

[11] Boneh D, Nguyen W D, Ozdemir A . Efficient functional commitments: how to commit to private functions. Cryptology ePrint Archive, 2021, 2021: 1342

[12] Peikert C, Pepin Z, Sharp C. Vector and functional commitments from lattices. In: Proceedings of the 19th International Conference on Theory of Cryptography. 2021, 480−511

[13] Albrecht M R, Cini V, Lai R W F, Malavolta G, Thyagarajan S A. Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable. In: Proceedings of the 42nd Annual International Cryptology Conference. 2022, 102−132

[14] Balbás D, Catalano D, Fiore D, Lai R W F . Functional commitments for circuits from falsifiable assumptions. Cryptology ePrint Archive, 2022, 2022: 1365

[15] Wee H, Wu D J. Succinct vector, polynomial, and functional commitments from lattices. In: Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2023, 385−416

[16] Sha J, Liu S, Han S . Functional commitments for arbitrary circuits of bounded sizes. Designs, Codes and Cryptography, 2024, 92( 12): 3919–3953

[17] Wee H. Functional commitments and SNARGs for P/poly from SIS. In: Proceedings of the 45th Annual International Cryptology Conference. 2025, 617−640

[18] Wee H. Circuit ABE with poly(depth, λ)-sized ciphertexts and keys from lattices. In: Proceedings of the 44th Annual International Cryptology Conference. 2024, 178−209

[19] Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 75−92

[20] Gorbunov S, Vaikuntanathan V, Wichs D. Leveled fully homomorphic signatures from standard lattices. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing. 2015, 469−477

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

[22] Schnorr C P . A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 1987, 53( 2−3): 201–224

[23] Ajtai M, Kumar R, Sivakumar D. A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. 2001, 601−610

[24] 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: Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2014, 533−556

[25] Micciancio D, Peikert C. Trapdoors for lattices: simpler, tighter, faster, smaller. In: Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2012, 700−718

[26] Dodis Y, Reyzin L, Smith A. Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. 2004, 523−540

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

[28] Ajtai M. Generating hard instances of lattice problems (extended abstract). In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. 1996, 99−108

Rights & permissions

Higher Education Press