5 ms·
How to Search on Encrypted Data (2013)
- katella 3y agoI wonder if zk can be used?
- noam_k 3y agoNo, ZK solves a different problem. (Namely: providing a proof (usually of knowledge), without compromising some secret information.)
- xyzzy4747 3y agoSunscreen could be used: https://docs.sunscreen.tech/fhe/fhe_programs/pir_intro.html https://docs.sunscreen.tech/fhe/fhe_programs/pir_intro.html >With private information retrieval (PIR), a user can retrieve an item from a database without revealing to the server which item she's interested in. PIR is useful for both web2 and web3 applications. In web2, for example, PIR can be used to help detect harmful images in end-to-end encrypted messaging. For private cryptocurrencies, PIR can help light clients retrieve relevant transactions.
- bawolff 3y agoPIR is usually about preventing the server from knowing what subset of data a specific client is retrieving, not preventing the server from knowing the contents of the database. So i don't really see the applicability.
- munchler 3y agoAs a programmer with little crypto experience, the thing that jumped out at me about the first solution is that it only supports searching for a predetermined set of keywords. That makes the problem much easier and seems like a pretty major limitation.
- cantrevealname 3y ago> The High-Level Idea ... where di,j=EncDK2(wi,j), ci=EncRK1(Di) and ptr(ci) is a pointer to ciphertext c My eyes just glaze over when even the "high-level explanation" jumps into formal notation like this. I wish the article would spend a few more sentences explaining each of the 6 ideas in plain English and with simple examples. Here, I'll do a high-level explanation of idea #1, property-preserving encryption: Imagine that in a database of encrypted emails you might need to search for keywords like payroll, revenue, and dividends. Before encrypting and uploading the emails to the server, you would pick out all the likely keywords and encrypt them individually. So that payroll becomes 6hD4jFFjk, revenue is GG5fDK00hFFC, and dividends turns into IbggfFJJ7h. You would them upload the encrypted emails and the list of encrypted keywords (6hD4jFFjk, GG5fDK00hFFC, IbggfFJJ7h). If you later wanted to see all the emails that mentioned payroll, you would encrypt the word payroll on the client side (i.e., on your own computer) to get 6hD4jFFjk again, then send a request to the server to find all emails containing the string 6hD4jFFjk. The server would send back to you all the encrypted emails containing 6hD4jFFjk. For this idea to work, you would have to use a method of encryption where the same plaintext word always turns into the same ciphertext string. This way of encrypting data is almost never used these days because it leaks a lot information. For example, the server knows that every occurrence of the string 6hD4jFFjk must refer to the same word. Therefore, although this method would work and be acceptably fast, it would be considered extremely poor security.
- username135 3y agoTo absolutely reduce this idea you could probably say 'vlookup = bad'
- _a_a_a_ 3y agoAgree. Moar of this kind of thing plz.
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- jll29 3y agoMinor correction: "Practical Techniques for Searches on Encrypted Data" by Song et al. was published in 2000, not in 2001 (at the IEEE S&P conf.).