All right, so this is joint work with Sean Kennedy
and Gordon Wilfong at Bell Labs.
This is work, really, on secure computation,
and how to evaluate Boolean circuits securely.
So I'll motivate the problem, what really we're solving,
and then show a heuristic, how to reduce circuit size
in certain scenarios that make sense,
and then explain how some tools in garbled circuits and GMW
support the improvements that we make.
So this is all about SFE, Secure Function Evaluation.
What has it done?
How do you do it?
Today, given a function F that you want to compute,
the most concretely efficient way, in most cases,
is that you generate a Boolean circuit that
computes the function F, and then you
run a garbled circuit or a GMW.
And people really squeeze a lot of efficiency
out of those approaches.
It's really, really hard to get to even
a small, several-percent performance improvement.
There is much less work on the circuit representation
of the function that is being computed,
and this work is kind of in this domain.
So circuit representation, a lot of the time,
is really inefficient.
And there are several major inefficiencies
that I could think about, and some of them
are being addressed, and some of them are not.
So random access is one thing.
If you have an array, and you want
to access a random element in that array,
you have to read the entire array.
So people work a lot on this, and I think ORAM,
its whole direction is really important.
It's really fundamentally changing asymptotics
of secure computation.
And then you have loops.
I don't know what you can do about that.
And today I'll focus on what happens if you
have conditional statements.
So today, if you have a garbled circuit-- OK,
so when do you have conditional statements?
A lot of the time, conditional statements come up,
and this is a very simple example that I'll start with.
But it will be general, and you'll
see how it generalizes to whatever you want.
So let's say there is a function that you want to compute,
F of c, x, y, where c is a choice bit,
or choice several bits, that is given to one party.
And then x is the input of one party,
and y is the input of the other party.
So in other case, you can think of it like a private policy
selection.
I want to evaluate one of 30 functions on our inputs,
but I don't want to tell you which one.
And this comes up in a lot of places.
In particular, in the private database
scenario that we were doing.
OK, so let's say I'm the circuit generator.
I'm thinking of garbled circuits.
If I'm the circuit generator, and I'm giving you
this function to evaluate, this is the circuit
that you're going to see.
So the circuit, basically, is going
to be 30 of these kind of circuits.
And then, going to be a selection sub-circuit.
And what you have to do, you have to evaluate all of them,
and then you have to choose the output that you really
are going to be using.
Well, so actually, what really you're going to see
is you're going to see this, where each
node-- this is a Boolean gate.
So what we see is a topology.
You don't know what gate function you're evaluating,
kind of, in general.
There are some free XOR things, but really you
can think about it this way.
So our idea is that, how about we do this?
We are going to overlay those topologies,
if there is some kind of really cool way of putting all
of these on top of each other in a way
that it all makes sense, that you can program each of them,
each one of the 30.
Then, all of this stuff goes away.
You don't need the selection of anything anymore.
All you have to do is just to evaluate this one thing.
And so if you could overlay it like this,
then a circuit generator can program these gates,
and then you get profit.
OK, so but how?
You still need the selection bit, no?
No.
You still need c as an input.
How do you know which--
If I know c, I program it right away.
I give it to you.
I'll tell--
But c could come as an input, no?
Or is c--
Let's say c is my input, and I'm doing garbled circuit.
I just send you the right programming.
Oh, so [INAUDIBLE].
If c is my input.
If c is not-- no.
Later I'll talk about when c is not fixed.
So it can be an internal variable,
and it makes a big difference between garbled circuit
and GMW, the cost of this.
Well, it will be there very soon.
OK, so how do you embed?
So optimal embedding is NP-hard.
We have a theorem that says that.
Naive evaluation of all of the clauses
works, and that's what is done today,
is basically you just execute all of the clauses.
The universal circuit also works,
but it's too expensive in most reasonable cases
that you can think about.
Because the recent calculations of the size
of a universal circuit is above--
it's 10 n log n, where n is the maximum of the circuit that
has to be there.
Hand-designs don't really work.
People don't know how to design-- how
to program circuits.
Nobody really knows how they look.
It's the machines that generate them.
OK, so what do we do?
We try to exploit, obviously, the common topologies.
And we can do a lot of things.
Because we can insert all sorts of gates
with all sorts of functionalities,
like no-op gates and pass through gates,
we can insert edges as needed, et cetera.
OK, so this is work with the graph theory people,
and so we have to talk in two languages.
So we start with a Boolean circuit,
and then we kind of translate it into the graph domain.
A very simple and natural translation.
So from a Boolean circuit, we get a DAG, simply
by replacing-- whenever you have a gate, you put a node.
Makes sense.
Also, we put some weight, because we
care about concrete things, like free XORs, and stuff like that.
So we're going to put some weight on the nodes.
I'm not going to get into more details, because of the time.
So our goal is that given two clauses, given
two circuits or two DAGs, you want to generate the container
DAG, such that you can implement either of the circuits.
OK, so to talk about this, we have
to define what an embedding is.
And this is a definition of embedding.
An embedding of a DAG D into D prime
is a mapping from nodes to out-arborescences.
We're generalizing nodes into sub-graphs, in the right sense.
So nodes to out-arborescences, and also
embedding maps directed-edges to directed-edges.
And this embedding has to have these properties.
These are natural properties that basically
say that correctness will work out,
if you can implement the right-- the stuff that you get
will have the topology that allows
you to implement the regional circuit, and things like that.
OK, so how do we do that?
Again, this is, as it turns, actually
a very simple heuristic, but took a long time
to kind of narrow it down, and it took a kind
of painful implementation.
But it seems to be nice.
So first thing to look at is that if our graphs are
formulas, so they're these trees,
then a straightforward dynamic programming approach gives us
an optimal solution.
And it's not too expensive.
So all you do is just do dynamic programming
with the right nodes, and then you get.
And so we have a theorem that there
exists an algorithm of this cost,
and you can have an optimal circuit embedding D1 and D2.
But formulas is too weak.
It is not really interesting.
So the general case, this is where a lot of efficiency loss
comes, but we have-- in terms of how close we are to optimal.
But it's not-- it's pretty good in our experiments, at least.
Can you state what is your result?
You said that this is hard to do in general?
Yes.
And it's also hard to do by hand--
Yes.
--case by case.
Yeah, so we have-- the result is a heuristic the outputs contain
circuits that there are small in size,
relative to the sizes of the input circuits.
I have a graph, later.
But the result is two results.
One is a heuristic for graphs, and the second result is secure
computation-related tools that allow you to run--
Heuristic means it's always successful,
but it's not always the optimal or good?
It's not always good.
It's definitely not always optimal.
I don't know what success is.
It's correct.
The correct--
Yeah, yeah, yeah.
It's always correct, but the size is not-- all right.
So given the general circuit-- so here is D1 and D2--
we generate two spanning forest rooted at each output node.
So each of these is actually going to be a tree.
So we have to drop some nodes, so we take a tree-- all right,
we generate a bunch of spanning forests
so that all nodes are covered.
And then each of these make a tree,
so we drop the edges between the trees
and the-- we drop the edges inside, to make them formulas.
So now we've got this graph and this graph, so this is a tree,
this is, everything is a tree.
And then we do all combinations of trees.
And we find whatever is best.
And then, the edges that we dropped, we put them back.
And we hope that everything is still OK.
So everything is not still OK.
We have to fix some things.
The two things, actually, that we need to fix
is that the fan-in can become too large,
because when you re-insert the edges that you dropped,
you can increase that.
So that's important for garbled circuit.
And actually, interestingly, with the new observation,
it's not so much important for GMW.
But we still try to keep it for fan-in two.
And we solve it simply by adding an extra node.
And also, when you reinsert the edges, cycles can happen.
You don't want cycles in your graphic.
Because you can kind of visually see backward-looking edges
that you dropped.
But then, when you reinserted them,
you can have a situation like that.
But also, that situation is solvable by adding a few nodes.
So after all is fixed-- so that's
the description of the heuristic.
By thinking about it, it's hard to say how good it performs,
so the only thing really, reasonably, you
can do is just to run it.
So we generated a bunch of circuits using
some compilers, CBMC compiler.
And we did kind of pairwise-- we have 32 circuits,
and then we do a competition style
and choose the best pairings that we could find.
And this is the empirical results.
This is a number of non-XOR gates in everything.
So this is the input column.
So the input, there were 20,000 non-XOR gates in 32 circuits.
After first round, we got 16 circuits,
because we did it pairwise.
So in these 16 circuits, there were
14,000 gates total non-XOR, in the 16 circuits, and so on.
Until, in the end, we get one circuit
that can implement all of the 32 input circuits,
and its size was about--
Well, but what are these 32?
You did for a specific 32--
For these.
So you did one circuit that-- it's
like an if statement with 32 options
and these are the 32 options?
Yeah, yeah.
So it's a [INAUDIBLE] function at the end of the day, right?
Sure.
OK.
How much time do I have?
Not much.
Eight minutes.
OK, that's not bad.
So that's great, right?
So it was about six times performance improvement.
Now, what can you do now?
What does it give you when you go back
to actually having to securely evaluate this?
OK, well, if you are in the case where
you know which circuits you want to evaluate--
let's say for the database policy or something--
then I get six times performance improvement directly from that.
Because all I do, I'm going to generate
a garbled circuit implementing all of these things.
Well, now I just have to generate a garbled circuit that
is much smaller.
And I know what is my policy, so I just
implement that policy in that topology.
And I give it to you for evaluation.
And you cannot tell which one it has evaluated,
because we know that this container circuit can implement
any of the 30 circuits, or 32 circuits.
So there, there is a direct six times
performance improvement, just from that.
In a garbled circuit, if your clause
is selected by an internal variable, then you have to pay.
Actually, it's kind of expensive to pay.
So how would you do it?
So let's say there is an internal variable that makes
us secret-share the knowledge.
So there's two players, and we secret-share
the knowledge of which clause is actually being evaluated.
Then you can do oblivious transfer.
So the same idea.
All I want to do is I want to transfer
the right garbled tables to program that right circuit.
So now I can do OT on those things, where the OT selection
is happening based on the internal variable that
is secret-shared to us.
So nobody knows what happened, but you
get the right programming.
Well, so that's not great, because to do 1 out of k OT,
you have to pay basically proportional to 2k.
Because under the hood, you need to transfer all the k
encryptions.
OK, so the first improvement, the garbled circuit
improvement, is that we observed that we don't need to do 1 out
of k OT on the garbled gates.
Instead, we are going to do 1 out
of k OT on the programming string,
where the programming string is very short.
Let's see where we are.
Here, so I'm going to do and OT where
I'm going to send you a programming string where
each symbol of the programming string tells you
which gate is going to be evaluated.
And then you use that information
to do OT selection-- to run OT and to select
the right garbled table.
So the difference is that now, we're
going to have to do only 1 out of 5 OTs of garbled tables,
and those are the expensive OTs.
And we're still going to have to do 1 out
of k OT on the programming strings, but those are short.
The computational security parameter of 100
is not going to be a multiplicative factor in the 1
out of k, and so that's a small thing.
It's not interactive?
It's not--
Yeah, yeah, yeah, yeah.
Yeah, you need to interact.
Yeah.
OK.
But the most interesting impact here is in the GMW.
So GMW and garbled circuit, they're kind of competitive,
and people write some papers called, GMW versus Yao, which
one is better?
And things like that.
And this work, actually, I think is-- so this observation
that I'm making, and this, I think
it's also relevant in this kind of discussion-- which is
better, GMW or garbled circuit?
So to recall, at the very high level, what happens in the GMW,
when you evaluate a gate, you need to do 1 out
of 4 oblivious transfer.
I'm not going to tell you of what, because it's a little bit
involved.
And there was a work with Ranjit a couple years ago,
who observed that you can do 1 out
of n, for relatively small n OT, for approximately
the same cost as 1 out of 4 OT.
And the observation that we're making here,
and it's relevant to the application,
is that you can evaluate multi-input GMW gates, roughly
at the same cost as two input gates.
OK, so multi-input is not going to be 100-input,
but like 5-input.
5-input GMW gates will cost you the same as 2-input GMW gates.
And now--
Where did the five come from?
Why five?
Just a small number.
It's the right kind of range.
I don't see, don't understand the trade-off.
If two is the same as five, why isn't five the same as 10?
Yeah, so the cost is exponential on the number of inputs,
but there is a-- so to do with the GMW OT, what you need
to do, you need to do something that's
proportional to the security parameter,
multiplicative security parameter k.
And then, after you've done that,
you have to do something that is exponential on the number
of inputs but not dependent on the security parameter k.
So that exponential in the number of inputs
is growing fast, but it's starting very low, right?
So like 5, 7, I don't know, something like that,
is the right thing.
And so when-- OK.
This is the last slide.
Yeah.
So when we use GMW to do this-- so the thing
that I was talking about for garbled circuit,
you have to do 1 out of 5 gate table OT.
So this corresponds to multi-input GMW gates,
and they can be done pretty much with no overhead,
or a couple of bits per gate.
Overhead that we can say that we can ignore.
And so overall, this improvement that we bring with the circuit
size, due to overlaying circuits, pretty much
translates directly into the total cost,
which I count as communication.
But computation cost is not really differing.
So that improvement directly translates, the same factor
improvement you're going to get in GMW.
OK, so that's all.
Thank you.
[APPLAUSE]