Suppose we have bit commitment scheme: $n=p*q$ and $t \in QNR_n$, with Jacobi $(\frac{t}{n})=1$

Commitment(P), random $x\in \mathbb{Z}_n$, $y=x^2t^b$, where $b$ is bit.

Ok, suppose we have $y_1$ and $y_2$ blobs containing same $b$

How P can prove that both blobs contain same bit without revealing it?


Give a zero-knowledge proof that $y_1 \times y_2$ is a Quadratic Residue.

[Extra verbage included because a one line answer feels too brief]

If we have $y_1 = x_1^2 t^{b_1}$ and $y_2 = x_2^2 t^{b_2}$, then $y_1 y_2 = (x_1x_2)^2 t^{b_1 + b_2}$.

If $b_1 = b_2$, this product is either $(x_1x_2)^2$ (if $b_1 = b_2 = 0$), or $(x_1x_2t)^2$ (if $b_1 = b_2 = 1$), in both cases a Quadratic Residue.

If $b_1 \ne b_2$, this product is $(x_1x_2)^2 t$, which is a Quadratic Nonresidue, hence we would not be able to generate a Zero Knowledge Proof that it is.

| improve this answer | |
  • $\begingroup$ poncho: I confess I didn't understand this protocol, as anyone on receiving $y_1=x_1^2.t^b$ and $y_2=x_2^2.t^b$ is able with the given asumptions to determine if bit b is 0 or 1, after calculating the Jacobi Symbol. $\endgroup$ – Robert NACIRI Mar 24 '15 at 20:52
  • $\begingroup$ @RobertNACIRI: actually, that is not true; the Jacobi symbol will be 1 regardless of whether $b$ is 0 or 1. Remember, $t$ is chosen with a Jacobi symbol 1, $x^2$ also has Jacobi symbol 1, and so both $x^2t^0$ and $x^2t^1$ will have Jacobi symbol one. You might be thinking of a prime modulus (where the Jacobi symbol does indicate whether the number is a QR); this is done over a composite modulus, where there are nonQRs with Jacobi symbol 1. $\endgroup$ – poncho Mar 24 '15 at 21:49
  • $\begingroup$ The computational problem for this is the quadratic residuosity problem. Basically, this is the Goldwasser-Micali encryption scheme utilized as commitment scheme. $\endgroup$ – tylo Mar 25 '15 at 14:43
  • $\begingroup$ @tylo: Actually, this is subtly different from Goldwasser-Micali; in GM, the holder of the private key knew the factorization of $n$; here, the committer need not know that -- they can reveal the secret by revealing $x$. And, they can generate a ZKP that $y_1y_2$ is a QR (if $b_1=b_2$) because they know the squareroot (either $x_1x_2$ or $x_1x_2t$) $\endgroup$ – poncho Mar 25 '15 at 15:18
  • 2
    $\begingroup$ @poncho You're right. But that is one of the general ways to construct a commitment scheme from a public key encryption scheme: You just take a public key (in this case $n$ and $t$, and to find a correct $t$ you even need to know the trapdoor), and then you commit by encrypting the message. Unveiling is done by showing your random coins (and if needed the message). $\endgroup$ – tylo Mar 25 '15 at 15:55

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.