[osaariki]

Homomorphic encryption (HE) is NOT what people would understand as "on-chip cryptography", i.e., secure enclaves. HE is a form of encryption that allows arithmetic operations on encrypted numbers without any access to the decryption key. Secure enclaves on the other hand do decrypt data on-chip and are thus vulnerable to side channel attacks.

You can use HE to implement things like encrypted database lookups that don't reveal what is being queried (even to the database server) and the security of the encrypted query does not depend on any hardware properties of the server providing the service.

[Dylan16807]

While noting that "database lookup" is a painful scenario for HE because you have to read through the entire thing just to find a single row.

[Misdicorl]

Wouldn't a normal db btree index work just fine? Scans certainly seem problematic though

[Dylan16807]

A tree would require the ability to have control flow based on data, or using data as an index. You can't do that while keeping the data secret.

Just to select a single row you have to do something like sum(row_meets_criteria() * row). With row_meets_criteria returning 0 or 1.

[trhway]

for equality predicate you can just use hash based index, for range search the situation is of course worse, yet you can have a somewhat like a partially/probabilistically preserving order hash so that you can produce a number of candidates orders of magnitude less than the whole table scan.

[RobLach]

The mere fact that you did not need to scan the entire db means the data was not securely encrypted in the first place.

[bawolff]

But then you are not using FHE, but something with much weaker security properties.

[dodobirdlord]

If every query didn’t walk the entire dataset then the server could figure out what was queried based on what data was loaded and what data was not loaded.

[Misdicorl]

Can't it already figure that out based on the query? E.g. I'm asking for the value at key `7`. So my query asks for the encrypted value for whatever `7` gets encrypted to. The db/algo already knows I'm asking for `qasfdj`, and that its returning `zsqwer`.

It doesn't matter whether it walks the dataset or not, it gets to know those two values. So may as well build an index on the keys?

[dodobirdlord]

Most FHE schemes introduce some randomness into the request that differs on every request so that the executor can’t make that sort of association. So if you want the value at key ‘7’ you instead send a request like (7, nonce) but encrypted in a way so that different nonces will make the encrypted bytes of the request look totally different.

If the FHE program then bundles the nonce back into the response you get a brand new request/response on every query, even if you’re just querying the same key over and over.

[bawolff]

Couldn't ORAM help with that? https://en.m.wikipedia.org/wiki/Oblivious_RAM

Regardless, this is pretty far afield of FHE...

[dodobirdlord]

Maybe, but you’d have to bundle the ORAM translation layer inside of the encryption. Conditional logic inside of FHE is extremely expensive in computation time, so this might be infeasibly slow.

[mikepurvis]

Does that matter if the indexes, the data, and the query are all encrypted?

[im3w1l]

Possibly? It could leak data in a lot of ways. For instance you might see that a particular IP is accessing particular rows.

Or you might see that certain rows are accessed together. For instance if rows represent users, you could look at the "shape" of accesses and try to match that to the shape of a social network you know from elsewhere. As an unrealistic reduced example: Maybe you know that Alice is friends with Bob and Charlie and Dennis. Bob is friends with Charlie. Now you see that W has 3 friends X, Y, Z, of which X and Z are friends with each other. Then W might be Alice, the X and Z might be Bob and Charlie (but we don't know which is which), and the Y Dennis.

    . ABCD
    A  xxx
    B x x
    C xx
    D x

    . XYZW
    X   xx
    Y    x
    Z x  x
    W xxxx

[mikepurvis]

Fair. I suppose it really depends what the motivating use cases are for this kind of thing— in my head, the killer app would be a mail server where I decrypt (from GPG) my email in my local client, and then re-encrypt (with HE) and prepare indexing information which is sent to a cloud service for long-term archival. The cloud service allows me to search on and retrieve my email without ever seeing the contents or knowing any of the metadata other than when you uploaded them and the message lengths (and even that could be scrambled up a bunch by adding arbitrary padding and periodically re-uploading old messages). In this scenario there isn't really the "known from elsewhere" info— knowing that certain groups of messages are returned together in response to sets of queries is unlikely to be meaningful if you don't have anything else to map that info to.

And thinking about it further, the client could do other shenanigans to further protect the user, like arranging for every query to return 20% "false" results that are filtered out before display, or storing duplicate instances in the database so that the server thinks query X leads to result A and query Y leads to result B, without knowing the A and B are in fact the same thing.

[bawolff]

Either (a) the index is encrypted in such a way the db engine cannot make branches based on it, in which vase its useless. Or (b) the db-engine can take branches based on the index, in which case the index can't have been encrypted very good if the db engine can read it.

Remember, in fully homomorphic encryption, the algorithm is the party you are trying to hide data from.

[mikepurvis]

The point would be that the index would serve to route "scrambled search term X" to "scrambled record Y", and the degree to which that scheme could protect the privacy of users would be a function of how much redundancy was inserted into the system at various points, all of which could be tunable on the client side (dummy record entries, dummy index entries, dummy queries, whatever).