Search
  • Salman Avestimehr

InfoCommit!



In a recent paper posted on arxiv, we have introduced InfoCommit, a protocol for polynomial commitment and verification. Info-Commit has four salient features:

  1. Verifiability. The verifier is able to detect, with high probability, if the prover has responded with evaluations of the same polynomial that he has initially committed to.

  2. Double-efficiency. InfoCommit is doubly-efficient in the sense that in the evaluation phase, the verifier runs in O(\sqrt{d}) and the prover runs in O(d), where d−1 is the degree of the polynomial.

  3. Privacy. InfoCommit provides rigorous privacy guarantees for the prover: upon observing the initial commitment and the response provided by the prover to m evaluation requests, the verifier only learns O(m^2) symbols about the coefficients of the polynomial.

  4. Information-theoretic guarantees without relying on any trusted party. Both the verifiability and the privacy of Info-Commit are information- theoretic, meaning that the verifier and the prover can have unbounded computation power and may arbitrarily deviate from the prescribed protocol. Furthermore, Info-Commit does not rely on any trusted party, not even in the initial commitment phase.


36 views

University of Southern California

© 2019 by Salman Avestimehr