This is the third part of a series on searching on encrypted data. See parts 1, 2, 4, 5. Previously, we covered the simplest solution for encrypted search which consisted of using a deterministic encryption scheme (more generally, using a property-preserving encryption scheme) to encrypt keywords. This resulted in an encrypted search solution with sub-linear (in \(n\)) search time but that leaked quite a bit of information to the server.