# Security Requirements

In this section, we briefly discuss the security requirement for polynomial commitment schemes.

A polynomial commitment scheme is said to be secure if it satisfies the following properties:

• Correctness. The correctness property says that if the scheme is executed honestly then the verification algorithms, namely, $$\mathsf{VerifyPoly}$$ and $$\mathsf{VerifyEval}$$, always returns $$1$$. In particular, assume that $$ck \leftarrow \mathsf{Setup}(1^\kappa, t)$$ and $$(c, d) \leftarrow \mathsf{Commit}(ck, f(X))$$. Then, $$\mathsf{VerifyPoly}(ck, f(X), c, d)$$ always returns $$1$$. And, for any $$w_i$$ output by $$\mathsf{CreateWitness}(ck, f(i), i, d)$$, algorithm $$\mathsf{VerifyEval}(ck, c, i, f(i), w_i)$$ always returns $$1$$.

• Polynomial Binding. For a given commitment key $$ck$$ output by $$\mathsf{Setup}(1^\lambda, t)$$, this property says that it is hard to output commitment $$c$$ and two tuples $$(f(X), d)$$ and $$(f'(X), d')$$ such that $$f(X)$$ and $$f'(X)$$ are distinct and have degrees at most $$t$$, and $$c$$ is commitment to both $$f(X)$$ and $$f'(X)$$ with respect to openings $$d$$ and $$d'$$, respectively. More precisely, it is hard to make $$\mathsf{VerifyPoly}(ck, f(X), c, d) = 1$$ and $$\mathsf{VerifyPoly}(ck, f'(X), c, d') = 1$$ if $$f(X) \not= f'(X)$$, $$\deg(f) \leq t$$ and $$\deg(f') \leq t$$.

• Evaluation Binding. The evaluation binding property says that a committed polynomial evaluating on an index $$i$$ cannot produce two different outcomes $$v$$ and $$v'$$. More precisely, an adversary cannot provide an index $$i$$ and $$2$$ tuples $$(v, w_i)$$ and $$(v', w'_i)$$ satisfying $$v \not= v'$$ such that $$\mathsf{VerifyEval}(ck, c, i, v, w_i) = 1$$ and $$\mathsf{VerifyEval}(ck, c, i, v', w'_i) = 1$$.

• Hiding. An adversary $$\mathcal{A}$$ who knows at most $$\deg(f)$$ evaluations of a committed polynomial $$f(X)$$ cannot determine any evaluation that it does not know before.

We remind that knowing $$\deg(f) + 1$$ different evaluations helps to determine polynomial, and hence all other evaluations. Therefore, we use the bound $$\deg(f)$$ here as a maxmimum number of evaluations that the adversary is allowed to know in order not to correctly obtain the evaluations of all other indices.