0
$\begingroup$

I was going through some lecture notes where it said that if we have a 2-party protocol that requires both the parties to generate random integers during the course of protocol, then if we migrate the protocol and tweak it to make it work in Malicious setting, then we need to ensure that both parties instantiate random numbers which are indeed random.

It said that this can be achieved by using the following protocol:

$P_1$______________________________________________________$P_2$
commitment($s_1$) -------------------------------------------------->>
<<------------------------------------------------------commitment($s_2$)
$s_2'$----------------------------------------------------------------------->>
<<---------------------------------------------------------------------------$s_1'$

Now, both parties can find their random number $r_i$, $i\in \{1,2\}$ as
$r_i = s_i \oplus s_i'$.
I had a doubt that how does a party ensure that the other party will find $r_i$ as $s_i \oplus s_i'$ and not as just $r_i = s_i$?
How is this ensured that both parties will find their $r_i$s in the exact same way as the protocol says?

$\endgroup$
1
$\begingroup$

The way that this is used is that each party proves in zero-knowledge during the protocol that it sent the correct message based on its committed input, the randomness defined by the committed $s_i$ value and the clear $s'_i$ value, and the series of incoming messages. This proof forces the party to not use any other randomness.

However, in order for this to work formally, you can't use plain commitments. Rather, the commitment must be something that we call ``extractable'' by a simulator.

In any case, you should read more about this as the GMW compiler. You can read about it in the 2nd volume of Goldreich's textbook.

$\endgroup$

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.