Abstract: Search on encrypted data has been focus of research both in database and cryptography communities. Traditionally the results in cryptography community provide strong security guarantees: typically hiding everything but user's access pattern to the server. However, the server needs to scan the whole database for each query, which yields unacceptably-slow performance for practical databases. In contrast, research from database community, provides encryption schemes with efficient and optimized indexing and flexible query support for various data types. But, unfortunately, the security of these schemes is far less clear.
In this talk we will give an overview of a new line of research in cryptography community that tries to narrow this gap. The results in this category mostly investigate the best security guaranties for an encryption scheme which also enables sub-linear (typically logarithmic) search. We will in particular discuss deterministic and order preserving encryption schemes which enable privacy-preserving search for exact-match and range queries respectively with almost the same efficiency of search over un-encrypted data.