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.

New privacy laws like the European Union's General Data Protection Regulation (GDPR) require database administrators (DBAs) to identify all information related to an individual on request, e.g. , to return or delete it. This requires time-consuming manual labor today, particularly for legacy schemas and applications. In this paper, we investigate what it takes to provide mostly-automated tools that assist DBAs in GDPR-compliant data extraction for legacy databases. We find that a combination of techniques is needed to realize a tool that works for the databases of real-world applications, such as web applications, which may violate strict normal forms or encode data relationships in bespoke ways. Our tool, GDPRizer, relies on foreign keys, query logs that identify implied relationships, data-driven methods, and coarse-grained annotations provided by the DBA to extract an individual's data. In a case study with three popular web applications, GDPRizer achieves 100% precision and 96--100% recall. GDPRizer saves work compared to hand-written queries, and while manual verification of its outputs is required, GDPRizer simplifies privacy compliance.

Blockchain databases are storage systems that combine properties of blockchains and databases like decentralization, tamperproofness, low query latency and support for complex queries. Blockchain databases are an emerging and important class of blockchain technology that is critical to the development of non-trivial smart contracts, distributed applications and decentralized marketplaces.

Abstract The problem of privatizing statistical databases is a well-studied topic that has culminated with the notion of differential privacy. The complementary problem of securing these differentially private databases, however, has—as far as we know—not been considered in the past. While the security of private databases is in theory orthogonal to the problem of private statistical analysis (e.g., in the central model of differential privacy the curator is trusted) the recent real-world deployments of differentially-private systems suggest that it will become a problem of increasing importance. In this work, we consider the problem of designing encrypted databases (EDB) that support differentially-private statistical queries. More precisely, these EDBs should support a set of encrypted operations with which a curator can securely query and manage its data, and a set of private operations with which an analyst can privately analyze the data. Using such an EDB, a curator can securely outsource its database to an untrusted server (e.g., on-premise or in the cloud) while still allowing an analyst to privately query it. We show how to design an EDB that supports private histogram queries. As a building block, we introduce a differentially-private encrypted counter based on the binary mechanism of Chan et al. (ICALP, 2010). We then carefully combine multiple instances of this counter with a standard encrypted database scheme to support differentially-private histogram queries.

We study the problem of minimally activating a resource that is shared by multiple jobs. In a power-aware computing environment, the resource needs to be activated (powered-up) so that it can service the jobs. Each job specifies an interval during which its needs the services of the resource and the duration (time length) for which it requires the resource to be active. Our goal is to activate the resource for a minimum amount of time, while satisfying all the jobs. We study two variants of this problem, the contiguous and the non-contiguous cases. In the contiguous case, each job requires that its demand for the resource be serviced with a set of contiguous timeslots whereas in the non-contiguous case, the demand of a job may be serviced with a set of non-contiguous timeslots. For the contiguous case, we present an optimal polynomial time algorithm; this improves the best known result, which is an approximation algorithm having a ratio of 2. For the non-contiguous case, we present efficient algorithms for finding optimal and approximate solutions.

In this paper, we study a class of set cover problems that satisfy a special property which we call the small neighborhood cover property. This class encompasses several well-studied problems including vertex cover, interval cover, bag interval cover and tree cover. We design unified distributed and parallel algorithms that can handle any set cover problem falling under the above framework and yield constant factor approximations. These algorithms run in polylogarithmic communication rounds in the distributed setting and are in NC, in the parallel setting.