Data breaches are an ever increasing concern nowadays. For instance, the 2017 Equifax breach exposed sensitive financial information of an estimated 143 millions US persons. Furthermore, companies are often powerless to protected themselves as exemplified by Yahoo! which was breached in 2013 and then again in 2014!

As a defense, some security researchers have advocated for the use of always-encrypted databases. A prominent approach to construct always-encrypted databases is to leverage weak forms of encryption which expose, in their ciphertexts, some plaintext information in order to