Oblivious RAM (ORAM) is a central cryptographic primitive that enables secure memory access while hiding access patterns. Among existing ORAM paradigms, hierarchical ORAMs were long considered impractical despite their asymptotic optimality. However, recent advancements (FutORAMa, CCS'23) demonstrate that hierarchical ORAM-based schemes can be made efficient given sufficient client-side memory. In this work, we present a new hierarchical ORAM construction that achieves practical performance without requiring large local memory.

Abstract. An oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky [ J. ACM, 43 (1996), pp. 431–473] is a (probabilistic) RAM that hides its access pattern; i.e., for every input the observed locations accessed are similarly distributed. In recent years there has been great progress both in terms of upper bounds and in terms of lower bounds, essentially pinning down the smallest overhead possible in various settings of parameters. We observe that there is a very natural setting of parameters in which no nontrivial lower bound is known—not even those in restricted models of computation (like the so-called balls and bins model). Let [Formula: see text] and [Formula: see text] be the number of cells and bit-size of cells, respectively, in the RAM that we wish to simulate obliviously. Denote by [Formula: see text] the cell bit-size of the ORAM. All previous ORAM lower bounds have a multiplicative [Formula: see text] factor which makes them trivial in many settings of parameters of interest. In this work, we prove a new ORAM lower bound that captures this setting (and in all other settings it is at least as good as previous ones, quantitatively). We show that any ORAM must make (amortized) [Formula: see text] memory probes for every logical operation. Here, [Formula: see text] denotes the bit-size of the local storage of the ORAM. Our lower bound implies that logarithmic overhead in accesses is necessary, even if [Formula: see text]. Our lower bound is tight for all settings of parameters, up to the [Formula: see text] factor. Our bound also extends to the noncolluding multiserver setting. As an application, we derive the first (unconditional) separation between the overhead needed for ORAMs in the online versus offline models. Specifically, we show that when [Formula: see text] and [Formula: see text], there exists an offline ORAM that makes (on average) [Formula: see text] memory probes per logical operation, while every online one must make [Formula: see text] memory probes per logical operation. No such previous separation was known for any setting of parameters—not even in the balls and bins model.

A (single server) private information retrieval (PIR) allows a client to read data from a public database held on a remote server, without revealing to the server which locations she is reading. In a doubly efficient PIR (DEPIR), the database is first preprocessed, but the server can subsequently answer any client’s query in time that is sub-linear in the database size. Prior work gave a plausible candidate for a public-key variant of DEPIR, where a trusted party is needed to securely preprocess the database and generate a corresponding public key for the clients; security relied on a new non-standard code-based assumption and a heuristic use of ideal obfuscation. In this work we construct the stronger unkeyed notion of DEPIR, where the preprocessing is a deterministic procedure that the server can execute on its own. Moreover, we prove security under just the standard ring learning-with-errors (RingLWE) assumption. For a database of size N and any constant ε>0, the preprocessing run-time and size is O(N1+ε), while the run-time and communication-complexity of each PIR query is polylog(N). We also show how to update the preprocessed database in time O(Nε). Our approach is to first construct a standard PIR where the server’s computation consists of evaluating a multivariate polynomial; we then convert it to a DEPIR by preprocessing the polynomial to allow for fast evaluation, using the techniques of Kedlaya and Umans (STOC ’08).

Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC ’87 and J. ACM ’96) is a technique for provably obfuscating programs’ access patterns, such that the access patterns leak no information about the programs’ secret inputs. To compile a general program to an oblivious counterpart, it is well-known that Ω (log N ) amortized blowup in memory accesses is necessary, where N is the size of the logical memory. This was shown in Goldreich and Ostrovksy’s original ORAM work for statistical security and in a somewhat restricted model (the so-called balls-and-bins model), and recently by Larsen and Nielsen (CRYPTO ’18) for computational security. A long-standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). In this article, we resolve this problem and present the first secure ORAM with O (log N ) amortized blowup, assuming one-way functions. Our result is inspired by and non-trivially improves on the recent beautiful work of Patel et al. (FOCS ’18) who gave a construction with O (log N ⋅ log log N ) amortized blowup, assuming one-way functions. One of our building blocks of independent interest is a linear-time deterministic oblivious algorithm for tight compaction: Given an array of n elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our O ( n ) algorithm improves the previously best-known deterministic or randomized algorithms whose running time is O ( n ⋅ log n ) or O ( n ⋅ log log n ), respectively.

An oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (STOC '87 and J. ACM '96), is a technique for hiding RAM's access pattern. That is, for every input the distribution of the observed locations accessed by the machine is essentially independent of the machine's secret inputs. Recent progress culminated in a work of Asharov et al. (EUROCRYPT '20), obtaining an ORAM with (amortized) logarithmic overhead in total work, which is known to be optimal. Oblivious Parallel RAM (OPRAM) is a natural extension of ORAM to the (more realistic) parallel setting where several processors make concurrent accesses to a shared memory. It is known that any OPRAM must incur logarithmic work overhead (in the balls and bins model). Despite the significant recent advances for constructing ORAM, there is still a significant gap for OPRAM: all existing OPRAM schemes incur a poly-logarithmic overhead either in total work or in depth. Our main result closes the aforementioned gap and provides an optimal OPRAM. Specifically, assuming one-way functions, we show that any Parallel RAM with memory capacity N can be obliviously simulated in space O(N), incurring only O(log N) blowup in (amortized) total work as well as in depth. Our transformation supports all PRAMs in the CRCW (concurrent read, concurrent write) mode and the resulting simulation is in the CRCW mode as well.

A long-standing open question in the algorithms and complexity literature is whether there exist sorting circuits of size o(n log n). A recent work by Asharov, Lin, and Shi (SODA'21) showed that if the elements to be sorted have short keys whose length k = o(log n), then one can indeed overcome the n log n barrier for sorting circuits, by leveraging non-comparison-based techniques. More specifically, Asharov et al. showed that there exist O(n) · min(k, log n)-sized sorting circuits for k-bit keys, ignoring polylog∗ factors. Interestingly, the recent works by Farhadi et al. (STOC'19) and Asharov et al. (SODA'21) also showed that the above result is essentially optimal for every key length k, assuming that the famous Li-Li network coding conjecture holds. Note also that proving any unconditional super-linear circuit lower bound for a wide class of problems is beyond the reach of current techniques. Unfortunately, the approach taken by previous works to achieve optimality in size somewhat crucially relies on sacrificing the depth: specifically, their circuit is super-polylogarithmic in depth even for 1-bit keys. Asharov et al. phrase it as an open question how to achieve optimality both in size and depth. In this paper, we close this important gap in our understanding. We construct a sorting circuit of size O(n) · min(k, log n) (ignoring polylog∗ terms) and depth O(log n). To achieve this, our approach departs significantly from the prior works. Our result can be viewed as a generalization of the landmark result by Ajtai, Komlós, and Szemerédi (STOC'83), simultaneously in terms of size and depth. Specifically, for k = o(log n), we achieve asymptotical improvements in size over the AKS sorting circuit, while preserving optimality in depth.

We consider the classical problem of sorting an input array containing $n$ elements, where each element is described with a $k$-bit comparison key and a $w$-bit payload. A long-standing open problem is whether there exist $(k + w) \cdot o(n \log n)$-sized Boolean circuits for sorting. A landmark result in this area is the work by Ajtai, Komlós, and Szemerédi (An $O(n \log n)$ sorting network, STOC'83), where they showed how to achieve sorting circuits with $(k + w) \cdot O(n \log n)$ Boolean gates. The recent work of Farhadi et al. (Lower bounds for external memory integer sorting via network coding, STOC'19) showed that if the famous Li-Li network coding conjecture is true, then sorting circuits of size $w \cdot o(n \log n)$ do not exist for general $k$; however, no unconditional lower bound is known (in fact proving superlinear circuit lower bounds in general is out of the reach of existing techniques). In this paper, we show that one can overcome the $n\log n$ barrier when the keys to be sorted are short. Specifically, we prove that there is a circuit with $(k + w) \cdot O(n k) \cdot (\log^*n - \log^* (w + k))^{2+\epsilon}$ Boolean gates capable of sorting any input array containing $n$ elements, each described with a $k$-bit key and a $w$-bit payload. Therefore, if the keys to be sorted are short, say, $k < o(\log n)$, our result is asymptotically better than the classical Ajtai, Komlós, and Szemerédi sorting network (ignoring ${\sf poly}\log^*$ terms); and we also overcome the $n \log n$ barrier in such cases. Such a result might be surprising initially because it is long known that comparator-based techniques must incur $\Omega(n \log n)$ comparator gates even when the keys to be sorted are only 1-bit long (e.g., see Knuth's “Art of Programming” textbook). To the best of our knowledge, we are the first to achieve nontrivial results for sorting circuits using non-comparison-based techniques. We also show that if the Li-Li network coding conjecture is true, our upper bound is optimal, barring ${\sf poly}\log^*$ terms, for every $k$ as long as $k = O(\log n)$.

We consider the classical problem of sorting n elements, where each element is described with a k-bit comparison-key and a w-bit payload. A long-standing open problem is whether there exist (k + w) · o(n log n)-sized boolean circuits for sorting. Ajtai, Komlós, and Szemerédi (STOC'83) constructed the famous AKS sorting network with (k + w) · O(n log n) boolean gates. Recently, Farhadi et al. (STOC'19) showed that if the famous Li-Li network coding conjecture is true, then sorting circuits of size w · o(n log n) do not exist for general k (while unconditional circuit lower bound is out of the reach of existing techniques). In this paper, we show that one can overcome the n log n barrier when the comparison-keys are short. Specifically, we construct a sorting circuit with (k +w) · O(nk) · poly(log∗ n – log∗(w + k)) boolean gates, asymptotically better than AKS sorting network if the keys are short, say, k = o(log n) (ignoring poly log∗ terms). Such a result might be surprising since comparator-based techniques must incur Ω(n log n) comparators even when the keys are only 1-bit long (e.g., see Knuth's “Art of Programming” textbook). To the best of our knowledge, this is also the first non-trivial result on non-comparison-based sorting circuits. We also show that if the Li-Li network coding conjecture is true, our upper bound is optimal, barring poly log∗ terms, for every k = O(log n).

Massively Parallel Computation (MPC) is a model of computation widely believed to best capture realistic parallel computing architectures such as large-scale MapReduce and Hadoop clusters. Motivated by the fact that many data analytics tasks performed on these platforms involve sensitive user data, we initiate the theoretical exploration of how to leverage MPC architectures to enable efficient, privacy-preserving computation over massive data. Clearly if a computation task does not lend itself to an efficient implementation on MPC even without security, then we cannot hope to compute it efficiently on MPC with security. We show, on the other hand, that any task that can be efficiently computed on MPC can also be securely computed with comparable efficiency. Specifically, we show the following results: - any MPC algorithm can be compiled to a communication-oblivious counterpart while asymptotically preserving its round and space complexity, where communication-obliviousness ensures that any network intermediary observing the communication patterns learn no information about the secret inputs; - assuming the existence of Fully Homomorphic Encryption with a suitable notion of compactness and other standard cryptographic assumptions, any MPC algorithm can be compiled to a secure counterpart that defends against an adversary who controls not only intermediate network routers but additionally up to 1/3 - η fraction of machines (for an arbitrarily small constant η) - moreover, this compilation preserves the round complexity tightly, and preserves the space complexity upto a multiplicative security parameter related blowup. As an initial exploration of this important direction, our work suggests new definitions and proposes novel protocols that blend algorithmic and cryptographic techniques.

It is well-known that non-comparison-based techniques can allow us to sort n elements in o(n log n) time on a Random-Access Machine (RAM). On the other hand, it is a long-standing open question whether (non-comparison-based) circuits can sort n elements from the domain [1‥2k] with o(kn log n) boolean gates. We consider weakened forms of this question: first, we consider a restricted class of sorting where the number of distinct keys is much smaller than the input length; and second, we explore Oblivious RAMs and probabilistic circuit families, i.e., computational models that are somewhat more powerful than circuits but much weaker than RAM. We show that Oblivious RAMs and probabilistic circuit families can sort o(log n)-bit keys in o(n log n) time or o(kn log n) circuit complexity. Our algorithms work in the indivisible model, i.e., not only can they sort an array of numerical keys — if each key additionally carries an opaque ball, our algorithms can also move the balls into the correct order. We further show that in such an indivisible model, it is impossible to sort Ω(log n)-bit keys in o(n log n) time, and thus the o(log n)-bit-key assumption is necessary for overcoming the n log n barrier. Finally, after optimizing the IO efficiency, we show that even the 1-bit special case can solve open questions: our oblivious algorithms solve tight compaction and selection with optimal IO efficiency for the first time.

Although external-memory sorting has been a classical algorithms abstraction and has been heavily studied in the literature, perhaps somewhat surprisingly, when data-obliviousness is a requirement, even very rudimentary questions remain open. Prior to our work, it is not even known how to construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost. We make a significant step forward in our understanding of external-memory, oblivious sorting algorithms. Not only do we construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost, our algorithm is also cache-agnostic in that the algorithm need not know the storage hierarchy's internal parameters such as the cache and cache-line sizes. Our result immediately implies a cache-agnostic ORAM construction whose asymptotic IO-cost matches the best known cache-aware scheme. Last but not the least, we propose and adopt a new and stronger security notion for external-memory, oblivious algorithms and argue that this new notion is desirable for resisting possible cache-timing attacks. Thus our work also lays a foundation for the study of oblivious algorithms in the cache-agnostic model.

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.

Some coevolutionary issues are illustrated elsewhere. This paper investigates the ability of coevolutionary genetic algorithm to solve games. Specifically, it focuses on two-player, zero-sum and symmetric games with both pure and mixed strategies. Games with mixed strategies are challenging for coevolution since the Nash strategy does not yield a higher payoff. On the other hand, games with pure strategies are more co-evolvable especially with mechanisms to keep the population diverse. Empirically, adopting niching techniques such as restricted tournament selection helps coevolution. Finally, this paper demonstrates the existence of games that require an exponential population size with respect to the size of the game.

This paper investigates the utility of sampling as an evaluation-relaxation technique in genetic algorithms (GAs). In many real-world applications, sampling can be used to generate a less accurate, but computationally inexpensive fitness evaluator to speed GAs up. This paper focuses on the problem of polynomial regression as an example of problems with positive dependency among genes. Via statistical analysis of the noise introduced by sampling, this paper develops facet-wise models for the optimal sampling size, and these models are empirically verified. The results show that when the population is sized properly, small sampling sizes are preferred for most applications. When a fixed population size is adopted, which is usually the case in real-world applications, an optimal sampling size exists. If the sampling size is too small, the sampling noise increases, and GAs would perform poorly because of an insufficiently large population. If the sampling size is too large, the GA would spend too much time in fitness calculation and cannot perform well either within limited run duration.