>It is possible to compute over encrypted data without access to the secret key
I don't think this is counterintuitive for most people. The most basic encryption scheme that everyone knows is the Caesar cipher. It's easy to see that shifts of the cipher text will cause shifts in the plain text.
I agree, I really don’t like this one either. There are many things in math that are counterintuitive, but the idea of a homomorphism is not one of them in my opinion.
Once someone explains the idea, and provides a few examples it is very natural.
I also don’t like the text explaining zero knowledge proof. It needs the phrase “practically speaking” somewhere or “for practical purposes” since it’s not true in a strict sense
But overall there were some fun ideas on the list!
What do you mean by the line about zkps? We have perfectly-hiding proofs that reveal no information about the secret information, no matter how powerful the adversary is.
Yes, but they're not proofs in the mathematical sense, since there's always an (exponentially-shrinking) chance that the answers were only correct due to coincidence.
Exactly, practically it makes no different that the method could be fooled with a very tiny probability, but when making these counterintuitive statements I think it is important to be precise.
Ideally the reader should fully understand the statement and still feel amazed, rather than doubting the statement for a valid reason: perfect zero knowledge proof systems (which do not fail sometimes) are impossible and a reader would be right to think so
>It is possible to compute over encrypted data without access to the secret key
This is counter intuitive to me. For one, I don't consider the Caesar Cipher to be an encryption scheme that I would actually use for data.
In addition, when I want to "compute" data, I want to do things like identify sentiment analysis in free form text or identify key themes in a paragraph - and I'm not sure this actually IS possible with data that is encrypted
Maybe a simpler example would be doing a not operation on a ciphertext for a one time pad? When you decrypt it you will get the plain text with all of the bits flipped.
Doing computations on cipher text is very limited which is why it's not very efficient to do complicated operations.
But in a Caesar cipher only some types of computation is possible (to wit, addition and subtraction).
Now, "multiplication" of letters is, well, dodgy as a concept. But, the thing is that you can build encryption systems where D(E(k) op V) is equal to k op V, and op contains both addition and multiplication.
I don't think this is counterintuitive for most people. The most basic encryption scheme that everyone knows is the Caesar cipher. It's easy to see that shifts of the cipher text will cause shifts in the plain text.