# Commitment to a polynomial

$$A(x) \bmod B(x) = C(x)$$ and $$A(x) \bmod D(x) = E(x)$$:

A dealer knows $$A(x)$$ polynomial, which is a secret. He distributes $$C(x)$$ and $$E(x)$$ privately to $$X$$ and $$Y$$, respectively. $$B(x)$$ and $$D(x)$$ are public. $$X$$ and $$Y$$ want to know that $$C(x)$$ and $$E(x)$$ is the result of $$A(x) \bmod B(x)$$ and $$A(x) \bmod D(x)$$, respectively, without getting to know $$A(x)$$.

Is it possible to the dealer to commmit to $$A(x)$$ to prove that this is the polynomial being used in both expressions?

• A dealer owns A(x), which is secret. He distributes C(x) and E(x) privately to X and Y, respectively. B(x) and D(x) are public. X and Y want to know that C(x) and E(x) is the result of A(x) mod B(x) and A(x) mod D(x), respectively, without getting to know A(x). – Fiono Sep 3 at 18:48
• What ring/field are the polynomials defined over? $\mathbb{Z}$? $GF(p)$ for some prime $p$? Can we pick it? (I have a solution if we're allowed to pick a prime $p$ large enough that the DLog problem is hard) – poncho Sep 3 at 19:01
• The polynomials are defined over Zp, which can be a large prime. Can you tell me your solution, please? – Fiono Sep 3 at 19:06

My solution is based on Pedersen commitments; in this scheme, we work in a prime-sized ($$p$$) subfield of some group, perhaps $$\mathbb{Z}_{kp+1}$$, so some prime $$kp+1$$; where both $$p$$ and $$kp+1$$ are large enough to make the discrete log problem intractible. We have two generators of this subgroup $$g$$ and $$h$$, and it is important that no one knows the discrete log of $$h$$ base $$g$$.

A commitment in this scheme to a value $$x_i$$ is the value $$g^{x_i} h^{r_i}$$ for a random value $$r_i$$; if you want to open the commitment, you reveal $$x_i, r_i$$.

One of the things that is interesting about this scheme is that it makes it easy to prove linear relationships; for example, if we have committed to $$n$$ $$x_i$$ values, issuing the commitments $$c_i = g^{x_i} h^{r_i}$$, and want to issue a proof that $$\sum a_i x_i = b$$ for some public constants $$a$$ and $$b$$, all we need to do is to proof that we know the value $$y$$ such that $$\prod (c_i)^{a_i}\cdot g^{-b} = h^y$$ - the left side can be computed by the verifier, and so a simple Schnorr proof suffices (and, assuming that the prover remembers all the $$r_i$$ values he used, he can easily compute $$y$$)

And, I'll assume that the polynomials $$B(x), D(x)$$ have a known maximum degree $$n$$; the polynomials $$A(x), A'(x)$$ have a known maximum degree $$m$$ (which may be larger).

With this tool in our toolbox (and with the above assumption), it becomes easy. To commit to $$A(x)$$, you publish Pedersen commitments to each coefficient individually (and similarly with $$A'(x)$$ - there is no need to use the same $$r_i$$ values unless you decide to make the relationship between $$A(x), A'(x)$$ obvious at the start)

Then, to send $$C(x)$$ to X (along with a proof that $$C(x) = A(x) \bmod B(x)$$), well, we have $$A(x) = B(x)K(x) + C(x)$$ for some polynomial $$K(x)$$; so you would give $$m-n+1$$ Pedersen commitments for the coefficients of $$K$$. Then, the above equation can be viewed as a series of linear equations between $$A(x)$$ and $$K(x)$$ (and the public to X polynomials $$B(x), C(x)$$. So, we just issue $$m+1$$ proofs that each individual coefficient of $$B(x)K(x) + C(x)$$ matches $$A(x)$$.

The last step is to issue a proof that $$A(x) = A'(x)$$; that is easily done, as that is just another linear relationship, and so the same tool can do it.

QED

• Thank you so much :) I'll have to digest it better, but I think this is exactly what i need. Almost 100k of reputation, you are a crypto god! Can't imagine how many people you already helped. – Fiono Sep 4 at 0:33
• Can't you just send individual commitments ci=g^xi of A(X) and K(x) to X? He can commit ci = g^xi of C(x) and B(x) and check that every commitment of A(x) is equal to every commitment of B(x)K(x) + C(x). @poncho – Fiono Sep 19 at 14:19
• @Fiono: X cannot compare commitments. That is, commitments are randomized (they have to be, otherwise they wouldn't be hiding), and so X cannot tell if two different commitments are to the same value. To do so, he needs some help from the entity that issued the commitments. – poncho Sep 19 at 14:24
• Makes sense, thanks! – Fiono Sep 19 at 14:27
• Is it possible to make only one commitment to A(x) and another commitment to K(x) and one proof that A(x) = B(x) * K(x) + C(x) instead of multiple ones? Like commit to a weighted sum of the coefficients of the polynomial. @poncho – Fiono Sep 24 at 22:33