Working with encrypted data without decrypting: CryptDB, ZeroDB and homomorphic | Hacker News Reader

Working with encrypted data without decrypting: CryptDB, ZeroDB and homomorphic

zdnet.com

43 pointsmichwill14 comments

I see a few problems here, or perhaps I didn't get it at all:

1. What happens with data shared among a dynamic group of users? A temporary password could be saved and then re-encrypted for each one of them?

2. If a suer changes its password or certificate, all its records of the databse should be updated? In a cloud service or backup that could be expensive (unless a all the information and password travels back to the user and it is reencrypted)

3. In case an attacker breaks into the remote system or database: game over. He installs custom code there and waits that the user logs in again. Or exploits the client doing a personalized MITM for the DB.

1. Yes, this is a fair problem. Currently common solution is this. You encrypt data with, say, AES, and AES content keys with your public key. Whenever you want to share, you (not cloud) re-encrypt all the content keys for all people you want to share with. This can be pretty computationally expensive. The way to solve this, mentioned in the article - proxy re-encryption. There are such algorithms which allow the cloud to re-encrypt data on your behalf, without knowing your keys. Compromised cloud would have only choice of executing or not executing re-encryption.

2. Same as (1). You either re-encrypt all the content keys on the client side, which could be an expensive process. Or you use proxy re-encryption to let the server re-encrypt data for your new key.

3. That I don't understand. Ok, attacker breaks into remote database. What can he do? When user logs in, he[user] doesn't ever say decryption key to the server. That was the whole point of this article :-)

Could something explain to me how FHE could allow for arbitrary computation?

For example, how could a server using FHE possibly execute any algorithm whose steps are data-dependent? Like, if the client gives the server an encrypted number and asks it to "return 'good' if the number is even and 'bad' if the number is odd", how could the server possibly do that without actually knowing what it's returning? Heck, even knowing the LENGTH of the return string would be enough to tell the server what the input was!

The thing is the server doesn't even know what it's returning (or, more precisely, what "means" its response). In your example, the "encrypted algorithm" could be "If the last byte of the input module 0xab is greater than 0x04, then answer 0xff, else answer 0xaa". The server just follows the steps but had no idea what is happening.

So you're saying only some algorithms can be implemented this way? i.e., an algorithm whose output size isn't fixed beforehand can't be implemented this way, correct?

Well, imagine that after "encrypting" the algorithm, its output always become fixed length. Of course, this is all a big metaphor, not the exact way FHE works.

I don't get how something like that could ever be practical though, even on a theoretical level. Like say you ask a server for a list of all flights from airport A to airport B. The only way this could work without making the server "know" what is happening is if the output size accommodated the list of ALL flights in ALL databases globally. So you'd have to return the client gigabytes(?) of data even though the answer probably fit in a kilobyte.

Basically, fundamentally I just can't see how computation could be efficient with FHE (and this has nothing to do with the efficiency of FHE itself).

What sort of encryption was used in the fully-homomorphic case? Was it something recognizable like AES or something completely new?

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.

Has that solved the problem of f and g being asymptotically more expensive than addition and multiplication?

Ah, 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.

Right, 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.

There's no high-level overview because the construction itself is extremely complex. Unfortunately we do not have any simple constructions of FHE.

> The security compromise is that performing some operations reveals a "little bit" about the encrypted data.

How big a problem is this?

Reply on news.ycombinator.com