Could someone explain the protocol of Yevgeniy Dodis, Shai Halevi, and Tal Rabin in details?

Question

This is from the paper of Yevgeniy Dodis, Shai Halevi, and Tal Rabin

Could anyone provide some help about understanding how the following protocol is executed? The game is played based on the sequel assumptions: ``the players are (1) computationally bounded and (2) can communicate prior to playing the original game, which the authors believe are quite natural and minimalistic assumptions"

Could anybody simplify the formulation of maths and explain what each of the functions on the protocol below serve our ends? For example, it is not obvious to me why to we pick a permutation $\pi$ and random strings $r_i,s_i$ and then an encryption scheme emerges with many functions taking place in each step. What $Enc_{pk}(a_{\pi(i)};r_{\pi(i)})$ serves for? why do we use $;$ instead of $,$. The protocol is here to serve the purpose that the players can succeed in replication the device of communication or the mediator, but how does this happen after all?

In one question, I would appreciate if someone could explain the protocol step by step, simplifying the functions to $f$ instead of enc $g$ instead of dec, explaining their arguments and what is the information that is shared between the players and the mechanism which at the end gives to every player only one information and no information of the other participant.

Answer 1

This is a two party ($P$, the preparer and $C$ the chooser) protocol with $4$ steps (and three rounds of communication, if the ZKP are non interactive). The two parties have as common information the public key $pk$ and the pairs $(a_i, b_i)$. The preparer knows also the secret key $sk$.

During the first step, the preparer $P$ apply a random permutation of the pairs, and encrypt (according to $pk$) each pair coordinate and send the result to the chooser, and make a ZKP that this result has been honestly computed.

During the second step, the chooser chooses an index $\ell$, and blind the ciphertext $c_\ell$ (which is an encryption of one of the $a$). They send this blind ciphertext $e$, and makes a ZKP it has been honestly generated.

During the third step the preparer computes the decryption $a$ of $e$ and output (it means, it is the result for him). Then he send the chain of $b$ with the randomness in the order of the permutation he previously chosen.

And finally at the last step, the chooser retrieve the plain element of the same index of the $c$ he previously blind (he can, because he knows the index he has chosen), checks it's the good one by reencrypting it (because he also receive the randomness), and then output the corresponding $b$.

At the end of the protocol $P$ knows an $a$, and $C$ a $b$ which are correlated (they correspond to a pair $(a_i, b_i)$), And neither $P$, nor $V$ can force a particular pair to be chosen (if only one is honest, the pair will be chosen uniformly at random).