0
$\begingroup$

Let us assume that Alice and Bob are playing a game. Alice first commits her value chosen from $\{0,1\}$ via Pedersen commitment scheme and sends the commitment to Bob. Then Bob sends his value chosen from $\{0,1\}$ to Alice. Finally, Alice opens this commitment to Bob. If Alice's value is equal to Bob's, then Alice wins. Otherwise, Bob wins. We assume that there is no abortion during the procedure.

A malicious Alice may try to open the commitment to the same value as Bob. But the intuition is that Pedersen commitment scheme is computational binding, and thus Alice cannot equivocate the committed value.

However, I am wondering whether we could provide a formal security proof via reduction. I.e., whether we could use malicious Alice to break the binding property of the commitment scheme. If we cannot do this, I am wondering how to formally show that the protocol is secure.

Improve this question
$\endgroup$
6
  • $\begingroup$ Well, the proof shouldn't be "too hard": Start with $c,(m,r),(m',r')$ with $m\neq m'$ and the tuples both being valid openings for $c$. Then try to find the discrete logarithm between the pedersen reference elements $g,h$. $\endgroup$ – SEJPM♦ Jun 6 '20 at 8:52
  • $\begingroup$ @SEJPM Thank you very much. I know that starting from these two openings, we can use them to break the DL assumption. But I am wondering whether we can use Alice as a sub-routine to break the binding property via reduction. It seems that if we regard Alice as a black-box, we cannot know whether she opens the commitment to another value even she opens to the same value as Bob every time, and thus we cannot use Alice to win the computational binding game. $\endgroup$ – Pure Air Jun 6 '20 at 9:04
  • $\begingroup$ Well, if you iterate the protocol enough and Alice always wins, you know (with overwhelming probability) that Alice can break the dlog instance. Right now I don't see a black-box way of breaking Dlog with an "Alice-like" algorithm. However if you allow rewinding you could have Alice generate a commitment, then request $0$, then rewind her to just after issuing the current commitment and requesting $1$. Now you have two different openings which should allow you to break the Dlog instance. $\endgroup$ – SEJPM♦ Jun 6 '20 at 9:25
  • $\begingroup$ @SEJPM Thank you very much for your kind reply. If we don't allow rewinding, we cannot provide a reduction to break the computational binding. Is it enough to just claim that the commitment is computational binding, and thus Alice cannot open the commitment to other values in the security proof? $\endgroup$ – Pure Air Jun 7 '20 at 7:37
  • $\begingroup$ Indeed, you can usually just use the properties of the underlying schemes, in this case that the underlying scheme is binding. $\endgroup$ – SEJPM♦ Jun 7 '20 at 9:20

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.