Info-Commit: Information-Theoretic Polynomial Commitment
Saeid Sahraei, A. Salman Avestimehr, Ramy E. Ali · IEEE Transactions on Information Forensics and Security · 2022
We introduceInfo-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-Commithas 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-Commitprovides 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-Commitis doubly-efficient in the sense that in the evaluation phase, the user runs in$O(\sqrt {d})$time and the server runs in$O(d)$time, where$d-1$is the degree of the polynomial$f$.