2
$\begingroup$

Is it possible to ever have a commitment scheme that is statistically binding but not perfectly binding?

The sender would be computationally unbounded, hence could always computationally trudge through all potential (message,key) pairs. Statistically binding would mean the probability of finding a pair is very very unlikely, but if the sender is computationally unbounded, it definitely could eventually.

| improve this question | |
$\endgroup$
  • $\begingroup$ In an interactive commitment at least, you can consider a scheme in which the receiver has some internal randomness and with some probability $\epsilon$, depending on that randomness, will accept any opening whatsoever. If the protocol is otherwise perfectly binding you'll end up with statistical but non-perfect binding. $\endgroup$ – Maeher Jan 14 at 17:12
  • $\begingroup$ In a non-interactive commitment scheme said randomness could probably be part of the key instead. $\endgroup$ – Maeher Jan 14 at 17:14
  • $\begingroup$ Thanks, that makes sense. I've tried to look at some examples of interactive commitment schemes, do you know any good papers? All the papers I've seen so far have been on non-interactive commitment schemes. $\endgroup$ – Buals Jan 14 at 18:03
  • $\begingroup$ Isn't this always true? Like you said, they can brute-force it. $\endgroup$ – user253751 Jan 15 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.