How to Search on Encrypted Data: Oblivious RAMs (Part 4)

This is the fourth part of a series on searching on encrypted data. See parts 1, 2, 3, 5. In the previous posts we covered two different ways to search on encrypted data. The first was based on property-preserving encryption (in particular, on deterministic encryption), achieved sub-linear search time but had weak security properties. The second was based on functional encryption, achieved linear search time but provided stronger security guarantees.