4 ms·
This is super cool! For a long time I've wanted a database in the cloud where my cloud provider can't quietly look through all my data. Thats easy enough to do
by josephg 5y ago
This is super cool! For a long time I've wanted a database in the cloud where my cloud provider can't quietly look through all my data. Thats easy enough to do by encrypting specific database entries, but the problem comes from indexing. Most of the obvious ways you could implement an index accidentally end up leaking information as a result of their access patterns.
I'm curious if this approach could be used to build database indexes, and if so, whats the performance cost in using it?
I read about an approach a few years ago which needed hundreds of milliseconds of computation for simple operations. Has the state of the art improved?
- warkdarrior 5y agoFor (database) index structures, you want something like Oblix: https://people.eecs.berkeley.edu/~raluca/oblix.pdf https://people.eecs.berkeley.edu/~raluca/oblix.pdf [PDF]
- Ar-Curunir 5y agoMore generally you want systems that implement oblivious accesses. There’s been a lot of cool work recently in making thi more practical, and I’m excited to see how it pans out in the near future :) I will also note that for efficiency, Oblix relies on Intel SGX. I’m not sure if a purely cryptographic solution can provide the same security and efficiency properties.
- warkdarrior 5y agoORAM provides the purely cryptographic solution, but you have to pick your scheme based on the amount of leakage you are willing to have. In the worst case accessing one row in a database would require reading the whole database.
- ignoramous 5y agoWell, FHE may not be there yet but there are other approaches using functional encryption (?) [ref] concepts, like this one I stumbled upon: https://www.cossacklabs.com/blog/secure-search-over-encrypted-data-acra-se.html https://www.cossacklabs.com/blog/secure-search-over-encrypte... [ref] https://cseweb.ucsd.edu/~daniele/LatticeLinks/FE.html https://cseweb.ucsd.edu/~daniele/LatticeLinks/FE.html
- ipsum2 5y ago> I read about an approach a few years ago which needed hundreds of milliseconds of computation for simple operations. Has the state of the art improved? Google still relies on the same group you read about, probably. From the docs: > This transpiler connects Google’s XLS library to the TFHE library. On the TFHE website (https://tfhe.github.io/tfhe/ https://tfhe.github.io/tfhe/): > Each binary gate takes about 13 milliseconds single-core time to evaluate, which improves [DM15] by a factor 53, and the mux gate takes about 26 CPU-ms.
- disgruntledphd2 5y agoAs a minor pedantic point, this is just someone who works at Google's side project, they have disclaimers in the docs, but it's released by "Google" because of their IP policy, AFAIK.
- ipsum2 5y agoNo, probably not. They have an entire team on it, and has an official Google blog post: https://developers.googleblog.com/2021/06/our-latest-updates-on-fully-homomorphic-encryption.html https://developers.googleblog.com/2021/06/our-latest-updates...
- disgruntledphd2 5y agoYeah, I saw that post later, and was pleasantly surprised that they seem to be putting work into it.
- deleted 5y ago[deleted]
- jcbsd 5y agoThe state of the art has definitely improved. Zama are doing something called 'programmable bootstrapping' which can enable efficient (e.g., faster) Homomorphic Inference on deep neural networks -- https://whitepaper.zama.ai/whitepaper.pdf?_ga=2.218937936.879794490.1623664533-158940722.1622744631 https://whitepaper.zama.ai/whitepaper.pdf?_ga=2.218937936.87... Good question about database indexes; that could be an interesting use case study.