# Math(s)! Currently: Homomorphic Encryption

Discussion in 'General Chatter' started by Exohedron, Mar 14, 2015.

1. ### ExohedronDoesn't like words

Today I learned that if you don't know about primes but you do know about even and odd, then you can prove that the square root of 5 is irrational. Similarly for all non-square integers up to 17. At 17 you need something more.

• Informative x 1
2. ### ExohedronDoesn't like words

I want to start telling people that there exists a thing that might be called "non-deterministic linear algebra" and then point them at Sheldon Axler.

3. ### ExohedronDoesn't like words

Slightly off of pure mathematics, here is a paper on the longest possible chess game. It's kind of great.

• Informative x 1

5. ### ExohedronDoesn't like words

I'm going to write all of my papers that way.

6. ### ExohedronDoesn't like words

Homomorphic Encryption

Suppose, purely hypothetically, you and a bunch of other people need to jointly make a decision between some number of choices that will affect all of you. Obviously, you should be the one making the decision, but the rest of them don't trust your judgment for some reason. Ludicrous, of course, but bear with me.

Fortunately, you're pretty sure that most of the group would agree with your choice so you suggest taking a vote. But the other guys are untrustworthy and might try to cause trouble, for instance by threatening to punish those who vote the "wrong way".

So we want to hide how people voted. The modern answer to that problem is encryption. Unfortunately, most forms of encryption deliberately mangle structure, so that Enc(1)+Enc(1) is not equal to Enc(2). A lot of the time we kind of want this, because if you send someone a message saying "Account 1 pays X to account 2", you don't want someone to be able to add two of those messages together to get "Account 1 pays 2X to account 2", or "Account 1 pays 1000X to account 2".

But that's not the only way to do things. Sometimes you want Enc(1) + Enc(1) = Enc(2). Like if you want to be able to tally votes without actually seeing what the individual votes are.

How do we do that? Well, let's look at the El-Gamal method as an example. Suppose we only want to know about whether the voters approve a particular proposition.

We start with a big cyclic group G, and a particular element g. And the person running the election picks a number s and computes K = gs, and they tell everyone K but don't tell anyone s.
Now each voter says "do I like this proposition?" And if they do, they pick a random number r and compute
EncK(m, r) = (gr, gmKr)
where m is 1 if they like the proposition and 0 if they don't.
And they submit that to the person running the election.

Now there are two useful properties:
First, if you have EncK(a, r1) = (gr1, gaKr1) and EncK(b, r2) = (gr2, gbKr2), then multiplying them together component-wise gives
(gr1+r2, ga+bKr1+r2) = EncK(a+b,r1+r2)
So you can combine two votes and get the sum, i.e. we have a homomorphism, sort-of. The random numbers r provide a bit of interference. But that's taken care of by property 2.
Second, the person running the election can take a ciphertext (A,B) and compute
Decs(A,B) = B/As
which, if A = gr and B = gmKr, gives
gmKr/grs = gmgsr/grs = gm
which gets rid of the randomness from r. Now if m is constrained to a small enough number, i.e. if there aren't too many voters, then the person running the election can just test to see what value of m gives gm = Decs(A,B)

We call this homomorphic encryption: we have an encryption scheme (Enc, Dec) such that the decryption operation Dec is a homomorphism. Note that Enc isn't really the homomorphism we care about, because of the randomness.

Why the randomness? Well, suppose we didn't have it. Then each submission of EncK(1) would look exactly the same. Then once the votes were tallied, then people know the total votes for the proposition, and can say "well, everyone either submitted a vote encrypted as A or a vote encrypted as B, and there were m votes that were encrypted as A, so those must correspond to votes for the proposition." Which defeats the purpose of encrypting things in the first place.
So instead we have the randomness, which means that even if two votes are both for or both against the proposition, their encryptions look different. This is called semantic security: people can't tell how you voted by comparing your vote to other people's votes; they have to actually be able to decrypt in order to find out.

There are a few directions to go from here. One of them is how to prevent people from cheating, either by the voters submitting fraudulent votes (for instance, if you send EncK(10000000, r), then you violate the "one man, one vote" principle) or by the system changing the votes during transmission, or the person running the election choosing to decrypt individual votes before tallying. There are a number of proposals for dealing with these issues, mostly involving Zero-Knowledge-Proofs, basically all Schnorr protocols or variants thereof.

Another direction is asking, "okay, we can add underneath encryption. Can we multiply as well? Can we do general computation?" And the answer is yes, but in a ridiculous fashion.
Let's slightly change the scenario a bit. Suppose you have a bunch of secret data that you want to do a computation on, but you don't have the compute power. You could dump it all on a server hosted by a book distribution company, in some hypothetical world where a book distribution company has significant compute power for sale, but you don't trust said book distribution company with the data. So instead you want to encrypt the data, send the encryptions to the company, have them do the computations underneath the encryption, and then send the encrypted results back to you, which you can then decrypt.
Other than preventing a book distribution company from harvesting your data, this also has applications to, say, medical studies with privacy issues, where the researchers don't want their subjects' medical information to be given directly to those perfidious statisticians, but they would like to find out what the statistical models say.

Unfortunately, the El-Gamal scheme I showed you doesn't really like encrypted multiplication as much as it likes encrypted addition, and that makes sense because it involves exponentials. In general, trying to make an encryption scheme that allows for both addition and multiplication underneath the encryption is pretty hard.
Instead, you can do some fun stuff with lattice encryption, which gives you homomorphisms, sort-of. Lattice encryption involves including noise terms that might cause the decryption to fail if it's too large. I mean, if you have a message m, then Dec(Enc(m)) will always yield m. The problem is that as you try to do encrypted operations, the amount of noise builds up until it gets to the point where you can't reliably decrypt anymore. We say that we have somewhat homomorphic encryption, since we can only do a small number of operations between decryptions.
So what you do when you think you might be reaching that point is you decrypt what you have, getting an exact answer, and then encrypt again, getting a new encryption with only a small amount of noise.

But wait, you say, you don't want to decrypt in the middle; that lets the book distribution company see what you're doing. That's a good point. So instead we're going to reverse the order of operations.

Imagine encryption like wrapping something in an envelope, and decryption like removing the envelope to get to the message inside. If we have a message in an envelope, we don't want to remove the envelope because then people will see the message.
So what we do is we wrap the enveloped message inside a second envelope, and then remove the inner envelope.

Just, think about that image for a moment. One of the reasons I like cryptography is because it does some absolutely ludicrous things, and this is one of them.

So suppose that, after some computation, the book distribution company has C1, which is encrypted with a public key K1 that has a corresponding secret key s1, and if C1 were decrypted with key s1 it would yield m, but it's got a lot of noise.
Now what we do is, we take a second secret key s2 and public key K2, and we encrypt s1 using K2 to get S, and send that to the book distribution company.
The book distribution company takes C1 and encrypts that using K2 to get C'. Then they homomorphically run the decryption operation on C' using the "key" S to undo the encryption by K1, all of this underneath the encryption by K2, and yields C2, which decrypts to m if you use key s2. And now we've got our message in a nice, shiny new envelope, without ever revealing it to the book distribution company.
Note that the book distribution company never sees s1 or s2, all they see is the encryption of s1, so they can't actually decrypt C1 to get m, they can only homomorphically decrypt an encryption of C1 to get an encryption of m.
I'm omitting a lot of details necessary to ensure that C2 actually has a smaller amount of noise than C1, but whatever.

This process is called, appropriately, bootstrapping. This is some Cantor-style nonsense, encrypting the encryption scheme inside itself in a way that successfully runs.

• Like x 1