Title: MPC: Practical Dynamic Composition of Operators in Secure Computation: VoIP and SQL

Pre-computation of circuits has long been the rule for secure computation: we implement pre-defined functions, however complex, over a set of external, unchanging inputs - a circuit model. However, the circuit model of computation rarely seems to represent the real world: It may be impractical to determine a priori how large the circuit input will be, or the computation's structure may rely on intermediate results. To facilitate practical computation under these constraints, we turn to the RAM model. In this talk we present two use cases where the circuit model is impractical and gives way to the RAM model. In the area of privacy-preserving signal processing, we present a streaming data voice processing application that iterates over successive inputs and stored intermediate results. In the area of secure database queries, we present current work on a query processing approach that sequentially computes operator results and holds them for the next operator in the query tree. Both areas of work rely on the RAM model of computation supported by secure multi-party computation engines.

Title: Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations

Searchable symmetric encryption (SSE) enables a client to store a database on an untrusted server while supporting keyword search in a secure manner. Despite the rapidly increasing interest in SSE technology, experiments indicate that the performance of the known schemes scales badly to large databases. Somewhat surprisingly, this is not due to their usage of cryptographic tools, but rather due to their poor locality (where locality is defined as the number of {\em non-contiguous} memory locations the server accesses with each query). The only known schemes that do not suffer from poor locality suffer either from an impractical space overhead or from an impractical read efficiency (where read efficiency is defined as the ratio between the number of bits the server reads with each query and the actual size of the answer).

We construct the first SSE schemes that simultaneously enjoy optimal locality, optimal space overhead, and nearly-optimal read efficiency. Specifically, for a database of size N, under the modest assumption that no keyword appears in more than N1-1/loglogN documents, we construct a scheme with read efficiency O~(loglogN). This essentially matches the lower bound of Cash and Tessaro (EUROCRYPT '14) showing that any SSE scheme must be sub-optimal in either its locality, its space overhead, or its read efficiency. In addition, even without making any assumptions on the structure of the database, we construct a scheme with read efficiency O~(logN).

Our schemes are obtained via a two-dimensional generalization of the classic balanced allocations (``balls and bins'') problem that we put forward. We construct nearly-optimal two-dimensional balanced allocation schemes, and then combine their algorithmic structure with subtle cryptographic techniques.

A joint work with Moni Naor, Gil Segev and Ido Shahaf.

Title: Deploying Secure Computing for Real-world Applications

Secure computation (SC) stands for a group of technologies for computing on encrypted inputs without decrypting them. In this talk, I will introduce Sharemind, a secure application server that uses secure computation for building privacy-preserving applications. Sharemind supports multiple secure computing technologies, with more mature ones supporting secure operations on encrypted integers, fixed-point and floating point numbers, strings and bits. We have built Sharemind-powered systems for analyzing confidential government tax and education databases, detect large-scale fraud from transactions and to build more secure cloud services. The talk will focus on scaling secure computing applications from efficient primitives to applications processing up to a hundred million records.

Title: Adaptive Succinct Garbled RAM or How To Delegate Your Database

We show how to garble a large database and then a sequence of adaptively and adversarially chosen RAM programs that query and modify the database in arbitrary ways. The security property is that the garbled database and programs reveal only the outputs of the programs when run in sequence on the database. The runtime, space requirements and description size of the garbled programs are proportional only to those of the plaintext programs and the security parameter. The construction is based on indistinguishability obfuscation for circuits and poly-to-one collision-resistant hash functions.

As an immediate application, our scheme is the first to provide a way to outsource large databases to untrusted servers, and later query and update the database over time in a private and verifiable way, with complexity and description size proportional to those of the unprotected queries.

Joint work with Ran Canetti, Justin Holmgren and Mariana Raykova.

Title: Cryptography for Parallel RAM from Indistinguishability Obfuscation

Since many cryptographic schemes are about performing computation on data, it is important to consider a computation model which captures the prominent features of modern system architecture. Parallel random access machine (PRAM) is such an abstraction which not only models multiprocessor platforms, but also new frameworks supporting massive parallel computation such as MapReduce.

We explore the feasibility of designing cryptographic solutions for the PRAM model of computation to achieve security while leveraging the power of parallelism and random data access. At the core of our work is a succinct garbling/randomized encoding (RE) scheme for PRAM based on indistinguishability obfuscations and one-way functions. This, combined with transformations from previous works, yields general feasibility results for a wide-range of cryptographic tasks in the PRAM model, such as functional encryption, searchable encryption, secure multiparty computation, and delegation scheme with persistent database, based on the same assumptions.

In this talk, I will focus on our construction of succinct RE for PRAM, which is built on the seminal work of Koppula et al [STOC 2015] for Turing machines, where the main challenge is to develop techniques to enable the power of parallelism and random data access while maintaining security and efficiency.

Joint work with Yu-Chi Chen, Sherman S. M. Chow, Russell W. F. Lai, Wei-Kai Lin, and Hong-Sheng Zhou.

Title: Constrained PRFs for Unconstrained Inputs

A constrained pseudorandom function (PRF) behaves like a standard PRF, but with the added feature that the (master) secret key holder, having secret key K, can produce a constrained key, K{f}, that allows for the evaluation of the PRF on all inputs satisfied by the constraint f. Most existing constrained PRF constructions can handle only bounded length inputs. Abusalah et al. [AFP14] have constructed a constrained PRF scheme where constraints can be represented as Turing machines with unbounded inputs. Their proof of security, however, requires risky “knowledge type” assumptions such as (public coins) differing inputs obfuscation for circuits and SNARKs. In this work, we construct a constrained PRF scheme for Turing machines with unbounded inputs under weaker assumptions, namely, the existence of indistinguishability obfuscation for circuits (and injective pseudorandom generators). Under the same assumptions, we also construct selectively secure attribute-based encryption for Turing machines.

Title: The Ascend Secure Processor

Privacy of data storage has long been a central problem in computer security, having direct implications for many Internet-era applications such as storage/computation outsourcing and the Internet of Things (IoT). Yet, the prevailing way we protect our data - through encryption techniques - doesn't protect _where_ we read or write in our data. This additional information, the access pattern, can be used to reverse-engineer proprietary programs as they run, reveal a user's physical location or health information, and more, even if data is correctly encrypted.

In this talk, I will describe Ascend, a secure processor that in different form factors can improve security in these modern settings. The central component in Ascend is an optimized Oblivious RAM (ORAM) controller built directly into the hardware. This ORAM allows Ascend to hide program access pattern to main memory, thwarting attackers with software/physical access to the device memory. In the talk, I will describe some themes we took in building the hardware ORAM that blend ideas from applied security and computer architecture.

Along the way, I will describe (and pass around!) a real and working Ascend chip, taped out in 32 nm silicon. Finally, I will show a demo of Ascend running on an FPGA (and try to attack it using a blast chiller).

Title: Secure Computation of MIPS Machine Code

Existing systems for secure computation require programmers to express the program to be securely computed as a circuit, or in some domain-specific language that can be compiled to a form suitable for applying known protocols. We propose a new system that can securely execute native MIPS code with no special annotations. Our system has the advantage of allowing programmers to use a language of their choice to express their programs, together with any off-the-shelf compiler to MIPS; it can be used for secure computation of existing "legacy" MIPS code as well.

Our system uses oblivious RAM for fetching instructions and performing load/store operations in memory, and garbled universal circuits for the execution of a MIPS ALU in each instruction step. We also explore various optimizations based on an offline analysis of the MIPS code to be executed, in order to minimize the overhead of executing each instruction while still maintaining security.

Title: Intel's Software Guard Extensions technology and the Memory Encryption Engine

Intel has recently introduced a powerful security architecture called "Software Guard Extensions" (SGX). This security technology is designed to allow a general purpose computer platform to run application software in a trustworthy manner, and to handle secrets that are inaccessible to anyone outside the defined trust boundaries. These trust boundaries encompass only the CPU internals, implying, in particular, that the system memory is untrusted. Consequently, cryptographic protection of memory is required for SGX. To this end, SGX is supported by an autonomous hardware unit called the Memory Encryption Engine (MEE), whose role is to protect the confidentiality, integrity, and freshness of the CPU-DRAM traffic over some memory range.

In this talk, I will start by a brief description of the basic functionality of SGX, the MEE threat model, its security objectives, and design challenges under very strict engineering constraints. I will then explain the MEE design, cryptographic properties and security margins, and will show some concrete performance results.

Title: Non-Interactive RAM Delegation from any PIR

We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of short-vector lattice problems). In our protocol, the prover and the verifier do not need to interact at all: The verifier sets up a public key ahead of time, and this key can be used by any prover to prove arbitrary statements in a completely adaptive manner. Verification is done using a secret verification key, and soundness relies on this key not being known to the prover. Our protocol further allows to prove statements about computations of arbitrary RAM machines.

Previous works either relied on knowledge assumptions, or could only offer non-adaptive two-message protocols (where the first message could not be re-used), and required either obfuscation-based assumptions or super-polynomial hardness assumptions.

Additionally, for any NP language L, we show a 2-message argument of knowledge which enjoys ``batch succinctness'' -- the communication complexity is the size of one witness, but allows proving membership in L for many instances simultaneously.

Based on joint work with Zvika Brakerski and Yael Kalai.

Title: Adaptively Secure Garbled Circuits from One-Way Functions

A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output C(x) but hides everything else. In many settings, the circuit can be garbled off-line without strict efficiency constraints, but the input must be garbled very efficiently on-line, with much lower complexity than evaluating the circuit. Yao's scheme has essentially optimal on-line complexity, but only achieves selective security, where the adversary must choose the input x prior to seeing the garbled circuit. It has remained an open problem to achieve adaptive security, where the adversary can choose x after seeing the garbled circuit, while preserving on-line efficiency.

In this work, we modify Yao's scheme in a way that allows us to prove adaptive security under one-way functions. As our main instantiation, we get a scheme where the on-line complexity is only proportional to the width w of the circuit, which corresponds to the space complexity of the computation, but is independent of the circuit's depth d. Alternately, we can also get an instantiation where the on-line complexity is only proportional to the input/output size and the depth d of the circuit but independent of its width w, albeit in this case we incur a 2O(d) security loss in our reduction. More broadly, we relate the on-line complexity of adaptively secure garbling schemes in our framework to a certain type of pebble complexity of the circuit.

As our main tool, of independent interest, we develop a new notion of somewhere equivocal encryption, which allows us to efficiently equivocate on a small subset of the message bits.

Title: Further Improvements in Oblivious RAM for MPC for 3 Parties with Honest Majority

In Asiacrypt'15 we showed that secure computation of RAM programs in the case of 3 parties with honest majority can be significantly faster than in the case of 2-party secure computation. However, the 3-Party SC-ORAM of Asiacrypt'15 was based on a sub-optimal version of Path ORAM with a simple, and hence "secure-computation friendly", eviction procedure which used linear-sized buckets. Here we show a 3-party MPC protocol that efficiently emulates the eviction procedure utilized by the "Circuit ORAM" developed for the 2-Party SC-ORAM by Wang, Chan, and Shi, thus leading to a 3-Party SC-ORAM protocol with constant-sized buckets. In particular, the costs of access in the resulting 3-Party SC-ORAM protocol matches the access cost in recent ORAM schemes.

Title: The Oblivious Machine - or: How to Put the C into MPC

We present an oblivious machine, a concrete notion for a multiparty random access machine (RAM) computation and a toolchain to allow the efficient execution of general programs written in a subset of C that allows RAM-model computation over the integers. The machine only leaks the list of possible instructions and the running time. Our work is based on the oblivious array for secret-sharing-based multiparty computation by Keller and Scholl (Asiacrypt `14). This means that we only incur a polylogarithmic overhead over the execution on a normal CPU.

We describe an implementation of our construction using the Clang compiler from LLVM project and the SPDZ protocol by Damgård et al. (Crypto `12). The latter provides active security against a dishonest majority and works in the preprocessing model. The online phase clock rate of the resulting machine is 41 Hz for a memory size of 1024 64-bit integers and 2.2 Hz for a memory of 2^20 integers. Both timings have been taken for two parties in a local network.

Title: Indistinguishability Obfuscation from Constant Degree Graded Encodings

We construct a general-purpose indistinguishability obfuscation (IO) scheme for all polynomial-size circuits from constant-degree graded encoding schemes in the plain model, assuming the existence of a subexponentially secure Pseudo-Random Generator (PRG) computable by constant-degree arithmetic circuits (or equivalently in NC0), and the subexponential hardness of the Learning With Errors (LWE) problems. In contrast, previous general-purpose IO schemes all rely on polynomial-degree graded encodings.

Title: HOP: Hardware makes Obfuscation Practical

Although program obfuscation has been widely considered in cryptographic literature, it has been shown that software only obfuscation of general programs is impossible. In this work, we assume the existence of stateless tamper proof hardware tokens to achieve program obfuscation. From a theoretical perspective, we construct an obfuscation scheme for RAM programs using stateless hardware tokens. We outline a proof of security for our construction under a UC simulation notion. From a practical perspective, we implement a complete and real hardware system using stateful hardware tokens, called HOP, which can be used to execute an obfuscated program. We show that HOP incurs overhead of 8x ∼ 76x over an insecure system, and performs 5x ∼ 238x better than a baseline hardware obfuscation scheme across simple to sophisticated programs. We also demonstrate how HOP incurs only 2x ∼ 41x slowdown to prior oblivious computation hardware schemes that do not guarantee program privacy. HOP exemplifies a new approach of designing secure processors with matching formal abstractions that allow the consumer to think of the hardware token as a trusted third party.

Title: New Results on Secure Outsourced Database Storage

We give new positive and negative results about the problem of securely outsourcing storage of a confidential database to an untrusted server while supporting efficient query processing. On the positive side, we show the first construction of an order-revealing encryption scheme (ORE) without using multilinear maps that has a leakage profile provably unachievable by order-preserving encryption. The scheme is based on bilinear maps and is relatively efficient: for n-bit plaintexts, ciphertexts consist of about 4n group elements and order comparison requires about n^2 pairings.

On the negative side, we show that any outsourced database protocol for range queries that leaks either the access pattern or the communication volume is subject to ``reconstruction attacks'' where the untrusted server learns every secret search key in the database after polynomially-many queries in the domain size. These results are in a weak adversarial model where the untrusted server does not choose the queries but only knows their underlying distribution. This motivates the search for different ways of using tools like ORE in outsourced database protocols than existing work.

Based on joint works with David Cash, Feng-Hao Lui, and Cong Zhang, and with George Kellaris, George Kollios, and Kobbi Nissim.

Title: Analysis and Design of Blockchains

Nakamoto's famous blockchain protocol enables achieving consensus in a so-called *permissionless* setting---anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents "sybil attacks" (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. "moderately hard functions") introduced by Dwork and Naor (Crypto'92).

Prior works that analyze the blockchain protocol either make the simplifying assumption that network channels are fully synchronous (i.e. messages are instantly delivered without delays) (Garay et al, Eurocrypt'15) or only consider specific attacks (Nakamoto'08; Sampolinsky and Zohar, FinancialCrypt'15); additionally, as far as we know, none of them deal with players joining or leaving the protocol.

We prove that the blockchain consensus mechanism satisfies a strong forms of consistency and liveness in an asynchronous network with adversarial delays that are a-priori bounded, within a formal model allowing for adaptive corruption and spawning of new players, assuming that the computational puzzle is modeled as a random oracle. (We complement this result by showing a simple attack against the blockchain protocol in a fully asynchronous setting, showing that the "puzzle-hardness" needs to be appropriately set as a function of the maximum network delay.)

As an independent contribution, we define an abstract notion of a blockchain protocol and identify appropriate security properties of such protocols; we prove that Nakamoto's blockchain protocol satisfies them and that these properties are sufficient for typical applications. We finally show how to use our analysis to build *new* blockchain protocols that overcome some of the bottlenecks in Nakamoto's original protocol.

The analysis of Nakamoto's blockchain is based on joint work with Lior Seeman and abhi shelat, and the new blockchain protocols are based on joint work with Elaine Shi. No prior knowledge of Bitcoin or the blockchain will be assumed.

Title: Better Two-Round Adaptive Multi-Party Computation

The only known two-round multi-party computation protocol that withstands adaptive corruption of all parties is the ingenious protocol of Garg and Polychroniadou [TCC 15]. We present protocols that improve on the GP protocol in a number of ways. First, concentrating on the semi-honest case and taking a different approach, we show a two-round, adaptively secure protocol where:
- Only a global (i.e., non-programmable) reference string is needed.
- The communication complexity depends only on the size of the RAM description of the evaluated function (and not on its circuit size). The work of each party depends on RAM complexity of the function.
- Even not well-formed randomized functionalities can be evaluated securely.
- Only polynomially-secure indistinguishability obfuscation for circuits and one way functions are assumed.

Second, we modify the GP protocol to have only RAM complexity even in the case of Byzantine corruptions. For this we construct the first statistically-sound non-interactive Zero-Knowledge scheme with RAM complexity.

Title: The Exact Round Complexity of Secure Computation

We revisit the exact round complexity of secure computation in the multi-party and two-party settings. For the special case of two-parties without a simultaneous message exchange channel, this question has been extensively studied and resolved. In particular, Katz and Ostrovsky (CRYPTO '04) proved that 5 rounds are necessary and sufficient for securely realizing every two-party functionality where both parties receive the output. However, the exact round complexity of general multi-party computation, as well as two-party computation with a simultaneous message exchange channel, is not very well understood.

These questions are intimately connected to the round complexity of non-malleable commitments. Indeed, the exact relationship between the round complexities of non-malleable commitments and secure multi-party computation has also not been explored.

In this work, we revisit these questions and obtain several new results. First, we establish the following main results. Suppose that there exists a k-round non-malleable commitment scheme, and let k' = max(4, k + 1); then,
-(Two-party setting with simultaneous message transmission): there exists a k'-round protocol for securely realizing every two-party functionality;
-(Multi-party setting):there exists a k'-round protocol for securely realizing the multi-party coin-flipping functionality.

As a corollary of the above results, by instantiating them with existing non-malleable commitment protocols (from the literature), we establish that four rounds are both necessary and sufficient for both the results above. Furthermore, we establish that, for every multi-party functionality five rounds are sufficient. We actually obtain a variety of results offering trade-offs between rounds and the cryptographic assumptions used, depending upon the particular instantiations of underlying protocols.

Title: Stronger Public Key Encryption System Withstanding RAM Scraper Like Attacks

The indistinguishability of ciphertext under the chosen ciphertext attack (IND-CCA2) is often considered to offer the strongest security notion for a public key encryption system. Nowadays, due to availability of powerful malwares, an adversary is able to obtain "more" information than what he could obtain in the CCA2 security model. In order to realistically model the threats posed by such malwares, we need to empower the adversary to obtain additional information. RAM SCRAPERS are a new kind of malware that could watch an execution of a specific code and pass the values that are available in RAM during the execution of the code. Specifically, RAM SCRAPERS have the potential to make some of the intermediate values generated during the execution of a decryption algorithm to an adversary. Thus, the adversary who mounts the traditional lunch time attack is now likely to obtain more information from the execution of the decryption algorithm. This paper initiates a research to counter malwares such as RAM scrapers and extend the CCA2 model with oracles providing additional information to capture the effect of RAM scrapers precisely. We call this stronger security notion as Glass Box Decryption. After discussing the new kind of attack/threat and the related oracle, we show that almost all CCA2 secure systems are vulnerable to this kind of attack. We then propose a new system that offers security against glass box decryption and provide the formal security proof for the new system in the standard model.

Title: Secure Linear Regression on Vertically Partitioned Datasets

We propose multi-party computation protocols for securely computing a linear regression model from a vertically partitioned training database. This problem arises in data analysis problems where multiple parties hold different sets of columns of the database that needs to be analyzed. Our solution enables organizations that are willing to collaborate to construct better predictive models on their joint data while protecting the privacy of their inputs. Our approach is based on a hybrid MPC protocol combining garbled circuits with an offline phase enabled by a semi-trusted external party. As part of our contribution, we evaluate several algorithms and implementations for solving systems of linear equations using garbled circuits. Experiments conducted with an implementation of our protocols indicate that our approach leads to highly scalable solutions that can solve data analysis problems with one million records and one hundred features in less than one hour.

Joint work with Adria Gascon, Phillipp Schoppmann, Borja Balle, Samee Zahur, Jack Doerner, David Evans.

Title: Making Password Checking Systems Better

Most computing systems still rely on user-chosen passwords to authenticate access to data and systems. But passwords are hard to use, easy to guess, and tricky to securely store. In practice one sees high failure rates of (legitimate) password login attempts, as well as a never-ending stream of damaging password database compromises. I will present a sequence of new results that target making password authentication systems better. We will look at how to address concerns in three areas: (1) usability by way of easy-to-deploy typo-tolerant password authentication validated using experiments at Dropbox; (2) hardening password storage against cracking attacks via our new Pythia crypto service; and, time allowing, (3) building cracking-resistant password vaults via a new cryptographic primitive called honey encryption.

Joint work with Anish Athayle, Devdatta Akawhe, Joseph Bonneau, Rahul Chatterjee, and Ari Juels.

Title: Secure Stable and Perfect Matchings

I will explain how we can use 2-party computation to securely compute stable matchings on instances the size of the 2016 NRMP medical residency matching in less than 1 day. Prior work on this problem was stuck on toy instances involving a few hundred participants. The insight is to exploit an algorithmic property of matchings and design a new secure computation data structure. I will then discuss new methods for securely computing perfect and maximal matchings which also exploit the algorithmic structure.

Title: TaoStore: Overcoming Asynchronicity in Oblivious Data Storage

We consider oblivious storage systems hiding both the contents of the data as well as access patterns from an untrusted cloud provider. We target a scenario where multiple users from a trusted group (e.g., corporate employees) asynchronously access and edit potentially overlapping data sets through a trusted proxy mediating client-cloud communication.

The main contribution of our work is twofold. Foremost, we initiate the first formal study of asynchronicity in oblivious storage systems. We provide security definitions for scenarios where both client requests and network communication are asynchronous (and in fact, even adversarially scheduled). While security issues in ObliviStore (Stefanov and Shi, S&P 2013) have recently been surfaced, our treatment shows that also CURIOUS (Bindschaedler at al., CCS 2015), proposed with the exact goal of preventing these attacks, is insecure under asynchronous scheduling of network communication.

Second, we develop and evaluate a new oblivious storage system, called Tree-based Asynchronous Oblivious Store, or TaoStore for short, which we prove secure in asynchronous environments. TaoStore is built on top of a new tree-based ORAM scheme that processes client requests concurrently and asynchronously in a non-blocking fashion. This results in a substantial gain in throughput, simplicity, and flexibility over previous systems.

Title: Verifiable ASICs: Trustworthy Chips with Untrusted Components

A manufacturer of custom hardware (an ASIC) can undermine the intended execution of that hardware. High-assurance execution thus requires controlling the manufacturing chain. However, a trusted platform might be orders of magnitude worse in performance or price than an advanced, untrusted platform.

We explore an alternative: using verifiable computation (VC), an untrusted ASIC computes proofs of correct execution, which are verified by a trusted processor or ASIC. In contrast to the usual VC setup, here the prover and verifier together must impose less cost than running the given computation directly on the trusted platform. We respond to this challenge by designing and implementing physically realizable, area-efficient, high-throughput ASICs for a prover and verifier. The system, called Zebra, is based on the CMT and Allspice interactive proof protocols, which are themselves based on the GKR "Muggles" protocol. Zebra incorporates new observations about CMT, careful hardware design, and attention to architectural challenges. For a class of real computations, Zebra meets or exceeds the performance of executing directly on the trusted platform. Further, Zebra's prover has the best throughput in the literature: tens of thousands of proofs per second.

Joint work with: Max Howald, Siddharth Garg, abhi shelat, Michael Walfish.

Title: Revisiting Square-Root ORAM: Efficient Random Access in Multi-Party Computation

Hiding memory access patterns is required for secure computation, but remains prohibitively expensive for many interesting applications. Prior work has either developed custom algorithms that minimize the need for data-dependant memory access, or proposed the use of Oblivious RAM (ORAM) to provide a general-purpose solution. However, most ORAMs are designed for clientserver scenarios, and provide only asymptotic benefits in secure computation. Even the best prior schemes show concrete benefits over naïve linear scan only for array sizes greater than 100. This immediately implies each ORAM access is 100 times slower than a single access at a known location. Even then, prior evaluations ignore the substantial initialization cost of existing schemes.

We show how the classical square-root ORAM of Goldreich and Ostrovsky can be modified to overcome these problems, even though it is asymptotically worse than the best known schemes. Specifically, we show a design that has over 100 times lower initialization cost, and provides benefits over linear scan for just 8 blocks of data. For all benchmark applications we tried, including Gale-Shapley stable matching and the scrypt key derivation function, our scheme outperforms alternate approaches across a wide range of parameters, often by several orders of magnitude.