Suppose I have 2 bit commitment schemes, C1 and C2 which are computationally hiding.Suppose I commit the same bit using both and send them to an adversary who knows that the same bit was committed. Is the scheme still computationally hiding, or are there counterexamples?


It is certainly safe for any commitment scheme we would want to use. However, I believe that we can make a stronger statement; we can show that if there is such a method, then either C1 or C2 is not computationally hiding.

Suppose we have an oracle $\theta( C_1^x, C_2^y )$ that would take a commitment in C1 to the bit $x$ and a commitment in C2 to the bit $y$, and if those two commitments were to the same bit ($x=y$), it would output that common value; if they were to different bits, then the behavior is unspecified.

Then, suppose we were given a commitment $C_1^b$ in scheme C1 to a bit $b$. When we could do is generate two commitments in C2, namely $C_2^0$ and $C_2^1$, and evaluate both $\theta(C_1^b, C_2^0)$ and $\theta(C_1^b, C_2^1)$. Now, if $b=0$, we know that $\theta(C_1^b, C_2^0)$ must evaluate to zero (by the definition of the oracle); and so if the behavior of $\theta(C_1^b, C_2^1)$ was anything other than evaluating to one with high probability, we would be able to deduce that $b=0$. Similarly, if $b=1$, then we see that $\theta(C_1^b, C_2^0)$ must evaluate to zero with high probability.

Hence, for C1 to be hiding, we must have $\theta(C_1^b, C_2^x) = x$ almost all the time.

This gives us a computationally efficient method to evaluate C2 commitments, that is, C2 is not hiding.

| improve this answer | |

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.