Clients of outsourced databases need Query Authentication (QA) guaranteeing the integrity and authenticity of query results returned by potentially compromised providers. Prior work provides QA assurances for a limited class of queries by deploying several software-based cryptographic constructs. The constructs are often designed assuming read-only or infrequently updated databases. For dynamic datasets, the data owner is required to perform all updates on behalf of clients. Hence, for concurrent updates by multiple clients, such as for OLTP workloads, existing QA solutions are inefficient. We present ConcurDB, a concurrent QA scheme that enables simultaneous updates by multiple clients. To realize concurrent QA, we have designed several new mechanisms. First, we identify and use an important relationship between QA and memory checking to decouple query execution and verification. We allow clients to execute transactions concurrently and perform verifications in parallel using an offline memory checking based protocol. Then, to extend QA to a multi-client scenario, we design new protocols that enable clients to securely exchange a small set of authentication data even when using the untrusted provider as a communication hub. Finally, we overcome provider-side replay attacks. Using ConcurDB, we provide and evaluate concurrent QA for the full TPC-C benchmark. For updates, ConcurDB shows a 4x performance increase over existing solutions.

Today's (predominantly cloud-based) File sharing products leave users at the mercy of providers and nation-state adversaries with subpoena and National Security Letter (NSL) powers. In-transit and provider-side at-rest encryption do little to handle this.Almost-weekly breaches [7-13, 17] and NSL revelations [2] show that the problem becomes only worse with increasingly privacy-unfriendly regulation [14]. We believe it is important to provide hype-free, easy-to-use strongly-secure solutions that protect individual privacy while also defeating cloud breaches and compromises. CipherLocker provides practical, easy-to-use, client-side encrypted File sharing with integrated ranked search. All data and metadata is strongly encrypted before leaving the client. Users can securely store, share, sync, and search. The design does not allow even a compromised or compelled cloud provider to ever access user data or search queries. CipherLocker shows that highly-scalable, fast ranked search on encrypted data is possible without the deployment of expensive and often insecure server-side search-on-encrypted-data cryptography which would require 3-5 orders of magnitude more resources and cannot scale to even thousands of users, or the simplest sharing scenarios without breaking security. CipherLocker is the result of several years of work and it cannot be exhaustively detailed and analyzed in this space. This is the first of a series of papers discussing CipherLocker design, implementation and security properties. The main goal here is to briefly overview and introduce key design decisions and behaviors.

The way data structures organize data is often a function of the sequence of past operations. The organization of data is referred to as the data structure's state, and the sequence of past operations constitutes the data structure's history. A data structure state can, therefore, be used as an oracle to derive information about its history. For history-sensitive applications, such as privacy in e-voting, it is imperative to conceal historical information contained within data structure states. Data structure history can be hidden by making data structures history independent. In this paper, we explore how to achieve history independence (HI). We observe that the current HI notions are significantly limited in number and scope. There are two existing notions of HI: 1) weak HI (WHI) and 2) strong HI (SHI). WHI does not protect against insider adversaries, and SHI mandates canonical representations, resulting in inefficiency. We postulate the need for a broad, encompassing notion of HI, which can capture WHI, SHI, and a broad spectrum of new HI notions. To this end, we introduce AHI, a generic game-based framework that is malleable enough to accommodate the existing and new HI notions. As an essential step toward formalizing AHI, we explore the concepts of abstract data types, data structures, machine models, memory representations, and HI. Finally, to bridge the gap between theory and practice, we outline a general recipe for building end-to-end, history-independent systems and demonstrate the use of the recipe in designing two historyindependent file systems.

Traditionally, as soon as confidentiality becomes a concern, data are encrypted before outsourcing to a service provider. Any software-based cryptographic constructs then deployed, for server-side query processing on the encrypted data, inherently limit query expressiveness. Here, we introduce TrustedDB, an outsourced database prototype that allows clients to execute SQL queries with privacy and under regulatory compliance constraints by leveraging server-hosted, tamper-proof trusted hardware in critical query processing stages, thereby removing any limitations on the type of supported queries. Despite the cost overhead and performance limitations of trusted hardware, we show that the costs per query are orders of magnitude lower than any (existing or) potential future software-only mechanisms. TrustedDB is built and runs on actual hardware, and its performance and costs are evaluated here.

Ensuring complete irrecoverability of deleted data is difficult to achieve in modern systems. Simply overwriting data or deploying encryption with ephemeral keys is not sufficient. The mere (previous) existence of deleted records impacts the current system state implicitly at all layers. This can be used as an oracle to derive information about the past existence of deleted records.

It has become apparent that in the digital world data once stored is never truly deleted even when such an expunction is desired either as a normal system function or for regulatory compliance purposes. Forensic Analysis techniques on systems are often successful at recovering information said to have been deleted in the past. Efforts aimed at thwarting such forensic analysis of systems have either focused on (i) identifying the system components where deleted data lingers and performing a secure delete operation over these remnants, or (ii) designing history independent data structures that hide information about past operations which result in the current system state. Yet, new data is constantly derived by processing existing (input) data which makes it increasingly difficult to remove all traces of this existing data, i.e., for regulatory compliance purposes. Even after deletion, significant information can linger in and be recoverable from the side effects the deleted data records left on the currently available state. In this paper we address this aspect in the context of a relational database, such that when combined with (i) & (ii), complete erasure of data and its effects can be achieved (“un-traceable deletion”). We introduce Ficklebase - a relational database wherein once a tuple has been “expired” - any and all its side-effects are removed, thereby eliminating all its traces, rendering it unrecoverable, and also guaranteeing that the deletion itself is undetectable. We present the design and evaluation of Ficklebase, and then discuss several of the fundamental functional implications of un-traceable deletion.

Clients of outsourced databases need Query Authentication (QA) guaranteeing the integrity (correctness and completeness), and authenticity of the query results returned by potentially compromised providers. Existing results provide QA assurances for a limited class of queries by deploying several software cryptographic constructs. Here, we show that, to achieve QA, however, it is significantly cheaper and more practical to deploy server-hosted, tamper-proof co-processors, despite their higher acquisition costs. Further, this provides the ability to handle arbitrary queries. To reach this insight, we extensively survey existing QA work and identify interdependencies and efficiency relationships. We then introduce CorrectDB, a new DBMS with full QA assurances, leveraging server-hosted, tamper-proof, trusted hardware in close proximity to the outsourced data.

TrustedDB is an outsourced database prototype that allows clients to execute SQL queries with privacy and under regulatory compliance constraints without having to trust the service provider. TrustedDB achieves this by leveraging server-hosted tamper-proof trusted hardware in critical query processing stages.TrustedDB does not limit the query expressiveness of supported queries. And, despite the cost overhead and performance limitations of trusted hardware, the costs per query are orders of magnitude lower than any (existing or) potential future software-only mechanisms. TrustedDB is built and runs on actual hardware, and its performance and costs are evaluated here.