5 ms·

Yes. Homomorphic encryption databases are totally unrealistic in practice. It’s a common BS justification for research to make it “practical.” (There are real

Yes. Homomorphic encryption databases are totally unrealistic in practice. It’s a common BS justification for research to make it “practical.” (There are real applications, particularly in privacy preserving financial cryptography. But the database application is just a BS non-niche justification for grant purposes.)

SilasX 6y ago
Currently totally unrealistic in practice, but it's proven that the algorithms are in P (polynomial time), and it's just ("just", I know...) a matter of getting the constant factor overheads down. It's definitely desirable, because it means some untrusted host could perform operations on your data without ever knowing what they were operating on e.g. "I added your numbers but I don't know what they are or their sum."
- deleted 6y ago
  [deleted]
- marcinzm 6y ago
  Polynomial time is pretty bad I feel and not due to any constant factor. A search in a regular database with an index is either O(1) or O(log(N)) depending on the design.
- deleted 6y ago
  [deleted]
- a1369209993 6y ago
  Indexing a N-element array (a O(log N) operation frequently approximated as O(1)) inside a homomorphic enclave requires O(N) operations. Constant factors exacerbate the problem, but any usefully large database is wholely unsuitable for homomorphic use.
  - mdpopescu 6y ago
    Hmm... I don't understand this. O(N) is very fast for most realistic purposes I can come up with. It's faster than sorting - O(N log N) - which I was taught is "basically a free operation". (Coursera class with Tim Roughgarden.)
    - FartyMcFarter 6y ago
      O(N) search is not fast. Hash tables and trees are O(1) or O(lg N) which are vastly faster than O(N). Imagine a database with billions of records. O(N) search on this database will absolutely murder performance.
    - terminalcommand 6y ago
      I am also an amateur in these things. If indexing is O(N), does that mean it has the same performance as a linked list? Basically that would mean you have to go through each and every item until you reach the index you want. Does homomorphic encryption allow running operations blindly on an encrypted dataset and return encrypted results without ever decrypting the dataset?
    - twicetwice 6y ago
      Sorting (or any other O(N log N) operation) is only "basically a free operation" for small N, and if you're not doing it very often. A billion times log base two of a billion is roughly thirty billion. If an operation takes a billionth of a second, your "basically free operation" is taking thirty seconds. Also, you definitely want to avoid doing an O(N log N) operation more often than you have to. For example, doing for element of listB: listA.add(element) listA.sort() is going to be much, much slower than listA.sort() for element of listB: listA.insertInSortedPosition(element) since "insert in sorted position" should be O(log N) — just use binary search to find the correct position. The first algorithm is O(N^2 log N) while the second algorithm is O(N log N). For any non-negligible N, you definitely don't want to be running in polynomial time if you can avoid it! And can you guarantee your algorithm will never be run on non-negligible N? I mean, yeah, sometimes you can. And in that case, "premature optimization is the root of all evil," sure. If you're just pulling a couple hundred product records out of a database and then sorting them in code, then yeah, an O(N log N) sort is "basically a free operation." But sometimes you want to do more complicated things than that, and then it's not true. So overall I think it's pretty irresponsible to teach that sorting is basically free (without caveats). That's definitely not always true!
- richthegeek 6y ago
  I'm reading this thread and I still can't figure out the point or how it protects things. What client would want to add some numbers without knowing what the result is? I can't imagine any interaction with a database where I don't need to do an operation with the resulting data (even if it's just passing it into a different API/DB unchanged). My interpretation of your example in human terms is "add your day of birth to your bank balance, but don't tell me the answer" and then walking away. What am I missing? -- edit -- Maybe I'm looking at it in the wrong direction? Is it more like "here are some numbers that, add them up on your calculator but don't look at the result before showing it to me"?
  - garmaine 6y ago
    “This thing I’m handing you is a $10 bill. Also, I have a proof that the serial number on it is real, and not duplicated which I can share (the proof) with any third party, to prove my payment or validate the ledger of payments, without revealing which serial number it is (thereby preserving your privacy).” That is essentially what zcash is. So as I said, numerous applications in financial crypto (where we can reasonably spend full seconds on desktop, or minutes on secure hardware grinding away at proof to send funds), but not so practical to spend an even greater amount of time on each database query.
  - dowem 6y ago
    The latter is more like it. It is a case where you want something computed, like the sum of your paychecks over the last year, Or some credit card risk evaluation thing, or if you have markers for cancer in your genome data based on your personal information. Instead of sending these values to the server (perhaps encrypting in flight) where they are processed in plaintext (open to malicious intent on the server-side, or honest-but-curious folks who mine your sensitive personal information) the values, you upload remain encrypted so only you know what they mean. However the cloud side can sum them, perform threshold evaluations, search for things, determine fitness for a loan etc, without knowing anything, they go through the motions of the computation for you, but without being able to decipher anything about the computation result at any step along the way. Then when the server-side is done, it has computed whatever you asked it to do, but knows nothing. The server side reliably and deterministically manipulated symbols in a language it cant read. As it turns out, you can, so when the encrypted server-side results are sent back, you decrypt them and understand if you have been approved or have genetic markers for cancer or something.
vbezhenar 6y ago
80 seconds is not that bad.
- ReactiveJelly 6y ago
  Isn't that about 1000x slowdown?
  - twoodfin 6y ago
    Closer to 1,000,000X, I’d say.
- marcinzm 6y ago
  There's only 50 countries in Europe. This is taking over a second per row in the database. I'm fairly sure a 1950s computer could do better using a regular algorithm.
viraptor 6y ago
We've had lots of problems over last few decades which went from "practically impossible" to "doable on home computers", whether that's with improvements in software or hardware design. Extreme cases - realtime raytracing and fluid simulations, hardware-assisted encryption, practical NN. Why do you think HE value map cannot be ever improved?
- bawolff 6y ago
  I'm of the opinion it can be, but i don't know if a comparison to the era of moore's law is really compelling, since we are not in that world anymore.
remcob 6y ago
It has current practical applications in inter-bank fraud detection, where you want to query if someone is on someone else's blacklist but not reveal the blacklist or the person being queried. These applications can easily handle an 80 sec delay. It's also likely that queries scale well by batching into larger combined queries (since you need to involve every row already anyway).
- jellyksong 6y ago
  A bunch of the papers I found from a quick Google search use secure MPC rather than FHE for interbank fraud. Which one is more practical these days wrt latency?
- sterlind 6y ago
  Because I was confused by this scenario I wrote down the steps: 1. Alice provides Bob with her public and evaluation keys. 2. Bob encrypts each row of the blacklist with her public key. 3. Alice encrypts her query (e.g. for "Eve") and sends to Bob. 4. Bob evaluates some circuit on Alice's query and Bob's rows, and sends her one (encrypted) result per row 5. Alice decrypts the rows and sees if any are ones. Ways this can be made more efficient: * Outputs from each row's evaluation can chain into the next evaluation, so Bob only need return O(1) data. * Bloom filters could cut down on average-case performance, but that would make Alice leak information (whether she follows up her FHE bloom filter query with a more precise query.)

SilasX 6y ago

Currently totally unrealistic in practice, but it's proven that the algorithms are in P (polynomial time), and it's just ("just", I know...) a matter of getting the constant factor overheads down. It's definitely desirable, because it means some untrusted host could perform operations on your data without ever knowing what they were operating on e.g. "I added your numbers but I don't know what they are or their sum."

deleted 6y ago
[deleted]
marcinzm 6y ago
Polynomial time is pretty bad I feel and not due to any constant factor. A search in a regular database with an index is either O(1) or O(log(N)) depending on the design.
deleted 6y ago
[deleted]
a1369209993 6y ago
Indexing a N-element array (a O(log N) operation frequently approximated as O(1)) inside a homomorphic enclave requires O(N) operations. Constant factors exacerbate the problem, but any usefully large database is wholely unsuitable for homomorphic use.
- mdpopescu 6y ago
  Hmm... I don't understand this. O(N) is very fast for most realistic purposes I can come up with. It's faster than sorting - O(N log N) - which I was taught is "basically a free operation". (Coursera class with Tim Roughgarden.)
  - FartyMcFarter 6y ago
    O(N) search is not fast. Hash tables and trees are O(1) or O(lg N) which are vastly faster than O(N). Imagine a database with billions of records. O(N) search on this database will absolutely murder performance.
  - terminalcommand 6y ago
    I am also an amateur in these things. If indexing is O(N), does that mean it has the same performance as a linked list? Basically that would mean you have to go through each and every item until you reach the index you want. Does homomorphic encryption allow running operations blindly on an encrypted dataset and return encrypted results without ever decrypting the dataset?
  - twicetwice 6y ago
    Sorting (or any other O(N log N) operation) is only "basically a free operation" for small N, and if you're not doing it very often. A billion times log base two of a billion is roughly thirty billion. If an operation takes a billionth of a second, your "basically free operation" is taking thirty seconds. Also, you definitely want to avoid doing an O(N log N) operation more often than you have to. For example, doing for element of listB: listA.add(element) listA.sort() is going to be much, much slower than listA.sort() for element of listB: listA.insertInSortedPosition(element) since "insert in sorted position" should be O(log N) — just use binary search to find the correct position. The first algorithm is O(N^2 log N) while the second algorithm is O(N log N). For any non-negligible N, you definitely don't want to be running in polynomial time if you can avoid it! And can you guarantee your algorithm will never be run on non-negligible N? I mean, yeah, sometimes you can. And in that case, "premature optimization is the root of all evil," sure. If you're just pulling a couple hundred product records out of a database and then sorting them in code, then yeah, an O(N log N) sort is "basically a free operation." But sometimes you want to do more complicated things than that, and then it's not true. So overall I think it's pretty irresponsible to teach that sorting is basically free (without caveats). That's definitely not always true!
richthegeek 6y ago
I'm reading this thread and I still can't figure out the point or how it protects things. What client would want to add some numbers without knowing what the result is? I can't imagine any interaction with a database where I don't need to do an operation with the resulting data (even if it's just passing it into a different API/DB unchanged). My interpretation of your example in human terms is "add your day of birth to your bank balance, but don't tell me the answer" and then walking away. What am I missing? -- edit -- Maybe I'm looking at it in the wrong direction? Is it more like "here are some numbers that, add them up on your calculator but don't look at the result before showing it to me"?
- garmaine 6y ago
  “This thing I’m handing you is a $10 bill. Also, I have a proof that the serial number on it is real, and not duplicated which I can share (the proof) with any third party, to prove my payment or validate the ledger of payments, without revealing which serial number it is (thereby preserving your privacy).” That is essentially what zcash is. So as I said, numerous applications in financial crypto (where we can reasonably spend full seconds on desktop, or minutes on secure hardware grinding away at proof to send funds), but not so practical to spend an even greater amount of time on each database query.
- dowem 6y ago
  The latter is more like it. It is a case where you want something computed, like the sum of your paychecks over the last year, Or some credit card risk evaluation thing, or if you have markers for cancer in your genome data based on your personal information. Instead of sending these values to the server (perhaps encrypting in flight) where they are processed in plaintext (open to malicious intent on the server-side, or honest-but-curious folks who mine your sensitive personal information) the values, you upload remain encrypted so only you know what they mean. However the cloud side can sum them, perform threshold evaluations, search for things, determine fitness for a loan etc, without knowing anything, they go through the motions of the computation for you, but without being able to decipher anything about the computation result at any step along the way. Then when the server-side is done, it has computed whatever you asked it to do, but knows nothing. The server side reliably and deterministically manipulated symbols in a language it cant read. As it turns out, you can, so when the encrypted server-side results are sent back, you decrypt them and understand if you have been approved or have genetic markers for cancer or something.

vbezhenar 6y ago

80 seconds is not that bad.

ReactiveJelly 6y ago
Isn't that about 1000x slowdown?
- twoodfin 6y ago
  Closer to 1,000,000X, I’d say.
marcinzm 6y ago
There's only 50 countries in Europe. This is taking over a second per row in the database. I'm fairly sure a 1950s computer could do better using a regular algorithm.

viraptor 6y ago

We've had lots of problems over last few decades which went from "practically impossible" to "doable on home computers", whether that's with improvements in software or hardware design. Extreme cases - realtime raytracing and fluid simulations, hardware-assisted encryption, practical NN. Why do you think HE value map cannot be ever improved?

bawolff 6y ago
I'm of the opinion it can be, but i don't know if a comparison to the era of moore's law is really compelling, since we are not in that world anymore.

remcob 6y ago

It has current practical applications in inter-bank fraud detection, where you want to query if someone is on someone else's blacklist but not reveal the blacklist or the person being queried. These applications can easily handle an 80 sec delay. It's also likely that queries scale well by batching into larger combined queries (since you need to involve every row already anyway).

jellyksong 6y ago
A bunch of the papers I found from a quick Google search use secure MPC rather than FHE for interbank fraud. Which one is more practical these days wrt latency?
sterlind 6y ago
Because I was confused by this scenario I wrote down the steps: 1. Alice provides Bob with her public and evaluation keys. 2. Bob encrypts each row of the blacklist with her public key. 3. Alice encrypts her query (e.g. for "Eve") and sends to Bob. 4. Bob evaluates some circuit on Alice's query and Bob's rows, and sends her one (encrypted) result per row 5. Alice decrypts the rows and sees if any are ones. Ways this can be made more efficient: * Outputs from each row's evaluation can chain into the next evaluation, so Bob only need return O(1) data. * Bloom filters could cut down on average-case performance, but that would make Alice leak information (whether she follows up her FHE bloom filter query with a more precise query.)