0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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
$\endgroup$
5
  • $\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
    Commented Mar 24, 2015 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
    Commented Mar 24, 2015 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
    Commented Mar 25, 2015 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
    Commented Mar 25, 2015 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
    Commented Mar 25, 2015 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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