{'fraction_non_alphanumeric': 0.04221947823345506, 'fraction_numerical': 0.013109844205659039, 'mean_word_length': 4.0738469741402294, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exploring Differential Obliviousness

In a recent paper Chan et al. [SODA '19] proposed a relaxation of the notion of (full) memory obliviousness, which was introduced by Goldreich and Ostrovsky [J. ACM '96] and extensively researched by cryptographers. The new notion, differential obliviousness, requires that any two neighboring inputs exhibit similar memory access patterns, where the similarity requirement is that of differential privacy. Chan et al. demonstrated that differential obliviousness allows achieving improved efficiency for several algorithmic tasks, including sorting, merging of sorted lists, and range query data structures. In this work, we continue the exploration and mapping of differential obliviousness, focusing on algorithms that do not necessarily examine all their input. This choice is motivated by the fact that the existence of logarithmic overhead ORAM protocols implies that differential obliviousness can yield at most a logarithmic improvement in efficiency for computations that need to examine all their input. In particular, we explore property testing, where we show that differential obliviousness yields an almost linear improvement in overhead in the dense graph model, and at most quadratic improvement in the bounded degree model. We also explore tasks where a non-oblivious algorithm would need to explore different portions of the input, where the latter would depend on the input itself, and where we show that such a behavior can be maintained under differential obliviousness, but not under full obliviousness. Our examples suggest that there would be benefits in further exploring which class of computational tasks are amenable to differential obliviousness.


Introduction
A program's memory access pattern can leak significant information about the private information used by the program even if the memory content is encrypted. Such leakage can turn into a data protection problem in various settings. In particular, where data is outsourced to be stored on an external server, it has been shown that access pattern leakage can be exploited in practical attacks and lead to the compromise of the underlying data [19,4,27,20,22]. Such leakages can also be exploited when a program is executed in a secure enclave environment but needs to access memory that is external to the enclave.
Memory access pattern leakage can be avoided by employing a strategy that makes the sequence of memory accesses (computationally or statistically) independent of the content being processed. Beginning with the seminal work of Goldreich and Ostrovsky, it is well known how to transform any program running on a random access memory (RAM) machine to one with an oblivious memory access pattern while retaining efficiency by using an Oblivious RAM protocol (ORAM) [10,28,13]. Current state-of-the-art ORAM protocols achieve logarithmic overhead [2], matching a recent lowerbound by Larsen and Nielsen [23], and protocols with O(1) overhead exist when large blocks are retrieved [6,26]. To further reduce the overhead, oblivious memory access pattern protocols have been devised for specific tasks, including graph algorithms [3,17], geometric algorithms [8] and sorting [16,24]. The latter is motivated by sorting being a fundamental and well researched computational task as well as its ubiquity in data processing.

Differential Obliviousness
Full obliviousness is rather a strong requirement: any two possible inputs (of the same size) should exhibit identical or indistinguishable sequences of memory accesses. Achieving full obliviousness via a generic use of ORAM protocols requires a setup phase with running time (at least) linear in the memory size and then a logarithmic overhead per each memory access.
A recent work by Chan, Chung, Maggs, and Shi [5] put forward a relaxation of the obliviousness requirement where indistinguishability is replaced with differential privacy. Intuitively, this means that any two possible neighboring inputs should exhibit memory access patters that are similar enough to satisfy differential privacy, but may still be too dissimilar to be "cryptographically" indistinguishable. It is not a priori clear whether differential obliviousness can be achieved without resorting to full obliviousness. However, the recent work Chan et al. showed that differential obliviousness does allow achieving improved efficiency for several algorithmic tasks, including sorting (over very small domains), merging of sorted lists, and range query data structures.
Furthermore, even the use of ORAM protocols may be insufficient for preventing leakage in cases where the number of memory probes is input dependent. In fact, Kellaris et al. [20] show that such leakage can result in a complete reconstruction in the case of retrieving elements specified by range queries, as the number of records returned depends on the contents of the data structure. Full obliviousness would require that the sequence of memory accesses would be padded to a maximal one to avoid such leakage, a solution that would have a dire effect on the efficiency of many algorithms. Differential obliviousness may in some cases allow achieving meaningful privacy while maintaining efficiency. Examples of such protocols include the combination of ORAM with differentially private sanitization by Kellaris et al. [21] and the more recent work of Chan et al. [5] on range query data structures, which avoids using ORAM.

This Work: Exploring Differential Obliviousness
Noting that the existence of logarithmic overhead ORAM protocols implies that differential obliviousness can yield at most a logarithmic improvement in efficiency for computations that need to examine all their input, we explore tasks where this is not the case. In particular, we focus on property testing and on tasks where the number of memory accesses can depend on the input.
Property testing. As evidence that differential obliviousness can provide a significant improvement over full obliviousness, we show in Section 3 that property testers in the dense graph model, where the input is in the adjacency matrix representation [12], can be made differentially oblivious. This result captures a large set of testable graph properties [12,1] including, e.g., graph bipartitness and having a large clique. Testers in this class probe a uniformly random subgraph and hence are fully oblivious without any modification, as their access pattern does not depend on the input graph. However, this is not the case if the tester reveals its output to the adversary, as this allows learning information about the specific probed subgraph. A fully oblivious tester would need to access a linear-sized subgraph, whereas we show that a differentially oblivious tester only needs to apply the original tester for O(1) times. 1 We also consider property testing in the bounded degree model, where the input is in the incidence lists model [14]. In this model we provide negative results, demonstrating that adaptive testers cannot, generally, be made differentially oblivious without a significant loss in efficiency. In particular, in Section 4 we consider differentially oblivious property testers for connectivity in graphs of degree at most two. For non-oblivious testers, it is known that constant number of probes suffice when the tester is adaptive [14]. 2 It is also known that any non-adaptive tester for this task requires probing Ω( √ n) nodes [29]. We show that this lower bound extends to differentially oblivious testers, i.e., any differentially oblivious tester for connectivity in graphs of maximal degree 2 requires Ω( √ n) probes. While this still improves over full obliviousness, the gap between full and differential obliviousness is in this case diminished.
Locating an Object Satisfying a Property. Here, our goal is to check whether a given data set of objects includes an object that satisfies a specified property. Without obliviousness requirements, a natural approach is to probe elements in a random order until an element satisfying the property is found or all elements were probed. If a p fraction of the elements satisfy the property, then the expected number of probes is 1/p. This algorithm is in fact instance optimal when the data set is randomly permuted. 3 A fully oblivious algorithm would require Ω(n) probes on any dataset even when p = 1. In contrast, we demonstrate in Section 5 that with differential obliviousness instance optimality can, to a large extent, be preserved. Our differentially oblivious algorithm always returns a correct answer and makes at most m probes with probability at least 1 − e −O(mp) .
Prefix Sum. Our last example considers a sorted dataset (possibly, the result of an earlier phase in the computation). Our goal is to compute the sum of all records in the (sorted) dataset that are less than or equal to a given value a. 4 Without obliviousness requirements, one can find the greatest record less than or equal to value a, say, using binary search, and then compute the prefix sum by a quick scan through all records appearing before such record. This algorithm is in fact nearly instance optimal, as it can be shown that any algorithm which returns the correct exact answer with non-negligible probability must probe all entries greater than a. However, fully oblivious algorithms would have to probe the entire dataset.
In Section 6 we give our nearly instance optimal differentially oblivious prefix sum algorithm. As the probes of a binary search would leak information about the memory content, we introduce a differen- 1 We omit dependencies on privacy and accuracy parameters from this introductory description. 2 In an adaptive tester at least one choice of a node to probe should depend on information gathered from incidence lists of previously probed nodes. 3 Our treatment of instance optimality is rather informal. The concept was originally presented in [9]. 4 See Section 6 for the definition of privacy.
tially oblivious "simulation" of the binary search. Our differentially oblivious binary search runs in time O(log 2 n).
We also address the scenario where there are multiple prefix sum queries to the same database. If the number of queries is bounded by some integer t, then each differentially oblivious binary search will run in time O(t log 2 n) (as we need to run the search algorithm with a smaller privacy parameter ε). Using ORAM, one can answer such queries with O(n log n) prepossessing time and O(log 2 n) time per query. Combining our algorithm and ORAM, we can amortize the pre-processing time over O( √ n) queries, that is, without any pre-processing, the running of time of answering the i-th query is O(i log 4 n) for the first O( √ n) queries and O(log 2 n) for any further query.

Background Work
The work by Chan, Chung, Maggs, and Shi [5] mentioned above is most relevant for this article. Goldreich, Goldwasser, and Ron [12] initiated the research on graph property testing. Goldreich's book on property testing [11] gives sufficient background for our discussion. Dwork, McSherry, Nissim, and Smith [7] presented differential Privacy. For more details on ORAM and a list of relevant papers, the reader can consult [2].

Model of Computation
We consider the standard Random Access Memory (RAM) model of computation that consists of a CPU and a memory. The CPU executes a program and is allowed to perform two types of memory operations: read a value from a specified physical address, and write a value to a specified physical address. We assume that the CPU has a private cache of where it can store a O(1) values (and/or a polylogarithmic number of bits). As an example, in the setting of a client storing its data on the cloud, the client plays the role of the CPU and the cloud server plays the role of the memory. We assume that a program's sequence of read and write operations may be visible to an adversary. We will call this sequence the program's access pattern. We will further assume that the memory content is encrypted so that no other information is leaked about the content read from and stored in memory location. The program's access pattern may depend on the program's input, and may hence leak information about it.

Oblivious Algorithms
There are various works focused on oblivious algorithms [8,15,25] and Oblivious RAM (ORAM) constructions [13]. These works adopt "full obliviousness" as a privacy notion. Suppose that M (λ, x) is an algorithm that takes in two inputs, a security parameter λ and an input dataset denoted x. We denote by Access M (λ, x), the ordered sequence of memory accesses the algorithm M makes on the input λ and x. Definition 2.1 (Fully Oblivious Algorithms). Let δ be a function in a security parameter λ. We say that algorithm M is δ-statistically oblivious, iff for all inputs x and y of equal length, and for all λ, it holds that Access M (λ, x) ≈ δ(λ) Access M (λ, y) where ≈ δ(λ) denotes that the two distributions have at most δ(λ) statistical distance. We say that M is perfectly oblivious when δ = 0.

Differentially Oblivious Algorithms
Suppose that M (λ, x, q) is an (stateful) algorithm that takes in three inputs, a security parameter λ > 0, an input dataset denoted by x and a value q. We slightly change the definition of differential oblivious algorithms given in [5]: Definition 2.2 (Neighbor-respecting). We say that two input datasets x and y are neighboring iff they are of the same length and differ in exactly one entry. We say that A = (A 1 , A 2 ) is neighbor-respecting adversary iff for every λ and every n, A 1 outputs neighboring datasets x 0 , x 1 , with probability 1. Definition 2.3. Let ε, δ be privacy parameters. Let M be a (possibly stateful) algorithm described as above. To an adversary A we associate the experiment in Figure 1, for every λ ∈ N. We say that M is (ε, δ)-adaptively differentially oblivious if for any (unbounded) stateful neighbor-respecting adversary A we have In Figure 1, Access M (x, q, state) denotes the ordered sequence of memory accesses the algorithm M makes on the inputs x, q and state.
Remark 2.4. The notion of adaptivity here is different from the one defined in [5]. We require that the dataset x remain the same through the experiment whereas in [5] the adaptive adversary can add or remove entries to the dataset.
As with differential privacy, we usually think about ε as a small constant and require that δ = o(1/n) where n = |x| [7]. Observe that if M is δ-statistically oblivious then it is also (0, δ)-differentially oblivious.
The following simple lemma will be useful to analyze our algorithms. The proof of the lemma appears in Appendix A.
Lemma 2.5. Let A be an (ε, 0)-differentially oblivious algorithm and B be an algorithm such that for every dataset x the statistical distance between A(x) and

Differentially Oblivious Property Testing of Dense Graphs Properties
In this section, we present a differentially oblivious property tester for dense graphs properties in the adjacency matrix representation model. A property tester is an algorithm that decides whether a given object has a predetermined property or is far from any object having this property by examining a small random sample of its input. The correctness requirement of property testers ignores objects that neither have the property nor are far from having the property. However, the privacy requirement is "worst case" and should hold for any two neighboring graphs. For the definition of privacy we say that two graphs G, G of size n are neighbors if one can get G by changing the neighbors of exactly one node of G.
Property testing of graph properties in the adjacency matrix representation was introduced in [12].
and only if u and v are adjacent in G. The notion of distance between graphs is defined to be the number of different matrix entries over |V | 2 . This model is most suitable for dense graphs where the number of edges O(|V | 2 ). We define a property P of graphs to be a subset of the graphs. We write G ∈ P to show that graph G has the property P. For example, we can define the bipartiteness property, where P is the set of all bipartite graphs. 5 We say that an n-vertex G is γ-far from P if for every n-vertex graph G = (V , E ) ∈ P it holds that the symmetric difference between E and E is greater than γn 2 . We define the property testing in this model as follows: . A (β, γ)-tester for a graph property P is a probabilistic algorithm that, on inputs n, β, γ, and an adjacency matrix of an n-vertex graph G = (V, E): 1. Outputs 1 with probability at least β, if G ∈ P.
2. Outputs 0 with probability at least β, if G is γ-far from P.
We say a tester has one-sided error, if it accepts every graph in P with probability 1. We say a tester is non-adaptive if it determines all its queries to adjacency matrix only based on n, β, γ, and its randomness; otherwise, we say it is adaptive. 12]). Consider the following (2/3, γ)-tester for bipartiteness: Choose a random subset A ⊂ V of sizeÕ(1/γ 2 ) with uniform distribution and output 1 iff the graph induced by A is bipartite. Clearly, if G is bipartite, then the tester will always return 1. Goldreich et al. [12] proved that if G is γ-far from a bipartite graph, then the probability that the algorithm returns 1 is at most 1/3.
Recall that in the graph property testing, the tester T chooses a random subset of the graph with uniform distribution to test the property P. Given the access pattern of the tester T , an adversary will learn nothing since it is uniformly random. Thus, the access pattern by itself does not reveal any information about the input graph. However, we assume that the adversary also learns the tester's output and can hence learn some information about the input graph based on the output of the tester. To protect this information, we run tester T for constant number of times and output 1 iff the number of times T outputs 1 exceed a (randomly chosen) threshold.
Let T be a (β, γ)-tester for a graph property P where β ≤ 1/4. We write c β,γ for the number of nodes that T samples. Note that c β,γ is constant in the graph size and a function of β and γ. For simplicity, we only consider property testers with one-sided error. In Figure 2, we describe a (β, γ)-tester Tester T that outputs 1 with probability at least β if G ∈ P and outputs 0 with probability at least β, if G is γ -far from P, where γ is defined below.
. Algorithm Tester T is an (ε, δ(1 + e ε ))-differentially oblivious algorithm that outputs 1 with probability 1 if G ∈ P, and output 0 with probability at least The proof of Theorem 3.3 appears in Appendix A.2. 5 Recall that an undirected graph is bipartite (or 2-colorable) if if its vertices can be 2-partitioned into two parts, V1 and V2, such that each part is an independent set (i.e.,

Lower Bounds on Testing Connectivity in the Incidence Lists Model
We now consider connectivity differentially oblivious testing in the incidence lists model [14]. In this model a graph has a bounded degree d and is represented as a function f : ). In this model, the relative distance between graphs is normalized by dn -the maximal number of edges in the graph. Formally, for two graphs with n vertices, A (β, γ)-tester in the incidence lists model is defined as in Definition 3.1, where a property P is a set of graphs whose maximal degree is d and the distance to a property is defined with respect to dist d . Goldreich and Ron [14] showed how to test if a graph is connected in the incidence list model in timẽ O(1/γ). Raskhodnikova and Smith [29] showed that a tester for connectivity (or any non-trivial property) with run-time o( √ n) has to be adaptive, that is, the nodes that the algorithm probes should depend on the neighbors of nodes the algorithm has already probed (e.g., the algorithm probes some node u, discovers that v is a neighbor and u, and probes v). We strengthen their results by showing that any tester for connectivity in graphs of maximal degree 2 and run-time o( √ n) cannot be a differentially oblivious algorithm. We stress that adaptivity alone is not a reason for inefficiency with differential obliviousness. In fact, there exist differentially oblivious algorithms that are adaptive (e.g., our algorithm in Section 6).
Proof. Let TESTER be a (3/4, 1/3)-tester for connectivity in graphs of degree at most 2. We somewhat relax the definition of probes and assume that once the tester probes a node, it sees all edges adjacent to this node. We prove that if TESTER probes less than c √ n/e 2ε nodes (for some constant c), then it is not (ε, δ)-oblivious.
Assume that n ≡ 0 (mod 3). Let G 1 = (V, E 1 ) be a cycle of length n and G 2 = (V, E 1 ) consist of n/3 disjoint triangles. Clearly, G 1 is connected and G 2 is 1/3-far from a connected graph. For a permutation π : V → V , define π(G i ) = (V, π(E i )), where π(E i ) = {(π(u), π(v)) : (u, v) ∈ E i }, and let perm(G i ) be a random graph isomorphic to G i , that is, perm(G i ) = π(G i ) for a permutation π chosen with uniform distribution. 6 On the random graph perm(G ) TESTER has to say "yes" with probability at least 3/4 and on the random graph perm(G 2 ) TESTER has to say "no" with probability at least 3/4. Observation 4.2. If TESTER does not probe two distinct nodes whose distance is at most two, then TESTER sees a collection paths of length two and cannot know if the graph is perm(G 1 ) or perm(G 2 ). Claim 4.3. Given the random graph perm(G 1 ), the tester has to probe two distinct nodes whose distance is at most 2 with probability at least 1/2.
Proof. Consider TESTER's answer when it sees a collection of paths of length 2. Assume first that the tester returns "No" with probability at least half in this case and let p be the probability that TESTER probes two distinct nodes whose distance is at most two on the random graph perm(G 1 ). The probability that TESTER returns "Yes" on perm(G 1 ) is at most p + 0.5(1 − p) = 0.5 + 0.5p. Thus, 0.5 + 0.5p ≥ 3/4, i.e., p ≥ 0.5.
If the tester returns "Yes" with probability at least half, then, by symmetric arguments, with probability at least 1/2 TESTER has to probe two nodes whose distance is at most two on the random graph perm(G 2 ). For a permutation π, if the distance between two nodes in π(G 2 ) is at most 2, then the distance between these two nodes in π(G 1 ) is at most 2. Thus, by Observation 4.2, Pr[TESTER probes 2 nodes whose distance is 1 or 2 on perm(G 1 )] ≥ Pr[TESTER probes 2 nodes whose distance is 1 or 2 perm(G 2 )] ≥ 1/2.
Denote the nodes of G 1 by V = {v 0 , . . . , v n−1 } and define a distribution on pairs of graphs H 1 , H 2 , obtained by the following process: • Choose a permutation π : V → V with uniform distribution and let H 1 = π(G 1 ).
The graphs are described in Figure 3. Note that H 2 is also a a random graph isomorphic to G 1 , thus, given H 2 one cannot know which pair of non-adjacent nodes u i , u j was used to create H 2 .
Observe that H 1 and H 2 differ on 4 nodes. Since TESTER is (ε, δ)-differntially oblivious, for every algorithm A,

Consider the following algorithm A:
If u i and at least one of u i+1 , u i+2 is probed by TESTER(H) prior to seeing any other pair of nodes of distance at most 2 in H 1 or H 2 , then return 1 otherwise return 0. Proof. The node u is a uniformly distributed node in H i and v is any node of distance at least 3 from v, thus there are n(n − 5)/2 options for {u, v}. Given a collection of paths of length at most 2 in H i all options are equally likely. Let w 1 , . . . , w k be the nodes probed in some execution of TESTER. Fix some pair of indices k 1 < k 2 . The probability that {u i , u i+1 } = {w k 1 , w k+2 } is at most 1/n(n − 5). Thus, the probability that u and v are probed is at most ( q 2 ) n(n−5)/2 = O(q 2 /n 2 ). Claim 4.5. Assume that TESTER probes at most q queries. The probability that A(H 1 ) = 1 is at least 1/2n − O(q 2 /n 2 ).
Proof. By Claim 4.3, the probability that TESTER probes at least one pair of nodes with distance at most 2 is at least 1/2. Given that this event occurs, the probability that the random u i (chosen with uniform distribution) has the smallest index in the first such pair in H 1 (i.e., the first pair is either (u i , u i+1 ) or (u i , u i+2 )) is at least 1/n.
Clearly, given these events no two nodes with distance at most 2 in H 1 were probed prior to probing the pair containing u i . Furthermore, there are O(1) pairs of nodes that are of distance at most 2 in H 2 and are of distance greater than 2 in H 1 . By Claim 4.4, the probability that such pair is probed prior to TESTER probing a pair of distance at most 2 in H 1 is O(q 2 /n 2 ). Claim 4.6. Suppose that TESTER probes at most q nodes. The probability that A(H 2 ) = 1 is O(q 2 /n 2 ).
Proof. The node u i is a uniformly distributed node in H 2 . Furthermore, the nodes u i+1 is a uniformly distributed node of distance at least 3 from u i in H 2 , thus by Claim 4.4, the probability that TESTER probes both u i and u i+1 prior to seeing any pair of distance at least 2 in H 2 is O(q 2 /n 2 ). This probability can only decrease if we require that TESTER probes both u i and u i+1 prior to seeing any pair of distance at least 2 in H 1 and in H 2 .
By the same arguments, the probability that TESTER probes both u i and u i+2 prior to seeing any pair of distance at least 2 in H 1 and in H 2 is O(q 2 /n 2 ).

Differentially Oblivious Algorithm for Locating an Object
Given a dataset of objects x our goal is to locate an object that satisfies a property P, if one exists. E.g., given a dataset consisting of employee records, find out an employee with income in the range $35, 000-$70, 000 if at least one such an employee exists in the dataset. Absent privacy requirements, a simple approach is to probe elements of the dataset in a random order until an element satisfying the property is found or all elements were probed. If a p fraction of the dataset enries satisfy P then the expected number of elements sampled by the non-private algorithm is 1/p. However, a perfectly oblivious algorithm would require Ω(n) probes on any dataset, in particular on a dataset where all elements satisfy P, where non-privately one probe would suffice. To see why, let P(x) = 1 if x = 1 and P(x) = 0 otherwise and let x include exactly one 1-entry in a uniformly random location. Observe that in expectation it requires Ω(n) memory probes to locate the 1-entry in x. Perfect obliviousness would hence imply an Ω(n) probes on any input.
We give a nearly instance optimal differentially oblivious algorithm that always returns a correct answer. Except for probability e −Ω(mp) the algorithm halts after m steps.
Detailed Algorithm. Given the access pattern of the non-private algorithm, an adversary can learn that the last probed element satisfies P. To hide this information, we change the stopping condition to having probed at least a (randomly chosen) threshold of elements satisfying P. If after n/2 probes the number of elements satisfying P is below the threshold the entire dataset is scanned. Our algorithm Locate P is described in Figure 4. On a given array x, algorithm Locate P outputs 1 iff there exists an element in x satisfying the property P. We remark that Algorithm Locate P uses a mechanism similar to the the sparse vector mechanism of [18]. However, in our case instead of using a single noisy threshold accross all steps, Algorithm Locate P generates in each step a noisy thresholdT = T + Lap( 1 ε ). The value of T ensures that with high probabilityT > 0. The proof of Theorem 5.1 is given in Appendix A.3.

Differentially Oblivious Prefix Sum
Suppose that there is a dataset consisting of sorted sensitive user records, and one would like to compute the sum of all records in the (sorted) dataset that are less than or equal to a value a in a way that respects individual user's privacy. We call this task differentially oblivious prefix sum. For the definition of privacy we say that two datasets of size n are neighbors if they agree on n − 1 elements (although, as sorted arrays they can disagree on many indices). For example, (1,2,3,4) and (1,3,4,5) are neighbors and should have similar access pattern. Without privacy one can find the greatest record less than or equal to value a, and then compute the prefix sum by a quick scan through all records appearing before such record. Any perfectly secure algorithm must read the entire dataset (since it is possible that all elements are smaller than a). Here, we give a differentially oblivious prefix sum algorithm that for many instances is much faster than any perfectly oblivious algorithm.
Intuition. Absent privacy requirements, using binary search, one can find the greatest element less than or equal to a, and then compute the prefix sum by a quick scan through all records that appear before such record. However, the binary search access pattern allows the adversary to gain sensitive information about the input. Our main idea is to approximately simulate the binary search and obfuscate the memory accesses to obtain differential obliviousness. In order to do that, we first divide the input array into k chunks (where k is polynomial in 1/ε, log 1/δ, and log n). Then, we find the chunk that contains the greatest element less than or equal to a by comparing the first element (hence, the smallest element) of each chunk to a. Let I be the index of such chunk. Next, we compute a noisy interval that contains I using the Laplacian distribution. We iteractively repeat this process on the noisy interval, where in each step we eliminate more than a quarter of the elements of the interval. We continue until the size of the array is less than or equal to k. Next, we scan all elements in the remaining array and find the index of the greatest element smaller than or equal to a. Let i be the index of such element; we compute the prefix sum by scanning the array x until index i.
The Search Algorithm. We present a search algorithm in Figure 5; on input x = (x 1 , . . . , x n ) and a this algorithm finds the largest index I such that x I ≤ a. To compute the prefix sum, we computê I = I + Lap(1/ε) + log 1/δ ε and scan the firstÎ elements of the dataset, summing only the first I. We show in Theorem 6.2 that our search algorithm is (ε, δ)-differentially oblivious.
Remark 6.1. We prove that algorithm SEARCH is an (ε, 0)-differentially private algorithm that returns a correct index with probability at least 1 − β. We could change it to an (ε, δ)-differentially private algorithm that never errs. This is done by truncating the noise to log 1/δ ε . Theorem 6.2. Let β < 1/n and ε < log 2 n. Algorithm SEARCH is an (ε, 0)-differentially oblivious algorithm that, for any input array with size n and a ∈ R, returns a correct index with probability at least 1 − β. The running time of Algorithm SEARCH is O( 1 ε log 2 n log 1 β ).
Theorem 6.2 is proved in Appendix A.4.

Dealing with Multiple Queries
We extend our prefix sum algorithm to answer multiple queries. We can answer a bounded number of queries by running the differentially oblivious prefix sum algorithm multiple times. That is, when we want an (ε, 0)-oblivious algorithm correctly answering t queries with probability at least 1 − β, we execute algorithm SEARCH t times with privacy parameter ε/t and error probability β/t (each time also computing the appropriate prefix sum). Thus, the running time of the algorithm is O( t 2 ε log 2 n log t β ) (excluding the scan time for computing the sum).
On the other hand, we can use an ORAM to answer unbounded number of queries. That is, in a preprocessing stage we store the n records and for each record we store the sum of all records up to this record. Thereafter, answering each query will require one binary search. Using the ORAM of [2], the pre-processing will take time O(n log n) and answering each query will take time O(log 2 n). Thus, the ORAM algorithm is more efficient when t ≥ √ n. We use ORAM along with our differentially oblivious prefix sum algorithm to answer unbounded number of queries while preserving privacy, combining the advantages of both of the previous algorithms. Theorem 6.3. Algorithm MULTISEARCH, described in Figure 6, is an (ε, 0)-oblivious algorithm, which executes Algorithm SEARCH at most O( √ n) times, where the run time of the t-th execution is O( t ε log 3 n log n β ), scans the original database at most once, and in addition each query run time is at most O(log 2 n).
Proof. First note that we only pay for privacy in the executions of algorithm SEARCH (reading and writing to the ORAM is perfectly private). In the t-th execution of algorithm SEARCH, we insert at least 2t elements to the ORAM, thus after √ n executions we inserted at least √ n t=1 2t = n elements to the ORAM. By simple composition, algorithm MULTISEARCH is (ε , 0)-differentialy private, where where the last inequality is implied by the sum of the harmonic series.    Proof. Let x and y be two neighboring datasets and S be a sets of outputs. Then, A.2 Proof of the Correctness and Privacy of Algorithm TESTER T Theorem 3.3 is implied by the following lemmas.
Proof. We first analyze a variant of Tester T , denoted by TESTER T , in which Step 4 is replaced by "If c >T then output 1" (that is, the algorithm does not check if c > min{4T,T } before deciding in the positive). Let G = (V, E) and G = (V , E ) be two neighboring graphs such that they differ on node v ∈ V . Fix the random choices of subsets A in Step 2b and observe that after the execution of for loop, the count c can differ by at most 1 between the executions on G and G . LetT be the smallest integer greater thanT . Since algorithm TESTER T uses the Laplace mechanism e −ε Pr[T < a] ≤ Pr[T < a − 1] ≤ e ε Pr[T < a] for every a. Thus, We next prove that Tester T is (ε, δ(1 + e ε ))-differentially oblivious using Lemma 2.5, that is we prove that for every graph G, the statistical distance between Tester T (G) and TESTER T (G) is at most δ. Let E be the event thatT > 4T and observe that the probability E occurs is at most δ. 7  Observe that Algorithm Tester T never errs when G ∈ P as in that case after the for loop is executed c = 4T and hence in Step 4 Tester T outputs 1. The next lemma analyses the error probability when G is γ -far from P.
, γ )-tester for the graph property P.
Proof. Observe that on Step 2c of the algorithm, we are eliminating at most n · c β,γ edges. Thus, we are eliminating at most 4T nc β,γ edges in total. Then, when G is γ -far from P, it is also γ-far from P after the removal of the observed nodes in each step of the for loop. We next prove that Algorithm Tester T fails with probability at most 2δ

A.3 Proof of the Correctness and Privacy of Algorithm LOCATE P
The proof of Theorem 5.1 follows from the following claim and lemmas.
Claim A.3. Let ≥ log n/ log log n. The probability that there exists an element j ∈ [n] such that algorithm Locate P samples the element j in Step 2a more than 2 times is less that 2 − .
Proof. We first analyze a variant of Locate P , denoted by LOCATE P , in which Step 2(c)ii is replaced by "If c >T then output 1" (that is, the algorithm does not check ifT > 0) and no element is sampled more than 2 log(2/δ) times. We analyze the privacy of LOCATE P (x ) similarly to the analysis of the sparse vector mechanism in [18]. Let x and x be two neighboring datasets that such that P(x j ) = 1 and P(x j ) = 0 for some j. Denote by τ = (T 1 , . . . ,T log n ) the values of the thresholds in an execution of LOCATE P , where each threshold is rounded up to the smallest integer greater thanT . Furthermore, let τ ∈ [log n] be the index such that LOCATE P on input x outputs 1 when i = 2 τ (if no such i exists, then τ ∈ log n +1). Observe that in each execution of Step 2(c)ii the count c on input x is at least the count on input x and can exceed it by at most 2 log(2/δ) (since j is sampled at most 2 log(2/δ) times). Thus, LOCATE P on input x with thresholds τ = (T 1 , . . . ,T τ −1 ,T τ − 2 log(2/δ),T τ +1 , . . . ,T log n ) outputs 1 when i = 2 τ . Since algorithm LOCATE P uses the Laplace mechanism with ε = ε/(2 log(1/δ)), We next prove that Locate P is (ε, δ(1 + e ε ))-differentially oblivious using Lemma 2.5. I.e, we prove that for every dataset x, the statistical distance between Access Locate P (x) and Access LOCATE P (x) is at most δ. Notice that if all the thresholds are positive and all elements are sampled at most 2 log(2/δ) times then Locate P (x) and LOCATE P (x) have the same access pattern. By Claim A.3, the probability that there exists a j that is sampled more than 2 log(2/δ) is at 2 − log(2/δ) = δ/2. We next observe that the probability that a thresholdT = T + Lap( 1 ε ) is negative is at most δ/2. Recall that Pr[Lap( 1 ε ) ≤ −t/ε ] = 1 2 e −t for every t > 0. Thus, Pr[T ≤ 0] = Pr[Lap( 1 ε ) ≤ − 1 ε ln( log n δ )] = δ 2 log n . Let A be the event that at least one of the log n thresholdsT is at most 0 or some j is sampled more that 2 log(2/δ) times. By the union bound the probability of A is at most δ. Therefore, for every set of access patterns S Next, we show that algorithm SEARCH is (ε, 0)-differentially oblivious.
Proof. We show below that each step of the while loop in algorithm SEARCH is (ε , 0)-differentially oblivious. Applying the basic composition theorem and Claim A.6, we obtain that the SEARCH algorithm is (ε = (2.5 log n)ε , 0)-differentially oblivious.
Fix a step of the loop and view it as an algorithm that returns min and max (given these values the access pattern of the next step is fixed). Let x and x be two neighboring datasets such that for some j we have x j > x j and x i = x i for all i < j. It holds that x i−1 ≤ x i ≤ x i for every i. Let I(x) and I(x ) be the values computed in step 2c of the algorithm on inputs x and x respectively. Thus, the value I(x) is at least the value I(x ) and can exceed it by one. Intuitively, since algorithm SEARCH uses the Laplace mechanism, the probabilities of returning a value min on x and x are at most e ±ε apart.