2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ It would greatly help if you provide a bit of detail regarding the concrete parts of the protocol you don't understand. $\endgroup$
    – Daniel
    Commented Dec 14, 2021 at 17:26
  • $\begingroup$ @Daniel I refer to the case of the mulatiparty computations but llet me add some parts in the main text $\endgroup$ Commented Dec 15, 2021 at 8:52

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ 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... ? $\endgroup$ Commented Dec 18, 2021 at 8:20
  • $\begingroup$ 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. $\endgroup$
    – Daniel
    Commented Dec 19, 2021 at 1:42
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Daniel
    Commented Dec 22, 2021 at 17:50
  • 1
    $\begingroup$ @KingOdysseus sorry for this mess of comments in your question...it would be better to do a new question that is mine... $\endgroup$ Commented Dec 22, 2021 at 18:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – Daniel
    Commented Dec 22, 2021 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.