[paulrudy]

> FHE enables computation on encrypted data

This is fascinating. Could someone ELI5 how computation can work using encrypted data?

And does "computation" apply to ordinary internet transactions like when using a REST API, for example?

[dachrillz]

A very basic way of how it works: encryption is basically just a function e(m, k)=c. “m” is your plaintext and “c” is the encrypted data. We call it an encryption function if the output looks random to anyone that does not have the key

If we could find some kind of function “e” that preserves the underlying structure even when the data is encrypted you have the outline of a homomorphic system. E.g. if the following happens:

e(2,k)*e(m,k) = e(2m,k)

Here we multiplied our message with 2 even in its encrypted form. The important thing is that every computation must produce something that looks random, but once decrypted it should have preserved the actual computation that happened.

It’s been a while since I did crypto, so google might be your friend here; but there are situations when e.g RSA preserves multiplication, making it partially homomorphic.

[littlecranky67]

I get how that works for arithmetic operations - what about stuff like sorting, finding an element in a set etc? This would require knowledge of the cleartext data, wouldn't it?

[JohnFen]

> If we could find some kind of function “e” that preserves the underlying structure even when the data is encrypted

But isn't such a function a weakened form of encryption? Properly encrypted data should be indistinguishable from noise. "Preserving underlying structure" seems to me to be in opposition to the goal of encryption.

[xhrpost]

This made me wonder if there is such a thing as homomorphic compression. A cursory search says yes but seems like limited information.

[paulrudy]

Thank you, this really clarified things for me!

[pluto_modadic]

a simple example of partial homomorphic encryption (not full), would be if a system supports addition or multiplication. You know the public key, and the modulus, so you can respect the "wrap around" value, and do multiplication on an encrypted number.

other ones I imagine behave kinda like translating, stretching, or skewing a polynomial or a donut/torus, such that the point/intercepts are still solveable, still unknown to an observer, and actually represent the correct mathematical value of the operation.

just means you treat the []byte value with special rules

[paulrudy]

Thank you. So based on your examples it sounds like the "computation" term is quite literal. How would this apply at larger levels of complexity like interacting anonymously with a database or something like that?