1
$\begingroup$

$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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Fiono Sep 3 at 18:48
  • $\begingroup$ 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) $\endgroup$ – poncho Sep 3 at 19:01
  • $\begingroup$ The polynomials are defined over Zp, which can be a large prime. Can you tell me your solution, please? $\endgroup$ – Fiono Sep 3 at 19:06
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Fiono Sep 4 at 0:33
  • $\begingroup$ 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 $\endgroup$ – Fiono Sep 19 at 14:19
  • 1
    $\begingroup$ @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. $\endgroup$ – poncho Sep 19 at 14:24
  • $\begingroup$ Makes sense, thanks! $\endgroup$ – Fiono Sep 19 at 14:27
  • $\begingroup$ 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 $\endgroup$ – Fiono Sep 24 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.