Welcome. Our first speaker today is Matt Chang. He's talking about hacking on multi-party
computation. It's okay to take pictures of the speaker. For this talk, give it up for Matt
Chang. All right. Thank you. Okay. So I'm going to talk a little bit about my experience with
multi-party computation. It's something that I first encountered about six years ago. And
I thought it was a really cool topic and wanted to share it with you guys. So what is multi-party
computation? Well, the idea is that you might have multiple parties that want to have private
inputs to a function, but they want to jointly compute that function without revealing what it
is they're computing. And when I first heard this, I know that sounded like magic. But of course,
it's just math, right?
Yeah.
It's just something that might be just as good as magic. So a little bit of history. One of the
first problems that was posed in the area of multi-party computation is called the millionaire's
problem. And I guess nowadays it would probably be the billionaire's problem because millionaire,
that's no big deal now, right? So the idea is that you have two millionaires. They want to
compare their net worth, but they don't want to reveal what that net worth is. So how can they
determine who is the winner in that without revealing it? And so the answer that was first
developed was to use something called garbled circuits. That's a pretty fancy name, but
basically it takes a Boolean circuit and turns it into some sort of encrypted Boolean circuit.
And we'll see a little bit about how they do that. But first, one of the key concepts,
in order to make this work, is called oblivious transfer. And so the idea here, and this is,
I think, one of the first things I was like, well, this is magic, is that say I have two pieces
of information, and you want to request one of them without telling me which one you requested,
and I want to send it to you, but without revealing the one that you didn't request. And so
that's what oblivious transfer does. It allows you to request a piece of information and only get
back what you requested without telling me which one you requested. And this is just like in more
formal language what that is. Okay, so what is the whole garbled circuit protocol? So first,
you have to take your function and describe it as a Boolean circuit. So in the case of the millionaires,
problem, you want to create the greater than comparator operator in terms of the Boolean
circuit. And then, of course, this is a cryptography, so our two players in this protocol are Alice
and Bob. And so Alice garbles or encrypts the circuit, and she sends this garbled circuit
to Bob along with her encrypted inputs. Bob receives the encrypted inputs and does oblivious
transfer to get his encrypted outputs. Or, sorry, you get the encrypted inputs through
oblivious transfer. Bob then evaluates the circuit, and then he needs to communicate back
with Alice to determine what the output of the function is. And this can either be done by just
having Alice find out what the answer is, or they could share the answer. But
this allows evaluation of essentially arbitrary Boolean circuits, but it is relatively so. It
requires a lot of communication. So a different mechanism for doing this kind of multi-party
computation is what's known as homomorphic encryption. And this is something that was
observed early on with one of the first public-key cryptosystems already. And this is a
RSA. And it was observed that RSA exhibits a multiplicatively homomorphic property. Also,
another encryption scheme which isn't quite as widely used, but was defined about the
same time, was Algomol. So they both have this multiplicative property. And just to give a brief
overview of what RSA is, RSA is a multi-party encryption scheme. And RSA is a multi-party
encryption system. I'm not sure if you've heard of this. Briefly, an RSA public key
is a pair of numbers, N and E. And, without getting into details about E and everything,
N is a product of two large primes, P and Q. And to encrypt a message, we simply raise,
We view the message as a number from 0 to N and raise M to the E power.
And it was observed that if you take the ciphertext of two of the two ciphertexts and you multiply them together,
just because of the way that multiplying two numbers with raise the same power works,
that's the same thing as encrypting the product.
So, you have this property.
I could give you two, or you could give me two values that have been encrypted with RSA,
and I can just multiply them together and give that back to you,
and then that's an encryption of the product of the original numbers.
Now, this is, again, with unpadded RSA, sort of a textbook RSA,
but it's an interesting property to observe.
Algamal is a different scheme that isn't as widely used,
and I'm glossing over a bunch of details here,
but the main point is that there's a public key that specifies a prime number,
and I guess there should also be a generator there,
and a public value Y,
and to encrypt...
Each time that somebody encrypts a message,
they generate a random number R,
raise G to the Rth power, mod P,
and multiply the message, M, by Y to the Rth power.
And just like with RSA, this has a multiplicative property.
If you do component-wise multiplication,
in the first component, the exponents add,
but that's just another G to random number.
And in the second component, you have...
The M1 and M2 multiply together, times Y to that same random number
that G is being raised to.
So, it's, again, multiplicatively homomorphic.
But, something that's perhaps a little bit more useful,
and at least something that I actually had used before,
was absolutely homomorphic encryption schemes.
So...
Whoa, that's loud.
The first one is...
Additive Algamal.
So, we could actually modify the Algamal scheme that we saw before
to produce an additively homomorphic scheme.
And then there's also PiA,
which actually works out a little bit better.
But, we'll start off with Additive Algamal.
So, this just requires a slight tweak to the original scheme.
So, instead of multiplying just by the message,
we're going to raise the generator G to the Mth power,
and then, when we multiply component-wise,
the addition will happen in the exponent.
And, though, there is a little bit of a problem with this scheme,
in that, when you try to do the decryption,
you'll do the same process as you do normally,
where what you do to decrypt is raise the first component,
the G, to the X power, that's the private key.
And...
That...
That will give you the Y to the R1 plus R2,
and then you compute its inverse,
do that multiplication,
and you're left with G to the M1 plus M2.
And that is not easy to come up with,
because, in fact, the entire security around this scheme
is that it's hard to determine what the exponent is,
given just the number.
So, that's what's referred to as the discrete log problem.
Um...
But, there's still useful cases for this.
Um...
PiA, on the other hand...
Okay, this is a much longer key generation scheme.
Um...
It uses, uh, in, like, an RSA-style modulus.
Um...
And a bunch of technical details here
that, um...
I'm just having for your sake,
but I don't think that I really need to
talk about all the details.
Um...
A lot of feedback.
Okay, so, um...
But, the upshot of all this...
So, this is the encryption, uh, algorithm.
And then, to decrypt,
it has this nice property that...
Okay, just going back.
You see that, just like with the additive Elgamol,
the message goes in the exponent of this G value.
And so, when you multiply ciphertext together,
you'll have that additive property.
But, um, this essentially allows you
to compute discrete logs, uh, easily
if you have the private key information.
Um...
So...
Uh, so far, I've just talked about
a multiplicatively homomorphic scheme
or an additively homomorphic scheme.
But, um, what would be really nice
is to be able to do both
or have a fully homomorphic scheme.
So, have it so that it, um, can...
the, um, compute addition and multiplication
on the ciphertext.
Um, it turns out that, uh...
So, this is...
This was, I think, first accomplished in 2009
by Craig Gentry.
And what he did was, um...
He used this last-based encryption scheme,
um, that was somewhat homomorphic...
somewhat fully homomorphic.
And what that means is that, um...
you can do addition and multiplication
up to a point, uh,
in particular, you can evaluate
polynomials up to a certain degree.
And it turns out that with his scheme,
um, you could write the decryption circuit
in terms of, uh, this, um...
in terms of polynomials that's small enough
so that you can, um, sort of decrypt
while, uh, homomorphically.
Uh, and then doing one more operation.
So, um...
You can sort of imagine this as
you have, like, two locked boxes,
one inside of the other,
and you're able to unlock the inner box
without having to unlock the outer box.
Um...
So that's, uh, how that works.
Currently, it's still pretty slow.
I know that there have been some improvements,
but, um...
It's generally a pretty slow procedure.
Um...
Now...
This is...
So there was actually a tool that I've used in the past,
although it was pretty tricky to get to work,
but, um...
It's the Tool for Automating Secure Two-Party Computation,
or TASTY for short.
Um...
And...
The language for it was a Python-like language,
um, and what you do is specify
what the client and server operations are,
and it would compile two separate binaries,
a client and server, for you,
um, and it actually supported
both additively homomorphic encryption
and garbled circuits,
so you could actually combine those two operations
into a single protocol.
Um...
So one example of how this might be useful is,
um, say, uh...
This is an example I can think of,
that, uh, in machine learning,
uh, oftentimes, uh,
when you're doing some, like, say, a classification,
um, procedure,
you...
After you've trained your algorithm,
you have some vector
that, um, represents information about your...
what, um, your algorithm is trained,
um, and this may be some sort of proprietary information
that you don't want to share,
um, and correspondingly,
somebody who might want to, um,
run their information against your classifier
doesn't want to actually share the information,
so what you could do is, um,
the client could encrypt their, uh,
the information that would go into the algorithm
and submit it,
and on the server side,
they, uh, keep the, uh, vector in plain text,
and, uh, with an additively homomorphic scheme,
you can compute the inner product of two vectors,
um, where one is encrypted
and the other is just a plain text vector,
because, um,
if you multiply a...
an encrypted number by...
an encrypted value by just a number,
um, then that just works like, uh,
the way that you would think about from grade school
how multiplication works, right,
where you define multiplication as repeated addition,
so you can do the same thing
with an additively homomorphic scheme.
So, um, you could first do that
to come up with a, um,
a value, and then, um,
what you often have to do is compare that to
whether or not, uh, it's greater than or less than
a particular value, so you could then use a garbled circuit
to, uh, compare the, uh, resulting value
with what, um,
the algorithm wants, so, um,
it's...
it was difficult to use, I found.
I think I was only able to get this thing to work
using Gentile,
uh, and a lot of painful work, um,
but, um,
part of the point of this talk was
to show that, um,
there are actually some tools out there
where you can start playing with these kinds of, um,
algorithms and techniques.
Um,
we're going to take a little bit of a detour
from, um,
the hardcore computational aspects
and, um,
talk a little bit about zero knowledge proofs.
So I'm going to, like, speed run
through, um, a blog posting by Matthew Green.
I'm really cribbing this section from his blog post.
Um, he wrote, uh, an awesome blog.
He, uh, I have listed in the references slide,
uh, that explains, uh,
what zero knowledge is all about,
and so the, the main idea behind it is that,
um, I want to convince somebody that I know some information,
uh, but without revealing what that information is,
and we're going to go through a particular example that he wrote.
went through in his blog posting. And so there are three properties of zero knowledge. Completeness,
that means that if I actually know the information that I'm trying to prove, then I can prove
it to you. Soundness means that, in fact, I can only convince you that I know the answer
if I do know the answer to the problem. And the zero knowledge is the part where you're
not able to extract information about the solution from my proof.
So the example Matthew Green gave was a graph recoloring problem. So he picked Google. He
said, like, maybe some customer comes to Google and says, I want you to use all of your computational
power to find the answer to the problem. And so he's like, well, I don't know. I don't
know. I'm gonna try to find the answer to the problem. And so they do, and they find
find the answer. And so they find the three coloring of a graph. And this could be useful
for cell phone providers to make sure that they're not overlapping frequencies at cell
towers. But Google doesn't want to do all this work and then just give it away. And
likewise, their client doesn't want to pay for it unless they are actually sure that
Google did the problem. Right? So you have some graph here, and you have to make sure
that you can find coloring.
colorings with only three colors so that no two colors share an edge. Here's an example
coloring of that graph. This is a small graph, so this is one that would be fairly easy to
just do by hand, but imagine you have a much larger one. Google wants to hide all information,
so it's going to put hats on top of its graph. You imagine that they have this big room with
the graph laid out, and underneath it's colored, but they're going to cover it up with hats,
and what they're going to do to prove that they've solved the problem is say to the customer,
I'll let you pick two hats to reveal what colors they are. And if the customer does
this enough times, they will ultimately be convinced that Google did
actually do the three coloring. So they pick up those two and they see, okay, node seven is
purple and node eight is blue. But one thing that Google doesn't want, so the client's like,
okay, well I might have just gotten lucky that one time. I want you to prove it to me by letting
me do it more times. But if we just left the coloring the same, then they could learn most
of the coloring and maybe even be able to figure out the rest of it on their own.
So what Google does is each time the customer picks up those two hats and puts them back
down, they randomly recolor it, but still making it a valid three coloring. And so
no information about which colors were in the first try will help somebody on the second
try learning more information about the three coloring. At least that's what we hoped for.
And so the...
I hope it's fairly clear that the completeness and soundness portion should be fairly clear
here. The interesting thing is how do we know that this is really not leaking any information
about the three coloring? And so that's where the blog post was really informative for me
was that it illustrates that the way that you have to think about it is how could you
cheat this protocol? And so Matthew Green's solution was time machines.
Now, what does he mean by that? Well, suppose that Google was cheating and just came up
with a random coloring. And any time they got caught, they hop into a DeLorean, go
back in time, and change the coloring. They know which two hats they're going to be picking,
so they're like, all right, we're just going to make sure that those two colors are different.
Now it turns out that this procedure would be indistinguishable from if they had actually
done it correctly. So the point being that if the customer was able to figure out information
about the three coloring from this protocol, then they would have been able to do it from
the cheating protocol with the time machine. But that was garbage. So that's the general
idea of the proof of that. They're not able to extract it when it's actually done correctly.
So this is, again, another tool.
It's developed by the folks at JHU, and Matthew Green in particular, which I haven't had a
chance to play with yet, but I've been meaning to. It's called Charm, and it supports a number
of crypto primitives, including, as it says here, some basic math things, rings and fields,
elliptic curves, and zero-knowledge proofs, all that kind of good stuff. So something
to take a look at.
So why do we go off on this zero-knowledge stuff? Well, there are two security models
for these protocols. There's honest but curious and then the malicious model. And honest but
curious is what you might think. It's just, I'm going to run through the protocol correctly,
and I want to get information about what the other person had put into it, but I'm
not going to try and cheat.
And the malicious one is, I'm going to try and cheat as much as I can, and you have to
try and catch me.
And so that's where the zero-knowledge proofs come in, is that the zero-knowledge proofs
are used to detect cheating and allow somebody to abort if the cheating is detected.
So I'm going to briefly talk about, like, really briefly talk about this protocol that
I helped do some implementation work with six years ago. This is called, it was a secure-text
pattern.
It's a matching algorithm called 5PM. And I'll briefly illustrate. This is the sort
of insecure version of it. The idea behind this protocol is that you set up these what
are called character delay vectors that tell you that if a letter in the pattern that you're
looking for is found, then let's just assume that we found it in our pattern, how many
steps further would we have to go before we reach the end of the pattern? And then we're
going to put a 1 there. And so that's what the vectors over on the left are. And we just
go through the text on the server side, and we add and shift down. And we can use an additively
homomorphic encryption scheme to replace the, replace this insecure version with a version
that operates on encrypted data. And so you can use PyA or, you know, whatever you want.
Additive Algemol, Elliptic Curved Algemol. And that's how the honest but curious version
works. In the malicious model, we use a couple of things. One thing is called threshold encryption,
which allows the two players to jointly come up with an encryption key that they will then
use to encrypt both of their inputs. They actually swap, both go through that same,
you know, text search protocol using some linear algebra, and then they use zero knowledge
proofs to detect if one or the other is cheating and abort in that case. And so I'll quickly
conclude with saying that cryptography generally is kind of about any time that you want, you
wish you had some third, trusted third party who could handle information for you, we're going to
use cryptography to do that instead. And there are some tools out there that you can try to use
some of your own communications. I actually just recently redid the honest but curious
version of that protocol in Python, like during a hackathon at night really quick. But of course,
don't lie on anything that's not been verified. And with that, there are some references, but I'll
be releasing the slides after the talk, so. And I'll tweet about that at Crypto Village. So I
think I'm just out of time. So thank you.
Thank you.