Score:2

Can anybody explain the proof of Rabin and Ben-or of secure multiparty computation?

ua flag

Can anybody explain the proof of Rabin and Ben-or of secure multiparty computation?

The idea is that every player $i$, of $N<+\infty$ players, holds a secret say $s_i$. All of them want to share their information in such a way that a rule function $f(s_1,s_2,\cdots,s_N)=(a_1,a_2,...a_N)$ is shaped and every player at the end of the protocol will know only her own component $a_i$ and no other information.

  • How does the protocol of Rabin and Ben-or is executed step by step? Can anybody explain the procedure?
  • Do the authors use permutations? If not could we provide a different proof of such a protocol with permutations? in other words what are these functions $f$ that take like inputs encrypted messages of the secret sharing among the players and can compute the output $a$ that could be a profile of stocastic action recommendation, where every player $i$ learns $a_i$?

Ok, let me give more details from the protocol with the following definition

$\textbf{Definition:}$ A group of $N$ players holds a verified secret (data) $s$, shared using the polynomial $f(x)$, so that $f(0)=s$, and satisfying the conditions of VSS if:

  • The polynomial $f(x)$ is of degree $t$
  • Each player, $P_i$, holds a share of the secret $b_i=f(a_i)$
  • Every piece $b_i$ was shared by $P_i$, using WSS

In case, a mediator exists, this is easy to show it, but when there is no mediator the problem becomes complex and challenging. From my point of view I understand that the first thing that I want to do is to show that the secret is verifiable. But what happens when the secret that every player holds is private information known to the players before they start exchanging information? Namely, every player has a private secret $s_i$ and if all of them share their secrets with a specific scheme, then they will buld a rule function which will take as inputs the individual signals and give them as outpouts "new" information that they will use it to play an action in the game which may differ with respect to the case where no communication exists. So, in order to generate this function $f$ I need to proove that the individual secrets $s_i$ which are components of the secet data $s=(s_1,s_2,...,s_N)$ follow a verifiable secret sharing scheme and also that the prootocol is endowed with the addition and multiplication of this verifiable secret. Based on the protocol of Rabin and Ben-or how can I prooce this?

Also, could I use the protocol of Dodis et al (2000) instead of Rabin and Ben-or protocol to show verifiable secret sharing scheme for more than two players?

Daniel avatar
ru flag
It would greatly help if you provide a bit of detail regarding the concrete parts of the protocol you don't understand.
Hunger Learn avatar
ua flag
@Daniel I refer to the case of the mulatiparty computations but llet me add some parts in the main text
Score:2
ru flag

To be honest, I'm not 100% familiar with the original presentation in RB89, but they introduced several techniques that have been used in multiple subsequent papers, and today there is a sort of simplified version (in modern terms) of the robust secret-sharing scheme there. For example, a high level description can be found in page 3 here.

In a nutshell, the goal is to take a secret $s\in\mathbb{F}$ and distribute it among $n$ parties $P_1,\ldots,P_n$ so that, at later point in time, the parties can reconstruct this secret to each other, while guaranteeing that even if some $t$ corrupt parties with $t<n/2$ send incorrect values, the honest (i.e. non-corrupted) parties can still obtain the underlying secret. This is achieved as follows:

  • The dealer uses traditional Shamir secret-sharing to obtain shares of the secret $(s_1,\ldots,s_n)$. If $t<n/2$, then these shares provide error detection, meaning that a party getting these shares, where $t$ of them might be modified due to adversarial behavior, can find out whether or not the secret has been tampered with, but, in case there are errors, the given party cannot "fix them" to reconstruct the correct secret. This is insufficient for robust secret-sharing.

  • The dealer samples uniformly random pairs $(\alpha_{ij},\beta_{ij})\in\mathbb{F}^2$ and computes $\tau_{ji} = \alpha_{ij}\cdot s_j + \beta_{ij}$ for every pair $i,j\in[n]$ (here $[n] = \{1,\ldots,n\}$). As we will see, the goal of this extra data is to ensure that a receiving party can not only detect if the shares were tampered with, but actually identify the incorrect ones, hence filtering out the ones that are correct, which leads to the right secret being reconstructed.

  • The dealer sends $\sigma_i = (s_i, \{(\alpha_{ij},\beta_{ij})\}_{j\in[n]}, \{\tau_{ij}\}_{j\in[n]})$ to each party $P_i$. In words: every $P_i$ gets a share $s_i$ plus a pair of keys $(\alpha_{ij},\beta_{ij})$ for each other party. In addition, $P_i$ gets an "authenticated version of $s_i$" using the keys of each other party.

Let's say that a party $P_j$ is supposed to learn the secret. To this end, the parties $P_i$ for $i\in[n]\setminus\{j\}$ send $P_j$ their values $(s_i',\tau_{ij}')$ (if $P_i$ is honest, then $s_i' = s_i$ and $\tau_{ij}' = \tau_{ij}$, but a corrupt party may send incorrect values), and $P_j$ checks, using his/her own key $(\alpha_{ji},\beta_{ji})$, that $\tau_{ij}' = \alpha_{ji}\cdot s_i' + \beta_{ji}$.

As an exercise, one can check that if $s_i'\neq s_i$, then the probability that this equation holds is at most $1/|\mathbb{F}|$ (this makes use of the fact that $P_i$ does not know the key $(\alpha_{ji}, \beta_{ji})$, which is random), so, as long as the field is large enough, $P_j$ will be able to filter out the wrong shares, and hence reconstruct the secret from the remaining correct ones.


Does this somehow help you with the concrete questions you had? Feel free to drop in any comment if you need clarification in certain direction.

Hunger Learn avatar
ua flag
So, in other words the whole work is done by the dealer. He is the one that gives the information to the agents in a scheme that is called authentication scheme and they need to exchange some messages between them so as to obtain all the parts of their individual message and encrypt it with some kind of procees... ?
Daniel avatar
ru flag
In RB89 a Robust Secret Sharing scheme is proposed: There is a dealer with a secret $s$, who distributes it to a set of parties in certain way. Later on, there is a reconstructor who wants to learn this secret, so the parties send some information to this reconstructor. That's what is described in RB89.
Hunger Learn avatar
ua flag
Ok, I understand this now. But, my idea was the following. Suppose that every player hold her own secret, which is some kind of private infromation. All of them, think of a certain way to exchange their private secrets with the rest of the plaeyrs in order to replicate the rule function $f$. So in my point of view, every player can be the deler and the other players can be the receivers of the message with a certain way as it is proposed by RB89. But the role of reconstructor, how is this different of the other parties?
Hunger Learn avatar
ua flag
@Daniel somewhere in the formula where you write, that is $\tau_{ji}=\alpha_{i,j}\cdot s_j+\beta_{i,j}$, there should a term modulo $n$ (mod $n$) right?
Daniel avatar
ru flag
@HungerLearn Not really. There is a modular reduction happening under the hood, but it's kind of implicit from the fact that the elements are taken over the field $\mathbb{F}$. This finite field could be, for instance, integers modulo a prime $p$ (but definitely not modulo $n$, since $n$ is already used to denote the number of shares/parties).
Hunger Learn avatar
ua flag
@Daniel you are right. So this prime p denotes the cardinality of the field?
Daniel avatar
ru flag
@HungerLearn Yes, there other finite fields (extension fields), but in case $\mathbb{F}$ denotes the set of integers modulo a prime $p$, the cardinality of the resulting field would be $p$.
Hunger Learn avatar
ua flag
so it would be ok to write $\tau_{ij}=\alpha_{ij}\cdot s_i+\beta_{ij} mod p$? And a last question.... protocols or Rabin Ben-or and Ben-or et al are protocols where you can construct any rule function that is an addition or a multiplication of the secrets. In other words if you define a field with the operators of addition and multiplication you have a well defined algebraic structure to build any function that you desire. This function could be either deterministic or probabilistic right?
Hunger Learn avatar
ua flag
@KingOdysseus sorry for this mess of comments in your question...it would be better to do a new question that is mine...
Daniel avatar
ru flag
@HungerLearn Yes, you can use the modulus notation. You can define any function (deterministic or probabilistic) that uses additions and multiplications over a field, and use existing MPC protocols (such as BGW) to securely compute these functions.
Hunger Learn avatar
ua flag
Do they implicitly assume that they work with abelian groups?
Daniel avatar
ru flag
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/132553/discussion-between-daniel-and-hunger-learn).
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.