5
$\begingroup$

A Computationally Binding commitment scheme is defined as a tuple of protocols $(\mathsf{Keygen}, \mathsf{Com}, \mathsf{Open})$, that along with correctness guarantees that for all PPT algorithms the probability that, given a correctly generated commitment key $k$, it outputs a commitment and two different openings is negligible.

Now, if the receiver sends a message $R$ between the committing phase and the opening phase, called $m$ the message revealed, then it's almost never the case that $m$ and $R$ are independent (with negligible probability the adversary could open to a function of $R$). Can we at least say that $m$ and $R$ are "almost independent" (in this question I proposed a way to have relaxed independence)?

In case the answer is negative, what are computationally binding commitments used for?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Why is it an issue that R and m are not independent? Btw, this has nothing to do with computational binding. In fact computational binding is necessary if you want independence, since you can only get independence if the commitment is perfectly hiding. $\endgroup$
    – Maeher
    Commented Jul 31, 2020 at 7:53
  • 1
    $\begingroup$ I'm unsure of what independence you are refering to in the last sentence, anyway consider for example an auction protocol where $A$ commits to $a$ and then $B$ commits $b$. Whoever is the last one to open its commitment have a small probability to modify the opening value to be greater than the opponent's one. How can you argue security then? $\endgroup$
    – JayTuma
    Commented Jul 31, 2020 at 9:04
  • 1
    $\begingroup$ Another example. In a $ZK$ protocol $\mathcal{V}(x,w)$ begin committing to some $m_1$, then the prover sends a $m_2$ and the verifier replies opening $m_1$ and doing other things. Now in general (but a good example is the protocol of page 36 in eprint.iacr.org/2017/552.pdf) to argue computational soundness you need that the commitment is computationally hiding, but to argue even just computationally zero knowledge I'm not sure if computationally bindingness is enough. If you can prove me wrong with an example i'd be happy $\endgroup$
    – JayTuma
    Commented Jul 31, 2020 at 9:24
  • 1
    $\begingroup$ Not sure I understand the question exactly, but are you interested in commitment schemes that are secure under a notion of composition called concurrent composition, as discussed for example, here. $\endgroup$
    – ckamath
    Commented Aug 5, 2020 at 2:27

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.