Abstract
Vector commitment (VC) schemes allow one to commit concisely to an ordered sequence of values, so that the values at desired positions can later be proved concisely. In addition, a VC can be statelessly updatable, meaning that commitments and proofs can be updated to reflect changes to individual entries, using knowledge of just those changes (and not the entire vector). VCs have found important applications in verifiable outsourced databases, cryptographic accumulators, and cryptocurrencies. However, to date there have been relatively few post-quantum constructions, i.e., ones that are plausibly secure against quantum attacks.
More generally, functional commitment (FC) schemes allow one to concisely and verifiably reveal various functions of committed data, such as linear functions (i.e., inner products, including evaluations of a committed polynomial). Under falsifiable assumptions, all known functional commitments schemes have been limited to “linearizable” functions, and there are no known post-quantum FC schemes beyond ordinary VCs.
In this work we give post-quantum constructions of vector and functional commitments based on the standard Short Integer Solution lattice problem (appropriately parameterized):
-
First, we present new statelessly updatable VCs with significantly shorter proofs than (and efficiency otherwise similar to) the only prior post-quantum, statelessly updatable construction (Papamanthou et al., EUROCRYPT 13). Our constructions use private-key setup, in which an authority generates public parameters and then goes offline.
-
Second, we construct functional commitments for arbitrary (bounded) Boolean circuits and branching programs. Under falsifiable assumptions, this is the first post-quantum FC scheme beyond ordinary VCs, and the first FC scheme of any kind that goes beyond linearizable functions. Our construction works in a new model involving an authority that generates the public parameters and remains online to provide public, reusable “opening keys” for desired functions of committed messages.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In this overview we aim only for position binding, and dispense with hiding.
- 2.
As an optimization, for Boolean functions f the matrix \(\mathbf {C}_{m}\) can be further compressed to just a single vector \(\mathbf {c}_{m} \in \mathbb {Z}_q^{n}\); we omit the details in this overview.
- 3.
However, if the class has only polynomially many functions, then the authority can publish all the opening keys and then go offline (disappear).
- 4.
- 5.
The determinism is without loss of generality, because \(\mathsf {PrepareUpdates} \) can include any needed random coins in \(\delta _{c}\); the same also applies for \(\mathsf {UpdateP}, \delta _{p}\) and \(\mathsf {UpdateS}, \delta _{s}\).
- 6.
For statelessly updatable schemes, this step can be replaced by \(\mathsf {PrepareUpdates} ^{\text {no-st}}(cp, j, m_j, m'_j)\), and for differentially updatable ones, it can be replaced by \(\mathsf {PrepareUpdates} ^{\text {diff}}(cp, j, \delta = m'_j - m_j)\).
- 7.
We stress that \(\mathbf {G}^{-1}\) is a function, not a matrix, and it does not necessarily satisfy \(\mathbf {G}^{-1}(\mathbf {G}\cdot \mathbf {z}) = \mathbf {z}\) for \(\mathbf {z}\in \mathbb {Z}^{w}\).
- 8.
Alternatively, depending on how much space it requires to represent \(\boldsymbol{\delta }\) compared to an element of \(\mathbb {Z}_q^{n}\), it may be preferable to output \(\delta _{c} = (j, \boldsymbol{\delta })\) as the commitment update, and have \(\mathsf {UpdateC} \) compute \(\mathbf {U}_{j} \boldsymbol{\delta }\).
- 9.
Alternatively, if \(\mathsf {UpdateP} \) has access to all the \(\mathbf {R}_{i,j}\) (via the committer parameters), then we can output a smaller proof update \(\delta _{p} = \boldsymbol{\delta }\), and \(\mathsf {UpdateP} \) can compute \(\mathbf {r}_{i} = \mathbf {R}_{i,j} \boldsymbol{\delta }\) itself.
- 10.
A smaller \(\gamma \) can be used if we have a tighter bound on \(\Vert \mathbf {m}\Vert \), e.g., if we know from the surrounding application that \(\mathbf {m}\) is sparse.
- 11.
We use the term combinability rather than aggregatability because the latter is often used for the ability to combine proofs for several different locations, which we do not see how to do for our construction.
- 12.
The factor \(M_{\overline{I}} \cdot w \cdot d^{h}\) in \(M_{I}\) may be replaced by an upper bound on \(\Vert \mathbf {m}\Vert _{1}\) for only those message vectors \(\mathbf {m}\) that may be used in an application, e.g., sparse vectors.
- 13.
Specifically, \(\mathbf {U}^{(k)}_{\overline{\jmath }} = \mathbf {U}_{j} \mathbf {G}^{-1}(\mathbf {U}^{(k-1)}_{\overline{\jmath }'})\) where \(\overline{\jmath } = j d^{k-1} + \overline{\jmath }'\) for \(\overline{\jmath } \in [d^{k}]\), \(j \in [d]\), and \(\overline{\jmath }' \in [d^{k-1}]\). Unrolling this fully, \(\mathbf {U}^{(k)}_{\overline{\jmath }} = \mathbf {U}_{j_{k-1}}\mathbf {G}^{-1}(\mathbf {U}_{j_{i-2}} \mathbf {G}^{-1}( \cdots \mathbf {G}^{-1}( \mathbf {U}_{j_{1}} \mathbf {G}^{-1}(\mathbf {U}_{j_{0}})) \cdots ))\) where \(j_{k-1} \cdots j_{1} j_{0}\) is the base-d representation of \(\overline{\jmath }\).
- 14.
Note that \(\mathbf {G}\overline{\mathbf {c}} = \mathbf {U}\mathbf {S}^{(k)} \overline{\mathbf {m}} \in \mathbb {Z}_q^{n}\) is the commitment output of \(\mathsf {Commit} (cp, \mathbf {S}^{(k)} \overline{\mathbf {m}})\), but we cannot necessarily compute \(\overline{\mathbf {c}}\) from that output.
- 15.
Alternatively, the computation of all the \(d^{h-1}\) intermediate commitments \(\overline{\mathbf {c}}_i\) could be done at commitment time, and stored in st.
- 16.
Note that we allow the adversary to query the oracle on any \(f \in \mathcal {F}\), even \(f=f^{*}\). This is because having an opening key for \(f^{*}\) does not inherently allow for breaking function binding for \(f^{*}\)—as opposed to, say, identity-based encryption, where a decryption key for the target identity trivially allows decryption of the challenge ciphertext.
- 17.
No homomorphic properties (only invertible differences) are needed for this encoding of the functions, so hashing is acceptable.
- 18.
For \(L > n\), we can simply treat the function as the concatenation of multiples functions, and extract keys and generate proofs for each of them individually.
References
Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: EUROCRYPT, pp. 553–572 (2010)
Agrawal, S., Freeman, D.M., Vaikuntanathan, V.: Functional encryption for inner product predicates from learning with errors. In: ASIACRYPT (2011)
Alperin-Sheriff, J., Peikert, C.: Faster bootstrapping with polynomial error. In: CRYPTO, pp. 297–314 (2014)
Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: IEEE Symposium on Security and Privacy, pp. 315–334 (2018)
Boneh, D., Drake, J., Fisch, B., Gabizon, A.: Halo infinite: Recursive zk-SNARKs from any additive polynomial commitment scheme. Cryptology ePrint Archive, Report 2020/1536 (2020). https://eprint.iacr.org/2020/1536
Benaloh, J.C., de Mare, M.: One-way accumulators: a decentralized alternative to digital sinatures (extended abstract). In: EUROCRYPT, vol. 765, pp. 274–285 (1993)
Bünz, B., Fisch, B., Szepieniec, A.: Transparent SNARKs from DARK compilers. In: EUROCRYPT, pp. 677–706 (2020)
Badrinarayanan, S., Goyal, V., Jain, A., Sahai, A.: Verifiable functional encryption. In: ASIACRYPT, pp. 557–587 (2016)
Benabbas, S., Gennaro, R., Vahlis, Y.: Verifiable delegation of computation over large datasets. In: CRYPTO, pp. 111–131 (2011)
Brakerski, Z., Vaikuntanathan, V.: Lattice-based FHE as secure as PKE. In: ITCS, pp. 1–12 (2014)
Canetti, R., et al.: Fiat-Shamir: from practice to theory. In: STOC, pp. 1082–1090 (2019)
Catalano, D., Fiore, D.: Vector commitments and their applications. In: PKC, pp. 55–72 (2013)
Campanelli, M., Fiore, D., Greco, N., Kolonelos, D., Nizzardo, L.: Incrementally aggregatable vector commitments and applications to verifiable decentralized storage. In: ASIACRYPT, pp. 3–35 (2020)
Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In: FOCS, pp. 383–395 (1985)
Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. J. Cryptol. 25(4), 601–639 (2012). Preliminary version in Eurocrypt 2010
Chepurnoy, A., Papamanthou, C., Srinivasan, S., Zhang, Y.: EDRAX: a cryptocurrency with stateless transaction validation. Cryptology ePrint Archive, Report 2018/968 (2018). https://eprint.iacr.org/2018/968
Catalano, D., Raimondo, M.D., Fiore, D., Messina, M.: Zero-knowledge sets with short proofs. IEEE Trans. Inf. Theory 57(4), 2488–2502 (2011). Preliminary version in EUROCRYPT 2008
Dwork, C., Naor, M.: An Efficient Existentially Unforgeable Signature Scheme and its Applications. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 234–246. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48658-5_23
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008)
Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: CRYPTO, pp. 75–92 (2013)
Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: STOC, pp. 469–477 (2015)
Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: STOC, pp. 99–108 (2011)
Hubácek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: ITCS, pp. 163–172 (2015)
Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC, pp. 723–732 (1992)
Kuszmaul, J.: Verkle trees (2018). Unpublished manuscript, available at https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf
Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: ASIACRYPT, pp. 177–194 (2010)
Liskov, M.D.: Updatable zero-knowledge databases. In: ASIACRYPT, pp. 174–198 (2005)
Lai, R.W.F., Malavolta, G.: Subvector commitments with application to succinct arguments. In: CRYPTO, pp. 530–560 (2019)
Lipmaa, H., Pavlyk, K.: Succinct functional commitment for a large class of arithmetic circuits. In: ASIACRYPT, pp. 686–716 (2020)
Libert, B., Ramanna, S.C., Yung, M.: Functional commitment schemes: from polynomial commitments to pairing-based accumulators from simple assumptions. In: ICALP, pp. 30:1–30:14 (2016)
Lyubashevsky, V., Wichs, D.: Simple lattice trapdoor sampling from a broad class of distributions. In: PKC, pp. 716–730 (2015)
Libert, B., Yung, M.: Concise mercurial vector commitments and independent zero-knowledge sets with short proofs. In: TCC, pp. 499–517 (2010)
Merkle, R.C.: A digital signature based on a conventional encryption function. In: CRYPTO, pp. 369–378 (1987)
Micali, S.: CS proofs. In: FOCS, pp. 436–453 (1994)
Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: EUROCRYPT, pp. 700–718 (2012)
Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007). Preliminary version in FOCS 2004
Micali, S., Rabin, M.O., Kilian, J.: Zero-knowledge sets. In: FOCS, pp. 80–91 (2003)
Peikert, C., Shiehian, S.: Noninteractive zero knowledge for NP from (plain) learning with errors. In: CRYPTO, pp. 89–114 (2019)
Papamanthou, C., Shi, E., Tamassia, R., Yi, K.: Streaming authenticated data structures. In: EUROCRYPT, pp. 353–370 (2013)
Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. SIAM J. Comput. 40(6), 1803–1844 (2011). Preliminary version in STOC 2008
Steinfeld, R., Bull, L., Zheng, Y.: Content extraction signatures. In: ICISC, pp. 285–304 (2001)
Tomescu, A., Abraham, I., Buterin, V., Drake, J., Feist, D., Khovratovich, D.: Aggregatable subvector commitments for stateless cryptocurrencies. In: SCN, Lecture Notes in Computer Science, pp. 45–64 (2020)
Xagawa, K.: Improved (hierarchical) inner-product encryption from lattices. In: PKC, pp. 235–252 (2013)
Yamada, S.: Adaptively secure identity-based encryption from lattices with asymptotically shorter public parameters. In: EUROCRYPT, pp. 32–62 (2016)
Acknowledgments
We thank the anonymous TCC reviewers for many helpful comments and suggestions. This material is based upon work supported by DARPA under Agreement No. HR00112020025. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 International Association for Cryptologic Research
About this paper
Cite this paper
Peikert, C., Pepin, Z., Sharp, C. (2021). Vector and Functional Commitments from Lattices. In: Nissim, K., Waters, B. (eds) Theory of Cryptography. TCC 2021. Lecture Notes in Computer Science(), vol 13044. Springer, Cham. https://doi.org/10.1007/978-3-030-90456-2_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-90456-2_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-90455-5
Online ISBN: 978-3-030-90456-2
eBook Packages: Computer ScienceComputer Science (R0)
