Constant-Size Commitments to Polynomials and Their Applications

By Aniket Kate, Gregory M. Zaverucha, Ian Goldberg. 2010

876 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Biscotti: A Ledger for Private and Secure Peer-to-Peer Machine Learning (2018, background): “dividual updates need to be made part of the block. However, storing them would leak information about private training data of the individuals. We solve this problem by using polynomial commitments. [27]. Polynomial commitments take an SGD update and map it to a point on an elliptic curve. (see App”
A Survey of Verifiable Computation (2017, background): “For instance, the schemes proposed in [4, 11, 16, 49] only support addition, exponentiation, or multiplication, so that they can achieve operation time in a microsecond level for each polynomiallevel computation.”
Transparent SNARKs from DARK Compilers (2020, methodology): “[39] to allow interactive evaluation proofs.”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, methodology): “There exist many polynomial commitment schemes in the literature [65, 75, 94], but most of them require a trusted setup that produces a structured common reference string with a secret trapdoor (analogous to GGPR-style protocols), which we wish to avoid.”
Doubly-Efficient zkSNARKs Without Trusted Setup (2018, methodology): “We apply their idea to the ZK setting,4 reducing communication and saving V computation, by devising a polynomial commitment scheme [61] tailored to multilinear polynomials.”
Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting (2016, background): “[26] have also provided protocols to commit to polynomials and then evaluate them at a given point in a verifiable way.”
Biscotti: A Blockchain System for Private and Secure Federated Learning (2021, methodology): “We solve this problem by using polynomial commitments [55].”
Poseidon: A New Hash Function for Zero-Knowledge Proof Systems (2021, methodology): “A PLONK proof is a combination of KZG polynomial commitments [40] and their openings, both using the SRS.”
Full Accounting for Verifiable Outsourcing (2017, methodology): “In work done concurrently with and independently of Giraffe, vSQL [88] has demonstrated how to support non-deterministic ACs, by composing GKR-derived protocols with polynomial commitment schemes [24, 41, 53, 65].”
Vector Commitments and Their Applications (2013, methodology): “Moreover, our concrete schemes allow for two new solutions of this problem relying, respectively, on RSA and CDH (rather than on Strong DH in bilinear groups as in [17]).”
One (Block) Size Fits All: PIR and SPIR with Variable-Length Records via Multi-Block Queries (2013, background): “It is (intentionally) straightforward to extend three of our four new SPIR protocols in Section IV with either Henry et al.’s or Camenisch et al.’s zero-knowledge proofs (or related techniques) to implement pricing and access control, although full details of how to do this is beyond the scope of…”