# Bit commitment, two blobs with same bit, without revealing it?

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.

• 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. – Robert NACIRI Mar 24 '15 at 20:52
• @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. – poncho Mar 24 '15 at 21:49
• The computational problem for this is the quadratic residuosity problem. Basically, this is the Goldwasser-Micali encryption scheme utilized as commitment scheme. – tylo Mar 25 '15 at 14:43
• @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$) – poncho Mar 25 '15 at 15:18
• @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). – tylo Mar 25 '15 at 15:55