Homomorphic Encryption

August 9, 2011 10:56 AM

Described as 'cryptography's holy grail', Homomorphic Encryption/Computation is a form of encryption where specific algebraic operations on the plaintext translate into different algebraic operations on the ciphertext, allowing the plaintext's owner to 'outsource' computations to untrusted machines.

There have been efficient 'partially' homomorphic cryptosystems that preserve either addition or multiplication, but not both, ever since RSA was discovered, the most well know being Diffie–Hellman key exchange. A 'fully' homomorphic cryptosystems permitting both ring operations was first devised in 2009 using lattice-based cryptography, but remained inefficient. Recent progress has centered upon finding good compromises of the two fully homomorphic systems that enable reasonable computations.

Applications include voting systems (pdf), collision-resistant hash functions, private information retrieval, watermarking, in-house security, DARPA funding, and obviously improving computational scalability through outsourcing computations on sensitive business data, conceivably already in limited use for algorithm trading. There might also be applications of public key homomorphic encryption to providing targeted advertisements without revealing personal information.

posted by jeffburdges (17 comments total)

"pure" and un-padded RSA is homomorphic with respect to multiplication.

It's pretty clear (from the first link) what it means for rot13 to be homomorphic wrt concat. But I don't get what homomorphicity wrt multiplication would mean. I run "ABC" through RSA. I get a bunch of numbers. I multiply those numbers by 5. I decrypt. I now have "ABC" x 5?

(I really like this blog, though.)
posted by DU at 11:08 AM on August 9, 2011

Related: a Technology Review article from Monday that says Microsoft has a working practical proof-of-concept for a partially homomorphic encryption system (details are thin, but all addition and some multiplication are supported). The referenced (unlinked, ugh) paper at Microsoft Research is only 11 pages and I've not yet dug into it.
posted by introp at 11:09 AM on August 9, 2011 [2 favorites]

Homomorphic with respect to multiplication means that you run 17 through your encryption engine which yields X, run 5 through your encryption engine which yields Y, and there's a method to multiply X and Y which produces a result Z that you, the key-holder, can decrypt and get 85. The process doing the multiplying has no idea what pre-encrypted values that X and Y represent.

(If the usefulness of this being extended isn't obvious, here's one pie-in-the-sky: imagine if you stored your email on Google's servers in a homomorphic encrypted form that supported a bunch of string operations. They could still index and search it for you but would have no idea what the underlying email *says*. Of course, that's no in their best interest, but you get the idea.)
posted by introp at 11:15 AM on August 9, 2011 [7 favorites]

A homomorphism is an operation that basically "preserves" structure. Formally for a ring, a ring homomorphism is a function f such that f(a+b) = f(a) + f(b) and f(a*b) = f(a) * f(b).

Keep in mind that at the algorithmic level, everything is a number. So the idea would be crypt(a) * crypt(b) = crypt(a*b). And it's fairly trivial to see why plain RSA is multiplicatively homomorphic. (See here.)
posted by kmz at 11:17 AM on August 9, 2011 [1 favorite]

You guys are too smart for me. I love it when a crypto thread pops up.

No really I do
posted by thsmchnekllsfascists at 11:25 AM on August 9, 2011

DU, introp's explanation of multiplication is correct. kmz's explanation is slightly misleading, insofar as it implies that the homomorphic multiplication is the same operation as the non-homomorphic operation. This isn't true in general and is certainly not the case with Gentry's system in particular. Instead, I would write something like (HMultiply(crypt(a), crypt(b)) = crypt(a*b).

[Long-time lurker, joined when my blog post turned up on the front page.]
posted by Craig Stuntz at 11:28 AM on August 9, 2011 [7 favorites]

Homomorphic with respect to multiplication means that you run 17 through your encryption engine which yields X, run 5 through your encryption engine which yields Y, and there's a method to multiply X and Y which produces a result Z that you, the key-holder, can decrypt and get 85.

OK. Now if you can do both AND and XOR and therefore compute any function, why can't you do this in the tax forms example:

i = 0
while TOTALLY_ENCRYPTED_VALUE < 0
  TOTALLY_ENCRYPTED_VALUE -= 1
print i

posted by DU at 11:31 AM on August 9, 2011

DU - The string ABC is also a sequence of bits which you can also treat as an integer. It's that number that gets multiplied by two.

If you have a magical ability to multiply by two and I want you to multiply my number by two but I don't want to reveal my number. I cleverly encrypt my number (in binary) using RSA and give it to you. You double it and return the result. I decrypt the result and, magic! I have my number doubled.

(I'm not sure that the multiplication on the encrypted data is exactly the same operation as "multiplication", but the basic idea is there. You do a "homomorphic multiply by two", which has the result of multiplying my data by two).

Since all computer operations, at their core, are simple arithmetic operations, I think you can see how this can get exponentially cooler if you have the ability to do a few more operations. Unfortunately, it also gets exponentially slower.
posted by It's Never Lurgi at 11:34 AM on August 9, 2011

DU, you can't do a conditional branch, because the program can't know the value of TOTALLY_ENCRYPTED_VALUE (because, obviously, it's encrypted). So code like you write isn't possible, because the program wouldn't know which branch to take. Instead, you must be able to represent your algorithms as mathematical operations (or, from an equivalent but slightly different point of view, as digital circuits) where knowing the result doesn't determine program flow.

I have a worked out example in this follow-up post.
posted by Craig Stuntz at 11:43 AM on August 9, 2011 [3 favorites]

Ah yes, sorry, it's been too long since my math camp days. Then again I often fell asleep during the algebra lectures back then too.
posted by kmz at 11:46 AM on August 9, 2011

So, for these purposes, Boolean logic gates don't do computation?
posted by LogicalDash at 1:49 PM on August 9, 2011

"(I really like this blog, though.)"

Holy shit, DU got hacked! Homomorphic Encryption NOW!
posted by Eideteker at 3:55 PM on August 9, 2011

If you can't do a conditional branch, then you can't compute every function. But in that same paragraph, you do say you are being "deliberately imprecise" so maybe that's part of the hand-waving exclusion.
posted by DU at 4:17 PM on August 9, 2011

Applications include... DARPA funding

Indeed, most research projects have this as an application. (The rest can be used for NIH or NSF funding.)
posted by phliar at 4:35 PM on August 9, 2011 [2 favorites]

Ain't nobody said you couldn't have cycles DU, hell even Brainfuck is Turing complete. Yes, you need some method for ending your loop, but that's doable by either asking the plaintext holder whether you're done. And maybe you could even send some termination signal from inside the encrypted computation.

There isn't anyone seeking to port the linux kernel some homomorphic encryption system, instead we'll just see very specialized computations run this way, roughly like quantum computing. An algorithmic trading house might outsource an enormous number of long sequences of matrix multiplications, for example.
posted by jeffburdges at 8:32 PM on August 9, 2011

I read this as "homoerotic encryption" the first time I scanned the page. That would be awesome.
posted by GallonOfAlan at 2:14 AM on August 10, 2011

I read this as "homoerotic encryption"...
And speaking of Alan Turing....
posted by wenestvedt at 5:35 AM on August 10, 2011