How to Search on Encrypted Data (2013)

>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.

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.