# MPC Study Group: BGW Protocol and Beaver Triples

In this week’s Zoom Meetup we discussed the BGW protocol and Beaver triples [1, 2]. You can watch the virtual meetup of the presentation followed by open discussion:

These are my personal study notes, so please refer to the references to verify any information in this post. The content of this post is mostly based on [1].

## Introduction

The BGW (Ben-Or, Goldwasser, Widgerson) protocol has historical importance as one of the first secure multi-party protocols from 1988 [2]. The protocol allows us to securely compute addition-, multiplication-by-constant, and multiplication-gates over a field. The protocol relies on secret sharing, originally for Shamir secret sharing, but the presented techniques can be applied to any linear secret-sharing scheme (LSSS). The idea is to use the additive homomorphism property of the LSSS, such that additions and multiplication-by-constant are non-interactive operations. However, as we will see, multiplication of two secrets still requires interaction.

## Summary

- Semi-honest security model
- Secure multi-party computation of arithmetic circuits over a field.
- Multi-party
- Security inherited from secret-sharing scheme used.
- If using <t, n> Shamir secret sharing, then is secure up to t corruptions. Note that for multiplication it is required that t < n/2.
- If using full-threshold secret sharing scheme, it is secure up to n-1 corruptions.

## Notation

`P_i`

is the party with index`i`

.`[x]`

is a secret-sharing of the plain-text value`x`

.`[x]_i`

is the secret-share of`[x]`

belonging to`P_i`

.`[x_j]_i`

is the secret share of`[x_j]`

belonging to`P_i`

, and`[x_j]`

is the sharing of plain-text value`x_j`

.

## Secret-Sharing Abstraction

The BGW protocol together with Beaver triples allows us to abstract the secret-sharing scheme [1, Sect. 3.4], such that we can use any LSSS with the following properties:

- Additive homomorphism
- Given two shared secrets
`[x], [y]`

, and a publicly known value`z`

, the parties can compute the following without interaction:`[x + y]`

,`[x + z]`

,`[x * z]`

. Beaver triples (see below) are used for multiplication of two secrets.

- Given two shared secrets
- Opening
- Given a shared secret
`[x]`

, the parties can through collaboration reveal the value`x`

, i.e. reconstruct the plain-text value.

- Given a shared secret
- Privacy
- The adversary can not gain any information on the plaintext value
`x`

from its shares of the shared secret`[x]`

.

- The adversary can not gain any information on the plaintext value

And it should be possible to generate the following during the preprocessing phase:

- Beaver triples
- A secret-sharing of random triples
`[a], [b], [c]`

, such that`c = a * b`

. These are generated during the preprocessing phase, there should be one triple per multiplication gate.

- A secret-sharing of random triples
- Random input gadgets
- Random secret-sharings
`[r_ij]`

, for which`P_i`

knows the plaintext value`r_ij`

. There should be one per input. This can be used for faster secret-sharing of inputs. If process`P_i`

has an input`x_j`

, then it is sufficient to broadcast the value`d = x_j - r_ij`

to all other parties, such that they each can locally compute their secret sharing as`[x] = [r_ij] + d`

.

- Random secret-sharings

We defer the discussion around secret-sharing schemes to another time.

## Beaver Triples

Beaver triples are generated during the preprocessing phase. There are multiple ways of generating beaver triples. A naive way of generating the triples would to generate two random secret-sharings and multiplying them:

- Generate random shared secrets
`[a] <- randomsecret()`

,`[b] <- randomsecret()`

, for additive and for Shamir, it is sufficient for each party to`P_i`

to sample a random value as their share`[a]_i <- random()`

and`[b]_i <- random()`

without interaction. - Compute
`[c] = [a] * [b]`

through secure multiplication protocol (there are faster methods using oblivious transfer).

Beaver triples can be used for the multiplication of two shared secrets:

- Input: Beaver triple
`[a], [b], [c]`

, secret-sharings`[x], [y]`

. Output:`[x * y]`

- Compute
`[d] = [x] - [a]`

,`[e] = [y] - [b]`

- Reveal
`d = reveal([d])`

and`e = reveal([e])`

. - All parties
`P_i`

compute`[x * y]_i = d*e + d*[b]_i + e*[a]_i + [c]_i`

.

- Compute

## BGW Protocol

Using the LSSS abstraction and beaver triples the BGW protocol becomes rather simple:

- Preprocessing (offline)
- The parties interact to generate a sufficient amount of beaver triples and input gadgets.

- Generate Inputs
- For each input we generate the secret-shared inputs using the input gadgets (described above).

- Compute Gates
- Each gate in the circuit is evaluated using the abstract interface of the secret sharing (described above).

- Reveal Output
- The output is revealed to all (or some) of the players using the abstract interface of the secret sharing.

## Discussion

We still had some open questions with regards to how to use this in practice. For example, we are unsure on how to generate an arithmetic circuit from an arbitrary program. Some operators like bit-shifting to the left can be achieved by multiplying by a factor of 2. Similarly, there are protocols for division. But it still remains somewhat elusive how to implement general programs.

We also discussed issues with malicious adversaries, and decided to look at a malicious variant of the BGW protocol for next weeks session.

The question of how this, or other MPC protocols, can be used for blockchain came up, which is an interesting question for future sessions.

## Follow-up Suggestions

Malicious BGW, comparison of linear secret sharing schemes, circuit generation from programs, complexity comparison of different protocols, MPC for blockchain.

## References

- [1] Evans, David, Vladimir Kolesnikov, and Mike Rosulek. “A pragmatic introduction to secure multi-party computation.” Foundations and Trends® in Privacy and Security 2, no. 2-3 (2017). URL https://securecomputation.org
- [2] Ben-Or, M., Goldwasser, S., and A. Wigderson. “Completeness Theorems for Non-cryptographic Fault-tolerant Distributed Computation.” In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC’88), pp. 1-10. 1988.