MACS Project Meeting, September 2017

Date:
Friday, September 8, 2017

Location:
Boston University, Hariri Seminar Room, MCS building room 180

Schedule:

Selected abstracts:

Mayank Varia, Systematization of Knowledge (SoK) on Cryptographically Protected Database Search

Protected database search systems cryptographically isolate the roles of reading from, writing to, and administering the database. This separation limits unnecessary administrator access and protects data in the case of system breaches. Since protected search was introduced in 2000, the area has grown rapidly; systems are offered by academia, start-ups, and established companies.

However, there is no best protected search system or set of techniques. Design of such systems is a balancing act between security, functionality, performance, and usability. This challenge is made more difficult by ongoing database specialization, as some users will want the functionality of SQL, NoSQL, or NewSQL databases. This database evolution will continue, and the protected search community should be able to quickly provide functionality consistent with newly invented databases.

At the same time, the community must accurately and clearly characterize the tradeoffs between different approaches. To address these challenges, we provide the following contributions:

1. An identification of the important primitive operations across database paradigms. We find there are a small number of base operations that can be used and combined to support a large number of database paradigms.
2. An evaluation of the current state of protected search systems in implementing these base operations. This evaluation describes the main approaches and tradeoffs for each base operation. Furthermore, it puts protected search in the context of unprotected search, identifying key gaps in functionality.
3. An analysis of attacks against protected search for different base queries.
4. A roadmap and tools for transforming a protected search system into a protected database, including an open-source performance evaluation platform and initial user opinions of protected search.

Saleet Klein, The Edited Truth

We introduce two new cryptographic notions in the realm of public and symmetric key encryption.

Encryption with invisible edits is an encryption scheme with two tiers of users: “privileged” and “unprivileged”. Privileged users know a key pair (pk,sk) and “unprivileged” users know a key pair (pke,ske) which is associated with an underlying edit e to be applied to messages encrypted. Each key pair on its own works exactly as in standard public-key encryption, but when an unprivileged user attempts to decrypt a ciphertext generated by a privileged user of an underlying plaintext m, it will be decrypted to an edited m’=Edit(m,e). Here, Edit is some supported edit function and e is a description of the particular edit to be applied. For example, we might want the edit to overwrite several sensitive blocks of data, replace all occurrences of one word with a different word, airbrush an encrypted image, etc. A user shouldn’t be able to tell whether he’s an unprivileged or a privileged user.

An encryption with deniable edits is an encryption scheme which allows a user who owns a ciphertext c encrypting a large corpus of data m under a secret key sk, to generate an alternative but legitimate looking secret key sk_(c,e) that decrypts c to an “edited” version of the data m’=Edit(m,e). This generalizes classical receiver deniable encryption, which can be viewed as a special case of deniable edits where the edit function performs a complete replacement of the original data. The new flexibility allows us to design solutions with much smaller key sizes than required in classical receiver deniable encryption, and in particular allows the key size to only scale with the description size of the edit e which can be much smaller than the size of the plaintext data m.

We construct encryption schemes with deniable and invisible edits for any polynomial-time computable edit function under minimal assumptions: in the public-key setting we only require the existence of standard public-key encryption and in the symmetric-key setting we only require the existence of one-way functions. The solutions to both problems use common ideas, however there is a significant conceptual difference between deniable edits and invisible edits. Whereas encryption with deniable edits enables a user to modify the meaning of a single ciphertext in hindsight, the goal of encryption with invisible edits is to enable ongoing modifications of multiple ciphertexts.

Marten van Dijk, Leveraging Hardware Isolation for Process Level Access Control and Authentication

Critical resource sharing among multiple entities in a processing system is inevitable, which in turn calls for the presence of appropriate authentication and access control mechanisms. Generally speaking, these mechanisms are implemented via trusted software “policy checkers” that enforce certain high level application-specific “rules” to enforce a policy. Whether implemented as operating system modules or embedded inside the application ad hoc, these policy checkers expose additional attack surface in addition to the application logic. In order to protect application software from an adversary, modern secure processing platforms, such as Intel’s Software Guard Extensions (SGX), employ principled hardware isolation to offer secure software containers or enclaves to execute trusted sensitive code with some integrity and privacy guarantees against a privileged software adversary. We extend this model further and propose using these hardware isolation mechanisms to shield the authentication and access control logic essential to policy checker software. While relying on the fundamental features of modern secure processors, our framework introduces productive software design guidelines which enable a guarded environment to execute sensitive policy checking code – hence enforcing application control flow integrity – and afford flexibility to the application designer to construct appropriate high-level policies to customize policy checker software.

Ran Canetti, Towards Doubly Efficient Private Information Retrieval

Private Information Retrieval (PIR) allows a client to obtain data from a public database without disclosing the locations accessed. Traditionally, the stress is on preserving sublinear work for the client, while the server’s work is taken to inevitably be at least linear in the database size. Beimel, Ishai and Malkin (JoC 2004) show PIR schemes where, following a linear-work preprocessing stage, the server’s work per query is sublinear in the database size. However, that work only addresses the case of multiple non-colluding servers; the existence of single-server PIR with sublinear server work remained unaddressed.

We consider single-server PIR schemes where, following a preprocessing stage in which the server obtains an encoded version of the database and the client obtains a short key, the per-query work of both server and client is polylogarithmic in the database size. We call such schemes {\em doubly efficient}. Concentrating on the case where the client’s key is secret, we show:

• A scheme, based on one-way functions, that works for a bounded number of queries, and where the server storage is linear in the number of queries plus the database size.
• A scheme for an unbounded number of queries, whose security follows from a new hardness assumption that is related to the hardness of solving a system of noisy linear equations.

We also show the insufficiency of a natural approach for obtaining doubly efficient PIR in the setting where the preprocessing is public.