论文标题
信息范围：信息理论多项式承诺
Info-Commit: Information-Theoretic Polynomial Commitment
论文作者
论文摘要
我们介绍了信息命令，这是一种用于多项式承诺和验证的信息理论协议。在值得信赖的初始化器的帮助下，向用户提供了对私人多项式$ F $的简洁承诺。然后，用户查询服务器以在用户选择的几个输入中获得$ f $的评估。服务器提供评估以及正确性证明，用户可以根据初始承诺进行验证。 Info-Commit具有四个主要功能。首先，如果服务器对最初承诺的相同多项式的评估进行了响应，则用户可以很高的概率检测。其次，Info-Commit为服务器提供了严格的隐私保证：在观察服务器对$ M $评估查询的初始承诺和响应后，用户仅学习$ O（M^2）$符号，内容涉及$ f $的系数。第三，无论双方的计算能力如何，验证性和隐私保证都是无条件的。最后，从$ O（\ sqrt {d}）$ time运行，信息命令是双重效率的，因为在评估阶段，用户在$ O（\ sqrt {d}）$ time中运行，而服务器则以$ o（d）$时间运行，其中$ d-1 $是polynomial $ f $的程度。
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(\sqrt{d})$ time and the server runs in $ O(d)$ time, where $d-1$ is the degree of the polynomial $f$.
