0
$\begingroup$

If we have two commitment schemes Com1 and Com2, which are possibly defective (in the sense of not satisfying hiding or binding properties), is it possible to construct a commitment scheme which does satisfy those properties?

Specifically, in the following scenarios:

  1. Both Com1 and Com2 satisfy the hiding property, and one of them satisfies the binding property (but you do not know which). In this case, I think that we could construct a commitment scheme by letting Com(m,s) = Com1(m,s)||Com2(m,s), but I am not sure if I am right or not.

  2. Both Com1 and Com2 satisfy the binding property, and one of them satisfies the hiding property (but you do not know which). In this case I do not think we could create a good commitment scheme. Suppose that Com1 is the scheme which does not satisfy the hiding property- we cannot be sure to avoid using Com1 in our construction since we do not know which of the two schemes satisfies the hiding property, and using Com1 in our construction in any way would seem to preclude our construction from satisfying the hiding property as well, unless I am mistaken?

Any help would be greatly appreciated, thank you!

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ I suspect your first construction works, but you should always try to prove it to be sure. This comment is to suggest $\mathsf{Com}(x; r_1||r_2) = \mathsf{Com}_1(\mathsf{Com}_2(x;r_2);r_1)$ as a construction for your second question. If $\mathsf{Com}_1$ is hiding, this seems fine. If $\mathsf{Com}_1$ is not hiding, one could potentially recover $\mathsf{Com}_2(x; r_2)$, but then $\mathsf{Com}_2$ is hiding, and things seem fine. $\endgroup$
    – Mark
    Dec 4, 2020 at 2:40
  • $\begingroup$ Interesting follow-up question: suppose you had two commitment schemes, Com1 which satisfies the hiding property but not necessarily the binding property, and Com2, which satisfies the binding property but not the hiding property - could you combine those two to generate a hiding and binding commitment scheme. The surprising answer to that is "no" (without any other cryptographic assumptions involved); the interesting question: how do you prove that? $\endgroup$
    – poncho
    Jan 8, 2021 at 21:18

2 Answers 2

Reset to default
1
$\begingroup$

It's been over a month, and so if this was a homework question, the due data has already passed.

  1. Both Com1 and Com2 satisfy the binding property, and one of them satisfies the hiding property (but you do not know which). In this case I do not think we could create a good commitment scheme.

Sure you can; you just do:

$$Com(m, r_1, r_2, r_3) = Com1( m \oplus r_3, r_1 ) || Com2( r_3, r_2 )$$

If Com1 does not have the hiding property, someone can learn the value $m \oplus r_3$, however if $r_3$ is selected randomly, they learn nothing about $m$. Similarly, if Com2 does not have the hiding property, they can learn the value of $r_3$; again, they learn nothing about $m$.

The other piece we need to show is that $Com$ also has the binding property; that is straightforward with the assumption that both $Com1$ and $Com2$ do; $Com1( m \oplus r_3, r_1 )$ can be opened only as $m \oplus r_3$, and $Com( r_3, r_2 )$ can be opened only as $r_3$, and the xor of the two will have to be the original committed string $m$.

Improve this answer
$\endgroup$
0
$\begingroup$

Regarding the first question, I do believe you need Com(m,s) = Com1(m,s)||Com2(m,s') instead, since given Com1(m,s), s might not be uniform anymore. Sampling two different random seeds ensure the hiding properties for both.

Improve this answer
$\endgroup$

Your Answer

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

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