Score:1

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

cd flag

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

Nav89 avatar
cd flag
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.
Score:1
cn flag

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

Nav89 avatar
cd flag
@levgeni could these scheme generalized for more than two parts? how?\
Ievgeni avatar
cn flag
@Nav89 Why do you think that?
Ievgeni avatar
cn flag
@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.
Nav89 avatar
cd flag
@levgeni Thanks I will consider it!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.