News for hackers. Stuff that matters.
Re:Cryptographers Solve Decades-Old Privacy Problem by calamari4065 on Saturday November 18, 2023 @04:40PM (#38324803)
Wait, so they're doing computation on encrypted data and inferring some information about the relationships between data in the encrypted set?

How is that even possible? That seems to defeat the purpose of encryption, or at least show that our encryption is severely flawed.

This is the first time I've heard of this and it's kind of blowing my mind

Re:Cryptographers Solve Decades-Old Privacy Problem by fiddlerwoaroof on Saturday November 18, 2023 @04:50PM (#38324908)
The idea is the result is encrypted too such that, when the person that holds the key gets it back they can decrypt it and see the result. So you can run an inference algorithm on data without ever having to decrypt it and see what the data actually is.

It seems to me that this intrinsically is vulnerable to side-channel attacks, but it will be interesting to see if we can avoid those with constant-time algorithms or something.

Re:Cryptographers Solve Decades-Old Privacy Problem by l33t7332273 on Saturday November 18, 2023 @05:45PM (#38325494)
What about this seems vulnerable to side channels?
Re:Cryptographers Solve Decades-Old Privacy Problem by fiddlerwoaroof on Saturday November 18, 2023 @05:58PM (#38325629)
Because, if you have a mechanism to run arbitrary computations on encrypted data, I’d be a bit concerned about an attacker running carefully crafted computations on the data and deducing information about the encrypted data based on how the ciphertext changes or the time/memory usage of the computation.

This isn’t really a particularly well-informed suspicion: it’s partly based on a sense that FHE is a “have your cake and eat it too” sort of technology that’s too good to be true and partly based on the recent discoveries that fairly well-understood things like speculative execution in CPUswere vulnerable to serious side-channel attacks.

Re:Cryptographers Solve Decades-Old Privacy Problem by HeadsUpHigh on Saturday November 18, 2023 @06:44PM (#38326227)
zk proofs are used in public blockchains to transmit millions in value so I would assume they aren't vulnerable to side channel attacks at least not on a superficial level.
Re:Cryptographers Solve Decades-Old Privacy Problem by l33t7332273 on Saturday November 18, 2023 @09:05PM (#38327630)
If running computations on encrypted data is enough to compromise the integrity of the encryption then that encryption algorithm is not even EAV secure, and EAV secure is a pretty low bar.
Re:Cryptographers Solve Decades-Old Privacy Problem by jkhdigital on Saturday November 18, 2023 @11:24PM (#38328925)
There is no side-channel because FHE effectively considers the computational hardware itself to be the adversary.
Re:Cryptographers Solve Decades-Old Privacy Problem by PeterisP on Saturday November 18, 2023 @08:08PM (#38327135)
No, FHE is not intrinsically vulnerable to any side-channel attacks, by definition; the properties hold no matter how the "executor" executes the operations and they include the assumption that obviously they can see (or change!) everything that happens during the execution.

However, that effectively means that any FHE approach has to be "anti-optimized", always touching all the data that might get touched, always taking all the conditional paths, not just the worst case path as in constant time algorithms, since the execution must return the correct result for any encrypted input data.

It's not that you can "see if we can avoid those with constant-time algorithms or something", the basic table stakes (which all FHE methods actually implement) is the constant-time algorithm approach taken to the extreme and then squared.

It does have "some" unavoidable performance impact because of that.

Re:Cryptographers Solve Decades-Old Privacy Problem by fiddlerwoaroof on Saturday November 18, 2023 @08:18PM (#38327209)
I suspect that you’re right, but my concern is more about unknown unknowns here: new tech like this often has failure modes we can’t imagine until the tech itself becomes commonplace.
Re:Cryptographers Solve Decades-Old Privacy Problem by l33t7332273 on Saturday November 18, 2023 @05:44PM (#38325488)
A homomorphism is a function so that f(ab) = f(a) f(b). So you can imagine the cloud customer wants to compute ab, but the use a homomorphic encryption function, f, to ask the cloud provider to computer f(ab) given f(a) and f(b).

Then the customer decrypts f(ab). This doesn’t imply any weakness in encryption.

FHE is a bit stronger than what I’ve described, but that’s the idea.

Re:Cryptographers Solve Decades-Old Privacy Problem by noman-land on Saturday November 18, 2023 @10:57PM (#38328715)
It's pretty damn insane. I implemented the simplest form of this in Javascript as a sort of test a while back and it's just so cool.

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

https://gist.github.com/noman-land/a65520aa4f2ce7ba3bf9f13d2...