Grassroots organizing requires establishing trust in digital artifacts (like event announcements or calls to action) while navigating significant security threats including surveillance, infiltration, and state violence. Traditional trust infrastructures like PKI and Web of Trust fail to address these specific needs, as they create public records of trust relationships that can expose activist networks and require institutional involvement that may be inaccessible or dangerous for marginalized communities. To address this, we introduce tigro, a novel trust infrastructure and system designed specifically for grassroots organizing contexts. Unlike conventional trust infrastructures, tigro implements a two-tier trust model: ground trust, which cryptographically binds digital annotations to physically vetted individuals, and artifact trust, which enables private, need-to-know sharing of assessments about digital content via annotations. Our protocol begins with an in-person key exchange that establishes a shared cryptographic key, creating a secure bridge between activists' existing physical vetting practices and their digital trust needs. To realize this approach, we define a new cryptographic primitive called an encrypted annotation system (EAS) and construct tigro using structured encryption and anonymous channels. We present two implementations with different security-performance tradeoffs: an efficient version for practical deployment that handles annotations in under a second, and a subliminal version that reveals virtually no metadata. Through this design, tigro enables activists to securely verify digital content without compromising relationship privacy or creating surveillance vulnerabilities, addressing a critical gap in existing trust infrastructure.

Encrypted data structures are essential for designing efficient encrypted search algorithms and secure databases. However, a critical aspect that has not been adequately addressed is the concurrent nature of modern databases, which allow multiple operations to be executed simultaneously. Agarwal, Kamara, and Moataz (Asiacrypt 2024) recently initiated the study of concurrent encrypted data structures and introduced formalisms for their design and analysis.Building on their foundational work, we adapt their security definitions to support sequential consistency instead of linearizability. While linearizability offers a strong correctness guarantee by ensuring operations appear to occur instantaneously, sequential consistency allows operations to be executed in a consistent order without immediate synchronization across clients, making it more efficient for concurrent environments. We present a new concurrent encrypted multimap (EMM), denoted as SCM, which achieves sequential consistency and provides significant improvements in both asymptotic and empirical efficiency compared to their linearizable EMM scheme, TST.Additionally, we develop a benchmarking suite designed to assess the performance of concurrent EMMs, extending the widely used YCSB benchmark to accommodate multimaps that allow multiple values to be associated with a single key. Our results demonstrate that SCM outperforms TST across various workloads and datasets, especially as the number of concurrent operations increases. In our experiments with 16 concurrent clients, SCM has up to 357× faster P95 read latency (with the best read performance as the overall percentage of reads decreases) and up to 69× faster P95 write latency (with the best write performance as the percentage of writes approaches 50%) than TST, demonstrating SCM effectively balances efficiency and correctness.

Data analytics is a core part of modern decision making, especially in public policy. However, there exists a tension between data privacy and otherwise socially beneficial analytics when data sources contain personal information. We design Synq, a system that supports analytics over encrypted data while accounting for the usability considerations institutions may have when conducting studies that affect public policy. We specifically use an application-centric approach and model Synq’s design requirements from a large-scale series of studies conducted on the opioid epidemic in Massachusetts. We systematize the design considerations of the public policy context and demonstrate how the combination of design considerations that Synq addresses is novel through a survey of the literature. We then present our protocol which combines structured encryption, somewhat homomorphic encryption, and oblivious pseudorandom functions to support a complex query language that includes filtering (retrieving rows by attribute/value pairs), linking (merging rows from different tables that represent the same individual) and aggregate functions (sum, count, average, variance, regression). We formally express the security of our protocol and show that Synq is efficient in practice while satisfying usability considerations that are critical to deployment in the setting of public policy studies.

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.