UC San Diego

We say that cryptographic schemes are "symmetric" whenever the sender and receiver share the same key. In this work we consider and evaluate two forms of such: authenticated encryption (AE) and structured encryption (StE).

AE is used to encrypt messages in a way that guarantees the privacy and integrity of the data therein. Our work draws attention to a gap between the theory and usage of nonces with regard to how nonces are communicated from sender to receiver. We bridge this with a new nonce-hiding treatment of authenticated encryption and propose simple, efficient schemes that conform to these new definitions.

StE is used to encrypt a large database for storage on an untrusted server in such a way that the client retains the ability to perform fast query-based search on the data. We first study the problem of indexing joins in encrypted SQL databases using StE. We introduce a new technique called partially precomputed joins which achieves lower leakage than existing techniques. We devise a hybrid indexing scheme which uses both indexes and provide a client-side leakage aware query optimization heuristic with which the client can choose which index to use at query time. We evaluate our indexing method and heuristic with simulations on real datasets.

We then revisit the idea of Chase and Kamara (ASIACRYPT 2010) to build more complex StE schemes from simple ones via the composition of dictionary and multimap StE. We show that the intuitive composition can run into some subtle issues related to the coordination of their simulators. We then address this situation in two ways. First, we provide a sufficient condition called content obliviousness under which this issue can be resolved. Second, we suggest an alternate monolithic approach that avoids composition altogether which uses a single data structure that supports more complex queries. To analyze this construction, we need a basic form of key-dependent security for StE, so we initiate a theoretical study of such by giving impossibility results, constructing generic transforms and evaluating existing schemes.