I can talk pretty loud and I can also encourage
people sitting in the way back to come closer.
There is plenty of space near to the front and
you can still do your email and stuff on your
laptops if you're close to the front. Um So
at least until until they have the mic working.
So so the way secure computation is traditionally introduced is
talking about this millionaire's problem where you have to millionaires
who want to figure out who's richer but don't want
to disclose their net worth to the other party.
Grad students tend to have a hard time relating to
that and ask questions like well what happens if both
parties have zero as their input? Um So that
example I like to use is genetic dating which um
is a more interesting example I think where you've got
two people that meet in a bar or some other
kind of establishment. Um And before engaging in any
archaic courtship rituals, they want to figure out if
they're a good genetic match. So they have a
little program on their android devices or their iphones.
If they don't have the same device, they're already
in big trouble. But let's assume they're at least
compatible enough to have the same mobile platform. Um
And they also have their genome encoded on their device.
So what they want to do is run some
protocol that's going to find out if they're compatible and
it will do something like tell them they could have
healthy offspring or it might give them a warning that
they shouldn't reproduce if they share common recessive diseases.
But they want to do this without disclosing their whole
genome. If they disclose their whole genome. Well
that might leak a lot of other information about themselves,
their propensity to alcoholism, other things about their
their background that they don't want to reveal yet.
They just want to be able to run this protocol
and get the output. If you don't believe me,
this is gonna be common pretty soon. Um
So this is a graph showing the cost of sequencing
the human genome. Uh going from 2001 up to
2010. I don't have the latest numbers here.
And if you look at that first the dark line
and uh my my scribbling tool is broken. So
hopefully you can see without me me scrambling. Um
It was going pretty well with Moore's Law doubling about
every 18 months um until 2007. And then here's
what happened after 2007. So it went crazy like
improving at a much faster rate than Moore's Law.
And now you can buy machines like this one that
has like a little ipod hookup that will sequence the
genome. Um And so to make sure it's clear
sort of what kind of impact that curve has on
real dollars and real figures. So here's a table
showing the cost Going down to 2009. Getting down
to $1,500. The actual cost of sequencing a genome
it's much lower today. But it starts at
57 million. And I've blacked out what year it
was 57 million to get down to 1500 in 2009.
Uh any guesses what year that was sorry,
closed to guests. 2000 2000. Any advances on
2000? Yeah. 2007. Right. So There
are not many things that cost $50 million 2007 that
cost a few $100 today. Um So this is
pretty crazy. You can also see how many authors
typical papers and biology have. Um So there's lots
and lots of people working on this. Um So
this is gonna happen right and there are lots of
things that we might be able to do with genomes
and so far at least medically it's been kind of
disappointing that all the hype about the human genome project
um has not produced a wealth of great new medicines
yet. But there is this hope that it will
lead to personalized medicine where instead of having to try
six drugs until you find out the one that works
for a particular patient, you should be able to
take your genome to the doctor and they can do
some analysis of it some comparison with the data the
pharmaceutical company might have And figure out which drug is
right for you. Or maybe craft one. If
if you're particular profile doesn't match that drug we might
have things like the genetic dating. You can decide
whether that belongs on the good side or the bad
side. Um But all this data could also be
misused. Um And sort of the extreme example of
misuse is this movie that some of you may have
seen. But there are lots of other ways that
could be misused in terms of personal privacy. So
what really matters is whether humans keep control over this
data themselves or have to disclose it to large entities
or governments that might abuse that data in some way.
And the promise of secure computation is we can
still get all the useful things like personalized medicine from
this private data without disclosing it. And the idea
is that we have our two parties that want to
compute some function and the inputs to that function they
want to keep private so they have their their genomes
. Um Could be some other private data. There
are lots of other motivating examples for this. But
what they want to do is compute some function.
Get the output of that function without revealing anything other
than the output to the other party. If they
all trusted some third party to do everything for them
. This would be easy. You just give all
your data to third party. The third party does
the computation and gives you the result and you're trusting
google or the N. S. A. Or
whoever you really trust with all your data. Um
This assumes that both people can agree on a third
party that they trust completely. Um and has lots
of drawbacks if you don't really trust some other party
google might already have all your data anyway. But
assuming they don't here lots of advantages to be able
to doing this without trusting some other parts. Um
so that's the goal of secure computation and it turns
out there are protocols that can do this that have
been known since since the 80s. Um the one
that I'm going to focus on is is called garbled
circuits and the idea is that one party will generate
a circuit so we can turn any computation into the
circuit. Um The other party will evaluate that circuit
and we can do this in a way that doesn't
reveal the inputs and I'll explain briefly how this works
. So this is the protocol that Andrew came up
with and we can think of any normal computation if
we think of circuits, we just have look up
tables right? We have a logic gate, This
is one for should I ask what this is for
to see if people are awake. Okay, good
. This is for and right. So it's just
a look up table normally to implemented and get what
we need to know what the inputs are. Alright
, we need to know what the input started look
up the output and we know what the output is
because that's what the output is, right. Our
goal is to be able to implement an and gate
without knowing what the inputs are and without seeing the
output. So the first step to that would be
well, obviously if we use the semantic values of
zero and 1 to represent inputs, that's not gonna
work. So we've got to use some other values
. So we're going to change those to arbitrary nonsense
. And the party doing the evaluation doesn't need to
know the mapping between the nonsense means zero and the
constant means one. This will just look like arbitrary
strings of bits. Um and we can do the
same thing with the output. Does this solve our
problem, is this enough to be able to execute
the end without revealing the inputs. So what does
the evaluator of such a gate learn? Can you
tell which of the X values represents 1? Yeah
. Right. If you know this is an and
gate and we're assuming that you do that, you
know what function you're computing? Well, three of
the outputs match. Right. Even if we scramble
order, there's always going to be three that represents
zero and one that represents one. So we're going
to know what the output is, that's gonna tell
us when the input was one. Um So this
is not enough but we can't just replace the values
. We've got to also hide the outputs and so
the way to do that is to encrypt them.
So we're gonna encrypt each of these outputs. We
need to encrypt them in a way that the evaluator
can figure out The actual output wire for the one
that it has the inputs for but can't figure out
any others. So the trick to doing that is
we're going to use the input nonsense as the keys
for the encryption. So if we encrypt um If
our inputs are representing zero and 1 we're going to
have one of these lines encrypted using those inputs.
That's the only one that the evaluator will be able
to decrypt to be able to decrypt. You need
both the keys used for encryption. Um and so
the evaluator learns that X0 value but doesn't know what
any of the outputs other outputs are. So it
doesn't learn that there are three that match that because
she can only decrypt one of those. Okay so
we of course also need to scramble the order.
Obviously if we kept everything in the same order that
would reveal it but that's easy. So that's what
we're gonna do. We don't need the other part
of the table. We're gonna have this random permutation
of the four outputs each encrypted with different keys and
the evaluation of the circuit can only evaluate one of
those and it's the one that actually corresponds to the
inputs that you have. So we can do any
gate this way we're gonna evaluate the gate. So
the generator generates the gate picks the nazis, send
it to the evaluator evaluator can decrypt one of those
to decrypt it. The evaluator needs to know these
actual inputs. That's the other problem we've got to
solve. Alice can send the one corresponding her own
input to bob. Right? So she she knows
her own values either zero or one and picks which
one of these to send. Bob. Doesn't know
what it means because they're just arbitrary nazis. But
bob needs to know his input as well. And
Alice can't send bob both B zero and B.
one. What would go wrong if if Alice could
send both inputs to bob. So, if bob
knows both, bob knows one of Alice's values in
both possibilities for representing bob spit. How many of
the lines in the garble table could bob decrypt Yeah
. Two. Alright, that's one. Too many
. Right. If bob could decrypt two lines well
then he can learn if the output for both of
those is zero, then he learns Alice's input.
All right. So, so that's a problem.
So, we need to make sure that bob only
gets one of that inputs corresponding to his own one
of the wire labels corresponding to his own input.
But he can't just ask Alice for which one he
wants because that would reveal his input. Tallis So
the trick is to use something called oblivious transfer.
Um Which I'm not gonna go into how that works
. There are lots of different protocols for doing this
. Um It's a it's a well studied cryptographic primitive
but it has this property that Alice can generate to
nonsense Bob Sends Picks one Bit which one he wants
. They execute a protocol and at the end of
this bob gets one of the values And Alice doesn't
learn which one Bob got and Bob doesn't learn anything
about the other value. Um It should be sort
of surprising to you that you can actually do this
right? This is one of these um magical crypto
things that can do something that you would think shouldn't
be possible but you can um Okay, so now
we can do any function this way because we can
pick our wire labels to propagate through the computation,
we can represent any function we want as gates and
we can execute any function this way there are a
couple of big issues. This is very different from
regular digital circuits. When we implement logic with regular
digital circuits, each operation is very efficient. We're
operating on known data, we're not trying to keep
the values secret and each operation takes a few nanoseconds
to do something like an and gate with garbled circuits
. Each operation requires encryption so it's very expensive to
do each operation. Um The other big differences.
We can't reuse anything right. If we reuse any
of the gates we would have a problem that that
would reveal some information. It would leak if we
got the same output as last time we learned something
about those inputs. So when we designed regular digital
circuits reuse is great, right? We want to
use the same transistors over and over again. When
we designed garbled circuits, we're not allowed to have
any reviews. So this means if we're designing circuits
to work on large problems, they get really huge
really fast. We end up with with billions of
gates. So until recently, at least until about
uh 10 years ago. This was really just an
interesting theoretical trick that Andrew came up with in the
80s that no one thought you could actually build systems
this way because if you have to do, you
know, for encryptions for each bit operation, that
just sounds crazy. But back in 2004, Benny
Pincus group actually developed a system this way built a
tool that could take a program, turn it into
a garbled table and actually execute it. Um And
it worked for examples like the Millionaire's problem where you're
doing a greater than comparison. Um The problem with
this is the size of circuit that you generate is
actually huge. It's it's not to scale. And
when you tried this approach on any problem that was
actually interesting, um you couldn't even finish building the
circuit because it blew up your memory and all your
displaced just trying to store the circuit. Um So
the first thing that we started doing to try to
make this faster was to observe that you don't actually
need to keep the whole circuit in memory, that's
your big bottleneck. Is this whole circuit, there's
no reason you need to keep the whole circuit in
memory. Um So my student came up with a
clever way of pipeline in it, where all you
need to do is create the gates, you need
to know the circuit structure, so you need to
know how you're valuing the gates and how they're connected
. But all the large amount of the circuit that
you can't reuse all these garbled tables that you have
to keep creating, well you don't need to keep
those. So you have a framework that's generating gates
as you generate gates, you send them to the
evaluator and the evaluator doesn't need the full circuit,
it just needs the gate and all the input of
that gate and it will evaluate them as they come
in. So we can pipeline all of this process
and never need to store the whole circuit, never
need to send the whole circuit. We're just sending
gates and evaluating them as they come. As long
as we've sorted the circuit of topological way the inputs
will be ready and we'll get the outputs. So
this basically means you can scale to any size circuit
the time to execute. Still depends on the number
of gates that you have to evaluate but there's um
you've you've solved the memory scaling problem, looking at
what's going on a little more closely were overlapping the
generation and evaluation phases. Alright, So now the
generator is generating the circuits as it transmits it,
they can be evaluated as they're going. The cost
to generate a circuit is for encryptions, you've got
to build that whole garble table. Um there's a
trick you can use to make it so to evaluate
a gate, you only need to decrypt one,
you can tell which one to decrypt without leaking any
information by embedding some some bits in the nonsense.
And then that means the evaluation is about a quarter
as much work as the generation. So evaluators got
all these idle times when it's waiting for the generator
to produce more gates for it to evaluate. So
keep that in mind because what we'll use those at
all times in a useful way soon. So this
has a big impact on performance. We can get
to the point where we're evaluating large circuits with billions
of gates and the time to evaluate a gate is
still many orders of magnitude slower than normal computation but
within the realm of doing sort of interesting large scale
problems. Okay, so in terms of security,
this really only gets us halfway there. So the
standard garbled circuit protocol and most of the work that
focused on building systems has this threat model that is
a really, really ridiculously weak one. And it's
called the semi honest threat model and what it means
is you provide these high privacy and correctness guarantees.
As long as both parties follow the protocol as specified
, right? Um Normally security is all about thinking
about what happens when their adversaries who don't follow the
rules. And these protocols only work when you assume
that both parties follow the rules. So that's a
really bad property for security protocol to have. But
there's a way to tweak it to actually get very
close to what we want with only adding a little
to the cost. So if you think about what
happens, if you don't send the results back,
then at least you get perfect privacy right? If
you have an oblivious transfer that that works correctly and
and we know about good oblivious transfer protocols and you
do a garbled circuit protocol, but the evaluator who
evaluates the circuit never sends anything back to the generator
. Well, that's a really good guarantee that you
have privacy. You're not sending anything back at all
. Um it doesn't give you correctness right, that
the generator could produce the circuit that implement some completely
different function from the one you wanted. Um and
so you don't know if you got the correct result
. And it also is very unfair because the generator
does all this work, but doesn't get any results
back and lots of the scenarios, we want to
use this, we want both parties to get the
results, but if you think about this, it
gives us sort of half of what we need.
It gives us strong privacy without that. So normally
if we get half of what we need by doing
something once, well we should do it twice,
then we'll get all of what we need. This
is a unstated composition role in computer science. Um
So that's what we're gonna do, we're gonna execute
it twice. Um and this is sort of like
the two executions in the picture. Um The difference
is when we do our two executions were gonna have
the executioner and the generator switch roles between them so
they'll each do one in each role. Um I
have not been able to find any actual executioners to
ask them whether this is a good idea for them
but I think they probably wouldn't be too enthusiastic about
the switching roles part. Um But it works well
for us, so here's what we're gonna do.
So we're going to execute the first protocol. Regular
, semi honest garbled circuit protocol Alice is going to
generate. The circuit bob's gonna evaluate it, bob
is going to get the result, then we're gonna
do the same thing in the other direction, bob
is going to generate the circuit Alice is going to
evaluate it. Alice will get the result. So
now they've both got results, if they were both
honest, the results should be the same. If
one sheeted the results would be different. So what
we want to do is compare those results. If
those results are equal then we know that if we
were honest the other party evaluated our circuit correctly,
um The results should be the same and we have
a lot of confidence that that we got the correct
results. Now we have to be real careful how
we do that equality test, right? We can't
allow one party to lie about the result in the
quality test because then they could trick us into thinking
our result is correct and we can't leak any more
information uh by doing the quality test. So we
need to do the quality test in a careful way
um In a way that that has the high security
properties but there are ways to do a quality test
and it's small, right? The quality test doesn't
scale with the size of the circuit and it only
depends on the size of the output. So that's
what we're gonna do. Um This isn't perfect.
Right? It does leak some information and the information
that leaks is the result of the quality test,
you certainly have to share that, right? If
you don't share the result of the quality test then
you haven't got anything. Um And so that's basically
one bit right. If the outputs are equal,
um an attacker could design a circuit. So for
some set of inputs, the outputs are b are
equal and some set of inputs. The outputs are
different and the attacker can learn whether your input is
in the set that makes it equal or the set
that makes it unequal So you're leaking one bit of
information. Um You're getting caught when you cheat,
right? At least in the case where they're different
, but in the case when they're not different,
you're still leaking some information because the attacker when they
weren't different, so that's what you're giving up and
you can think about that in terms of You're giving
a malicious party, the opportunity to partition the input
space into 2 2 groups. Um and those are
so f is the output of the actual function your
computing, G is the one bit that you get
that is the equality test and the other party,
if they're dishonest can learn which set your input is
in of these groups. Um There are ways of
eliminating this problem that start to get get much more
expensive and I won't get into now. Um and
the way to to reason about this. Um just
to mention a little bit that that you can formally
show that the protocol has this property. Um So
the normal malicious model is you've got a protocol that
behaves in the real world, You're looking at the
actual protocol and you want to compare that to an
ideal world model where you've got a protocol Done by
a trusted 3rd party that just sends you the output
, if those things can see if you can simulate
everything that you can do in the real world,
in the ideal world, then you're not leaking anything
. We obviously can't do that here because we know
we're leaking one bit. So the analogous model is
this real world with an extra one bit output of
an arbitrary function, and then we can prove that
the protocol that we have is equivalent to that.
Okay, so the way that we make this fast
is we can actually overlap these steps. So if
you remember when I showed you the pipe lining a
third of the time, I'm sorry, three quarters
of the time, the evaluator is idle approximately because
they have less work to do than the generator.
Well, now we're overlapping the two steps, they're
doing almost the same amount of work, and the
total work they're doing is just one and a quarter
what it was before. So the actual cost of
doing this is pretty low. There's also the quality
tests, which is pretty inexpensive. Um So here's
what that looks like in terms of what happens when
you actually run problems. Um if you've got a
dual core machine, You have very little cost over
the semi honest protocol where you're just doing it in
one direction because you're overlapping all this work. Um
if you can find the single core machine which is
really hard to do today or configure your machine to
only allow one core to be used for this,
then you see the cost is more like, like
the 30% you would expect um from the overlapping.
um So this works well enough that you can do
arbitrarily large circuits. There's no scaling problems because it's
all pipeline um and it's fast enough to do some
fairly interesting problems um and it's much faster than than
the best known solutions that avoid this problem of leaking
one bit And how important it is to Leak one
bit is definitely highly debatable question. One way to
think about that is you're already revealing the output which
is revealing a lot about your inputs. So this
extra bit that might be revealed through the quality test
um is pretty small compared to what you're already revealing
by sharing the outputs for most problems. Okay,
so the rest of the time I want to talk
some about applications and the applications that I've talked about
so far and that that we have results from here
. These are applications that quite naturally map two circuits
and that's why these are chosen and used as the
benchmarks. Things like doing encryption. So doing private
encryption is actually quite useful. You can have one
party know the data, you're encrypting one party,
no, the key. They can produce the encryption
of that data with that key without knowing knowing either
without either party knowing both the data and the key
. But encryption algorithms are designed to be efficient as
circuits. That's one of the factors used in deciding
an encryption algorithm is whether you can implement it as
a circuit well and these other problems like edit distance
also map very well, circuits, what we'd really
like to get to those is being able to take
arbitrary programs, being able to take things people do
in real code, turn it into a circuit and
be able to execute it in a reasonable time as
a secure computation. The problem is, real code
does all sorts of crazy things that seems horrible to
implement. Things like assigning to an array. Right
? So this doesn't seem that crazy if you're not
implementing in a circuit, probably uh you put stuff
like this in your code without thinking about how horrible
it is. But if you think about what you
have to do to do an arbitrary array assignment in
a circuit, well you've got to do something like
this. Right? So remember that its data oblivious
, we can't know anything about the inputs. So
to do that one assignment Well, we've got to
have a marks that looks at each element of the
race. So we're gonna check is the index value
we're assigning to equal to zero If it is,
we replace the value in element zero of the array
with the new value. But we got to do
that for every element of the array. And if
we don't know anything about the index and we need
to do this in a secure computation, we need
to design a circuit to be able to do this
. We're going to need a circuit that's as big
as the array. So if we want to solve
interesting problems are raised are pretty big and for every
array update, if we have to copy the entire
circuit, our program is not going to, our
protocol is not going to finish at least not in
any reasonable amount of time. So we want to
do something better than that as an example of where
we can see obvious ways to do better. So
suppose the update is in a loop like this,
well then we know that we're doing this for each
element in the array so we can build a circuit
that does them all at once. We don't need
them boxes. Alright. We can update each element
of the array the same way and whatever function we
want to update it. We don't need to do
you and copies of the circuit updating each one separately
. So this gives the insight that well, this
is a really obvious easy example for that. Most
things that we see in real code are not that
simple, but maybe we can take advantage of similar
properties and design ways of implementing data structures in circuits
that don't require all this copying but give us something
much more close to what we need in real programs
for fairly arbitrary access. So here's an example of
how we can do that. Um so we can
take advantage of local locality if we know that we
don't know exactly what elements being updated, but we
know which one of a small number of possible elements
could be updated, then we don't need to copy
the whole array and we can think of this like
a stack, so this code doesn't look explicitly like
a stack, but if we knew that we're starting
with the top element, we can turn this into
stack operations and think of it that way and there's
a small number of possible things that could be going
on here. The other thing to keep in mind
is because it's a circuit, we don't have any
control file. Alright. So anything that depends on
a condition like the if we have to embed in
the circuit we sort of have to embed in the
circuit following all paths. So what we want instead
of what would what you think of compiling this to
regular code. We want to turn it into code
that looks like a circuit. So it's going to
be conditional statements, so we can think of getting
the top element of the stack, we're going to
update it conditionally. So if the X is not
equal to zero predicate is true, then we update
the top of the stack, otherwise we do nothing
. And that's what these conditional operations do. And
then we push the stack. If both of these
tests are true. Um and then we update the
top of the stack again. So that's our goal
is to turn what seems like fairly arbitrary accesses in
real programs in the code that can be more localized
and that can be more easily turned into a circuit
. So once we've done that, then how do
we make a circuit that's efficient? Once we know
we're implementing something like a stack. So if we
did a naive conditional push, it would be something
like this. We have the p is the condition
that tells us whether we're pushing or not so that's
true or false. Um X is the new value
and for each element of the stack. Well,
if we push, we've got to move it down
one to make space for it. Um if we
didn't push, we copy it over. So this
still looks like we have the same problem we had
with our array update that we need to copy the
whole circuit for each push operation. Far more expensive
than we want, but we can do better than
that and we can take advantage of the locality by
looking at these operations and groups. So we're batch
in the operations and were knowing that they can only
affect a small part of the data structure. So
uh here's what that might look like with a concrete
push that the naive way we're going to move that
to a way that limits the amount of the stack
we have to look at for each operation. So
what we're gonna do is divide the stacking the levels
. So we have level zero is our top level
and our property Eddie's level is we're gonna have five
blocks and the size of each block doubles at each
level. So at the top level it's just one
element and we're going to have a constraint that we
have at our starting point is that we have at
least two full slots At each level and two empty
slots. That means that we can potentially do two
pushes. We can do to pops we can do
some mix of conditional pushes and pops without needing to
change the level of blood. So our goal is
to be able to for many operations only need to
look at a small part of the stack. So
here's how that's going to work. So if we
have our initial state, suppose we have a conditional
push. Well we have space and level zero for
that new element. Um The T. Values here
keep track of how many elements of that level are
alive. So we're going to push the new element
. Now we have four live elements at the top
level, the rest of it. Well, we
knew at circuit generation time, right? We don't
need to copy those over. We knew since we
started with two spaces left, we're never gonna need
to do anything with the other elements. So these
can all be copied at no cost and we have
space for another one. We can do another conditional
push that's going to fill up the top level.
We didn't have to do anything with other levels but
now we don't have any more space that we have
to do more operations and note that these are conditional
pushes so they might not have filled it up but
we don't know that. So we have to build
into the circuit to check at this point if the
top level is too full, then we shifted down
to the bottom level to have space for the next
operation. So that's going to work like this.
We're going to shift enough over to have space For
at least two empty slots and the bottom to end
up in one of the blocks on the next level
. Alright, so every two conditional operations at the
top level, we need to potentially do a shift
and then after um for conditional operations we might need
to do a shift at the next level so we
can advertise all the costs, We end up with
the cost scaling as the log of the size of
the stack, instead of linear in the size of
the stack that it would be with with the naive
way of doing this. Okay. And so this
this is the way to do it for stacks.
There are other ways to do it for other data
structures cues are quite similar to this. Um If
it's an array we can think of an array as
a mapping. So it's association map where the keys
are in texas but it works for any kind of
associative map. And there we also used the idea
of matching if we can sort the request and in
order then we can eliminate the ones we don't need
by looking for for ones with adjacent keys. Um
and and by batch ng them reduce the overall cost
. Um So here's an example of where this kind
of thing is useful. So our goal is to
get to be able to do secure computations that are
more like arbitrary real programs not limited to the things
that can be done easily in circuits. And if
we have a this is a clustering algorithm, dB
scan which is fairly popular in the machine learning community
. We have two parties that have their own databases
and these are multidimensional, I've drawn them as as
two dimensional points and what they want to do is
cluster them. Each one could cluster their own data
but they'll get better clustering results. If they can
combine their data they'll learn more. So this example
where this might be useful, it could be a
medical example, it could be financial fraud detection.
They're looking for um outlier transactions in some some data
set and by combining their data they'll get much better
results but they want to keep their data private.
So their goal is to combine their data figure out
the clusters each party will learn which cluster each of
its points is in but won't learn anything else about
the other parties points. Um And the way this
algorithm works is basically doing a depth first search finding
points that are in each other building clusters based on
some constraints of the minimum number of points you want
in a cluster in the density needs. Um The
important thing to notice is it's got lots of array
operations um and it's also using a stack, so
if we want to implement as a circuit, we
need to take advantage of these data structures. Um
some of the operations are within if blocks, so
they're going to be conditional pushes, conditional array updates
, things that we need to implement efficiently as circuits
. Um and this changes of matching and taking advantage
of locality means we can do that much more efficiently
. So um the red line is what you would
get with normal data structures um We're getting up to
even, it's fairly small having 480 points as a
secure computation, takes about 10 hours to run,
uh takes less than an hour with the optimized structures
and the difference will increase as we make things things
bigger. Um So our goal here is to get
to the point where you can take arbitrary programs and
make them run reasonably efficiently as private computations as circuits
. So one of the big questions that that I
haven't addressed and I think is really an important question
to think about and secure computation is how do you
actually get these kinds of things deployed? Right.
So we started from the question of you don't trust
the third party with all your data. Are you
really better off if you end up trusting a third
party to design a protocol for you and give you
code that you use give your data to. Um
and so as a way to start thinking about that
we built a toy android application. You can download
it if you want. Um It doesn't do the
genetic dating application because we don't have enough people with
genomes on their mobile phones yet. But it does
something that's sort of useful and you could argue it
is important for privacy that it takes your address book
um and finds out whether the person that you do
the protocol with any people that you know in common
. So it's doing an intersection of the entries in
your contact list um and it will give you an
output that says here's here's the people you know in
common. Um and it does this using a garbled
circuit protocol with all the security properties like I've described
except when you download this application, install it on
android. The first thing it asks you to do
is give this application full permission to your address book
and full permission to the network. So as a
user unless you sort of read our source code and
understand cryptography and build these protocols yourself. Um It's
only buying you something if if you really trust me
or trust trust the students and implement you can read
the reviews, you know um Both of these are
from well ones from the ones from the student who
did it. So whether you buy the reviews or
not, you know there's nothing that will really convince
you that this is keeping your data private. So
I think that's that's a big open question in this
area and something that um I hope some of you
will make progress on. Um So most of the
work that I talked about was done by john huang
who's finished his PhD? No is I guess a
doctor um Sammy did the work on the data structures
that I talked about at the end um and we
also collaborate with Jonathan katz at University of Maryland who
was as a fantastic cryptographer. So you can download
the code and all the papers from our might be
evil dot com site. Um which I'm happy to
say we pay the domain fees for this from a
gift from google. So they're very happy to sponsor
might be evil. Um And I would be very
happy to take questions. Yes. Okay. Thank
you mm hmm. Mhm. In the year two
this is the same year where gpu computing became very
prevalent. Yeah, kind of expected. This is
one four I thought. Sorry. Right thanks if
you Okay. Yeah. So the question is so
why did we see this dramatic decrease in the cost
of genome sequencing? Um And then the other question
about analyzing circuits. Yeah. Um um So so
there so that the main reason for the genome sequencing
. So if it was just computing power increasing we'd
think it would sort of stay along the moore's law
curve. Um And gpu s are part of that
and and could be you know better parallel algorithms are
part of that. Um The main difference is really
improved algorithms for doing genome assembly um that have reduced
the cost. Um So the old way of doing
genome sequencing um that was used for most of the
human genome project was you had to read a long
sequence and then you tried to align it Um and
you so you would read these long strips of about
500 nucleotides, you get all these out of your
machine and and then you would try to you'll find
the least common superstring that would contain all those in
overlapping them because their errors. It's it's um hard
to know if you've got exactly the right jean amount
of it. Um The big advance in algorithm for
this is now you can do this with really short
snippets and this was sort of came out of craig
venter's work where there was a lot of politics towards
the end of the human genome project and they ended
up sort of there was the publicly funded project that
Francis Collins was leading at the NIH and the competitive
commercial project that craig venter was leading and they were
doing what they called shotgun sequencing where you're having very
short snippets but using um more clever algorithms to be
able to still assemble them correctly um There's always potential
for error. You'd never know if it's really the
correct genome um but it greatly reduces the cost and
then they're they're both biochemical improvements as well as algorithmic
and computing improvements that that really contributed to that that
huge difference. Um The other part of the question
about sort of why use circuits? So for the
genome assembly stuff none of that's done with circuit.
So that's all done with regular maybe some using Gpus
but regular processing on general purpose computing, there's no
um attempts that I know to try to do that
part of it privately. Um The assumption if you
want a genome privacy you do you have to get
your genome sequenced by someone you trust to give you
the genome um and then uh not store it themselves
or do something else with it. Um All the
computations that I I talked about are things that you
would do after that stage where you've you've already got
the data um whether it's a genome or something else
then for the garbled circuit protocol we need to use
circuits because that's the way that we can do the
computing without revealing the data. Um the other interesting
point you bring out using Gpu so one of the
ways to make these protocols a lot faster. They're
highly paralyzed able. So you saw one of the
things we did was pipeline the circuit. So we've
got all these gates, we can do the encryptions
, we can do the gates mostly in parallel other
than dependencies. So um you can certainly get much
better results by using a GPO for this and there's
a few groups working on that. We we haven't
done that in my group but there's definitely a lot
of opportunity to get much better performance if you mhm
run this on a Gpu. And the computations you're
doing there there have been several works trying to make
encryption work fast on Gps um So that is very
paralyzed able to do this. Yeah. Thanks three
steps and the circuit to bomb the other Dallas and
then the equality and then the equality test. Um
and uh so so I have to question the threat
model for the first two steps are still under the
semi honest adversary model. Um And then um I
think the next question is I'm thinking is it possible
at all if you're doing some sort of pipe lining
um and then you could make it more secure in
the sense that if bob does something you know,
premature stopping the computation Alice would stop the computation as
well and then you know, no one gets anything
um you know, is it possible at all?
Okay, good. So the question about, you
know, the threat models for the dual execution protocol
, which probably it's too hard for me to go
back to. Um But so that the 22 important
, but so when you do the semi honest part
um nothing goes back in the middle, right?
So you can't if there's something invalid, like if
you get an error evaluating the circuit because none of
the, you know, some gate doesn't encrypt at
all or there's there's some flaw in the data.
You can't complain about that because if you complain about
that and said, oh I found, you know
, there was something broken the protocol or I didn't
get the gate I needed here. That reveals a
lot of information. It says, well what path
the circuit you were evaluating? Um The circuit could
be constructed to make it fail on some inputs,
but not others. So one of the important things
about the protocol, which which I didn't mention it
, it's good that you bring up, even if
the semi honest parts don't finish, you have to
pretend to keep going, right? So you have
to, as a participant in these protocols, you
have to run through the end. Um because if
you stop in the middle and reveal that something's broken
, that potentially leaks information, the quality test has
to be done um with a malicious security level,
so you can't do that if you did the quality
test at the semi honest level then you're not really
getting anything. Um The interesting thing about the quality
test you can also do that as a dual execution
protocol and that's one way to get the malicious level
security. There are more efficient ways to do it
because it's a simple there's custom protocols to do a
quality test and there's there's one we described in the
paper that does equality tests with militia security so it
provides the correct result. Even if the parties don't
uh it doesn't leak information and it will provide the
correct result. Um Even if the parties are attempting
not to follow the rules. Um And you need
to if you end the semi honest and you don't
have an output because it failed. You have to
make up a random output to pretend to continue with
that protocol and you'll get that you don't have equality
, you'll still like that one bit but you won't
leak more by pretending to continue the protocol. Yes
. Okay. Yes. So the question is could
you um make things more efficient by implementing these circuits
with an F. P. G. A.
And the reason that you really wouldn't want to do
that is um this property that we have for garbled
circuits that we don't reuse gates. All right.
So um if you you know for each gate that
you evaluate in the garbled circuit you're doing encryption operations
you can certainly maybe make those faster. If you
had an F P G a designed to do do
encryption. Um But the circuits that we're building we
can only use once so. Um and each each
gate is not a gate that we would implement as
a small amount of logic in an FDA it's doing
encryption. Um So it doesn't really make sense to
try to build these circuits in hardware. Um In
terms of designing the circuits we can learn a lot
by looking at the ways hardware circuits are designed but
the constraints are quite different for this um Especially because
of, you know, not being able to reuse
any gate. Yes, I wonder thinking of his
or run them. My where? Yes. Yeah
. So there's there's a great question. So the
question is about, you know, what's the connection
between private computation and side channel resistance? Um And
one of the great properties of of being able to
do say the A. E. S encryption as
a private computation is the properties that private computation has
. I guarantee you there's there's no side channel leaks
as well because the whole computation doesn't depend on the
data at all. Um There's no way it could
be leaking anything about that data because uh as long
as the properties is a secure computation is supposed to
have are true. However, you implement it is
not leaking anything about the data because nothing about the
computation actually depends on the data. Um So that's
at least one interesting case where there's a strong connection
between doing computations in this way and knowing that you
don't have any side channel leaks. Um and there
are probably others thinking about uh So so the other
two other interesting connections. One is with verifiable computation
and there are works in progress to be able to
prove that you did the computation, you said you
did as part of a secure computation. Um This
protocol doesn't have that property, but there are other
protocols that as you do the computation, you're also
building up a proof that you did the computation you
were supposed to do. Um So that's a maybe
not directly connected with the question you asked, but
another application of security computation to the problem of verifiable
computation of. Now, you're not so worried about
privacy, you're worried about did you do the computation
you were supposed to thank you, David for.
Okay. Thank you.