In today’s digital landscape, our interactions, from professional collaborations to personal data sharing involving photos, movies, and documents, have largely moved online. While transitioning these activities to digital platforms provides considerable convenience, it poses significant challenges in efficiently managing and securely erasing shared data in compliance with privacy regulations. Digital forgetting, particularly in co-owned data, transcends being merely desirable and becomes a mandate. Conventional data management paradigms, including cryptographic erasure techniques, typically apply uniform deletion across all stakeholders, neglecting audience-specific expiration and co-owner participation in deletion, which limits their applicability in contemporary cloud storage ecosystems. This article introduces a Policy-Based Conjunctive Scheme (PBCS) that enables conjunctive decision-making for data access and collaborative data forgetting, aligning with the General Data Protection Regulation (GDPR)’s Right to be Forgotten (RTBF). PBCS allows owners to upload their data to the cloud securely and offers policy-based access control to co-owners, granting them the ability to influence decisions about data deletion via democratic voting mechanisms significantly. The scheme leverages conjunctive access thresholds and mechanisms that gradually make data irretrievable. By integrating cryptographic primitives and Lagrange interpolation-based decay, PBCS supports a flexible, conjunctive governance model that upholds privacy and enhances the data lifecycle. We provide a formal analysis and an experimental evaluation of our scheme.

We revisit the problem of Authorized Private Set Intersection (APSI), which allows mutually untrusting parties to authorize their items using a trusted third-party judge before privately computing the intersection. We also initiate the study of Partial-APSI, a novel privacy-preserving generalization of APSI in which the client only reveals a subset of their items to a third-party semi-honest judge for authorization. Partial-APSI allows for partial verification of the set, preserving the privacy of the party whose items are being verified. Both APSI and Partial-APSI have a number of applications, including genome matching, ad conversion, and compliance with privacy policies such as the GDPR. We present two protocols based on bilinear pairings with linear communication. The first realizes the APSI functionality, is secure against a malicious client, and requires only one round of communication during the online phase. Our second protocol realizes the Partial-APSI functionality and is secure against a client that may maliciously inject elements into its input set, but who follows the protocol semi-honestly otherwise. We formally prove correctness and security of these protocols and provide an experimental evaluation to demonstrate their practicality. Our protocols can be efficiently run on commodity hardware. We also show that our protocols are massively parallelizable by running our experiments on a compute grid across 50 cores.

Leakage-abuse attacks using access pattern leakage from range queries have been shown to reconstruct encrypted databases. However, prior work is either restricted to one-dimensional databases or requires access to all possible responses in two-dimensions. In this paper, we explore what an adversary can achieve with minimal leakage, focusing on denser databases, and present a leakage abuse attack from access pattern of range queries in multiple dimensions. Our attack employs a novel technique to systematically amplify access pattern leakage, inferring a large number of new query responses that have not been requested by the user. Let m be the size of the database domain. Our attack works on d-dimensional databases and achieves approximate reconstruction. For dense databases and a parameter 0 < λ < 1, our attack fully reconstructs an inner portion of size λm of the database (referred to as the λ-core) after observing O(m log m) queries, uniformly at random. These are significant improvements over previous attacks that require the full set of responses, which has size O(m2). We are the first to leverage graph drawing techniques for database reconstruction attacks. We implement our attack and evaluate it with experiments on real-world databases, achieving accurate reconstructions after observing a small percentage of the responses.

In this work, we present the first database reconstruction attacks against response-hiding private range search schemes on encrypted databases of arbitrary dimensions. Falzon et al. (VLDB 2022) present a number of range-supporting schemes on arbitrary dimensions exhibiting different security and efficiency trade-offs. Additionally, they characterize a form of leakage, structure pattern leakage, also present in many one-dimensional schemes e.g., Demertzis et al. (SIGMOD 2016) and Faber et al. (ESORICS 2015). We present the first systematic study of this leakage and attack a broad collection of schemes, including schemes that allow the responses to contain false-positives (often considered the gold standard in security). We characterize the information theoretic limitations of a passive persistent adversary. Our work shows that for range queries, structure pattern leakage can be as vulnerable to attacks as access pattern leakage. We give a comprehensive evaluation of our attacks with a complexity analysis, a prototype implementation, and an experimental assessment on real-world datasets.

We present ARQ, a systematic framework for creating cryptographic schemes that handle range aggregate queries (sum, minimum, median, and mode) over encrypted datasets. Our framework does not rely on trusted hardware or specialized cryptographic primitives such as property-preserving or homomorphic encryption. Instead, ARQ unifies structures from the plaintext data management community with existing structured encryption primitives. We prove how such combinations yield efficient (and secure) constructions in the encrypted setting. We also propose a series of domain reduction techniques that can improve the space efficiency of our schemes against sparse datasets at the cost of small leakage. As part of this work, we designed and implemented a new, open-source, encrypted search library called Arca and implemented the ARQ framework using this library in order to evaluate ARQ’s practicality. Our experiments on real-world datasets demonstrate the efficiency of the schemes derived from ARQ in comparison to prior work.

This work addresses expressive queries over encrypted data by presenting the first systematic study of multi-attribute range search on a symmetrically encrypted database outsourced to an honest-but-curious server. Prior work includes a thorough analysis of single-attribute range search schemes (e.g. Demertzis et al. 2016) and a proposed high-level approach for multi-attribute schemes (De Capitani di Vimercati et al. 2021). We first introduce a flexible framework for building secure range search schemes over multiple attributes (dimensions) by adapting a broad class of geometric search data structures to operate on encrypted data. Our framework encompasses widely used data structures such as multi-dimensional range trees and quadtrees, and has strong security properties that we formally prove. We then develop six concrete highly parallelizable range search schemes within our framework that offer a sliding scale of efficiency and security tradeoffs to suit the needs of the application. We evaluate our schemes with a formal complexity and security analysis, a prototype implementation, and an experimental evaluation on real-world datasets.

Access and search pattern leakage from range queries are detrimental to the security of encrypted databases, as evidenced by a large body of work on attacks that reconstruct one-dimensional databases. Recently, the first attack from 2D range queries showed that higher-dimensional databases are also in danger (Falzon et al. CCS 2020). Their attack requires the access and search pattern of all possible queries. We present an order reconstruction attack that only depends on access pattern leakage, and empirically show that the order allows the attacker to infer the geometry of the underlying data. Notably, this attack also achieves full database reconstruction when the 1D horizontal and vertical projections of the points are dense. We also give an approximate database reconstruction attack that is distribution-agnostic and works with any sample of queries, given the search pattern and access pattern leakage of those queries, and the order of the database records. Finally, we show how to improve the reconstruction given knowledge of auxiliary information (e.g., the centroid of a related dataset). We support our results with formal analysis and experiments on real-world databases with queries drawn from various distributions.

In the past few years, we have seen multiple attacks on one-dimensional databases that support range queries. These attacks achieve full database reconstruction by exploiting access pattern leakage along with known query distribution or search pattern leakage. We are the first to go beyond one dimension, exploring this threat in two dimensions. We unveil an intrinsic limitation of reconstruction attacks by showing that there can be an exponential number of distinct databases that produce equivalent leakage. Next, we present a full database reconstruction attack. Our algorithm runs in polynomial time and returns a poly-size encoding of all databases consistent with the given leakage profile. We implement our algorithm and observe real-world databases that admit a large number of equivalent databases, which aligns with our theoretical results.

In this article, we study the leader election problem in the Signal-to-Interference-plus-Noise-Ratio (SINR) model where nodes can adjust their transmission power. We show that in this setting it is possible to solve the leader election problem in two communication rounds, with high probability. Previously, it was known that Omega(log n) rounds were sufficient and necessary when using uniform power, where n is the number of nodes in the network.