International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Seny Kamara

Publications

Year
Venue
Title
2021
EUROCRYPT
Structured Encryption and Dynamic Leakage Suppression
Structured encryption (STE) schemes encrypt data structures in such a way that they can be privately queried. Special cases ofSTE include searchable symmetric encryption (SSE) and graph encryption. Like all sub-linear encrypted search solutions, STE leaks information about queries against persistent adversaries. To address this, a line of work on leakage suppression was recently initiated that focuses on techniques to mitigate or completely remove the leakage of STE schemes (Kamara et al. CRYPTO’18 and Kamara and Moataz, Eurocrypt ’19). A notable example is the cache-based compiler which, when combined with the rebuild compiler, transforms any dynamic STE scheme that leaks the query equality into a new scheme that does not. Unfortunately, this compiler can only produce static schemes and it was left as an open problem to design a compiler that could yield dynamic constructions. In this work, we propose a dynamic variant of the cache-based compiler. Our compiler can transform any volume-hiding semi-dynamic or mutable STE scheme that leaks the query equality pattern into into a new fully-dynamic construction that does not. Using this compiler, we design three new fully-dynamic STE schemes that are “almost” and fully zero-leakage which, under natural assumptions about the data and query distributions, are asymptotically more efficient than using black-box ORAM simulation. These are the first constructions of their kind.
2020
CRYPTO
Crypto for the People 📺
Seny Kamara
2019
EUROCRYPT
Computationally Volume-Hiding Structured Encryption 📺
Seny Kamara Tarik Moataz
We initiate the study of structured encryption schemes with computationally-secure leakage. Specifically, we focus on the design of volume-hiding encrypted multi-maps; that is, of encrypted multi-maps that hide the response length to computationally-bounded adversaries. We describe the first volume-hiding STE schemes that do not rely on naïve padding; that is, padding all tuples to the same length. Our first construction has efficient query complexity and storage but can be lossy. We show, however, that the information loss can be bounded with overwhelming probability for a large class of multi-maps (i.e., with lengths distributed according to a Zipf distribution). Our second construction is not lossy and can achieve storage overhead that is asymptotically better than naïve padding for Zipf-distributed multi-maps. We also show how to further improve the storage when the multi-map is highly concentrated in the sense that it has a large number of tuples with a large intersection. We achieve these results by leveraging computational assumptions; not just for encryption but, more interestingly, to hide the volumes themselves. Our first construction achieves this using a pseudo-random function whereas our second construction achieves this by relying on the conjectured hardness of the planted densest subgraph problem which is a planted variant of the well-studied densest subgraph problem. This assumption was previously used to design public-key encryptions schemes (Applebaum et al., STOC ’10) and to study the computational complexity of financial products (Arora et al., ICS ’10).
2018
CRYPTO
Structured Encryption and Leakage Suppression
Structured encryption (STE) schemes encrypt data structures in such a way that they can be privately queried. One aspect of STE that is still poorly understood is its leakage. In this work, we describe a general framework to design STE schemes that do not leak the query/search pattern (i.e., if and when a query was previously made).Our framework consists of two compilers. The first can be used to make any dynamic STE scheme rebuildable in the sense that the encrypted structures it produces can be rebuilt efficiently using only O(1) client storage. The second transforms any rebuildable scheme that leaks the query/search pattern into a new scheme that does not. Our second compiler is a generalization of Goldreich and Ostrovsky’s square root oblivious RAM (ORAM) solution but does not make use of black-box ORAM simulation. We show that our framework produces STE schemes with query complexity that is asymptotically better than ORAM simulation in certain (natural) settings and comparable to special-purpose oblivious data structures.We use our framework to design a new STE scheme that is “almost” zero-leakage in the sense that it reveals an, intuitively-speaking, small amount of information. We also show how the scheme can be used to achieve zero-leakage queries when one can tolerate a probabilistic guarantee of correctness. This construction results from applying our compilers to a new STE scheme we design called the piggyback scheme. This scheme is a general-purpose STE construction (in the sense that it can encrypt any data structure) that leaks the search/query pattern but hides the response length on non-repeating queries.
2018
ASIACRYPT
SQL on Structurally-Encrypted Databases
Seny Kamara Tarik Moataz
We show how to encrypt a relational database in such a way that it can efficiently support a large class of SQL queries. Our construction is based solely on structured encryption (STE) and does not make use of any property-preserving encryption (PPE) schemes such as deterministic and order-preserving encryption. As such, our approach leaks considerably less than PPE-based solutions which have recently been shown to reveal a lot of information in certain settings (Naveed et al., CCS ’15). Our construction is efficient and—under some conditions on the database and queries—can have asymptotically-optimal query complexity. We also show how to extend our solution to be dynamic while maintaining the scheme’s optimal query complexity.
2017
EUROCRYPT
2015
EPRINT
2015
EPRINT
2010
ASIACRYPT
2009
ASIACRYPT
2008
FSE
2006
EPRINT
Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions
Searchable symmetric encryption (SSE) allows a party to outsource the storage of his data to another party in a private manner, while maintaining the ability to selectively search over it. This problem has been the focus of active research and several security definitions and constructions have been proposed. In this paper we review existing security definitions, pointing out their shortcomings, and propose two new stronger definitions which we prove equivalent. We then present two constructions that we show secure under our new definitions. Interestingly, in addition to satisfying stronger security guarantees, our constructions are more efficient than all previous constructions. Further, prior work on SSE only considered the setting where only the owner of the data is capable of submitting search queries. We consider the natural extension where an arbitrary group of parties other than the owner can submit search queries. We formally define SSE in this multi-user setting, and present an efficient construction.
2005
EPRINT
Key Regression: Enabling Efficient Key Distribution for Secure Distributed Storage
The Plutus file system introduced the notion of key rotation as a means to derive a sequence of temporally-related keys from the most recent key. In this paper we show that, despite natural intuition to the contrary, key rotation schemes cannot generically be used to key other cryptographic objects; in fact, keying an encryption scheme with the output of a key rotation scheme can yield a composite system that is insecure. To address these shortcomings, we introduce a new cryptographic object called a key regression scheme, and we propose three constructions that are provably secure under standard cryptographic assumptions. We implement key regression in a secure file system and empirically show that key regression can significantly reduce the bandwidth requirements of a content publisher under realistic workloads using lazy revocation. Our experiments also serve as the first empirical evaluation of either a key rotation or key regression scheme.

Program Committees

TCC 2020
Crypto 2018
Crypto 2017
PKC 2009