CRYPTO 11 Session 3

Session 3 - Outsourcing and Cloud Computation - looked at models and techniques for secure delegated computation. Imagine you store your e-mails on gmail or your data on amazon (all the talks started with an example like this) and you want to compute some function (how many e-mails have I sent Bob in the last month?)

As efficient fully homomorphic encryption is "not quite ready yet", the first talk presented protocols for efficient set intersection - the innovation here is that the proofs of correct computation by the server are bounded by the size of the result set, so if you take the intersection of two huge sets and it turns out to be empty then the corresponding proof is a constant size and not huge like the sets. The protocol works for union, intersection and other set operations and uses bilinear groups together with a Merkle-tree like construction.

Talks two and four both deal with computation over large datasets where the client shoud only require a witness sublinear in the data size. Usually one imagines the server/cloud computing some task that is verifiable in poly-time (for example factoring integers) where the client uses the cloud for computing power. But here we're dealing with the case of an efficient (perhaps even linear) operation on a huge database stored on the server - think of a simple search in an address book of the entire USA. Both talks looked at verification and presented models in which the client only requires a witness sublinear or even logarithmic in the size of the data set.

Talk three was my favourite: Computing Without Simultaneous Interaction.
Consider an online election: unlike "traditional" MPC, we can't ask all voters to be online at once let alone cooperate to compute the result. Rather, there's a fixed server and each voter only interacts with it once then goes away. Voter two may not appear until voter 1 is already gone. The speaker, Yehuda Lindell, called the resulting model "one-pass". Their protocol for binary symmetric functions (AND, OR, MAJORITY etc. - baiscally anything that takes binary inputs and only depends on the total number of 1-inputs provides) is secure in a sense even when the server and most voters are corrupt: they cannot compute more than what follows from the joint inputs of the honest voters (i.e. the number of honest 1-votes, but not their order or who cast them). However, each voter has to do work that may be proportional to the total number of voters in the system.

As an aside, after Ron Rivest talked about how often to change passwords earlier today, I've just been made aware of some professional advice on how to pick them.