Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Intro to Fully Homomorphic Encryption

blog.higashi.tech

Post reply on HN
Print view View original

21–30 of 31 posts

Re: Intro to Fully Homomorphic Encryption

#21

Post by mahmoudimus »

arkadiyt wrote: post #2

The author touched on the performance problem but is anyone aware of homomorphic encryption being used in the real world today, outside of academia?

There are a few companies doing some stuff commercially - some have mentioned TFHC, sponsored by commercial entity called Inpher (https://www.inpher.io/ ) and you have others like Enveil (https://enveil.com), who are building some cool use cases for Private Information Retrieval.

Ultimately, they end up being very niche use cases that are part of a broader security strategy- we are very far away from having this be practical enough for general use cases. Deployment are also difficult because they require client side changes to adapt to the underlying cryptographic protocols.

At my place of employment, we believe the right approach is a combination of locked down execution environments (see: keystone enclave) + webassembly that expose what is effectively a compiler to choose the right cryptographic computation paths based on query planner (similar technologies that power database query engines). It’s not a one-size fits all, but there are ways that you can optimize down to a fully homomorphic operation _for a particular computational path_. If this stuff is interesting to you, we are hiring :)!

Re: Intro to Fully Homomorphic Encryption

#22

Post by whatshisface »

exdsq wrote: post #19
galacticaactual wrote: post #18

Earlier quoted context omitted.

The notation in that article is basic discrete math stuff...

Says a stem grad?

The parent said "advanced mathematical notation," while in reality this is at most "mathematical notation," and at least "101-level notation."

Re: Intro to Fully Homomorphic Encryption

#23

Post by blincoln »

aildours wrote: post #11
daenz wrote: post #7

If Enc(2) + Enc(3) = Enc(5), and Enc(1) + Enc(4) = Enc(5). Does Enc(5) represent the same ciphertext in both cases? I'm asking because, if so, shouldn't it be trivial to uncover the plaintexts if you can perform any math op on the ciphertexts?

As KenoFischer says, they are not the same ciphertext, even if we consider a non homomorphic encryption system. Enc is basically a random algorithm, and we need it to return different ciphertexts for the same plaintext, otherwise it would be easy to break - if I know Enc(1) and the scheme is additive, then I'd know Enc(n) for all n...

Are there any existing FHE algorithms with that property, or is it just a theoretical goal for the field?

Every time I've heard FHE mentioned, I've had the same "this sounds like it has all the problems of ECB mode plus some new ones" reaction. This article (like all of the ones I've read) doesn't seem to cover how what you're describing would be achieved.

What is the input to the algorithm that makes two identical cleartexts encrypt to different ciphertexts? In a traditional block cipher, it would be an IV or a "confounder", but IVs are included with the ciphertext, so I'm assuming it's more like a "confounder".

If an FHE algorithm that exists today has this property, how does essentially randomizing the ciphertext not break the ability to perform calculations on it? It seems like whatever does the randomizing would need to be known to all parties in order to take it into account, and so anyone could factor it out in some way to get back to ciphertexts that are identical for identical cleartexts.

Re: Intro to Fully Homomorphic Encryption

#24

Post by bawolff »

exdsq wrote: post #19
galacticaactual wrote: post #18

Earlier quoted context omitted.

The notation in that article is basic discrete math stuff...

Says a stem grad?

Stem grads generally don't study "advanced mathamatical notation" unless you are the "m" in stem.

Of course, its all relative, grade school mathamatical notation is advanced notation to someone who doesn't know it

Re: Intro to Fully Homomorphic Encryption

#26

Post by bawolff »

blincoln wrote: post #23
aildours wrote: post #11

Earlier quoted context omitted.

As KenoFischer says, they are not the same ciphertext, even if we consider a non homomorphic encryption system. Enc is basically a random algorithm, and we need it to return different ciphertexts for the same plaintext, otherwise it would be easy to break - if I know Enc(1) and the scheme is additive, then I'd know Enc(n) for all n...

Are there any existing FHE algorithms with that property, or is it just a theoretical goal for the field? Every time I've heard FHE mentioned, I've had the same "this sounds like it has all the problems of ECB mode plus some new ones" reaction. This article (like all of the ones I've read) doesn't seem to cover how what you're describing would be achieved. What is the input to the algorithm that makes two identical c…

The article includes semantic security in the definition of FHE, so i would assume this implies that all the existing FHE scheme have this property.

Re: Intro to Fully Homomorphic Encryption

#27

Post by y7 »

blincoln wrote: post #23
aildours wrote: post #11

Earlier quoted context omitted.

As KenoFischer says, they are not the same ciphertext, even if we consider a non homomorphic encryption system. Enc is basically a random algorithm, and we need it to return different ciphertexts for the same plaintext, otherwise it would be easy to break - if I know Enc(1) and the scheme is additive, then I'd know Enc(n) for all n...

Are there any existing FHE algorithms with that property, or is it just a theoretical goal for the field? Every time I've heard FHE mentioned, I've had the same "this sounds like it has all the problems of ECB mode plus some new ones" reaction. This article (like all of the ones I've read) doesn't seem to cover how what you're describing would be achieved. What is the input to the algorithm that makes two identical c…

Yes, all existing FHE schemes have this property (called semantic security). The encryption algorithm is a randomized algorithm, which takes the plaintext and a random value as input (just like an IV). Note that we're talking about public-key crypto here, which is a different primitive from the symmetric crypto you're thinking of. Each key is actually a key pair consisting of a secret key and a public key. Such cryptosystems are based on some mathematical trapdoor: only with the secret key are you able to "undo" the randomization and learn the plaintext. It therefore doesn't matter if you want to undo the randomization on a direct encryption of a plaintext, or whether the ciphertext is the sum of several ciphertexts.

If you want to see how this works on a bit more technical level, look at the ElGamal cryptosystem [1]. It is in fact partially homomorphic (you can add ciphertexts, but cannot multiply), and it's probably the easiest to understand system with this property.

https://en.wikipedia.org/wiki/ElGamal_encryption

Re: Intro to Fully Homomorphic Encryption

#28

Post by skissane »

galacticaactual wrote: post #18
davidmurdoch wrote: post #3

This is only a "Gentle Intro" if you know advanced mathematical notation.

The notation in that article is basic discrete math stuff...

I got most of it, but... KeyGen(1^lambda), what does the 1^lambda part mean? They don't really explain that, and I don't remember encountering that notation in any of the mathematics courses I took at university

Re: Intro to Fully Homomorphic Encryption

#29

Post by tsimionescu »

davidmurdoch wrote: post #8
staycoolboy wrote: post #4

Earlier quoted context omitted.

Which really speaks to the complexity of the field. It'll be another century before the ELI5 version comes along.

ELI5 level isn't what I'd want, personally. Cryptography is of interest to many programmers, and the mental gymnastics needed for mathematics and programming are quite similar. This topic could be explained to a much broader audience without the mathematical notation, albeit not nearly as concisely, and it'd likely lack the exacting precision afforded by the notation.

This sounds like people are just scared of the maths. I find it very hard to imagine there are many people who know what modular arithmetic, polynomials, or groups are, but don't know the sigma notation for summing, the forall sign, or the general "prop1, prop2 : conclusion" for 'given prop1 and prop2 then conclusion'.

Re: Intro to Fully Homomorphic Encryption

#30

Post by ganzuul »

knappa wrote: post #25
davidmurdoch wrote: post #3

This is only a "Gentle Intro" if you know advanced mathematical notation.

I'm always confused by people complaining about knowing 'advanced' mathematical notation. The thing that requires effort to understand is the actual mathematics, not the notation.

Doew this author use square brackets to indicate a number-like object?
Post reply on HN