What exactly is homomorphic encryption?
Practical homomorphic encryption over integers (2017)
21–30 of 57 posts
Re: Practical homomorphic encryption over integers (2017)
#22This is one of the current 'tech' trends that I'm following, the idea of homomorphic encryption is really cool. I feel like there is a lot of real world applications for it, but I have failed to find them yet.
I really want to sarcastically say "blockchain homomorphic encryption", but, well, it's not necessarily a terrible idea, honestly. One can imagine some combination of the primitives in which you could prove that you added here the same amount you subtracted from there, that neither total is below zero, but for which the number actually transferred is encrypted. The current use case for something like BitCoin is often…
Hey, we're working on blockchain "somewhat homomorphic encryption" (SHE) via multiparty computation. In particular, a privacy layer for Ethereum.
Re: Practical homomorphic encryption over integers (2017)
#23What exactly is homomorphic encryption?
Encryption while keeping the "shape"/"form" of the data intact. This way you can have secure third-party computation, without that third-party knowing exactly what data it is operating on.
Re: Practical homomorphic encryption over integers (2017)
#24What exactly is homomorphic encryption?
You encrypt some data and send it to Bob.
Bob does some computations on the encrypted data and sends you the (still-encrypted) results.
You decrypt the results to get the answer of your computation. Bob never learns what your data is or what the results are.
The term "homomorphic" roughly refers to the fact that the encrypt/decrypt functions go "outside" the computation. That is, if Bob is applying the function f, we have f(Encrypt(data)) = Encrypt(f(data)). The left side is what Bob does, the right side is what you want to get (because you can decrypt it).
EDIT. To see how cool this is, think about this: I have two numbers, I encrypt them to form long strings of gibberish. Then I have Bob perform the "multiplication" function on the gibberish and send me the result, and I am able to decrypt that to get the result of multiplying the original two numbers. If that doesn't impress you, I send Bob my database of encrypted emails, then ask him to do a string lookup for "chocolate", he sends me back the set of matching emails without ever knowing what they say or what string I looked for.
Re: Practical homomorphic encryption over integers (2017)
#25What exactly is homomorphic encryption?
A homomorphism between two sets preserves relations between elements.
A set with a single operation (plus some extra properties) is called a group. The integers with addition (+) is an example of a group.
Suppose I have groups X and Y. Then a group homomorphism, h, is a mapping at that preserves the + in the two groups, so
h(x +_X y)=h(x) +_Y h(y)
Where +_X is addition in X and +_Y is addition in Y.
Homomorphic encryption means that what you used to do you encryption is a homomorphism.
Re: Practical homomorphic encryption over integers (2017)
#26What exactly is homomorphic encryption?
You encrypt some data and send it to Bob. Bob does some computations on the encrypted data and sends you the (still-encrypted) results. You decrypt the results to get the answer of your computation. Bob never learns what your data is or what the results are. The term "homomorphic" roughly refers to the fact that the encrypt/decrypt functions go "outside" the computation. That is, if Bob is applying the function f, we…
Does it generalize? Can you in theory perform any computation in this way?
Re: Practical homomorphic encryption over integers (2017)
#27Earlier quoted context omitted.
You encrypt some data and send it to Bob. Bob does some computations on the encrypted data and sends you the (still-encrypted) results. You decrypt the results to get the answer of your computation. Bob never learns what your data is or what the results are. The term "homomorphic" roughly refers to the fact that the encrypt/decrypt functions go "outside" the computation. That is, if Bob is applying the function f, we…
Does it generalize? Can you in theory perform any computation in this way?
To the extent that computations are feasible, yes. There was a pretty big paper like a decade ago proposing a fully homomorphic system. It was pretty much impractical, running like a million times slower than native instructions. I assume without reading that this post's paper reduces that multiplier to hundreds of thousands.
edit: reading the abstract, it looks like they don't have a faster fully homomorphic system, just some better results in the partial homomorphic domains.
Re: Practical homomorphic encryption over integers (2017)
#28Earlier quoted context omitted.
You encrypt some data and send it to Bob. Bob does some computations on the encrypted data and sends you the (still-encrypted) results. You decrypt the results to get the answer of your computation. Bob never learns what your data is or what the results are. The term "homomorphic" roughly refers to the fact that the encrypt/decrypt functions go "outside" the computation. That is, if Bob is applying the function f, we…
Does it generalize? Can you in theory perform any computation in this way?
It does generalize, but not all the way. You can't perform while loops (or anything with unbounded runtime) or operate on anything with unbounded (secret) size, so it isn't Turing complete.
You can do anything expressible as a bounded-depth (non-cyclic) circut of eg NAND gates. You can also do something like [a][+ b][+ c][+ d], where each [] is a new homomorphic operation, which gets around the bounded-size problem somewhat, but the attacker can obviously see how many chunks you're working on, just not the content, which provides some traffic analysis vulnerabilities.
All in all, it's a very useful tool but I don't really like the way people keep presenting it a silver bullet, like "yay, once we get this working we won't have to care that the cloud is full of phantom trolleys armed with hammers!".
Re: Practical homomorphic encryption over integers (2017)
#29This is one of the current 'tech' trends that I'm following, the idea of homomorphic encryption is really cool. I feel like there is a lot of real world applications for it, but I have failed to find them yet.
Cloud computing is the big one. You might want to rent some remote computer time without sending plaintext data to a third party. Homomorphic encryption lets you upload encrypted data and instructions for a third party to operate on it without having to decrypt it first. Edit: Try Greg Egan's book Permutation City .
If we had proper homorphic encryption, we could use regular home user machines for a cloud, airbnb style. You can't do that today because the security risks are completely unmanageable. But that all changes with homomorphic encryption.
Today it's not practical, but we see advances like this every year, maybe in a decade it will be practical.
Re: Practical homomorphic encryption over integers (2017)
#30This is one of the current 'tech' trends that I'm following, the idea of homomorphic encryption is really cool. I feel like there is a lot of real world applications for it, but I have failed to find them yet.
I really want to sarcastically say "blockchain homomorphic encryption", but, well, it's not necessarily a terrible idea, honestly. One can imagine some combination of the primitives in which you could prove that you added here the same amount you subtracted from there, that neither total is below zero, but for which the number actually transferred is encrypted. The current use case for something like BitCoin is often…
There's already practical cryptography to do what you just described called Confidential Transactions. It's not true homomorphic encryption, but it does securely hide the amount transferred on the blockchain while still guaranteeing that a legal transaction occured (no money created or destroyed)