Introduction

In this chapter we cover some techniques for improving the efficiency of the protocols we have seen earlier in this book, but some of the techniques also apply to secure computing protocols in general.

Circuit Randomization

Recall the way we represented secret data when we constructed the first multiparty computation (MPC) protocol for passive security: for a ∈ F, we defined the object [a;fa]t to be the set of shares fa(1),…,fa(n) where fa(0) = a and the degree of fa is at most t. At the same time it was understood that player Pi holds fa(i).

One of the most important properties of this way to represent data is that it is linear; that is, given representations of values a and b, players can compute a representation of a+b by only local computation. This is what we denoted by[a;fa]t + [b;fb]t = [a+b;fa+fb]t which for this particular representation means that each Pi locally computes fa(i) + fb(i).

Of course, this linearity property is not only satisfied by this representation. The representation [[a;fa]]t we defined, based on homomorphic commitments to shares, is also linear in this sense.

A final example can be derived from additively homomorphic encryption: if we represent a ∈ F by Epk(a), where pk is a public key and the corresponding secret key is shared among the players, then the additive homomorphic property exactly ensures that players can add ciphertexts and obtain an encryption of the sum; that is, it holds that Epk(a) + Epk(b) = Epk(a+b), where the addition of ciphertexts is an operation that can be computed efficiently given only the public key.

In the following, for simplicity, we will use the notation [a] to denote any representation that is linear in the sense we just discussed. In doing so, we suppress the randomness that is usually used to form the parts held by the players (such as the polynomial fa in [a;fa]t).

We assume some main properties of a linear representation that we only define informally here. For any of the examples we mentioned, it is easy to see what they concretely mean is each of the cases.

DEFINITION 8.1 A linear representation [·] over a finite field F satisfies the following properties:

1. Any player Pi can collaborate with the other players to create [r], where r ∈ F is chosen by Pi.