Efficient Protocols for Binary Fields in the 3-Party Honest Majority MPC Setting

1.1. MPC Protocols in Binary Fields

This document describes a multiplication protocol that is specialized for use with binary fields; see Section 2.2.¶

Composing binary operations into a complete MPC system has proven to be more efficient than alternatives using prime fields in a number of applications. Some of the components in this document can be applied to rings or larger prime fields, but the validation process used here has been specialized for use with binary values.¶

2.1. MPC Protocol Prerequisites

MPC parties require channels to each of the other parties that provide confidentiality, integrity and peer authentication. Mutually-authenticated TLS [RFC8446] provides the necessary capabilities, however, this document does not define how to arrange communication between parties; protocols that use these mechanisms need to define how communication between parties is established.¶

The multiplication protocol described depends on shared randomness for efficiency. The protocol depends on having a way for parties to pairwise agree on random values. MPC parties can execute a coin toss protocol using the communication channel, however it is considerably more efficient to use pseudorandom secret sharing [PRSS] when there are a large number of multiplications.¶

This section describes basic operations of secret sharing (Section 2.3), reveal protocol (Section 2.5), and addition (Section 2.6). Multiplication is more involved and is the subject of subsequent sections (Section 3, Section 4).¶

2.2. Fields and Rings

The basic multiplication protocol described in Section 3 operates in any commutative ring, which will be referred to as simply a "ring". A ring is a group that defines addition and multiplication operations that are both associative and commutative. A ring has an additive inverse for every element, which enables subtraction. A ring contains a "zero" element that is an additive identity plus a "one" element that is a multiplicative identity.¶

A simple realization of a ring is formed of integers modulo a chosen integer that is greater than 1.¶

The validation protocol described in this document (see Section 4) uses a modulo 2 ring. This ring is referred to throughout as a binary field as it is also a field and it contains two values: 0 and 1. Addition and multiplication in a binary field correspond to Boolean operations. Addition in a binary field is equivalent to the Boolean exclusive OR (XOR) operation. Multiplication in a binary field is equivalent to the Boolean AND operation.¶

The security properties of the validation protocol depend on the use of a prime field of sufficient size. Fields support the same operations as rings, adding multiplicative inversion of elements, which enables a division operation. A prime field can be realized from integers modulo any prime. The validation protocol integrates the projection of values in a binary field to a larger prime field, rather than requiring a separate conversion step.¶

2.3. Secret Sharing

Each input value (x) is split into three shares (x₁, x₂, x₃), such that x = x₁ + x₂ + x₃. Any method can be used, but the following process is typical:¶

x₁ = random()
x₂ = random()
x₃ = x - x₁ - x₂

Then, each party in the MPC receives a different set of two values. This document adopts the convention that P₁ receives (x₁, x₂), P₂ receives (x₂, x₃), and P₃ receives (x₃, x₁). From this sharing, no single party is able to construct the original value (x), but the values from any two parties include all three shares and can be used to reconstruct the original value.¶

Some protocols might require that the parties construct a sharing of a value which is known to all the parties. In that case, the value of x₁ is set to the known value, with x₂ and x₃ both set to zero.¶

2.4. Identifying Shares and Parties

This document identifies shares and parties by number. Three parties are identified as P₁, P₂, and P₃. The first, or left share, value held by each party is identified with the same subscript. The other share, or right share, held by each is the next highest-numbered share (with x₁ being the next highest after x₃). This is illustrated in Figure 1:¶

Three parties are identified as P₁, P₂, and P₃.¶

The three parties are logically placed in a ring, with higher numbered parties to the right of lower-numbered parties. P₃ is placed to the left of P₁. This means that if a protocol involves sending a value to the left, P₁ sends the value to P₃, P₂ sends to P₁, and P₃ sends to P₂. The sending directions are illustrated in Figure 2.¶

Protocols are often described in terms of the actions of a single party. The party to the left of that party is P_- and the party to the right is P₊. Where necessary, the current party is identified as P₌.¶

The two shares that each party holds are referred to as "left" and "right" shares. The "left" share is identified with a subscript of "-" (e.g., x_-); the numeric identifier for the left share at each party matches the identifier for that party, so the left share of x that P₁ holds is named x₁. The right share is designated with a subscript of "+" (e.g., y_+); the numeric identifier for the right share is one higher than the identifier for the party, so the right share at P₃ is (also) x₁.¶

2.5. Reveal Protocol

The output of a protocol can be revealed by sending all share values to the entity that will receive the final result. This entity can validate the consistency of the values it receives by ensuring that the replicated values it receives are identical. That is, the value of x₁ received from P₁ is the same as the value of x₁ it receives from P₃ and so forth. If the value of shares are inconsistent, the protocol fails. After discarding these duplicated values, the revealed value is the sum of the shares that it receives.¶

A value can be revealed by sending adjacent parties the one share value they do not have. That is, P₁ sends x₁ to P₂ and x₂ to P₃; P₂ sends x₂ to P₃ and x₃ to P_1; P₃ sends x₃ to P₁ and x₁ to P₂. Each party verifies that they receive the same value twice, and aborts if they do not.¶

If the protocol is executed correctly, each party learns the revealed value, which is the sum of the two shares it holds, plus the share that was received.¶

This basic reveal protocol requires that each party send and receive two elements. More efficient protocols are possible, but these are not defined in this document.¶

2.6. Addition

Addition of two values in this setting is trivial and requires no communication between parties. To add x to y, each party adds their shares. That is, to compute z = x + y, each party separately computes the sum of the shares they hold:¶

z₋ = x₋ + y₋
z₊ = x₊ + y₊

This produces shares of the sum without requiring communication.¶

A similar process can be used for multiplication with a value that is known to all parties, negation, and subtraction.¶

4.1. Additive Attack

By "additive attack", we mean that instead of sending the value z₋, a corrupted party could instead send z₋ + a. In the context of boolean circuits, the only possible additive attack is to add 1.¶

The multiplication protocol described does not prevent this. Since the value z₋ is randomly distributed, the party (P_-) that receives this value cannot tell if an additive attack has been applied.¶

While an additive attack does not result in information about the inputs being revealed, it corrupts the results. If a protocol depends on revealing certain values, this sort of corruption could be used to reveal information that might not otherwise be revealed.¶

For example, if the parties were computing a function that erases a value unless it has reached some minimum such as:¶

if total_count > 1000:
    reveal(total_count)
else:
    reveal(0)

If a corrupted helper wanted to reveal a total_count that was less than 1000, it could add 1 to the final multiplication used to compute the condition total_count > 1000. The result is that values below the minimum are revealed (and values above the minimum are erased), violating the conditions on the protocol.¶

4.2. Malicious Security

Before any values are revealed, the parties perform a validation protocol. This protocol confirms that all of the multiplications performed were performed correctly. That is, that no additive attack was applied by any party.¶

If this validation protocol fails, the parties abort the protocol and no values are revealed. All parties destroy the shares they hold.¶

4.3. Overview of the Validation Protocol

Each of the parties produces a "Zero Knowledge Proof" (ZKP) that proves to the two other parties (P_- and P₊) that all of the multiplications it performed were done correctly. The two other parties act as "verifiers" and validate this zero knowledge proof.¶

The validation protocol is therefore executed three times, with each party acting as a prover. Each validation can occur concurrently.¶

When operating in a boolean field, if P₌ followed the protocol correctly, this is how they would compute z₋:¶

z₋ = x₋·y₋ ⊕ x₋·y₊ ⊕ x₊·y₋ ⊕ r₋ ⊕ r₊

This can be restated as:¶

x₋·y₋ ⊕ x₋·y₊ ⊕ x₊·y₋ ⊕ r₋ ⊕ r₊ ⊕ z₋ = 0

The left hand side of this expression will equal zero if the protocol was followed correctly, but it will equal one if there was an additive attack.¶

Validation is made more efficient by validating multiple multiplications at the same time.¶

The above statement can be transformed to yield the result (either zero or one) as a value in a large prime field Section 4.6. These values can be summed across all the multiplications in a large batch. The total sum will be the count of additive attacks applied, which will be zero if the prover correctly followed the protocol. There will not be any wrapping around so long as the number of multiplications in the batch is smaller than the prime used to define the field.¶

For this protocol, the parties will use the field of integers mod p, where p is a large prime.¶

4.4. Distributed Zero-Knowledge Proofs

The prover (P₌) needs to prove that for each multiplication in a batch:¶

x₋·y₋ ⊕ x₋·y₊ ⊕ x₊·y₋ ⊕ r₋ ⊕ r₊ ⊕ z₋ = 0

The left verifier (P_-) knows the values of y₋, x₋, r₋, and z₋.¶

The right verifier (P₊) knows the values of x₊, y₊, r₊.¶

This means that the prover (P₌) does not need to send any of these values to the verifiers. Verifiers use information they already have to validate the proof.¶

Since the two verifiers possess all of this information distributed amongst themselves, this approach is referred to as "Distributed Zero Knowledge Proofs".¶

4.5. Distributed Zero Knowledge Proofs

[FLPCP] describes a system of zero-knowledge proofs that rely on linear operations. This is expanded in [BOYLE] to apply to three-party honest-majority MPC, requiring only O(logN) communication in total. These proofs are able to validate the computation of an inner product, or expressions of the form:¶

sum(i=0..n, uᵢ · vᵢ) = t

This depends on the prover (P₌) and left verifier (P_-) both possessing the n-vector u, the prover (P₌) and the right verifier (P₊) possessing the n-vector v, and the verifiers P_- and P₊ jointly holding shares of the target value, t (that is, P_- holds t₋ and P_- holds t₊ such that t₋ + t₊ = t).¶

However, the security of this protocol requires the vector elements u and v to be members of a large field. So the first step of the validation protocol is to take a batch of multiplications, and convert them into a dot product of vectors with elements in a large field.¶

4.6. Transforming into a Large Prime Field

[BINARY] describes how to apply [FLPCP] efficiently for binary fields. When binary values are directly lifted into a large field, the XOR operation can be computed with the expression:¶

f(x, y) = x ⊕ y
        = x + y - 2·x·y
        = x·(1 - 2·y) + y

Using this relation, the expression that must be proven can be converted into a dot-product of two vectors, one of which is known to both P₌ and P_-, the other being known to both P₌ and P₊.¶

Rearranging terms:¶

x₋·y₊ ⊕ (x₋·y₋ ⊕ z₋ ⊕ r₋ ) ⊕ x₊·y₋ ⊕ r₊ = 0

Define:¶

e₋ = x₋·y₋ ⊕ z₋ ⊕ r₋

Then:¶

(x₋·y₊ ⊕ e₋ ) ⊕ (x₊·y₋ ⊕ r₊) = 0

Using: x ⊕ y = x·(1 - 2·y) + y¶

(x₋·y₊·(1 - 2e₋) + e₋) ⊕ (x₊·y₋·(1 - 2r₊) + r₊) = 0

Using: x ⊕ y = x + y - 2·x·y¶

(x₋·y₊·(1 - 2e₋) + e₋)
+ (x₊·y₋·(1 - 2r₊) + r₊)
- 2(x₋·y₊·(1 - 2e₋) + e₋)(x₊·y₋·(1 - 2r₊) + r₊) = 0

Distributing and rearranging terms, plus subtracting 1/2 from both sides, produces:¶

- 2x₋·y₋·(1 - 2e₋)·y₊·x₊·(1 - 2r₊)
+ y₋·x₊·(1 - 2r₊) - 2e₋·y₋·x₊·(1 - 2r₊)
+ x₋·(1 - 2e₋)·y₊ - 2x₋·(1 - 2e₋)·y₊·r₊
+ e₋ - 2e₋·r₊ + r₊ - ½ = - ½

Factoring allows this to be written as an expression with four terms, each with a component taken from the left and a component from the right.¶

[-2x₋·y₋·(1 - 2e₋)] · [y₊·x₊·(1 - 2r₊)]
+ [y₋(1 - 2e₋)] · [x₊·(1 - 2r₊)]
+ [x₋·(1 - 2e₋)] · [y₊(1 - 2r₊)]
+ [-½(1 - 2e₋)] · [(1 - 2r₊)] = -½

Components on the left form a vector that can be named g, and components on the right form a vector, h. The result is the dot product of two four dimensional vectors:¶

g₁·h₁ + g₂·h₂ + g₃·h₃ + g₄·h₄ = -½

Alternatively:¶

sum(i=1..4, gᵢ·hᵢ) = -½

From this point, each party can compute the vectors that they are able to.¶

P₌ and P_- both compute gᵢ as follows:¶

g₁ = -2·x₋·y₋·(1 - 2·e₋ )
g₂ = y₋·(1 - 2·e₋ )
g₃ = x₋·(1 - 2·e₋ )
g₄ = -½(1 - 2·e₋)

And where:¶

e₋ = x₋·y₋ ⊕ z₋ ⊕ r₋

P₌ and P₊ both compute hᵢ as follows:¶

h₁ = y₊·x₊·(1 - 2·r₊)
h₂ = x₊·(1 - 2·r₊)
h₃ = y₊·(1 - 2·r₊)
h₄ = 1 − 2·r₊

These vectors form the basis of later stages of the proof.¶

4.7. Validating a batch of multiplications

Each multiplication therefore produces two vectors, with each vector being length 4. To validate a batch of m multiplications, the prover (P₌), forms two vectors of length 4m.¶

The prover (P₌), and left verifier (P_-) both produce the vector u by concatenating the vectors from all multiplications:¶

u = (g₁⁽¹⁾, g₂⁽¹⁾, g₃⁽¹⁾, g₄⁽¹⁾,
     g₁⁽²⁾, g₂⁽²⁾, g₃⁽²⁾, g₄⁽²⁾,
     …
     g₁⁽ᵐ⁾, g₂⁽ᵐ⁾, g₃⁽ᵐ⁾, g₄⁽ᵐ⁾)

The prover (P₌) and right verifier (P₊) both compute the vector v in the same way:¶

v = (h₁⁽¹⁾, h₂⁽¹⁾, h₃⁽¹⁾, h₄⁽¹⁾,
     h₁⁽²⁾, h₂⁽²⁾, h₃⁽²⁾, h₄⁽²⁾,
     … ,
     h₁⁽ᵐ⁾, h₂⁽ᵐ⁾, h₃⁽ᵐ⁾, h₄⁽ᵐ⁾)

If no additive attacks were applied by the prover, the dot product of these two vectors should be:¶

u·v = -m/2

4.8. Overview of Recursive Proof Compression

Now that we have expressed the work of the prover as a simple dot product of two vectors of large field elements, we can use a recursive approach to prove this expression with O(logN) communication.¶

The process is iterative, where at each stage there is a pair of vectors, u and v, and a target, t, where the goal is to prove that u·v = t. The values of u and v start as described in Section 4.7; with t initially set to a value of -m/2.¶

At each iteration:¶

1. Select a compression factor L.¶

2. Chunk the vectors u and v into s segments of length L.¶

   1. Each chunk of u uniquely defines a polynomial of degree L - 1 which are named pᵢ(x), indexed by i ∊ [0..s).¶

   2. Each chunk of v uniquely defines a polynomial of degree L - 1 which are named qᵢ(x), indexed by i ∊ [0..s).¶

3. The polynomial G(x) is defined as: sum(i=0..s, pᵢ(x) · qᵢ(x))¶

   For x ∊ [0..L-1), this polynomial G(x) computes the inner product of a portion of u and v. So the goal becomes proving that sum(i=0..L-1, G(i)) = t.¶

   In the first iteration, the target value t is known by all parties to be -m/2, so left verifier (P₋) sets their share t₋ to -m/2 and the right verifier P₊ sets their share t₊ to zero. In subsequent iterations the target value will not be known to both verifiers.¶

   1. The prover will compute the value of G(0), G(1), ... , G(2L - 2), the minimal number of points required to uniquely define it.¶

   2. These 2L - 1 points are split into two additive secret-shares G(x)_- and G(x)_+ and sent to the verifiers P₋ and P₊, respectively. These shares form the distributed zero-knowledge proof.¶

   3. The verifiers each sum together the first L - 1 points they were given: P₋ computes sum₋ = sum(i=0..L-1, G(i)_-). P₊ computes sum₊ = sum(i=0..L-1, G(i)_+). where sum₋ + sum₊ = sum(0..L-1, G(i)).¶

   4. Now the verifiers verify the proposition sum(i=0..L-1, G(i)) = t by having P₋ compute b₋ = t₋ - sum₋ and P₊ compute b₊ = t₊ - sum₊. They send each other these values and confirm that b₋ + b₊ = 0. If this test fails, the entire protocol is aborted.¶

4. At this point, the prover could have produced values for G(0..L-1) that pass this test even if they had performed an additive attack. The proof needs to be validated by confirming that G(r) = sum(i=0..s, pᵢ(r) · qᵢ(r)) for a randomly selected challenge point r. As long as the prover cannot control the choice of r, the likelihood that a dishonest prover can cheat without detection is inversely proportional to the field size.¶

   1. If we define two new vectors u′ = { p₀(r), …, pₛ₋₁(r) }, and v′ = { <q₀(r), …, qₛ₋₁(r) }, then we can rewrite the statement that needs to be proven as: u′ · v′ = G(r). This is of the same form as the original statement, but with the new vectors u′ and v′ having length L times shorter than the original vectors.¶

   2. u′ and v′ need not be communicated, since the prover and left verifier (P₋) can both compute each value pᵢ(r) using Lagrange interpolation, just as the prover and right verifier (P₊) can compute each value qᵢ(r).¶

   3. Each of the verifiers can use the 2L - 1 points they received (their share of G(x)) to compute a share of G(r) using Lagrange interpolation. These shares become their share of a new value for t.¶

   4. The Fiat-Shamir heuristic can be used to generate r by hashing the distributed zero knowledge proof. This transforms this protocol from a multi-round interactive protocol into a constant round protocol.¶

5. The vectors u and v are replaced by u′ and v′, the value of t is set to G(r), and the next iteration is started.¶

The recursion ends when the vectors u and v have length less than L. The verifiers validate the soundness of the final iteration of the proof in a simpler, more direct way; see Section 4.10.6.¶

4.9. Detailed Validation Algorithm

4.10. Producing the Zero Knowledge Proof

In order to prove that u·v = t, the prover will compute the value of 2L-1 points on the polynomial G(x), which is defined as:¶

G(x) = sum(i=1..s, pᵢ(x) · qᵢ(x))

The prover computes the values of { G(0), G(1), …, G(2L-2) } by incrementally aggregating the products of { pᵢ(0), pᵢ(1), …, pᵢ(2L-21) } and { qᵢ(L), qᵢ(L+1), …, qᵢ(2L-2) }, for each chunk.¶

These 2L-1 points on the polynomial G(x) constitute the zero-knowledge proof that u·v = t.¶

An equivalent method of proving u·v = t, is to show that sum(i=0..L-1, G(i)) = t.¶

b₋ = t₋ - sum(i=0..L-1, G(i)_-)

b₊ = t₊ - sum(i=0..L-1, G(i)_+)

commitment = SHA256(
  concat(
    SHA256([G(x)]_-),
    SHA256([G(x)]_+)
  )
)
r = (bytes2int(commitment[..16]) % (prime - L)) + L

G(x) = sum(i=0..s, pᵢ(x)·qᵢ(x))

u′ = <p₀(r), p₁(r), …>
v′ = <q₀(r), q₁(r), …>

t₋ = lagrange_interpolate(r, [G₋(0), G₋(1), …, G₋(2L-2)])
t₊ = lagrange_interpolate(r, [G₊(0), G₊(1), …, G₊(2L-2)])

b₋ = t₋ - sum(i=1..L-1, G₋(i))
b₊ = t₊ - sum(i=1..L-1, G₊(i))

G₋(r) + G₊(r) = p₀(r) · q₀(r)

5.1. Recommended Parameters

This document recommends several parameters, which are used in the security analysis. Alternative parameters can be used, provided that they meet the stated requirements.¶

For shared secrets, pseudorandom secret sharing [PRSS] is used. For PRSS parameters, HPKE [RFC9180] with DHKEM(X25519, HKDF-SHA256), HKDF-SHA256, and AES-128-GCM is RECOMMENDED, with the same KDF being used for PRSS and AES-128 as the PRP.¶

For validation, the prime field used is modulo the Mersenne prime 2⁶¹-1 validation. Any sufficiently large prime can be used, but this value provides both good performance on 64-bit hardware and useful security margins for typical batch sizes; see TODO/below for an analysis of the batch size requirements and security properties that can be obtained by using this particular prime.¶

The Fiat-Shamir transform Section 4.10.3 used in the validation proofs can use SHA-256. However, any preimage and collision-resistant hash function can be used provided that it has a enough output entropy to avoid bias in the selected field value.¶