Hacker News Reader

Comment by sillysaurusx | Hacker News Reader

I was going to make my usual comment of FHE being nice in theory but too slow in practice, and then the article points out that there’s now SHE (somewhat homomorphic encryption). I wasn’t aware that the security guarantees of FHE could be relaxed without sacrificing them. That’s pretty cool.

Is there any concrete info about noise budgets? It seems like that’s the critical concern, and I’d like to understand at what point precisely the security breaks down if you have too little (or too much?) noise.

View on HN

SHE vs FHE has nothing to do with security. Instead, it’s about how many operations (eg homomorphic multiplications and additions) can be performed before the correctness of the scheme fails due to too much noise accumulating in the ciphertext. Indeed all FHE schemes are also SHE schemes.

What typically makes FHE expensive computationally is a “bootstrapping” step for removing the noise that accumulated after X operations and threatening correctness. After bootstrapping you can do another X operations. Rinse and repeat until you finish the computation to you want to perform.

Im not an expert on this, but my understanding is "noise" is less a security breakdown and more the entire system breaksdown. That is where the "somewhat" comes in, unlike "full" where the system can do (expensive) things to get rid of noise, in somewhat the noise just accumulates until the system stops working. (Definitely talking out of my hat here)

Interesting! Are there any security concerns with SHE? If not, it sounds like all of the benefits of FHE with none of the downsides, other than the noise overwhelming the system. If that’s true, and SHE can run at least somewhat inexpensively, then this could be big. I was once super hyped about FHE till I realized it couldn’t be practical, and this has my old excitement stirring again.

Most FHE schemes are constructed out of SHE schemes. Also, there’s nothing preventing FHE from being practical, it’s just that existing constructions are not as fast we would like them to be

My impression is that SHE are still relatively expensive, not as crazy as FHE but still slow enough to preclude many usecases and the noise breakdown can happen relatively quickly making them not work for most algorithms people want to use FHE for.

Wait until you see all the ASICs getting taped out by various companies right now.

it's incredibly algorithm-dependent. if you look into the thesis that originates the 'bootstrapping' technique to transform SHE algorithms into FHE, they determine the noise limit of their specific algorithm in section 7.3 and then investigate expanding the noise limit in 8 and 10.

(written in 2009) http://crypto.stanford.edu/craig/craig-thesis.pdf

some newer FHE don't encounter a noise limit or don't use the bootstrapping technique.

All known FHE schemes use bootstrapping

i expected that, but a search turned up several things claiming to implement fhe without bootstrapping. i didn't investigate and i can't say i'm familiar so maybe they're bogus

Correction: all known even-remotely-practical schemes rely on bootstrapping. See https://crypto.stackexchange.com/questions/103341/fully-homo...

As always, there is no free lunch.

I did see an arxiv paper a while back that claimed to use category theory to do this, but my best bet was it was not secure.

SHE doesn’t relax security guarantees, it relaxes the class of supported computations

Not sure whether they use FHE or not (the literature I’m looking at simply says “homomorphic”), but we use ElectionGuard at our company to help verify elections for our customers. So there are definitely some practical uses.

Reply on news.ycombinator.com