1
$\begingroup$

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.

The proposed protocol of the authors

$\endgroup$
1
  • $\begingroup$ In case my question is not clear I repeat a statement - I want someone to explain the arguments of the functions explicitly and give the steps in details about how every player at the end of the protocol he will only know her own initial information and her own final recommendation and no further information about the what the other players knew before the execution of the protocol and what recommendations they will take. $\endgroup$
    – Nav89
    Jan 12 at 8:25

1 Answer 1

1
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ @levgeni could these scheme generalized for more than two parts? how?\ $\endgroup$
    – Nav89
    Jan 12 at 18:36
  • $\begingroup$ @Nav89 Why do you think that? $\endgroup$
    – Ievgeni
    Jan 12 at 18:46
  • $\begingroup$ @Nav89 As far as I see, it's clearly a non-trivial enough question to be answered in a comment. Then I suggest you to create a new question on the SE. $\endgroup$
    – Ievgeni
    Jan 13 at 19:03
  • $\begingroup$ @levgeni Thanks I will consider it! $\endgroup$
    – Nav89
    Jan 13 at 19:03

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.