We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
from Part I - Secure Multiparty Computation
Published online by Cambridge University Press: 05 August 2015
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.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
