There's a new idea brewing in the cryptographers' circles called Homomorphic encryption, and it will soon change the way we do everything from querying databases remotely to adding numbers. In this post I briefly explain what homomorphic encryption is and then list a few ideas others have had on how to use it in cool ways and one or two ideas I've had.
Given that this is a relatively new idea, many of you may be hearing about it for the first time; I'm going to spend a few paragraphs explaining what it is and at the end of this post I'll share a couple of papers and blog posts by awesome people on the subject and its applications.
How Homomorphic Encryption works (at least conceptually)
Instead of jumping straight into public key cryptography and how the idea actually came along, I'm going to start off with a simple problem and in this problem we have the following players:
- Bob (good guy)
- Alice (another good guy or girl I would rather say, Bob doesn't really trust Alice)
How do we solve this? One simple answer would be to tell Alice and Bob to agree on a secret and have them encrypt their communication using block and stream ciphers and super secure PRNGs. Though essentially this would not solve the problem, because Alice would still be able to know the numbers and their product.
The solution here is Homomorphic Encryption (HE) and essentially it allows Bob to have Alice receive the two numbers protected under encryption with Bob's secret--which Alice does not know obviously--and compute their product also encrypted under Bob's secret. Essentially all Alice knows is that she multiplied the numbers but because she has no knowledge of Bob's secret she cannot know what the numbers where and what their product was.
How on earth is this possible? How can Alice accurately perform multiplication on two numbers that are encrypted? Well the answer is a special Encryption function, Lets call it E and defined it like this:
E : K x P --> CWhich basically says that E is a function that accepts an element in a set of values called K which are the "keys", an element in a set of values called P; these are the plaintexts and spits out or "maps them to" some element in a set of values called C which we call the ciphertexts. Just about every Encryption function is defined this way, what makes E special is this property:
E(k,p) x E(k,p') = E(k,p'xp)
What this says is that if you were given two different cipher texts--namely the encryption of p and p'--from E encrypted under the same key "k" and multiply them it would be equal to the encryption of the products of the plaintexts. What this breaks down to is being able to give a untrusted third party a pair of ciphertexts---Alice---have her multiply them and return you the result without every seeing the actual plaintexts! E is called a partially homomorphic encryption function, this is merely because it only supports one operation, namely multiplication; if it was possible to add and multiply using ciphertexts we would call it a fully homomorphic encryption function.
I know you're probably saying this is crazy and these kinds of encryption schemes don't exist, well it turns out they've existed for quite a while now, and you've been using them all along! RSA and other public key encryption schemes exhibit this property because of the nature of their operation, namely that they work by multiplying large numbers together raised to certain powers; its easy to see that if you multiply two different numbers raised to the same power the result would be the same as multiplying the numbers and raising their product to the mentioned power. This is what I mean,
y^k x z^k = (y x z)^kWhy is this so cool? Well what if raising the number to a given power was part of some encryption scheme? And what if that encryption scheme is called RSA?
RSA(k,p,m) x RSA(k,p',m) = p^k x p'^k mod m = (p'xp)^k mod m = RSA(k,p' x p,m)
and viola RSA is partially homomorphic!
What does Homomorphic Encryption mean for the future?
Well essentially we are talking about being able to compute meaningful things without first stripping off encryption layers and this means the following will probably be possible once Homomorphic Encryption is adopted in industry:- Better online privacy. At the moment we use SSL/TLS to protect the semantic value of what we do online, though it still means the services we are using would still need to know what we are doing, Homomorphic Encryption introduces a completely new level of anonymity by design. You would be able to send emails, perform google searches, post statuses without Google, Facebook or Twitter ever needing to or being capable of knowing what those statuses or emails contain, because all you data would be encrypted by you and under your private keys.
- Reverse Engineering will become MUCH harder. We are talking about the ability to perform addition and multiplication on encrypted data and since all computers really do is add numbers this means we will be able to deploy completely encrypted software! Though according to most of the stuff I've read on Homomorphic encryption schemes and applications we will easily be able to encrypt the input and recieve encrypted output but the operations that are performed will still be sent over in plaintext or not be encrypted by the sender at least so reverse engineering from source code would become incredible difficult by there will always be hope for dynamic analysis.
- Steganography on steroids. Steganography is basically way to hide information inside other information e.g. a tweet about your new favorite pop song could actually be the location of a pot of gold, but this protection is only useful if adversaries don't know the scheme used to hide or interpret meaningful information from covertext; once an attacker knows your scheme you're dead in the water! When you add homomorphic encryption to the mix it means you would be able to perform steganography without ever revealing how you're interpreting your covertext, more than that; you have the power to interpret covertext in an untrusted environment, this means you would be able to run your "de-steganographing" program on an adversaries machine without him ever being able to know how the scheme works because both the input values and result of the operations will all be encrypted by your secret key! This idea is drawing from number 2. ---A simple way to imagine this would be to consider a program that takes in some covertext and returns a list of the positions of plaintext characters, if attackers get hold of some covertext and this program they would trivially thwart the steganorgaphy scheme, though if the program and the steg scheme relies on homomorphic encryption, attackers would also need to know your private key to get the positions of plaintext characters.
- Malware will hide like never before. If we can severely slow down attackers efforts to reverse engineer our software, this means attackers will be able to slow us down when reverse engineering and studying malware attack patterns.
Some of these ideas are not new, and may sound similar to something like the concepts of trusted computing though the point of these ideas is that ciphertext encrypted by you can be made useful without the need to decrypt it.
Some awesome stuff to read:
- Private Database Queries Using Somewhat Homomorphic Encryption --- http://eprint.iacr.org/2013/422.pdf
- "A Fully Homomorphic Encryption Scheme (Ph.D. thesis)" --- http://crypto.stanford.edu/craig/craig-thesis.pdf
- An Implementation of Homomorphic Encryption HELib --- https://github.com/shaih/HElib
- Fully Homomorphic Encryption for Mathematicians -- http://eprint.iacr.org/2013/250.pdf
- How to run Turing machines on Encrypted Data --- http://eprint.iacr.org/2013/229.pdf
- On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption --- http://eprint.iacr.org/2013/094.pdf
- Homomorphic Encryption --- http://en.wikipedia.org/wiki/Homomorphic_encryption
Comments
Post a Comment