Score:1

What security does the BMR protocol offer against corruption?

it flag

I've been conducting some research into general-purpose MPC protocols and have been unable to pinpoint the exact security offered by the BMR protocol. The reference I've been using for the majority of my research is “A pragmatic introduction to secure multi-party computation" by Evans et al., which states that BMR is able to achieve security "against any $t < n$ number of corruptions among the $n$ participating parties." (p47) However, it does not state which form of adversary this is referring to (i.e., are the adversaries passively or actively corrupt in this case?).

I've also briefly read through the original paper by Beaver et al. (p1), however this seems to contradict the above, stating "a majority of the players must behave honestly".

I feel like I might be missing something - is the BMR protocol secure against passive or active adversaries (or both), and what number of corrupt parties can the protocol tolerate in each case (e.g. $t < n$ or $t < n/2$, etc.)?

Edit: I've now found another paper by Lindell et al. that states that the "[t]he original BMR protocol only guarantees security for malicious adversaries if at most a minority of the parties are corrupt" (p2), which leads me to think that BMR is secure if:

  • $t < n/2$ parties are actively corrupt
  • $t < n $ parties are passively corrupt.

Is this the correct conclusion?

cn flag
BMR is an old protocol and there are a few protocols that are based on BMR but improved its security and performance, if you're interested. For example https://eprint.iacr.org/2017/214 uses BMR garbling but it's full threshold (secure against $n-1$ corruption) with active security. Another one is https://eprint.iacr.org/2017/189 with the same security guarantees.
Score:0
us flag

First of all, the BMR was initially proposed in Rogaway's thesis in [1], whose extended abstract you mention [2]. There, the protocol was proven secure under active adaptive adversaries corrupting and controlling strictly less than half of the parties (e.g. $t < n/2$).

The original proposed BMR protocol has appeared to have flaws in it's security even against a passive adversary. For more information you can check this [3] paper.

Now, considering that the above problem is solved and trying to answer your questions, after a lot of research I couldn't find any clear formal proof that the protocol is passively secure against adversaries controlling $t<n$ corrupted parties. However on p. 95 of Rogaway's thesis the following statement is made :

REQUIREMENT FOR HONEST MAJORITY. The assumption that $t < \tfrac{n}{2}$ was only required because Theorem 4.1.1 requires this; a garbled program reveals no useful information as long as $t<n$. Indeed, the proof we have given remains unmofied to establish this claim, apart from relaxing the bound in the conclusion of Claim 6 to $\ge \tfrac{ν(k)}{n} \ge \tfrac{ν(k)}{k^{10}}$

Also in [3] they prove that after their modifications their protocol is passively secure and they also mention the following :

Theorem 4.1 The circuit construction from BMR, modified with the use of splitter gates as de- scribed in this paper so that the fanout of all gates is at most one, is secure against a passive, honest-but-curious adversary.

From the above I assume that the protocol is secure against passive adversaries corrupting up to $t<n$ parties.

P.S. This paper [4] provided the best explanation of the protocol for me.

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.