Info-Commit: Information-Theoretic Polynomial Commitment

arXiv2002.00559MaRDI QIDQ6334004

Author name not available (Why is that?)

Publication date: 3 February 2020

Abstract: We introduce Info-Commit, an information-theoretic protocol for polynomial commitment and verification. With the help of a trusted initializer, a succinct commitment to a private polynomial $f$ is provided to the user. The user then queries the server to obtain evaluations of $f$ at several inputs chosen by the user. The server provides the evaluations along with proofs of correctness which the user can verify against the initial commitment. Info-Commit has four main features. Firstly, the user is able to detect, with high probability, if the server has responded with evaluations of the same polynomial initially committed to. Secondly, Info-Commit provides rigorous privacy guarantees for the server: upon observing the initial commitment and the response provided by the server to $m$ evaluation queries, the user only learns $O(m^2)$ symbols about the coefficients of $f$. Thirdly, the verifiability and the privacy guarantees are unconditional regardless of the computational power of the two parties. Lastly, Info-Commit is doubly-efficient in the sense that in the evaluation phase, the user runs in $O(sqrtd)$ time and the server runs in $O(d)$ time, where $d-1$ is the degree of the polynomial $f$.

This page was built for publication: Info-Commit: Information-Theoretic Polynomial Commitment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6334004)