3 ms·
No, it's nothing like AES. The idea with fully-homomorphic encryption is that you want not just any encryption function C, but a function C such that C(x + y) =
by pavpanchekha 11y ago
No, it's nothing like AES. The idea with fully-homomorphic encryption is that you want not just any encryption function C, but a function C such that C(x + y) = f(C(x), C(y)) and C(x × y) = g(C(x), C(y)). No such f and g exist for common encryption schemes, and in fact it's not clear that there should be any secure C where such f and g exist. But a very recent breakthrough in cryptography has constructed such a C; that's FHE.
- JoshTriplett 11y agoHas that solved the problem of f and g being asymptotically more expensive than addition and multiplication?
- pavpanchekha 11y agoAh, sorry, I was just referring to the construction of FHE itself as a breakthrough. Several steps have been made that make FHE more efficient, but there's still a ways to go. We're talking about fixed-size operations, so there's no notion of asymptotic expensiveness here, but yes, FHE "addition" and "multiplication" are very expensive.
- sp332 11y agoRight, I understand the result, and I'm endlessly fascinated that such a scheme exists, but there doesn't seem to be any simple high-level overview. Either you understand the scheme that's 1,000,000,000 times more complicated than multiplication or you're in the dark. Edit: Also I'm wondering how secure the encryption really is.
- pavpanchekha 11y agoThere's no high-level overview because the construction itself is extremely complex. Unfortunately we do not have any simple constructions of FHE.