As part of a series of four consecutive research programs through IARPA (APP, SPAR, ENTACT, SPARSE), we developed our searchable-encryption backend Secure Database (SDB). The power of SDB extends beyond the protections of basic searchable encryption by protecting the privacy of all system users:
- Data Owners
- Queriers
- System/Policy Regulators
Standard backends providing searchable encryption – that is, search over encrypted records – typically only provide limited protections for the underlying data being searched, thereby giving partial protection to data owners. By contrast, SDB encrypts not only the stored records, but also the search query being issued. In essence, this means that SDB is able to successfully return the results of a query, without being able to decipher either the query, which records match it, or the content of those records!
Additionally, SDB can enforce policies that limit what kinds of queries can be issued (e.g., “Do not allow queries that specify both a location and time”), who can submit a query, or which/how many records are allowed to be retrieved (e.g. “Do not return results if fewer than 5 results match”). The policy-enforcement mechanism itself is also protected, meaning that the policy rules are encrypted, and policy checking of the query and/or query results is all performed under encryption. If desired, the policy-check result can also be hidden, both from the database server as well as the searcher (e.g. the searcher only sees “no results returned,” but is unable to determine whether this is due to a policy violation or a lack of matching records).
In addition to providing protection for all three categories of system users above, SDB protects against indirect forms of leakage that most searchable encryption solutions are susceptible to. Namely, in SDB, the database server does not learn how many records matched nor which records matched. Note that hiding which records matched is an important property, even if the records are encrypted. For example, suppose an encrypted database was able to observe that the same record was being retrieved over and over again. This could lead to a number of attacks/vulnerabilities, e.g. knowing which records to delete/modify for maximal harm, or learning unacceptable things by cross-referencing this knowledge with other information available from (unencrypted) metadata, such as when the record in question was created or who created it. SDB protects against all such information leakage; indeed, even if an identical query is issued twice in a row, the database server not only does not realize it is serving an identical query (since all queries are encrypted), but it also does not realize that it has fetched the identical set of matching records.
While the privacy protections of SDB are unparalleled, the resulting performance hit is tolerable for most settings. We have demonstrated the viability of running SDB on tens of millions of records, storing terabytes of data. When comparing SDB to an off-the-shelf unencrypted search technology (e.g. mySQL), the end-to-end throughput suffers only by a factor of 3-4x, which is negligible in many practical scenarios and tolerable in most scenarios. For example, on a database consisting of over a million records (each record having multiple searchable attributes), most queries return results in under 20 seconds.
It is through a blend of cryptographic tools and in-house developed protocols that SDB is able to achieve the rigorous privacy protections with minimal impact on performance. Namely, SDB features components built upon MPC, FSS, and ORAM subprotocols, each of which were developed by our team of engineers to deliver cutting edge performance metrics without compromising on security or privacy. Indeed, the research we conducted as part our work on SDB led to a number of theoretic advancements in these respective subfields of cryptography, as demonstrated by the resulting publications, e.g., “Private Large-Scale Databases with Distributed Searchable Symmetric Encryption.”
This work was supported in part by the Intelligence Advanced Research Projects Activity (IARPA) via Department of Interior National Business Center (DoI/NBC) contract number D11PC20199.