These are good questions! FHE appears nonintuitive at first glance, but hopefully with a smaller example it can be made clear.
> Wouldn't the information required to identify what a "word" is require the running software to be able to see breaks/periods/etc?
Yes. But that information can be encrypted and still computed on. You might suppose that since encrypted data is essentially gibberish, then multiplying or adding different blocks of it together will only generate gibberish. The insight is that it is not entirely gibberish- or else how would we be able to decrypt it? The information to identify a word still there, and you can write a program that sees breaks/periods/etc, but you won't know when it sees a break/period until decryption of the result.
> Doesn't that leak information about the cyphertext?
This question seems to be encoding an assumption that the cloud in your example is able to see the result of the search query. The key insight here is that the cloud is only able to compute the encrypted result. It can only return the encrypted result to the requester who has the private key, and can decrypt the result, and see how many words were counted.
> How does it stop someone from writing software that, for example, maps out the position of all the a's, then b's, then c's, etc in a cyphertext and MITMing it?
I'm a bit confused by the attack here. I think it is also assuming that the untrusted computing party is able to read the plaintext result of the operation.
Here's an illustrative example. Suppose my encryption scheme is Enc(key, m) = key*m = c. Suppose my decryption scheme is Dec(key, c) = c/key = m. This scheme is not secure, but pretend that it is, and that separating out key and m from c is difficult.
I want the untrusted cloud to compute m1 * m2.
I can perform Enc(key, m1) = c1, Enc(key, m2) = c2 and send c1 and c2 to the cloud to multiply.
The cloud receives c1 and c2 which are really key*m1 and key*m2, but we are assuming that the cloud can't separate these factors from the products.
The cloud returns c1*c2, which we know equals key*m1*key*m2 = key^2 * (m1*m2).
If we divide c1*c2 by (key^2) - note: this is just running our decryption algorithm with a modified key - we will get m1*m2, which is what we wanted!
In your example you decryped by key^2. The decryption requiring a different or derivative key a general feature of the algorithm or just a quirk of your example?
In the ElGamal example I linked you'll see that we use the same key for encryption and decryption. However, we perform a modification on the cyphertext using known values. This has a similar effect.
It's also somewhat definitional. We're taking an established encryption scheme in both cases and constructing a new algorithm on top of it. Above where I say we're performing decryption with a key set to key^2, we could also think of it as doing Dec(key, key*m) where the key is the same but we've done some operation on the cyphertext.
I've been working on a webapp to scrape links users enter from Zillow/Apartments.com/Trulia/etc to build tables of listings you are interested in. It can show your commute time to work or queries for amenities nearby like "Trader Joe's".
This is really cool! So far I have a high score of 65612 :)
Some feedback:
- When opening the help menu, it wasn't obvious how to close it (I think the only way is by pressing '?')
- I like the Goblin music!
- It's a pretty nice interface to play with the instructions and I appreciate the color coding. It would be neat if there was a "sandbox mode" where you could preview the effects of running an instruction, and maybe modify your program once the game is over. I could see this being pretty useful for someone learning ARM assembly.
Thanks! I'm using invisible captcha to prevent spam and sanitizing inputs for now. As far as verification -- I could implement some sort of screenshot upload of application confirmation email / follow up email but seems like a bit overkill for now
> Wouldn't the information required to identify what a "word" is require the running software to be able to see breaks/periods/etc?
Yes. But that information can be encrypted and still computed on. You might suppose that since encrypted data is essentially gibberish, then multiplying or adding different blocks of it together will only generate gibberish. The insight is that it is not entirely gibberish- or else how would we be able to decrypt it? The information to identify a word still there, and you can write a program that sees breaks/periods/etc, but you won't know when it sees a break/period until decryption of the result.
> Doesn't that leak information about the cyphertext?
This question seems to be encoding an assumption that the cloud in your example is able to see the result of the search query. The key insight here is that the cloud is only able to compute the encrypted result. It can only return the encrypted result to the requester who has the private key, and can decrypt the result, and see how many words were counted.
> How does it stop someone from writing software that, for example, maps out the position of all the a's, then b's, then c's, etc in a cyphertext and MITMing it?
I'm a bit confused by the attack here. I think it is also assuming that the untrusted computing party is able to read the plaintext result of the operation.
Here's an illustrative example. Suppose my encryption scheme is Enc(key, m) = key*m = c. Suppose my decryption scheme is Dec(key, c) = c/key = m. This scheme is not secure, but pretend that it is, and that separating out key and m from c is difficult.
I want the untrusted cloud to compute m1 * m2.
I can perform Enc(key, m1) = c1, Enc(key, m2) = c2 and send c1 and c2 to the cloud to multiply.
The cloud receives c1 and c2 which are really key*m1 and key*m2, but we are assuming that the cloud can't separate these factors from the products.
The cloud returns c1*c2, which we know equals key*m1*key*m2 = key^2 * (m1*m2).
If we divide c1*c2 by (key^2) - note: this is just running our decryption algorithm with a modified key - we will get m1*m2, which is what we wanted!
For a more formal example using ElGamal Encryption (apologies for spelling ElGamal wrong in the paper) I wrote this up: https://github.com/lsnow99/elgamal/blob/main/elgamal.pdf
Credit to https://www.cs.cmu.edu/~goyal/15356/lecture_notes.pdf for definitions