Edge's Password Monitor feature uses homomorphic encryption to match passwords against a database of leaks without revealing anything about those passwords: https://www.microsoft.com/en-us/research/blog/password-monit... So not the first, but definitely cool to see more adoption!
I tried to look homomorphic encryption up casually earlier this year. I saw references that it was being used, but I don’t think they said where.
This is one topic I have a very hard time with, I just don’t know enough math to really grok it.
It just seems crazy a system could operate on encrypted data (which is effectively random noise from the server’s point of view) and return a result that is correctly calculated and encrypted for the client, despite never understanding the data at any point.
I sort of understand the theory (at a very simple level) but my brain doesn’t want to agree.
Maybe it’s the fact it can be done with multiple operators and strong encryption that is hard to grok, but at least here is a very simple example of a limited partially homomorphic encryption:
You have a 7-bit character representation (e.g. ASCII) and your encryption is to add 1 mod 128. E.g. 0 -> 1, 1 -> 2, ... 126 -> 127, 127 -> 0.
As it turns out, all your operations can be represented as adding or subtracting constants. You can now encrypt your data (+1), send it to a remote server, send all the adding and subtracting operations, pull back the processed data, decrypt the data (-1).
Of course, this example is neither useful encryption nor generally useful operation, but can be useful for grokking why it might be possible.
Let's say I want you to add two numbers, but I don't want you to know what those numbers are, nor what the result is. What I can do is multiply both numbers by some other number you don't know. I then give you the premultiplied numbers, you add them, and give back a premultiplied answer. I can then divide out the number to get the true result.
What we've done here is this:
(a * key) + (b * key) = (c * key)
The rules of elementary algebra allow us to divide out the key on both sides because of a few useful symmetries that addition and multiplication have. Namely, these two equations are always the same number:
(a + b) * key = (a * key) + (b * key)
This is known as the distributive property. Normally, we talk about it applying to numbers being added and multiplied, but there are plenty of other mathematical structures and pairs of operations that do this, too. In the language of abstract algebra, we call any number system and pair of operations that distribute like this a "field", of which addition and multiplication over real[0] numbers is just one of.
A simple example of a field that isn't the normal number system you're used to is a 'finite field'. To visualize these, imagine a number circle instead of a line. We get a finite field by chopping off the number line at some prime[1] number that we decide is the highest in the loop. But this is still a field: addition and multiplication keep distributing.
It turns out cryptography loves using finite fields, so a lot of these identities hold in various cryptosystems. If I encrypt some data with RSA, which is just a pair of finite field exponents, multiplying that encrypted data will multiply the result when I decrypt it later on. In normal crypto, this is an attack we have to defend against, but in homomorphic crypto we want to deliberately design systems that allow manipulation of encrypted data like this in ways we approve of.
[0] Also complex numbers.
[1] Yes, it has to be prime and I'm unable to find a compact explanation as to why, I assume all the symmetries of algebra we're used to stop working if it's not.
Second: Google Recaptcha Enterprise can use Homomorphic Encryption to check whether your password has been compromised (searching the set of all breached passwords without disclosing which individual password you want to check)
Now, in practice, HaveIBeenPwned does the exact same thing with a k-anonymity scheme based off of MD5 collisions, which is wayyyy easier in practice and what most people actually deploy, but the Google thing is cool too.
osaariki|1 year ago
cedws|1 year ago
dagmx|1 year ago
MBCook|1 year ago
This is one topic I have a very hard time with, I just don’t know enough math to really grok it.
It just seems crazy a system could operate on encrypted data (which is effectively random noise from the server’s point of view) and return a result that is correctly calculated and encrypted for the client, despite never understanding the data at any point.
I sort of understand the theory (at a very simple level) but my brain doesn’t want to agree.
oblvious-earth|1 year ago
You have a 7-bit character representation (e.g. ASCII) and your encryption is to add 1 mod 128. E.g. 0 -> 1, 1 -> 2, ... 126 -> 127, 127 -> 0.
As it turns out, all your operations can be represented as adding or subtracting constants. You can now encrypt your data (+1), send it to a remote server, send all the adding and subtracting operations, pull back the processed data, decrypt the data (-1).
Of course, this example is neither useful encryption nor generally useful operation, but can be useful for grokking why it might be possible.
kmeisthax|1 year ago
What we've done here is this:
(a * key) + (b * key) = (c * key)
The rules of elementary algebra allow us to divide out the key on both sides because of a few useful symmetries that addition and multiplication have. Namely, these two equations are always the same number:
(a + b) * key = (a * key) + (b * key)
This is known as the distributive property. Normally, we talk about it applying to numbers being added and multiplied, but there are plenty of other mathematical structures and pairs of operations that do this, too. In the language of abstract algebra, we call any number system and pair of operations that distribute like this a "field", of which addition and multiplication over real[0] numbers is just one of.
A simple example of a field that isn't the normal number system you're used to is a 'finite field'. To visualize these, imagine a number circle instead of a line. We get a finite field by chopping off the number line at some prime[1] number that we decide is the highest in the loop. But this is still a field: addition and multiplication keep distributing.
It turns out cryptography loves using finite fields, so a lot of these identities hold in various cryptosystems. If I encrypt some data with RSA, which is just a pair of finite field exponents, multiplying that encrypted data will multiply the result when I decrypt it later on. In normal crypto, this is an attack we have to defend against, but in homomorphic crypto we want to deliberately design systems that allow manipulation of encrypted data like this in ways we approve of.
[0] Also complex numbers.
[1] Yes, it has to be prime and I'm unable to find a compact explanation as to why, I assume all the symmetries of algebra we're used to stop working if it's not.
unknown|1 year ago
[deleted]
nightpool|1 year ago
Now, in practice, HaveIBeenPwned does the exact same thing with a k-anonymity scheme based off of MD5 collisions, which is wayyyy easier in practice and what most people actually deploy, but the Google thing is cool too.
7e|1 year ago
saagarjha|1 year ago
glenngillen|1 year ago
kmdupree|1 year ago
7e|1 year ago
[deleted]