International Association
for Cryptologic Research

Encrypted data structures have received a lot of attention due to their use as building blocks in the design of fast encrypted search algorithms and encrypted databases. An important design aspect that, as far as we know, has not been considered is that modern server architectures are concurrent in the sense that they support the execution of multiple operations simultaneously. In this work, we initiate the study of concurrent encrypted data structures. We identify new definitional and technical challenges posed by concurrency in the setting of encrypted search. In order to formalize the security of these schemes, we extend the standard framework of structured encryption to capture, among other things, fine-grained leakage which occurs at the instruction level as well as schedule-dependent leakage which changes as a function of the order in which instructions are executed. The latter is particularly challenging to handle when the scheduler is adversarial and adaptive. We provide security definitions in the ideal/real-world model which allows us to capture both security and consistency together. We combine techniques from structured encryption and concurrent data structures to design the first concurrent encrypted multi-map. We show that it is not only secure and efficient, but also satisfies a strong consistency guarantee called linearizability while supporting lock-free append operations and requiring no inter-client communication.

Recent work on dynamic structured and searchable symmetric encryption has focused on achieving the notion of forward-privacy. This is mainly motivated by the claim that forward privacy protects against adaptive file injection attacks (Zhang, Katz, Papamanthou, Usenix Security, 2016). In this work, we revisit the notion of forward-privacy in several respects. First, we observe that forward-privacy does not necessarily guarantee security against adaptive file injection attacks if a scheme reveals other leakage patterns like the query equality. We then propose a notion of security called correlation security which generalizes forward privacy. We then show how correlation security can be used to formally define security against different kinds of injection attacks. We then propose the first injection-secure multi-map encryption encryption scheme and use it as a building block to design the first injection-secure searchable symmetric encryption (SSE) scheme. Towards achieving this, we also propose a new fully-dynamic volume-hiding multi-map encryption scheme which may be of independent interest.

Grassroots organizers are people who work from within communities to effect economic, environmental, social, or political change. Engagement, communication, and trust between community members are vital to the success of grassroots movements. Grassroots organizers have therefore developed long-standing community-based trust and communication protocols that are grounded in physical community spaces such as schools, libraries, town halls, community centers, places of worship, parks, and streets. Digital networking tools afford organizers the ability to engage more people, quickly disseminate important information, and decentralize movements for change. However, they also increase the level of personal risk that communities face by organizing, since the visibility of personal information and communication on social media facilitates surveillance, disinformation, infiltration, and ultimately physical violence from law enforcement, hate groups, and foreign governments. In this talk, we will explore the question: How might we use cryptographic tools to adapt the existing trust and communication protocols of grassroots organizers from physical to digital spaces, without increasing the risk of surveillance, disinformation, and infiltration of grassroots movements?

Motivated by calls for privacy and data breaches of cloud services, efforts to broadly deploy Encrypted Search Algorithms (ESAs) are moving forward. ESAs allow search on encrypted data and can be found in research as well as industry. As all practical solutions leak some information, cryptanalysis plays an important role in the area of encrypted search. Many attacks have been proposed that exploit different leakage profiles under various assumptions. While leakage attacks aim to improve our common understanding of leakage, it is difficult to draw definite conclusions about their practical risk. This uncertainty stems from many limitations including a lack of reproducibility due to closed-source implementations, empirical evaluations conducted on small and/or unrealistic data, and reliance on very strong assumptions that can significantly affect accuracy. Particularly, assumptions made about the query distribution do not have any empirical basis because datasets containing users' queries are hard to find. In this talk, we present results from our extensive re-evaluation of leakage attacks on many new datasets in a variety of use cases that - for the first time - include query data. We show that in many of these cases the practical risk of leakage is not as expected. Moreover, the evaluations and conclusions of our work are far from final and still suffer from the fact that for increasingly practical studies of attacks more (especially query) data is desperately needed, which is largely unavailable to researchers. We therefore also cover the remaining challenges from both a research and an industry perspective towards practically assessing the security of ESAs to enable adequate deployments.

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.

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).

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.

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.