Plausibly-deniable (PD) storage systems allow users to securely hide data and plausibly deny its presence when challenged by adversaries who coerce them to provide encryption keys and passwords. However, PD systems need specialized software that renders them detectable by suspicious adversaries questioning the very use of a PD system. To address this fundamental problem, we introduce and formally define the notion of plausible invisibility, preventing adversaries from determining whether a PD system was used in the first place. We develop INVISILINE, a plausibly invisible system resilient against multi-snapshot adversaries that can access the device multiple times. To remain invisible, INVISILINE uses a data layout and encoding that is compatible with the Linux dmcrypt disk encryption subsystem, and stores hidden data in the initialization vectors used by dm-crypt to encrypt public data. INVISILINE ensures that any disk changes that result from changes to the hidden data between adversary snapshots, can be plausibly explained using changes to public data resulting from regular use of dm-crypt. In the presence of adversaries, INVISILINE enables users to access all and only the public data using only dm-crypt. INVISILINE can securely and invisibly hide 19GB on a 1TB disk with no impact on public data I/O, and an average of 4.5MB/s throughput for writing hidden data.

Advances in computer vision have made it possible to accurately map objects as regions in 3-dimensional space using LIDAR point clouds. These systems are key building blocks of several emerging technologies including autonomous vehicles. Comparing and validating the output of sensors at different vantage points observing the same scenery can enable these systems to detect faults, identify common obstacles, and improve decision making. However sharing sensor outputs among mutually untrusting parties can leak unwanted information, e.g., model parameters or relative location of the sensors. This work initiates the study of cryptographic protocols that enable two parties observing regions (or objects) in an arbitrary-dimension Euclidean space to privately detect if the regions overlap and approximate the volume of the overlapping region. The protocols rely only on cheap symmetric-key primitives and feature reasonable communication costs and compute times. As applications, the protocols have been benchmarked on data generated from the CARLA autonomous driving simulator and the ScanNet 3D image dataset; they outperform a 2PC garbled-circuit baseline in communication volume and compute time. For instance it takes roughly 0.5 seconds to approximate the volume of the overlapping region of two 3D boxes with low error probability.

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.

Abstract Protecting sensitive data stored on local storage devices e.g., laptops, tablets etc. is essential for privacy. When adversaries are powerful enough to coerce users to reveal encryption keys/passwords, encryption alone becomes insufficient for data protection. Additional mechanisms are required to hide the very presence of sensitive data. Plausibly deniable storage systems (PDS) are designed to defend against such powerful adversaries. Plausible deniability allows a user to deny the existence of certain stored data even when an adversary has access to the storage medium. However, existing plausible deniability solutions leave users at the mercy of adversaries suspicious of their very use. Indeed, it may be difficult to justify the use of a plausible deniability system while claiming that no sensitive data is being hidden. This work introduces INFUSE, a plausibly-deniable file system that hides not only contents but also the evidence that a particular system is being used to hide data. INFUSE is “invisible” (identical layout with standard file system), provides redundancy, handles overwrites, survives data loss, and is secure in the presence of multi-snapshot adversaries. INFUSE is efficient. Public data operations are orders of magnitude faster than existing multi-snapshot resilient PD systems, and only 15% slower than a standard non-PD baseline, and hidden data operations perform comparably to existing systems.

Oblivious RAMs (ORAMs) allow a client to access data from an untrusted storage device without revealing the access patterns. Typically, the ORAM adversary can observe both read and write accesses. Write-only ORAMs target a more practical, multi-snapshot adversary only monitoring client writes – typical for plausible deniability and censorship-resilient systems. This allows write-only ORAMs to achieve significantly-better asymptotic performance. However, these apparent gains do not materialize in real deployments primarily due to the random data placement strategies used to break correlations between logical and physical names-paces, a required property for write access privacy. Random access performs poorly on both rotational disks and SSDs (often increasing wear significantly, and interfering with wear-leveling mechanisms).

Abstract Encryption protects sensitive data from unauthorized access, yet is not sufficient when users are forced to surrender keys under duress. In contrast, plausible deniability enables users to not only encrypt data but also deny its existence when challenged. Most existing plausible deniability work (e.g. the successful and unfortunately now-defunct TrueCrypt) tackles “single snapshot” adversaries, and cannot handle the more realistic scenario of adversaries gaining access to a device at multiple time points. Such “multi-snapshot” adversaries can simply observe modifications between snapshots and detect the existence of hidden data. Existing ideas handling “multi-snapshot” scenarios feature prohibitive overheads when deployed on practically-sized disks. This is mostly due to a lack of data locality inherent in certain standard access-randomization mechanisms, one of the building blocks used to ensure plausible deniability. In this work, we show that such randomization is not necessary for strong plausible deniability. Instead, it can be replaced by a canonical form that permits most of writes to be done sequentially. This has two key advantages: 1) it reduces the impact of seek due to random accesses; 2) it reduces the overall number of physical blocks that need to be written for each logical write. As a result, PD-DM increases I/O throughput by orders of magnitude (10–100× in typical setups) over existing work while maintaining strong plausible deniability against multi-snapshot adversaries. Notably, PD-DM is the first plausible-deniable system getting within reach of the performance of standard encrypted volumes (dm-crypt) for random I/O.

Abstract Sensitive information is present on our phones, disks, watches and computers. Its protection is essential. Plausible deniability of stored data allows individuals to deny that their device contains a piece of sensitive information. This constitutes a key tool in the fight against oppressive governments and censorship. Unfortunately, existing solutions, such as the now defunct TrueCrypt [5], can defend only against an adversary that can access a user’s device at most once (“single-snapshot adversary”). Recent solutions have traded significant performance overheads for the ability to handle more powerful adversaries able to access the device at multiple points in time (“multi-snapshot adversary”). In this paper we show that this sacrifice is not necessary. We introduce and build DataLair1, a practical plausible deniability mechanism. When compared with existing approaches, DataLair is two orders of magnitude faster for public data accesses, and 5 times faster for hidden data accesses. An important component in DataLair is a new write-only ORAM construction which improves on the complexity of the state of the art write-only ORAM by a factor ofO(logN), where N denotes the underlying storage disk size.

Sensitive information is present on our phones, disks, watches and computers. Its protection is essential. Plausible deniability of stored data allows individuals to deny that their device contains a piece of sensitive information. This constitutes a key tool in the fight against oppressive governments and censorship.

Oblivious RAM (ORAM) mechanisms have improved rapidly in recent years as increasing amounts of data are outsourced. Although several tree-based ORAMs such as PathORAM [8] and RingORAM [6] have achieved near-optimal bandwidth for single client scenarios, their low overall throughput due to high latency of access -- as clients need to wait for or know about and coordinate with each other, lest privacy is lost -- reduces their applicability for multi-client scenarios.

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.