9 ms·

The example is called "Privacy Preserving Search". If the server could see which row was accessed, that would not satisfy the privacy requirement. This implies

• skybrian 6y ago
  I'm wondering if this sort of thing would fit well with GPU processing, which tends not to do well with branchy code?
  • remcob 6y ago
    People are working on it. The biggest problem is that cryptography usually requires bignum math and GPUs are not optimized for that. FPGAs are also being researched. The cost/benefit is not as big as you would imagine, CPUs are pretty optimized for bignum math.
    • mattmar96 6y ago
      I attended the event celebrating the solving of LCS35. LCS35 was a cryptographic challenge set by Ron Rivest (the R in RSA) in 1999. It was intended to be so difficult that only computers made 35 years in the future would be able to solve it. The challenge was solved by Bernard Fabrot. It was fairly simple code on I believe an intel 4770K. The math libraries and CPU had been optimized so much in the ~20 years since the challenge was set that a consumer CPU could calculate the answer. The only catch is that it took months on end of calculation. https://en.m.wikipedia.org/wiki/LCS35 https://en.m.wikipedia.org/wiki/LCS35
  • sterlind 6y ago
    NuFHE can do a binary operations in 0.1ms/bit, and mux operations in 0.2ms/bit using FFT, which is hyperoptimized on GPUs. I think the issue is that the keys tend to be rather large.. NuFHE's decryption keys are 110MB! So memory/FFT problem size may be the bottleneck now.
• viraptor 6y ago
  Does it actually have to process all rows equally? Would a bit of randomisation on search + erasure coding of data could allow both reconstruction of message, and preserving secrecy by querying random places for the same information?
  • remcob 6y ago
    I was oversimplifying to convey an intuition on why this is so hard. But yes, this is an active area of research. In this academic field the standard for privacy is usually extremely high. Even if you only access half of the rows, that still leaks one bit of information and would not be considered zero-knowledge.
    • crazypython 6y ago
      Well, the returned value leaks all the bits of information, unless that is randomized too to prevent replay attacks.
      • remcob 6y ago
        In homomorphic systems the server only sees the encrypted result. Since it can not decrypt it, it doesn't gain any information from it. And indeed the encryption is scrambled differently for each query, otherwise you could learn if two values are the same.
• plerpin 6y ago
  I'm getting a kick out of these performance numbers. It's a common refrain on HN condemning $BIG_COMPANY for not using homomorphic encryption for $CLOUD_SERVICE. With these performance numbers in hand, I'm finding those posts retroactively hilarious.
  • remcob 6y ago
    You should compare them to what the performance numbers where 5 and 10 years ago. Homomorphic crypto systems have become many orders of magnitude faster quite rapidly. While they are still no where near non-homomorphic solutions (and likely won't ever be), they have only recently become practical for applications where performance doesn't matter and privacy is valuable (in the sense that people pay a premium for it, which is often not the case).
  • cakoose 6y ago
    Is it really that common? I often see HN posts calling for end-to-end encryption, but not homomorphic encryption. (But even "just" end-to-end encryption is more difficult than many realize.)
    • Andrew_nenakhov 6y ago
      Most people asking for mandatory e2ee everywhere to protect their privace do so only because they have heard from someone that it is a good idea. Most often they do not understand the tradeoffs that come with mandatory e2ee (difficult information transfer, easy loss of data, no server-side search, etc), and are not ready to deal with them.
  • bawolff 6y ago
    Do people really condemn companies for not using FHE? Anyone who knows anything even remotely about FHE knows that its not practical in real applications yet, and won't be for a while.
    • andrewflnr 6y ago
      I can't think of any such instances. I suspect GP is thinking of something else.
• marta_morena_24 6y ago
  Why would you have to process "all" the rows equally? It should be more than sufficient for almost any practical scenario to use some constant factor of "scattering", i.e. access 100 random rows + 1 row that you actually are interested in. It will probably be more complicated than that, due to repeated queries revealing patterns, but there are other mitigations for that, some of which are sure being developed.
  • jhanschoo 6y ago
    If you omit half the rows, you may already have gained a lot of information about the retrieval purpose. Retrieval purposes do not scale by the number of rows needed to be retrieved. You also run into the problem that different retrieval purposes require different number of rows to be retrieved.
  • StrangeDoctor 6y ago
    You could trade off some security for speed like that, but 100 rows wouldn’t cut it. Ask for the same information again and you’ll probably only have 1 intersection. Even if you read half of the rows unnecessarily, you could figure out the true row in between 2 and approximately log2(rows) reads. Just isn’t worth the side channel attack.
    • snovv_crash 6y ago
      If it's the same query, it would be the same 100 random rows, wouldn't it? Then repeated queries wouldn't leak.
      • PeterisP 6y ago
        No, if you run the same query the server must not be able to determine that it was the same query. Repeated invocations of the same question would be transformed with added noise during encryption so that the encrypted query and answer is different each time. If the same query would access the same 100 random rows, then after seeing your (hidden) query and getting the 100-random-row signature it would be trivial to run a bunch of candidates and see which one of them gets the same 100-random-row signature and thus figure out what you queried.
• bawolff 6y ago
  FHE has a lot of properties beyond just those needed to search a db. If you have a specific application in mind there may be more efficient things. E.g. if you want to keep secret what you are looking at but server knows the keys, see research on private information retrieval. See also some of the research on order preserving encryption and the like (although lots of those schemes have questionable security properties). Of course everything has tradeoffs, but often "perfect" security is unnessary in an application.
• microcolonel 6y ago
  Seems like the constraints of this basically mean that you might as well just stream the database to the client and let them do the query.
  • occamrazor 6y ago
    You nay also want to limit the client’s access to the data: e.g. limit the number or types of queries, which, depending on the encryption type, may require data to be processed on the server.
  • bawolff 6y ago
    One of the scenarios is that the cloud provider has an algorithm they want to keep secret. Clients want to use the algorithm but dont trust cloud provider with their data. Honestly though, i mostly find FHE interesting theoretically. The fact that its possible at all is black magic. I'm sure if it ever gets remotely efficient people will come up with more creative applications, but in the meanwhile its resesrch worth it for research sake.
    • TeMPOraL 6y ago
      > One of the scenarios is that the cloud provider has an algorithm they want to keep secret. Clients want to use the algorithm but dont trust cloud provider with their data. That would indeed go a long way towards resolving the issues caused by the way SaaS is done. It would let us decouple compute provider from the service, in a way in which it would be the end users who are free to chose where the computation happens, and they'd own all the data by default, while the business secrets and IP of the service provider would still be protected. Shame to see it's so computationally expensive, I was really hoping this kind of computing would take off.
  • russfink 6y ago
    Your point alludes to the requirements one must consider before implementing private search: query privacy, and bandwidth efficiency. If I need only privacy, then do as you suggest. If I need only bandwidth efficiency, then reveal the query to the server. Thanks for bringing this up.
• Taek 6y ago
  You can use tricks to reduce this requirement. For example, you access a random subset, and at the same time you randomly rearrange a portion of the data. Viewer can't narrow anything down because you are shuffling fast enough to invalidate anything they learn from your access patterns.
  • heavenlyblue 6y ago
    You should be able to relax even that assumption: if the executor doesn’t know the contents of the database itself, then it may not even matter to you that they can correlate your query with the row in the database (they can build a book of correlations but they still would not be able to see the contents). It should be even more feasible if the query contains some random nonce too?
    • Someone 6y ago
      If they can correlate you with rows in the database, and they can correlate me with rows in the database, they can correlate you with me. Given enough queries and perseverance in unraveling things, a surprising amount of information can leak, for example whether you and me live in the same country, frequently travel together (indicating a relationship), etc.
      • heavenlyblue 6y ago
        I said “relax the condition” and also said “they know nothing about the information stored in the database”. I am trying to see whether I am missing something and you’re adding things I removed back into the equation.
        • sukilot 6y ago
          I think what you are missing is yet your assumptions are unreasonable and unrealistic. If we could just keep our data secret, we wouldn't need encryption at all.
    • Taek 6y ago
• dowem 6y ago
  In the algorithm implemented the search key is matched against all rows in the database. There is no short circuit evaluation and there cannot be... you cannot compare an encrypted value to a plaintext value and know they are equivalent without decrypting it first (which the server-side cannot do). This is true even for writing the code to do the search since you cannot do and if style comparison on encrypted values to break out of a loop. In the example, each value stored in the database is compared to the encrypted search term producing a partial result that is itself encrypted and meaningless to the server side. Once ALL value rows have been searched, the partial results (all those encrypted meaningless things) of all those comparisons are combined to yield a single encrypted result which is returned to the user that initiated the search. That result is then decrypted. There is no leakage because ALL code paths and all data must be evaluated for the program every time. However, from what I gather, the database can be shattered across multiple backend servers and each subset could be searched in parallel for a speedup for a practical deployment.