Brice Minaud
email: brice.minaud@ens.fr

Michael Reichle
email: michael.reichle@ens.fr

Dynamic Local Searchable Symmetric Encryption

In this article, we tackle for the first time the problem of dynamic memory-efficient Searchable Symmetric Encryption (SSE). In the term "memory-efficient" SSE, we encompass both the goals of local SSE, and page-efficient SSE. The centerpiece of our approach is a new connection between those two goals. We introduce a map, called the Generic Local Transform, which takes as input a page-efficient SSE scheme with certain special features, and outputs an SSE scheme with strong locality properties. We obtain several results.

-First, we build a dynamic SSE scheme with storage efficiency O (1) and page efficiency only O (log log(N/p)), where p is the page size, called LayeredSSE. The main technique behind LayeredSSE is a new weighted extension of the two-choice allocation process, of independent interest. -Second, we introduce the Generic Local Transform, and combine it with LayeredSSE to build a dynamic SSE scheme with storage efficiency O (1), locality O (1), and read efficiency O (log log N ), under the condition that the longest list is of size O N 1-1/ log log λ . This matches, in every respect, the purely static construction of Asharov et al. from STOC 2016: dynamism comes at no extra cost. -Finally, by applying the Generic Local Transform to a variant of the Tethys scheme by Bossuat et al. from Crypto 2021, we build an unconditional static SSE with storage efficiency O (1), locality O (1), and read efficiency O (log ε N ), for an arbitrarily small constant ε > 0. To our knowledge, this is the construction that comes closest to the lower bound presented by Cash and Tessaro at Eurocrypt 2014.

Introduction

Searchable Symmetric Encryption. In Searchable Symmetric Encryption (SSE), a client outsources the storage of a set of documents to an untrusted server. The client wishes to retain the ability to search the documents, by issuing search queries to the server. In the setting of dynamic SSE, the client may also issue update queries, in order to modify the contents of the database, for instance by adding or removing entries. The server must be able to correctly process all queries, while learning as little information as possible about the client's data and queries. SSE is relevant in many cloud storage scenarios: for example, in cases such as outsourcing the storage of a sensitive database, or offering an encrypted messaging service, some form of search functionality may be highly desirable.

In theory, SSE is a special case of computation on encrypted data, and could be realized using generic solutions, such as Fully Homomorphic Encryption. In practice, such approaches incur a large performance penalty. Instead, SSE schemes typically aim for high-performance solutions, scalable to large real-world databases. Towards that end, SSE trades off security for efficiency. The server is allowed to learn some information about the client's data. For example, SSE schemes typically leak to the server the repetition of queries (search pattern), and the identifiers of the documents that match a query (access pattern). The security model of SSE is parametrized by a leakage function, which specifies the nature of the information leaked to the server.

Locality. In the case of single-keyword SSE, search queries ask for all documents that contain a given keyword. To realize that functionality, the server maintains an (encrypted) reverse index, where each keyword is mapped to the list of identifiers of documents that match the keyword. When the client wishes to search for the documents that match a given keyword, the client simply retrieves the corresponding list from the server. A subtle issue, however, is how the lists should be stored and accessed by the server.

The naive approach of storing one list after the other is unsatisfactory: indeed, the position of a given list in memory becomes dependent on the lengths of other lists, thereby leaking information about those lists. A common approach to address that issue is to store each list element at a random location in memory. In that case, when retrieving a list, the server must visit as many random memory locations as the number of elements in the list. This is also undesirable, for a different reason: for virtually all modern storage media, accessing many random memory locations is much more expensive than visiting one continuous region. Because SSE relies on fast symmetric cryptographic primitives, the cost of memory accesses becomes the performance bottleneck. To capture that cost, [CT14] introduces the notion of locality: in short, the locality of an SSE scheme is the number of discontinuous memory locations that the server must access to answer a query.

The two extreme solutions outlined above suggest a conflict between security and locality. At Eurocrypt 2014, Cash and Tessaro showed that this conflict is inherent [CT14]: if a secure SSE scheme has constant storage efficiency (the size of the encrypted database is linear in the size of the plaintext database), and constant read efficiency (the amount of data read by the server to answer a search query is linear in the size of the plaintext answer), then it cannot have constant locality.

Local SSE constructions. Since then, many SSE schemes with constant locality have been proposed, typically at the cost of superconstant read efficiency. At STOC 2016, Asharov et al. presented . Several trade-offs with ω(1) storage efficiency were also proposed in [DP17]. When the size of the longest list in the database is bounded, stronger results are known. When such an upper bound is required, we will call the construction conditional. The first conditional SSE is due to Asharov et al., and achieves O (log log N ) read efficiency, on the condition that the size of the longest list is O N 1-1/ log log N . This was later improved to O (log log log N ) read efficiency, with a stronger condition of O N 1-1/ log log log N on the size of the longest list.

Locality was introduced as a performance measure for memory accesses, assuming an implementation on Hard Disk Drives (HDDs). In [BBF + 21], Bossuat et al. show that in the case of Solid State Drives (SSDs), such as flash disks, locality is no longer the relevant target. Instead, performance is mainly determined by the number of memory pages accessed, regardless of whether they are contiguous. In that setting the right performance metric is page efficiency. Page efficiency is defined as the number of pages read by the server to answer a query, divided by the number of pages needed to store the plaintext answer. The main construction of [BBF + 21] achieves O (1) storage efficiency and O (1) page efficiency, assuming a client-side memory of ω(log λ) pages.

To this day, a common point among all existing constructions, both local and page-efficient, is that they are purely static, as known techniques for sublogarithmic read efficiency and page efficiency do not apply to the dynamic setting. That may be because of the difficulty inherent in building local SSE, even in the static case (as evidenced, from the onset, by the impossibility result of Cash and Tessaro [CT14]). Nevertheless, many, if not most, applications of SSE require dynamism. This state of affairs significantly hinders the applicability of local and page-efficient SSE.

While one work [MM17] targets local SSE in a dynamic setting, and has constant storage efficiency and locality, it has read efficiency O (L log W ), where L is the maximum list size. Further, [MM17] employs an ORAM-variant which incurs a heavy computational overhead, in addition to the large read efficiency. When reinterpreting [MM17] in the context of page-efficiency, its guarantees improve to O (log W ) page efficiency and constant storage efficiency, but the heavy computational cost of ORAM remains.

Our Contributions

In this article, we consider the problem of dynamic memory-efficient SSE, by which we mean that we target both dynamic page-efficient SSE, and dynamic local SSE.

The centerpiece of our approach is a novel connection between these two goals. We introduce a map, called the Generic Local Transform, which takes as input a page-efficient SSE scheme with certain special features, and outputs a SSE scheme with strong locality properties. Our strategy will be to first build page-efficient schemes, then apply the Generic Local Transform to obtain local schemes. This approach turns out to be quite effective, and we present several results.

(1) Dynamic page-efficient SSE. We start by building a dynamic pageefficient SSE scheme, LayeredSSE. LayeredSSE achieves storage efficiency O (1), and page efficiency O log log N p , where p is the page size. In line with prior work on memory-efficient SSE, the technical core of LayeredSSE is a new dynamic allocation scheme, L2C. L2C is a weighted variant of the so-called "2-choice" algorithm, notorious in the resource allocation literature. L2C is of independent interest: the two-choice allocation process is ubiquitous in various areas of computer science, such as load balancing, hashing, job allocation, or circuit routing (a survey of applications may be found in [RMS01]). Weighted variants have been considered in the past, but have so far required a distributional assumption [TW07, TW14] or presorting [ANSS16]. What we show is that by slightly tweaking the two-choice process, a dynamic and distribution-free result can be obtained (Theorem 1). Such a distribution-free result is necessary for cryptographic applications, where the adversary may influence the weights (as in our case). Other uses beyond cryptography are discussed in Appendix F.

(2) Generic Local Transform. We introduce the Generic Local Transform. On input any page-efficient scheme PE-SSE with certain special features, called page-length-hiding SSE, the Generic Local Transform outputs a local SSE scheme Local [PE-SSE]. Roughly speaking, if PE-SSE has client storage O (1), storage efficiency O (1), and page efficiency O (P ), then Local[PE-SSE] has storage efficiency O (1), and read efficiency O (P ). Regarding locality, the key feature is that if PE-SSE has locality O (L) when querying lists of size at most one page, then Local[PE-SSE] has locality O (L + log log N ) when querying lists of any size. Thus, the Local construction may be viewed as bootstrapping a scheme with weak locality properties into a scheme with much stronger locality properties.

The Generic Local Transform also highlights an interesting connection between the goals of page efficiency and locality. Originally, locality and page efficiency were introduced as distinct performance criterions, targeting the two most widespread storage media, HDDs and SSDs respectively. It was already observed in [BBF + 21] that a scheme with locality L and read efficiency R must have page efficiency at most R + 2L. In that sense, page efficiency is an "easier" goal. With the Generic Local Transform, surprisingly, we build a connection in the reverse direction: we use page-efficient schemes as building blocks to obtain local schemes. On a theoretical level, this shows a strong connection between the two goals. On a practical level, it provides a strategy to target both goals at once.

(3) Dynamic local SSE. By applying the Generic Local Transform to the LayeredSSE page-efficient scheme, we immediately obtain a dynamic SSE scheme Local [LayeredSSE], with storage efficiency O (1), locality O (1), and read efficiency O (log log N ). The construction is conditional: it requires that the longest list is of size O N 1-1/ log log N . The asymptotic performance of Local [LayeredSSE] matches exactly the second static construction from [ANSS16], including the condition on maximum list size: dynamism comes at no extra cost. In particular, Local [LayeredSSE] matches the lower bound from [ASS21] for SSE schemes built using what [ASS21] refers to as "allocation schemes"-showing that the bound can be matched even in the dynamic setting.

(4) Unconditional local SSE in the static setting. The original 1choice scheme from [ANSS16] achieves O (1) storage efficiency, O (1) locality, and O (log N ) read efficiency, unconditionally. The read efficiency was improved to O log 2/3+ε N in [DPP18], for any constant ε > 0. This was, until now, the only SSE construction to achieve sublogarithmic efficiency unconditionally. By applying the Generic Local Transform to a variant of Tethys [BBF + 21], in combination with techniques inspired by [DPP18], we obtain an unconditional static SSE scheme with storage efficiency O (1), locality O (1), and read efficiency O (log ε N ), for any constant ε > 0. To our knowledge, this is the construction that comes closest to the impossibility result of Cash and Tessaro, stating that O (1) locality, storage efficiency, and read efficiency simultaneously is impossible.

Table 1 -Page-efficient SSE schemes. N denotes the total size of the database, W denotes the number of keywords, p is the number elements per page, ε > 0 is an arbitrarily small constant, and λ is the security parameter. information about unqueried keywords, but leak an identifier of the list being updated, as well as, in some cases, the length of the list. As a consequence, our dynamic schemes are not forward-secure. The underlying issue is that the goals of forward security and memory efficiency seem to be fundamentally at odds. Indeed, locality asks that identifiers associated to the same keywords must be stored close to each other; while forward-privacy requires that the location where a new identifier is inserted should be independent of the keyword it is associated with. That issue was already noted in [Bos16], who claims that "for dynamic schemes, locality and forward-privacy are two irreconcilable notions". We refer the reader to [Bos16] for more discussion of the problem and leave further analysis of this issue for future work.

Note that SSE has a very varied range of uses cases, for example private database services, online messaging and encrypted text search. In practice, its security requirements depend entirely on the use case. There are use cases where forward secrecy is crucial. The argument for forward security that is often given in the literature (e.g. [Bos16,?,?,?]) is to thwart file injection attacks in the style of [?]. Those attacks require injecting adversarially crafted entries into the target database. In an online messaging scenario, those attacks could be realistic, hence forward security is needed. In other cases, adversarial file injection is much less of a threat, and forward security can be reasonably dispensed with. For use cases where forward security is not required, we show that dynamism and memory efficiency are achievable at the same time.

Remark on the Focus on the Reverse Index. As most SSE literature, this work focuses on the (inverse) document index. The simplest usage scenario is to retrieve document indices from the index, then fetch those documents from a separate database. In reality, there are many other ways to use the index, for example by intersecting the document indices from several queries before fetching, fetching only some of the documents (see [?]), or building graph databases via several layers of inverse indices [?].

In most cases, the cost of fetching the actual documents is the same for the encrypted database as it is for the equivalent plaintext database: the efficiency overhead comes entirely from the inverse index. Schemes that hide access pattern or volume leakage are a possible exceptions but are out of the scope of this work.

Technical Overview

This work contains several results, tied together by the Generic Local Transform. As such, we believe it is beneficial to present them together within one paper. This requires introducing a number of different allocation mechanisms. We have endeavored to provide in this section a clear overview of those mechanisms. Formal specifications, theorems, and proofs will be presented in subsequent sections.

It is helpful to fist recall a few well-studied allocation mechanisms. In what follows, "with overwhelming probability" is synonymous with "except with negligible probability" (in the usual cryptographic sense), whereas "with high proba-bility" simply means with probability close to 1 in some sense, but not necessarily overwhelming.

One-choice allocation. In one-choice allocation, n balls are thrown into n bins. Each ball is inserted into a bin chosen independently and uniformly at random (by hashing an identifier of the ball). A standard analysis using Chernoff bounds shows that, at the outcome of the insertion process, the most loaded bin contains O (log n) balls with high probability [JK77]. (And at most O (f (n) log n) balls with overwhelming probability, for any f = ω(1).) Two-choice allocation. Once again, n balls are thrown into n bins. For each ball, two bins are chosen independently and uniformly at random (e.g. by hashing an identifier of the ball). The ball is inserted into whichever of the two bins contains the fewest balls at the time of insertion. A celebrated result by Azar et al. shows that, at the outcome of the insertion process, the most loaded bin contains O (log log n) balls with high probability [ABKU94]. (It was later shown that the result holds with overwhelming probability [RMS01].)

Layered 2-Choice Allocation

Our first goal is to build a dynamic page-efficient scheme. Let us summarize what this entails, starting with the static case. As explained in the introduction, to realize single-keyword SSE, we want to store lists of arbitrary sizes on an untrusted server. Hiding the contents of the lists can be achieved in a straightforward way using symmetric encryption. The main challenge is how to store the lists in the server memory, in such a way that accessing one list does not reveal information about the lengths of other lists.

In the case of page-efficient schemes, this challenge may be summarized as follows. We are given a set of lists, containing N items in total. We are also given a page size p, which represents the number of items that can fit within a physical memory page. The memory of the server is viewed as an array of pages. We want to store the lists in the server memory, with three goals in mind.

1. In order to store all lists, we use S N/p pages of server memory in total, where S is called the storage efficiency of the allocation scheme. We want S to be as small as possible. 2. Any list of length can be retrieved by visiting at most P /p pages in server memory, where P is called the page efficiency of the allocation scheme. We want P to be as small as possible. 3. Finally, the pages visited by the server to retrieve a given list should not depend on the lengths of other lists.

The first two goals are precisely the aim of bin packing algorithms. The third goal is a security goal: it stipulates that the pattern of memory accesses performed by the server should not leak certain information. As such, the goal relates to oblivious or data-independent algorithms. In [BBF + 21], a framework for realizing the three goals was formalized as Data-Independent Packing (DIP).

To ease presentation, we will focus on the case where all lists are of size at most one page. If a list is of length more than one page, the general idea is that it will be split into chunks of one page, plus one final chunk of size at most one page; each chunk will then be treated as a separate list by the allocation scheme. We assume from now on that lists are of length less than one page.

In a nutshell, the idea proposed by [BBF + 21] to instantiate a DIP scheme is to use weighted variant of cuckoo hashing [PR04]. In more detail, for each list, two pages are chosen uniformly at random, by hashing an identifier of the list. Each element of the list will then be stored in one of the two designated pages, or a stash. The stash is stored on the client side. In order to choose how each list is split between its three possible destinations (the two chosen pages, or the stash), [BBF + 21] uses a maximum flow algorithm. The details of this algorithm are not relevant for our purpose. The important point is that when retrieving a list, the server accesses two uniformly random pages. Clearly, this reveals no information to the server about the lengths of other lists. The resulting algorithm, called Tethys, achieves storage efficiency O (1), page efficiency O (1), with client storage ω(log λ) pages (used to store the stash).

In this paper, we wish to build a dynamic SSE. For that purpose, the underlying allocation scheme needs to allow for a new update operation. An update operation allows the client to add a new item to a list, increasing its length by one. The security goal remains essentially the same as in the static case: the pages accessed by the algorithm in order to update a given list should not depend on the lengths of other lists.

Tethys is not a suitable basis for a dynamic scheme, because it does not allow for an efficient data-independent update procedure: when inserting an element into a cell, the update procedure requires running a max flow algorithm. This either requires accessing other cells, with an access pattern that is intrinsically data-dependent, or performing a prohibitively expensive data-oblivious max flow computation each update. Instead, a natural idea is to use a weighted variant of the two-choice allocation scheme. With two-choice allocation, the access pattern made during an update is simple: only the two destination buckets associated to the list being updated need to be read. The new item is then inserted into whichever of the two buckets currently contains less items.

Instantiating that approach would require a weighted dynamic variant of two-choice allocation, along the following lines: given a multiset of list sizes { i : 1 ≤ i ≤ k} with i ≤ p and i = N , at the outcome of a twochoice allocation process into O (N/p) buckets, the most loaded bucket contains O (p log log N ) items with overwhelming probability, even if the weight of balls is updated during the process. However, a result of that form appears to be a long-standing open problem (some related partial results are discussed in [BFHM08]). The two-choice process with weighted items has been studied in the literature [TW07, TW14, ANSS16], but to our knowledge, all existing results assume that (1) either the weight of the balls are sampled identically and independently from a sufficiently smooth distribution or (2) the balls are sorted initially and then allocated in decreasing order. Even disregarding constraints on the distribution, in our setting, we cannot even afford to assume that list lengths are drawn independently: in the SSE security model, lists are chosen and updated arbitrarily by the adversary. Also, presorting the lists according to their length is not possible in a dynamic setting, as the list lengths can be changed via updates.

For our purpose, we require a distribution-free statement: we only know a bound p on the size of each list, and a bound N on the total size of all lists. We want an O (p log log N ) upper bound on the size of the most loaded bucket that holds for any set of list sizes satisfying those constraints, even if list sizes are updated during the process. A result of that form is known for one-choice allocation processes [BFHM08] (with a O (p log N ) upper bound), but the same article shows that the same techniques cannot extend to the two-choice process.

To solve that problem, we introduce a layered weighted 2-choice allocation algorithm, L2C. L2C has the same basic behavior as a (weighted) two-choice algorithm: for each ball, two bins are chosen uniformly at random as possible destinations. The only difference is how the bin where the ball is actually inserted is selected among the two destination bins. The most natural choice would be to store the ball in whichever bin currently has the least load, where the load of a bin is a the sum of the weights of the balls it currently contains. Instead, we use a slightly more complex decision process. In a nutshell, we partition the possible weights of balls into O (log log λ) subintervals, and the decision process is performed independently for balls in each subinterval. For the first subinterval (holding the smallest weights), we use a weighted one-choice process, while for the other subintervals, we use an unweighted two-choice process.

The point of this construction is that its analysis reduces to the analysis of the weighted one-choice process, and the unweighted two-choice process, for which powerful analytical techniques are known. We leverage those techniques to show that L2C achieves the desired distribution-free guarantees on the load of the most loaded bin. In practice, what this means is that we have an allocation algorithm that, for most intents and purposes, behaves like a weighted variant of two-choice allocation, and for which updates and distribution-free guarantees can be obtained relatively painlessly.

The LayeredSSE scheme is obtained by adding a layer of encryption and key management on top of L2C, using standard techniques from the SSE literature, although some care is required for updates. We refer the reader to Section 5 for more details.

Generic Local Transform

At Crypto 2018, Asharov et al. identified two main paradigms for building local SSE [ASS18]. The first is the allocation paradigm, which typically uses variants of multiple-choice allocation schemes, or cuckoo hashing. The second is the pad-andsplit approach. The main difficulty of memory-efficient SSE is to pack together lists of different sizes. The idea of the pad-and-split approach is to store lists separately according to their size, which circumvents the issue. The simplest way to realize this is to pad all lists length to the next power of 2. This yields log N possible values for list lengths. All lists of a given length can be stored together using, for instance, a standard hash table. Since we do not want to reveal the number of lists of each length, the hash table at each level needs to be dimensioned to be able to receive the entire database. As a result, a basic pad-and-split scheme has storage efficiency O (log N ), but easily achieves O (1) locality and read efficiency.

For the Generic Local Transform, we introduce the notion of Overflowing SSE (OSSE). An OSSE behaves like an SSE scheme in all aspects, except that, during its setup and during updates, it may refuse to store some list elements. Such elements are called overflowing. An OSSE is intended to be used as a subcomponent within an overarching SSE construction. The OSSE scheme is used to store part of the database, while overflowing elements are stored using a separate mechanism. The notion of OSSE was not formalized before, but in hindsight, the use of OSSE may be viewed as implicit in several existing constructions [DPP18, ASS18, BBF + 21]. We choose to introduce it explicitly here for ease of exposition.

We are now in a position to explain the Generic Local Transform. The chief limitation of the pad-and-split approach is that it creates a log N overhead in storage. The high-level idea of the Generic Local Transform, then, is to use an OSSE to store all but a fraction 1/ log N of the database. Then a pad-and-split variant is used to store the N/ log N overflowing elements. The intent is to benefit from the high efficiency of the pad-and-split approach, without having to pay for the log N storage overhead.

There is, however, a subtle but important issue with that approach. A given list may be either entirely stored within the OSSE scheme, or only partially stored, or not stored at all. In the OSSE scheme that we will later use (as well as OSSEs that were implicit in prior work), those three situations should be indistinguishable to the server, or else security breaks down. To address that issue, we proceed as follows.

Let us assume all lists have been padded to the next power of 2. For the pad-and-split part of the construction, we create log N SSE instances, one for each possible list size. We call each of these instances a layer. The overflowing elements of a list of size will be stored in the layer that handles lists of size , regardless of how many elements did overflow from the OSSE for that list.

The OSSE guarantees that the total number of overflowing items is at most n = O (N/ log N ). Thus, if we focus on the layer that handles lists of size , the layer will receive at most n elements. These elements will be split into lists of size at most (corresponding to the set of overflowing elements, for each list of size in the original database). To achieve storage efficiency O (S ) overall, we want the layer to store those lists using O (Sn) storage. To achieve read efficiency R, the layer should also be able to retrieve a given list by visiting at most R memory locations. This is where everything comes together: an SSE scheme satisfying those conditions is precisely a page-efficient SSE scheme with page size , storage efficiency S, and page efficiency R.

The page-efficient scheme used for each layer is also required satisfy a few extra properties: first, when searching for a list of size at most one page, the length of the list should not be leaked. We call this property page-length-hiding. (We avoid the term length-hiding to avoid confusion with volume-hiding SSE, which fully hides lengths.) All existing page-efficient constructions have that property. Second, we require the page-efficient scheme to have O (1) client storage. All constructions in this article satisfy that property, but the construction from [BBF + 21] does not. Finally, we require the scheme to have locality O (1) when fetching a single page. All existing page-efficient constructions have this property. (The last two properties could be relaxed, at the cost of more complex formulas and statements.) We call an SSE scheme satisfying those three properties suitable.

Putting everything together, the Generic Local Transform takes as input a suitable page-efficient scheme, with storage efficiency S and page efficiency P . It outputs a local scheme with storage efficiency S + S , read efficiency P + R , and locality L , where S , R , and L are the storage efficiency, read efficiency, and locality of the underlying OSSE. It remains to explain how to build a local OSSE scheme with O (N/ log N ) overflowing items, discussed next.

ClipOSSE: an OSSE scheme with O (N/ log N ) Overflowing Items

At STOC 2016, Asharov et al. introduced so-called "2-dimensional" variants of one-choice and two-choice allocation, for the purpose of building local SSE. The one-choice variant works as follows. Consider an SSE database with N elements. Allocate m = O (N/ log N ) buckets, initially empty. For each list of length in the database, choose one bucket uniformly at random. The first element of the list is inserted into that bucket. The second element of the list is inserted into the next bucket (assuming a fixed order of buckets, which wraps around when reaching the last bucket), the third one into the bucket after that, and so on, until all list elements have been inserted. Thus, assuming ≤ m, all list elements have been placed into consecutive buckets, one element in each. An analysis very similar to the usual analysis of the one-choice process shows that with overwhelming probability, the most loaded bucket receives at most τ = O (log N ) elements. To build a static SSE scheme from this allocation scheme, each bucket is padded to the maximal size τ and encrypted. Search queries proceed in the natural way. Such a scheme yields storage efficiency O (1), locality O (1) (since retrieving a list amounts to reading consecutive buckets), and read efficiency O (log N ) (since retrieving a list of length requires reading buckets, each of size τ = O (log N )). To build ClipOSSE, we start from the same premise, but "clip" buckets at the threshold τ = O (log log N ). That is, each bucket can only receive up to τ elements. Elements that cannot fit are overflowing.

In the standard one-choice process, where n balls are thrown i.i.d. into n bins, it is not difficult to show that clipping bins at height τ = O (log log n) results in at most O (n/ log n) overflowing elements with overwhelming probability. In fact, by adjusting the multiplicative constant in the choice of τ , the number of overflowing elements can be made O n/ log d n for any given constant d. We show that a result of that form still holds for (a close variant of) the 2-dimensional one-choice process outlined earlier. The result is conditional: it requires that the maximum list size is O (N/polylog N ). (A condition of that form is necessary, insofar as the result fails when the maximum list size gets close to N/ log N .) The proof of the corresponding theorem is the most technically challenging part of this work, and relies on the combination of a convexity argument with a stochastic dominance argument. An overview of the proof is given in section 6.5, so we omit more discussion here.

In Local[LayeredSSE] is a conditional scheme: it requires that the longest list is of length O N 1-1/ log log λ . The reason is subtle. ClipOSSE by itself has a condition that the longest list is O (N/polylog N ), which is less demanding. The reason for the condition comes down to the fact that LayeredSSE only achieves a negligible probability of failure as long as the number of pages in the scheme is at least Ω(λ 1/ log log λ ). More generally, the same holds for the number of bins in two-choice allocation processes in general, even the standard, unweighted process. The condition is optimal: [ASS21] shows that any sublogarithmic "allocation-based" scheme must be conditional, and gives a bound on the condition. Local[PE-SSE] matches that bound.

Unconditional Static Local SSE with O (log ε N ) Overhead

The (static) Tethys scheme from [BBF + 21] achieves storage efficiency O (1) and page efficiency O (1) simultaneously. It is also page-length-hiding. Since we have the Generic Local Transform at our disposal, it is tempting to apply it to Tethys. There is, however, one obstacle: Tethys uses ω(p log λ) client memory, in order to store a stash on the client side. For the Generic Local Transform, we need O (1) client memory. To reduce the client memory of Tethys, a simple idea is to store the stash on the server side. Naively, reading the stash for every search would increase the page efficiency to ω(log λ). To avoid this, we store the stash within an ORAM.

For that purpose, we need an ORAM with a failure probability of zero: indeed, since we may store as few as log λ elements in the ORAM, a correctness guarantee of the form negl(n), where n = log λ is the number items in the ORAM, fails to be sufficient (it is not negl(λ)). We also need the ORAM to have O (1) locality. An ORAM with these characteristics was devised in [DPP18], motivated by the same problem. The ORAM from [DPP18] achieves read efficiency O n 1/3+ε , for any arbitrary constant ε > 0. It was already conjectured in [DPP18] that it could be improved to O (n ε ). We build that variant explicitly, and name it LocORAM. Roughly speaking, LocORAM is a variant of the Goldreich-Ostrovsky hierarchical ORAM, with a constant number of levels.

By putting the stash of Tethys within LocORAM on the server side, we naturally obtain a page-efficient SSE scheme OramTethys, with O (log ε λ) read efficiency, suitable for use within the Generic Local Transform. This yields a static local SSE for lists of size at most N/polylog N . To handle larger lists, borrowing some ideas from [DPP18], we group lists by size, and use again OramTethys to store them. In the end, we obtain an unconditional SSE with O (1) store efficiency, O (1) locality, and O (log ε λ) read efficiency.

Comparing with the O log 2/3+ε λ construction from [DPP18], we note that the bottleneck of their construction comes from the allocation schemes the authors use for what they call "small" and "medium" lists. This is precisely the range where we use Local [OramTethys]. Our construction essentially removes that bottleneck, so that the O (log ε λ) read efficiency bottlneck now comes entirely from the ORAM component.

Preliminaries

Let λ ∈ N be the security parameter. For a probability distribution X, we denote by x ← X the process of sampling a value x from the distribution. Further, we say that x is We denote by

Symmetric Searchable Encryption

A database DB = {w i , (id 1 , ..., id i )} W
i=1 is a set of keyword-identifier pairs with W keywords. We assume that each keyword w i is represented by a machine word of O (λ) bits. We write DB(w i ) = (id 1 , ..., id i ) for the list of identifiers matching w i . Throughout the article, we set N = W i=1 i and define p as the page size (which we treat as a variable, independent of the size of the database N ).

A dynamic searchable symmetric encryption scheme Σ is a 4-tuple of PPT algorithms (KeyGen, Setup, Search, Update) such that -Σ.KeyGen(1 λ ): Takes as input the security parameter λ and outputs client secret key K. -Σ.Setup(K, N, DB): Takes as input the client secret key K, an upper bound on the database size N and a database DB. In the following, we omit the state st and assume that it is implicitly stored and updated by the client. We say that Σ is static, if it does not provide an Update algorithm. Further, we assume that the keyword w is preprocessed via a PRFby the client, whenever the client sends w to the server in either Search or Update. This ensures that the server never has access to w in plaintext and unqueried keywords are distributed uniformly random in the view of the server. Intuitively, the client uses Setup to encrypt and outsource a database DB to the server. Then, the client can search keywords w using Search and receives the list of matching identifiers DB(w) from the server. The list DB(w) can be updated via Update, provided that the size of the database stays below N . Note that we allow the client to add (or delete) multiple identifiers at once for a single keyword (which is required for the Generic Local Transform section 6).

Security. We now define correctness and semantic security of SSE. Intuitively, correctness guarantees that a search always retrieves all matching identifiers and semantic security guarantees that the server only learns limited information (quantified by a leakage function) from the client.

Definition 1 (Correctness). A SSE scheme Σ is correct if for all databases DB and N ∈ N, keys K ← Σ.KeyGen(1 λ ), EDB ← Σ.Setup(K, DB) and sequences of search, add or delete queries S, the search protocol returns the correct result for all queries of the sequence, if the size of the database remains at most N .

We use the standard semantic security notion for SSE (see [CGKO06]). Security is parameterized by a leakage function L = (L Stp , L Srch , L Updt ), composed of the setup leakage L Stp , the search leakage L Srch , and the update leakage L Updt . We define two games, SSEReal and SSEIdeal. First, the adversary chooses a database DB. In SSEReal, the encrypted database EDB is generated by Setup(K, N, DB), whereas in SSEIdeal the encrypted database is simulated by a (stateful) simulator Sim on input L Stp (DB, N ). After receiving EDB, the adversary issues search and update queries. All queries are answered honestly in SSEReal. In SSEIdeal, the search queries on keyword w are simulated by Sim on input L Srch (w), and update queries for operation op, keyword w and identifier list L are simulated by Sim on input L Updt (op, w, L). Finally, the adversary outputs a bit b.

We write SSEReal adp and SSEIdeal adp if the queries of the adversary were chosen adaptively, i.e. dependant on previous queries. Similarly, we write SSEReal sel and SSEIdeal sel if the queries are chosen selectively by the adversary, i.e. sent initially in conjunction with the database before receiving EDB.

Definition 2 (Semantic Security). Let Σ be a SSE scheme and L = (L Stp , L Srch , L Updt ) a leakage function. Scheme Σ is L-adaptively secure if for all PPT adversaries A, there exists a PPT simulator Sim such that

|Pr[SSEReal adp Σ,A (λ) = 1] -Pr[SSEIdeal adp Σ,Sim,L,A (λ) = 1]| = negl(λ) .
Similarly, scheme Σ is L-selectively secure if for all PPT adversaries A, there exists a PPT simulator Sim such that

|Pr[SSEReal sel Σ,A (λ) = 1] -Pr[SSEIdeal sel Σ,Sim,L,A (λ) = 1]| = negl(λ) .
Intuitively, semantic security guarantees that the interaction between client and server reveals no information to the server, except the leakage of the given query. The schemes from this article have common leakage patterns. We use the standard notions of query pattern qp and history Hist from [Bos16] to formalize this leakage: (1) The query pattern qp(w) for a keyword w are the indices of previous search or update queries for keyword w. (3) The history Hist(w) is comprised of the list of identifiers matching keyword w that were inserted during setup and the history of updates on keyword w, that is each deleted and inserted identifier. We can retrieve the number i of inserted identifiers and the number d i of deleted identifiers from Hist(w) for each keyword.

We define two leakage patterns we use throughout the article. (1) We define page-length hiding leakage L len-hid . We set L len-hid = (L len-hid Stp , L len-hid Srch , L len-hid Updt ), where the setup leakage is L len-hid Stp (DB, N ) = N is the maximal size N of the database, the search leakage L len-hid Srch (w) = (qp, i /p , d i /p ) is the query pattern and the number of pages required to store the inserted and deleted items, and the update leakage L len-hid Updt (op, w, L) = (op, qp,

( i + |L|)/p , (d i + |L|)/p , i /p , d i /p
) is the operation, the query pattern and the number of pages required to store the inserted and deleted items (before and after the update)1 .

(2) Similarly, we define length reveiling leakage L len-rev . We set

L len-rev = (L len-rev Stp , L len-rev Srch , L len-rev Updt ) with L len-rev Stp (DB, N ) = N , L len-rev Srch (w) = (qp, |L |, i , d i ) and lastly L len-rev Updt (op, w, L ) = (op, qp, |L |, i , d i ).
We will use L len-hid and L len-rev for both dynamic and static schemes. When we say that a static scheme is L-semantically secure, for L ∈ {L len-hid , L len-rev }, we simply ignore the update leakage. Note that both leakage patterns, L len-hid and L len-rev , have standard setup and search leakage, common in most SSE schemes. The update leakage of L len-hid and L len-rev is similar to their search leakage, and reveals nothing about unqueried keywords. While the update leakage is not forward secure, similar leakage patterns are commonly considered in literature, for example [CJJ + 14]. We hope our techniques pave the way for future work on dynamic schemes with forward security and memory efficiency.

Efficiency Measures. We recall the notions of locality, storage efficiency and read efficiency [CT14], and page efficiency [BBF + 21] (and extend them to the dynamic SSE setting in a natural manner). In the following definitions, we set K ← KeyGen(1 λ ) and EDB ← Setup(K, N, DB) given database DB and upper bound N on the number of document identifiers. Also, S = (op i , in i ) s i=1 is a sequence of search and update queries, where op i ∈ {add, del, ⊥} is a operation and in i = (op i , w i , L i , st i , EDB i ) its input. Here, w i is a keyword and L i is a (added or deleted) list of identifiers, and after executing all previous operations op j for j ≤ i, st i is the client state and EDB i the encrypted database. We denote by DB i the database after i operations. We assume that the total number of identifiers never exceeds N . (If op i = ⊥, the query is a search query and L i is empty.) Definition 3 (Read Pattern). Regard server-side storage as an array of memory locations, containing the encrypted database EDB. When processing search query Search(K, w i , st i ; EDB i ) or update query Update(K, (w i , L i ), op i , st i ; EDB i ), the server accesses memory locations m 1 , ..., m h . We call these locations the read pattern and denote it with RdPat(op i , in i ).

Definition 4 (Locality). A SSE scheme has locality L if for any λ, DB, N , sequence S, and any i, RdPat(op i , in i ) consists of at most L disjoint intervals.

Definition 5 (Read Efficiency). A SSE scheme has read efficiency R if for any λ, DB, N , sequence S, and any i, |RdPat(op i , in i )| ≤ R • P , where P is the number of memory locations needed to store all (added and deleted) document indices matching keyword w i in plaintext (by concatenating indices).

Definition 6 (Storage Efficiency). A SSE scheme has storage efficiency E if for any λ, DB, N , sequence S, and any i,

|EDB i | ≤ E • |DB i |.
Definition 7 (Page Pattern). Regard server-side storage as an array of pages, containing the encrypted database EDB. When processing search query Search(K, w i , st i ; EDB i ) or update query Update(K, (w i , L i ), op i , st i ; EDB i ), the read pattern RdPat(op i , in i ) induces a number of page accesses p 1 , ..., p h . We call these pages the page pattern, denoted by PgPat(op i , in i ).

Definition 8 (Page Cost). A SSE scheme has page cost aX + b, where a, b are real numbers, and X is a fixed symbol, if for any λ, DB, N , sequence S, and any i, |PgPat(op i , in i )| ≤ aX + b, where X is the number of pages needed to store document indices matching keyword w i in plaintext.

Definition 9 (Page Efficiency). A SSE scheme has page efficiency P if for any λ, DB, N , sequence S, and any i, |PgPat(op i , in i )| ≤ P • X, where X is the number of pages needed to store document indices matching keyword w i in plaintext.

Layered Two-Choice Allocation

In this section, we describe layered two-choice allocation (L2C), a variant of twochoice allocation that allows to allocate n weighted balls (b i , w i ) into m bins, where b i is a unique identifier and w i ∈ [0, 1] R is the weight of the ball. (We often write ball b i for short.) First, let 1 ≤ δ(λ) ≤ log(λ) be a function. We denote by w = n i=1 w i the sum of all weights and set m = w/(δ(λ) log log w). We will later choose δ(λ) = o(log log λ) such that allocation has negligible failure probability. In the overview, we set δ(λ) = 1 and assume that m = Ω(λ) for simplicity (which suffices for negligible failure probability).

Overview of L2C. L2C is based on both weighted one-choice allocation (1C) and unweighted two-choice allocation (2C). On a high level, we split the set of possible weights

[0, 1] R into log log m subintervals [0, 1/ log m] R , (1/ log m, 2/ log m] R , ..., (2 log log m-1 / log m, 1] R .
In words, the first interval is of size 1/ log m and the boundaries between intervals grow by a factor 2 every time. We will allocate balls with weights in a given subinterval independently from the others.

Balls in the first subinterval have weights w i ≤ log m and are thus small enough to apply weighted 1C. Intuitively, this suffices because one-choice (provably) performs worst for uniform weights of maximal size 1/ log m. In that case, there are at most n = w log m balls and we expect a bin to contain n /m = log m • log log w balls of uniform weight, since m = w/(log log w). As each ball has weight 1/ log m, the expected load per bin is log log w. This translates to a O (log log w ) bound with overwhelming probability after applying a Chernoff's bound.

For the other intervals, applying unweighted and independent 2C per interval suffices, as the weights of balls differ at most by a factor 2 and there are only log log m intervals. More concretely, let n i be the number of balls in the i-th subinterval A i = (2 i-1 / log m, 2 i / log m] R for i ∈ {1, ..., log log m}. Balls with weights in subinterval A i fill the bins with at most O (n i /m + log log m) balls, independent of other subintervals. Note that we are working with small weights, and thus potentially have ω(m) balls. Thus, we need to extend existing 2C results to negligible failure probability in m for the heavily-loaded case (cf. lemma 5). As there are only log log m subintervals, and balls in interval A i have weight at most 2 i / log m, we can just sum the load of each subinterval and receive a bound

log log m i=1 2 i log m O (n i /m + log log m) = O (w/m + log log m) .
In total, we have O (w/m + log log m) = O (log log w ) bounds for the first and the remaining intervals. Together, this shows that all bins have load at most O (log log w ) after allocating all n items. This matches the bound of standard 2C with unweighted balls if m = Ω(λ). For our SSE application, we want to allow for negligible failure probability with the least number of bins possible. We can set δ(λ) = log log log(λ) and obtain a bin size of O (log log w) with overwhelming probability, if m = w δ(λ) log log w . The analysis is identical in this case. Handling Updates. The described variant of L2C is static. That is, we have not shown a bound on the load of the most loaded bin if we add balls or update the weight of balls. Fortunately, inserts of new balls are trivially covered by the analysis sketched above, if m was chosen large enough initially in order to compensate for the added weight. Thus, we assume there is some upper bound w max on the total weights of added balls which is used to initially set up the bins. We can also update weights if we proceed with care.

For this, let b i be some ball with weight w old . We want to update its weight to w new > w old . If w old and w new reside in the subinterval, we can directly update the weight of b i , as L2C ignores the concrete weight of balls inside a given subinterval for the allocation. Indeed, in the first interval, the bin in which b i is inserted is determined by a single random choice, and for the remaining subintervals, the 2C process only considers the number of balls inside the same subinterval, ignoring concrete weights.

When w new is larger than the bounds of the current subinterval, we need to make sure that the ball is inserted into the correct bin of its two choices. For this, the ball b i is inserted into the bin with the lowest number of balls with weights inside the new subinterval. Even though the bin of b i might change in this process, we still need to consider b i as a ball of weight w old in the old bin for subsequent ball insertions in the old subinterval. Thus, we mark the ball as residual ball but do not remove it from its old bin. That is, we consider it as ball of weight w old for the 2C process but assume it is not identified by b i anymore. As there are only log log m different subintervals, storing the residual balls has a constant overhead. The full algorithm L2C is given in Algorithm 1. We parameterize it by a hash function H mapping uniformly into {1, ..., m} 2 . The random bin choices of a ball b i are given by α 1 , α 2 ← H(b i ).

Load Analysis of L2C. Let either δ(λ) = 1 or δ(λ) = log log log λ and m sufficiently large such that m -Ω(δ(λ) log log w) = negl(λ). (Note that this is the probability that allocation of 1C and 2C fails.)

We need to show that after setup and during a (selective) sequence of operations, the most loaded bin has a load of at most O (δ(λ) log log w max ), where w max is an upper bound on the total weight of the inserted balls. We sketch the proof here and refer to Appendix C for further details. First, we modify the sequence S such that we can reduce the analysis to only (sufficiently independent) L2C.InsertBall operations, while only increasing the final bin load by a constant factor. This is constant factor of the load is due to the additional weight of residual balls. Then, we analyze the load of the most loaded bin for the each subinterval independently. This boils down to an analysis of a 1C process in the first subinterval and a 2C process in the remaining subintervals as in the overview of L2C (see Section 4). Summing up the independent bounds yields the desired result.

Theorem 1. Let either δ(λ) = 1 or δ(λ) = log log log λ. Let w max = poly (λ) and m = w max /(δ(λ) log log w max ). We require that m = Ω(λ

1 log log λ ) if δ(λ) = log log log λ or m = Ω(λ) otherwise. Let {(b i , w i ) n
i=1 } be balls with (pair-wise unique) identifier b i and weight

w i ∈ [0, 1]. Further, let S = (op i , in i ) s+n i=n+1 be a sequence of s insert or update operations op i ∈ {L2C.InsertBall, L2C.UpdateBall} with input in i = (b i , w i , B αi,1 , B αi,2 ) for inserts and in i = (b i , o i , w i , B αi,1 , B αi,2 ) for updates.
Here, b i denotes the identifier of a ball with weight w i and old weight o i ≤ w i before the execution of op i . Also, the bins are chosen via

α i,1 , α i,2 ← H(b i ). Execute (B i ) m i=1 ← L2C.Setup({(b i , w i ) n i=1 }) and the operations op i (in i ) for all i ∈ [n + 1, n + s].
We require that n+s i=1 w i -o i ≤ w max , i.e. the total weight after all operations is at most w max .

Then it holds that throughout the process, the most loaded bin of B 1 , ..., B m has at most load O (δ(λ) log log w max ) except with negligible probability, if H is modeled as a random oracle.

Dynamic Page Efficient SSE -Overview

We introduce the SSE scheme LayeredSSE based on L2C. Essentially, we interpret lists L i of identifiers matching keyword w i as balls of a certain weight. Then, we use L2C to manage the balls in m encrypted bins, where each bin corresponds to a memory page, yielding page efficiency O (log log N/p) and constant storage efficiency. Let N be the maximal size of the database, p ≤ N 1-1/ log log λ be the page size2 and H be a hash function mapping into {1, ..., m} 2 for m = w max /(log log log λ • log log w max ) and w max = N/p. Due to space limitations, we assume that each keyword has at most p associated keywords, and outline the scheme and its security analysis. We refer to Appendix A for details (without restrictions on the database3 ).

For convenience, we adapt the notation of L2C to lists of identifiers. A ball (w, L) of weight |L|/p ∈ [0, 1] R is a list of (at most p) identifiers matching keyword w. The 2 bin choices α 1 , α 2 for ball (w, L) are given via (α 1 , α 2 ) ← H(w). Now, L2C.Setup takes input balls {(w i , L i )} W i=1 and maximal weight w max , and allocates them as before into m bins. L2C.InsertBall receives ball (w, L) and two bins (B α1 , B α2 ), and inserts (w, L) into either bin B α1 or bin B α2 as before.

Algorithm 1 Layered 2-Choice Allocation (L2C) L2C.Setup({(bi, wi)} n i=1 , wmax) 1: Receive n balls (bi, wi), and maximal total weight wmax 2: Initialize m = wmax/(δ(λ) log log wmax) empty bins B1, ..., Bm 3: for all i ∈ {1, ..., n} do 4:

Set α1, α2 ← H(bi)

5:

InsertBall(bi, wi, Bα 1 , Bα 2 ) 6: Return B1, ..., Bm L2C.InsertBall(bnew, wnew, Bα 1 , Bα 2 ) 1: Receive bins Bα 1 , Bα 2 , and ball (bnew, wnew) 2: Assert that α1, α2 are the choices given by H(bnew)

3: Split the set of possible weights [0, 1] R into log log m sub-intervals [0, 1/ log m] R , (1/ log m, 2/ log m] R , ..., (2 log log m-1 / log m, 1] R 4: Choose k ∈ N minimal such that wnew ≤ 2 k / log m 5: if k = 1 then 6: Set α ← α1 7: else 8:
Let Bα be the bin with the least number of balls of weight in

2 k-1 log m , 2 k log m R
among Bα 1 and Bα 2 9: Insert ball bnew into bin Bα L2C.UpdateBall(b old , w old , wnew, Bα 1 , Bα 2 ) 1: Receive bins Bα 1 , Bα 2 that contain ball (b old , w old ), and new weight wnew ≥ w old 2: Assert that α1, α2 are the choices given by H(b old )

3: if w old , wnew ∈ 2 k-1 log m , 2 k log m R
for some k then

L |/p ∈ [0, 1] R .)

LayeredSSE

We describe LayeredSSE, focusing on insert operations. In Appendix A, we describe LayeredSSE in more detail, and show how to treat arbitrary list sizes, introduce delete operations and show how to obtain updates in 1 RTT. A detailed description of LayeredSSE is given in algorithm 2.

Setup. To setup the initial database DB = (w, L i ) W i=1 , given upperbound N on the number of keyword-identifiers, allocate the balls (w, L i ) into m bins via L2C. Next, each bin is filled up to maximal size p • c log log log(λ) log log(N/p), for some constant c. Finally, the encrypted bins are output.

Search. During a search operation on keyword w, the client retrieves encrypted bins B α1 , B α2 for (α 1 , α 2 ) ← H(w) from the server.

Update. During an update operation to add identifier list L to keyword w, the client retrieves B α1 , B α2 , decrypts both bins and retrieves ball (w, L) from the corresponding bin B α ∈ {B α1 , B α2 }. Then, she calls L2C.UpdateBall with old ball (w, L), new identifiers L and bins B α1 , B α2 to insert the new identifiers L into one of the bins. Finally, she reencrypts the bins and sends them to the server. The server then replaces the old bins with the updated bins.

Algorithm 2 LayeredSSE

Global parameters: constant c ∈ N, page size p LayeredSSE.KeyGen(1 λ )

1: Sample K Enc for Enc with input 1 λ 2: return K = K Enc LayeredSSE.Setup(K, N, DB) 1: Set τ ← p • c log log log(λ) log log(N/p) 2: Sample bins B1, ..., Bm via L2C.Setup with input ({(wi, DB(wi))} W i=1 , N/p) 3: Fill B1, ..., Bm up to size τ with zeros 4: Set B enc i ← Enc K Enc (Bi) for i ∈ [1, m] 5: return EDB = (B enc 1 , ..., B enc m ) LayeredSSE.Search(K, w; EDB) Client:
1: return w Server:

1: Set α1, α2 ← H(w) 2: return B enc α 1 , B enc α 2
LayeredSSE.Update(K, (w, L ), add; EDB) Client:

1: return w Server:

1: Set α1, α2 ← H(w) 2: return B enc α 1 , B enc α 2
Client:

1: Set Bα i ← Dec K Enc (B enc α i ) for i ∈ {1, 2} 2: Retrieve ball (w, L) from Bα for appro- priate α ∈ {α1, α2} 3: Run L2C.UpdateBall((w, L), L , Bα 1 , Bα 2 ) 4: Set B new α i ← Enc K Enc (Bα i ) for i ∈ {1, 2} 5: return B new α 2 , B new α 2
Server:

1: Replace B enc α i with B new α i for i ∈ {1, 2}

Security and Efficiency

Correctness. LayeredSSE is correct as each keyword has two bins that contain its identifiers associated to it (and these bins are consistently retrieved and updated with L2C). If the hash function is modeled as a random oracle, the bin choices are uniformly random and Theorem 1 guarantees that bins do not overflow.

Selective Security. LayeredSSE is selectively secure and has standard setup leakage N , such as search and update leakage qp, where qp is the query pattern 4 . This can be shown with a simple hybrid argument, sketched here. For setup, the simulator Sim receives N , recomputes m and initializes m empty bins B 1 , ..., B m of size p • c log log log(λ) log log(N/p) each. Sim then outputs EDB = (Enc K Enc (B i ) m i=1 ) for some sampled key K Enc . As Enc is IND-CPA secure (and bins do not overflow in the real experiment except with negligible probability), the output EDB is indistinguishable from the output of Setup in the real experiment. For a search query on keyword w, Sim checks the query pattern qp whether w was already queried. If w was not queried before, Sim a new uniformly random keyword w . Otherwise, Sim responds with the same keyword w from the previous query. As we assume that keywords are preprocessed by the client via a PRF, the keywords w and w are indistinguishable. For an update query on keyword w, the client output in the first flow is the same as in a search query and thus, Sim can proceed as in search. For the second flow, Sim receives two bins B α1 , B α2 from the adversary, directly reencrypts them and sends them back to the adversary. This behaviour is indistinguishable, as the bins are encrypted and again, bins do not overflow except with negligible probability.

Adaptive Security. For adaptive security, the adversary can issue search and update queries that depend on previous queries. As Theorem 1 assumes selectively chosen InsertBall and UpdateBall operations, there is no guarantee that bins do not overflow anymore in the real game. Thus, the adversary can potentially distinguish update queries of the simulated game from real update queries if she manages to overflow a bin in the real game, as she would receive bins with increased size only in latter case. Fortunately, we can just add a check in Update whether one of the bins overflows after the L2C.UpdateBall operation. In that case, the client reverts the update and send back the (reencrypted) original bins. Now, Theorem 1 still guarantees that bins overflow only with negligible probability after Setup and we can show that the simulated game is indistinguishable from the real game as before. Note that LayeredSSE is still correct after this modification, since updates that lead to overflows cannot occur by accident, but only if the client systemically adapts the choice of updates to the random coins used during previous update operations (see Theorem 1).

Note that when the client remarks that a bin overflowed in an Update in a real world environment, this is due malicious Update operations. The client can adapt his reaction accordingly, whereas the server learns no information about the attack without being notified by the client. We can show that LayeredSSE with the adjustment of Update is correct and L len-hid -adaptively secure. The same simulator Sim suffices and we omit the details. Extensions. With some care, LayeredSSE can handle deletes and arbitrary lists (without sacrificing security and efficiency). We refer to Appendix A.3 for more details. The results are formalized in Theorem 2.

Theorem 2 (LayeredSSE). Let N be an upper bound on the size of database DB and p ≤ N 1-1/ log log λ be the page size. The scheme LayeredSSE is correct and L len-hid -adaptively semantically secure if Enc is IND-CPA secure and H is modeled as a random oracle. It has constant storage efficiency and O (log log N/p) page efficiency. If only lists up to size p are inserted, LayeredSSE has constant locality.

The Generic Local Transform

In this section, we define the Generic Local Transform (GLT), creating a link between the two IO-efficiency goals of locality and page efficiency. Namely, the GLT builds an SSE scheme with good locality properties from an SSE scheme with good page efficiency. For a page-efficient scheme to be used within the GLT, it needs to have certain extra properties. We define such schemes as suitable page-efficient schemes in Section 6.1. Next, we introduce the useful notion of overflowing SSE. The GLT is then obtained by combining an overflowing SSE with a suitable page-efficient scheme. The OSSE we will use for that purpose, ClipOSSE, is presented in Section 6.2. Finally, the GLT is built from the previous components in Section 6.4. An overview of the correctness and security proofs is provided in section 6.5. Full proofs are available in Appendix E.

Preliminaries

Suitable page-efficient SSE.

The GLT will create many instances of the underlying page-efficient scheme, each with a different page size. For that reason, for the purpose of the GLT, we slightly extend the standard SSE interface defined in Section 3: namely, Setup(K, N, DB, p) takes as an additional parameter the page size p. In addition, recall that, in Section 3, we have allowed the Update(K, (w, L), op, st; EDB) procedure to add a set of matching documents K to a given keyword w in a single call. Note that S is allowed to be empty, in which case nothing is added.

If a scheme instantiates that interface, and, in addition, satisfies the following three conditions, we will call such as scheme a suitable page-efficient SSE.

-The scheme has client storage O (1).

-The scheme has locality O (1) during searches and updates when accessing a list of length at most one page. -The leakage of the scheme is page-length-hiding.

Overflowing SSE. We introduce the notion of Overflowing SSE. An Overflowing SSE (OSSE) has the same interface and functionality as a standard SSE scheme, except that during a Setup or Update operation, it may refuse to store some document identifiers. Those identifiers are called overflowing. At the output of the Setup and Update operations, the client returns the set of overflowing elements. Compared to standard SSE, the correctness definition is relaxed in the following way: during a Search, only matching identifiers that were not overflowing need to be retrieved.

The intention of an Overflowing SSE is that it may be used as a component within a larger SSE scheme, which will store the overflowing identifiers using a separate mechanism. The use of an OSSE may be regarded as implicit in some prior SSE constructions. We have chosen to introduce the notion explicitly because it allows to cleanly split the presentation of the Generic Local Transform into two parts: an OSSE scheme that stores most of the database, and an array of page-efficient schemes that store the overflowing identifiers.

Dynamic Two-Dimensional One-Choice Allocation

The first component of the Generic Local Transform is an OSSE scheme, ClipOSSE.

In line with prior work, we split the presentation of ClipOSSE into two parts: an allocation scheme, which specifies where elements should be stored; and the SSE scheme built on top of it, which adds a layer of encryption, key management, and other mechanisms needed to convert the allocation scheme into a full SSE.

The allocation scheme within ClipOSSE is called 1C-Alloc. Similar to [ANSS16], the allocation scheme is an abstract construct that defines the memory locations where items should be stored, but does not store anything itself. In the case of 1C-Alloc, items are stored within buckets, and the procedures return as output the indices of buckets where items should be stored. From the point of view of 1C-Alloc, each bucket has unlimited storage. In more detail, 1C-Alloc contains two procedures, Fetch and Add.

-Fetch(m, w, ): given a number of buckets m, a keyword w, and a list length , Fetch returns (a superset of) the indices of buckets where elements matching keyword w may be stored, assuming there are such elements. -Add(m, w, ): given the same input, Add returns the index of the bucket where the next element matching keyword w should be inserted, assuming there are currently matching elements.

The intention is that Add is used during an SSE Update operation, in order to choose the bucket where the next list element is stored; while Fetch is used during a Search operation, in order to determine the buckets that need to be read to retrieve all list elements. 1C-Alloc will satisfy the correctness property given in Definition 10. Note that the number of buckets m is always assumed to be a power of 2.

Definition 10 (Correctness). For all m, w, , if m is a power of 2, then 0≤i≤ -1

Add(m, w, i) ⊆ Fetch(m, w, ).

To describe 1C-Alloc, it is convenient to conceptually group buckets into superbuckets. For = 2 i ≤ m, an -superbucket is a collection of consecutive buckets, with indices of the form k • , k • + 1, ..., (k + 1) • -1, for some k ≤ m/ . A 1-superbucket is the same as a bucket. Notice that for a given , the -superbuckets do not overlap. They form a partition of the set of buckets. For > 1, each -superbucket contains exactly two /2-superbuckets.

Let H be a hash function, whose output is assumed to be uniformly random in {1, ..., m}. 1C-Alloc works as follows. Fix a keyword w and length ≤ m (the case > m will be discussed later). Let = 2 log be the smallest power of 2 larger than . On input w and , 1C-Alloc.Fetch returns the (unique)superbucket that contains H(w).

Algorithm 3 Dynamic Two-Dimensional One-Choice Allocation (1C-Alloc)

1C-Alloc.Fetch(m, w, ) 1: ← 2 log 2: if ≥ m then 3: return {0, ..., m -1} 4: else 5: i ← H(w)/ 6: return { • i, ..., • i + -1} 1C-Alloc.Add(m, w, ) 1: ← mod m 2: ← 2 log( +1) 3: i ← H(w)/ 4: if 2H(w)/ mod 2 = 0 then 5: return • i + 6: else 7: return • i + -/2
Meanwhile, 1C-Alloc.Add is designed in order to ensure that the first successive locations returned by Add for keyword w are in fact included within the -superbucket above H(w) (that is, in order to ensure correctness). For the first list element (when = 0), Add returns the bucket H(w); for the second element, it returns the other bucket contained inside the 2-superbucket above H(w). More generally, if S is the smallest superbucket above H(w) that contains at least +1 buckets, Add returns the leftmost bucket within S that has not yet received an element. In practice, the index of that bucket can be computed easily based on and the binary decomposition of H(w), as done in Algorithm 3. (In fact, the exact order in which buckets are selected by Add is irrelevant, as long as it selects distinct buckets, and correctness holds.)

When the size of the list grows above the number of buckets m, Fetch returns all buckets, while Add selects the same buckets as it did for mod m.

Clipped One-Choice OSSE

ClipOSSE is the OSSE scheme obtained by storing lists according to 1C-Alloc, using m = O(N/ log log N ) buckets, with each bucket containing up to τ = α log log N items, for some constant α. Buckets are always padded to the threshold τ and encrypted before being stored on the server. Thus, from the server's point of view, they are completely opaque. A table T containing (in encrypted form) the length of the list matching each keyword w is also stored on the server.

Given 1C-Alloc, the details of ClipOSSE are straightforward. A short overview is given in text below. The encrypted database generated by Setup is essentially equivalent to starting from an empty database, and populating it by making repeated calls to Update, one for each keyword-document pair in the database. For that reason, we focus on Search and Update. The full specification for Setup, Search, and Update is given as pseudo-code in Algorithm 4.

Search. To retrieve the list of identifiers matching keyword w, ClipOSSE calls 1C-Alloc(m, w, ) to get the set of bucket indices where the elements matching keyword w have been stored. The client retrieves those buckets from the server, and decrypts them to obtain the desired information.

Update. For simplicity, we focus on a the case where a single identifier is added. The case of a set of identifiers can be obtained by repeating the process for each identifier in the set. To add the new item to the list matching keyword w, ClipOSSE calls 1C-Alloc(m, w, ) to determine the bucket where the new list item should be inserted. The client retrieves that bucket from the server, decrypts it, adds the new item, reencrypts the bucket, and sends it back to the server. If that bucket was already full, the item is overflowing, in the sense of Section 6.1.

Algorithm 4 Clipped One-Choice OSSE (ClipOSSE)

Global parameters: constants d, α ∈ N * ClipOSSE.KeyGen(1 λ ) 1: Generate keys K, K PRF for Enc, PRF 2: return K = (K, K PRF ) ClipOSSE.Setup(K, N, DB) 1: m ← 2 log(N/ log log N ) 2: τ ← α log log N 3: B0, ..., Bm-1, T, EDB, clip ← ∅ 4: for all each (w, {e1, ..., e }) in DB do 5: Kw ← PRFK PRF (w) 6: T [w] ← EncK w ( ) 7:
for all t from 1 to do 8: 1: send (w, Kw) = PRFK PRF (w) Server: To realize Local[PE-SSE], we use two structures. The first structure is an instance of ClipOSSE, which stores most of the database. The second structure is an array of n level instances of PE-SSE. The i-th instance, denoted PE-SSE i , has page size 2 i . The PE-SSE i instances are used to store elements that overflow from ClipOSSE. In addition, a table T stores (in encrypted form) the length of the list matching keyword w, for each keyword5 .

C ← ∅ 9: i ← 1C-Alloc.Add(m, w, t -1) 10: if then|B[i]| < τ 11: B[i] ← B[i] ∪ {ei} 12:
1: ← DecK w (T [w]) 2: S ← 1C-Alloc.Fetch(m, w, ) 3: return {B Enc [i] : i ∈ S} ClipOSSE.Update(K, (w, {e}), op, st; EDB) Client: (update token) 1: send (w, Kw = PRFK PRF (w)) Server: 1: ← DecK w (T [w]) 2: i ← 1C-Alloc.Add(m, w, ) 3: send B Enc [i] Client: 1: B ← DecK (B Enc [i]) 2: if |B| < τ then
Fix a keyword w, matching elements. Let = 2 log be the smallest power of 2 larger than . Let i = log . At any point in time, the elements matching w are stored in two locations: ClipOSSE, and PE-SSE i . Each of these two locations stores part of the elements: ClipOSSE stores the elements that did not overflow, and PE-SSE i stores the overflowing elements. Each element exists in only one of the two locations. Again, for simplicity, we define updates for adding a single identifier per keyword. The case of adding a set of identifiers at once can be deduced by repeating the same process for each identifier in the set.

Algorithm 5 Generic Local Transform (Local[PE-SSE]) Global parameters: constant d ∈ N * Local[PE-SSE].KeyGen(1 λ ) 1: Generate key K PRF for PRF 2: return K = (K, K PRF ) Local[PE-SSE].Update(K, (w, L); EDB) Client: (update token) 1: send (w, L, Kw = PRFK PRF (w)) Server: 1: C ← ClipOSSE.Update(w, L) 2: ← DecK w (T [w]) 3: T [w] ← EncK w ( +
DBi ← {(w, C) : (w, , C) ∈ clip and 2 i-1 < ≤ 2 i } 8: PE-SSEi ← PE-SSE.Setup( N/ log N , 2 i , DBi) Local[PE-SSE].Search(K, w, st; EDB) Client: (search token)
1: send (w, Kw = PRFK PRF (w)) Server:

1: i ← log(DecK w (T [w])) 2: return ClipOSSE.Search(w) ∪ PE-SSEi.Search(w)
Search. During a search operation, Local[PE-SSE] queries both structures, and combines their output to retrieve all matching elements.

Update. During an update operation to add element e, Local[PE-SSE] forwards the update query to ClipOSSE, and gets as output C = ∅ if the element did not overflow, or C = {e} if the element did overflow. For now, assume that log = log( + 1) , that is, the PE-SSE i instance associated with the list remains the same during the update operation. In that case, PE-SSE i is updated for the set C. (Recall from Section 6.1 that a length-hiding SSE such as PE-SSE accepts sets of elements as input in Update.) The length-hiding property is designed to guarantee that the content of C (including whether it is empty) is not leaked to the server. Now assume log < log( + 1) . In that case, the PE-SSE instance associated with the list becomes PE-SSE i+1 instead of PE-SSE i . The client retrieves all current overflowing elements from PE-SSE i , adds the content of C, and stores the result in PE-SSE i+1 .

Overflow of ClipOSSE

The main technical result in this section regards the number of overflowing items in ClipOSSE.

Theorem 3. Suppose that ClipOSSE receives as input a database of size N , such that the size of the longest list is O N/ log d N for some d ≥ 2.Then for any constant c, there exists a choice of parameters of ClipOSSE such that the number of overflowing items is O (N/ log c N ).

The proof of Theorem 3 is intricate. For space reasons, we only give a brief overview here. The full proof is given in Appendix E. A more detailed overview may also be found in Appendix E.2. First, we show that the result holds in the special case where all lists have length N/ log d N . This uses a negative association argument, similar to the proof of [DPP18, Theorem 1]. The core of the proof is to then show that this special case implies the general case. This is done by iteratively merging short lists, while showing that this merging process can only have a limited effect on the number of overflowing elements. At the outcome of the merging process, all lists have length N/ log d N , which reduces the problem to the special case. The main technique for the reduction is a stochastic dominance argument, combined with a convexity argument (similar to the proof of [BBF + 21, Theorem 5]).

The Generic Local Transform itself uses standard SSE techniques, and its properties follow from previous discussions. We provide a formal statement below.

Theorem 4 (Generic Local Transform). Let N be an upper bound on the size of database DB. Suppose that PE-SSE is a suitable page-efficient scheme with page efficiency P and storage efficiency S. Then Local[PE-SSE] is a correct and secure SSE scheme with storage efficiency O (S ), locality O (1), and read efficiency P + O (log log N ).

Unconditional Static Local SSE -Overview

We sketch our SSE scheme UncondSSE with constant locality, constant storage efficiency and O (log ε N ) read efficiency for any ε > 0, without condition on the maximal list size. On a high level, we proceed in 3 steps and refer to Appendix B for the detailed construction.

First, we construct LocORAM, a generalization of the ORAM of [DPP18] with constant locality and O (n ε ) bandwith, given that the block size is "large enough". The construction is straigthforward, though some details are technical.

Then, we use LocORAM to outsource the stash of Tethys (from [BBF + 21]) via trivial binpacking, obtaining the scheme OramTethys that has O (log ε λ) page efficiency, constant storage efficiency and contant client storage. Note that OramTethys requires p = Ω(λ) (which stems from the minimal block size requirement of LocORAM). Given Tethys and LocORAM, this is straigthforward. Now, we are ready to describe UncondSSE. For this, we follow the high level idea of [DPP18] to handle lists with different schemes depending on the list size. For some d ∈ N, we split the interval [1, N ] of possible list lengths into four different subintervals:

1. For the subinterval [1, N 1-1/ log log λ ), we can simply store the lists using

Local [LayeredSSE]. Here, the read efficiency is O (log log N ). 2. For the subinterval [N 1-1/ log log λ , N/ log d N ), the lengths are small enough for the local transformation and large enough for OramTethys. Thus, we store the lists using Local[OramTethys] with O (log ε N ) read efficiency. 3. We further split the subinterval [N/ log d N, N/ log ε N ) into a constant number of subintervals, such that OramTethys has O (log ε N ) read efficiency for each subinterval. 4. For the subinterval [N/ log ε N, N ], we can read the entire database. Thus, we simply encrypt DB and fetch it from the server each query.

Note that subinterval (2) is the bottleneck in [DPP18], and we can use the Generic Local Transform to remove it. The result is formalized in Theorem 5.

Theorem 5 (UncondSSE). The static scheme UncondSSE is correct and L len-revadaptively secure. It has constant client storage, O (1) locality and O (log ε N ) read efficiency for any ε > 0.

A Dynamic Page Efficient SSE

In this section, we introduce the SSE scheme LayeredSSE based on L2C. Essentially, we interpret lists L i of identifiers matching keyword w i as balls of a certain weight and use L2C to manage the balls in m bins. Let N be the maximal size of the database, p be the page size and H be a hash function mapping into {1, ..., m} 2 for m = w max /(log log log λ • log log w max ) and w max = N/p. Assume for now that |L i | ≤ p, i.e. each keyword has at most p associated keywords. Let p ≤ N 1-1/ log log λ . (This is needed for the requirement m ≥ λ 1/ log log λ of L2C, see Theorem 1.) For convenience, we adapt the notation of L2C to such lists as follows 6 :

-L2C.Setup({(w i , L i )} W i=1 , w max ): We interpret the pair (w i , L i ) as a ball with identifier w i and weight |L i |/p ∈ [0, 1], where L i is a list of (at most p) identifiers matching keyword w i . The bin choices for (w i , L i ) are given by α 1 , α 2 ← H(w i ). Run the setup defined in Algorithm 1 given these balls.

A.1 LayeredSSE

Here, we describe the dynamic page efficient symmetric searchable encryption scheme LayeredSSE based on L2C. For a concise overview, we assume that i ≤ p and ignore delete operations for now. Also, we present a version of the scheme with an update that requires 2 RTTs. Later, we show how to treat arbitrary list sizes, introduce delete operations and show how to obtain updates in 1 RTT. A detailed description of LayeredSSE is given in algorithm 6.

LayeredSSE.KeyGen(1 λ ). Sample encryption key K Enc for Enc with the given security parameter λ. Return the client's master secret key K = K Enc .

LayeredSSE.Setup(K, N, DB). Receive as input the client's secret key K, an upperbound N on the number of identifiers and the initial database DB = (DB(w i )) W i=1 . Recall that DB(w i ) = (id 1 , ..., id i ) is a list of i document identifiers and that

W i=1 i ≤ N . interpret (w i , DB(w i )) as a ball of weight i /p ∈ [0, 1]
6 As Algorithm 1 is kept purely combinatorial, balls technically have no content. We still need to retreive lists L given the keyword w in this context. Thus, we say that the pair (w, L) is a ball identified by w and scaled weight |L|/p. We assume that we can retrieve the list L given w from the bin that contains ball (w, L). Clearly, this does not change the behaviour of L2C and we can still apply Theorem 1 on the given variant.

and call L2C.Setup with maximal weight N/p and balls (w i , DB(w i )) W i=1 as input. The two random choices (α i,1 , α i,2 ) ← H(w i ) in L2C.Setup are drawn by evaluating H on w i . The result are m bins (B i ) m i=1 filled with the balls such that each bin has load at most c log log log(λ) log log(N/p) (see Theorem 1). Thus, each bin contains at most p • c log log log(λ) log log(N/p) identifiers as weights are scaled by a factor p. (The constant c ∈ N only depends on N but not the output of L2C.Setup.) Next, each bin is filled up to maximal size with dummy items. Finally, encrypt the bins B enc i ← Enc K Enc (B i ) and return EDB = (B enc i ) m i=1 . LayeredSSE.Search(K, w; EDB). The client receives its secret key K and keyword w. She sends w to the server, and in return receives bins B enc α1 , B enc α2 , where (α 1 , α 2 ) ← H(w).

LayeredSSE.Update(K, (w, L ), add; EDB). The client receives its secret key K, keyword w and a list L of new identifiers matching w. She sends w to the server and again receives bins B enc α1 , B enc α2 in return, where (α 1 , α 2 ) ← H(w). Next, the client decrypts B enc α1 , B enc α2 to B α1 , B α2 and retrieves ball (w, L) from the corresponding bin B α ∈ {B α1 , B α2 }. Then, she calls L2C.UpdateBall with old ball (w, L), new identifiers L and bins B α1 , B α2 to insert the new identifiers L into one of the bins. Finally, she reencrypts the bins and sends them to the server. The server then replaces the old bins with the updated bins. 1: return w Server:

Algorithm 6 LayeredSSE

1: Set α1, α2 ← H(w) 2: return B enc α 1 , B enc α 2
LayeredSSE.Update(K, (w, L ), add; EDB) Client:

1: return w Server:

1: Set α1, α2 ← H(w) 2: return B enc α 1 , B enc α 2
Client:

1: Set Bα i ← Dec K Enc (B enc α i ) for i ∈ {1, 2} 2: Retrieve ball (w, L) from Bα for appro- priate α ∈ {α1, α2} 3: Run L2C.UpdateBall((w, L), L , Bα 1 , Bα 2 ) 4: Set B new α i ← Enc K Enc (Bα i ) for i ∈ {1, 2} 5: return B new α 2 , B new α 2
Server:

1: Replace B enc α i with B new α i for i ∈ {1, 2}

A.2 Security

The scheme LayeredSSE is correct as each keyword has two bins that contain its identifiers associated to it (and these bins are consistently retrieved and updated with L2C). If the hash function is modeled as a random oracle, the bin choices are uniformly random and Theorem 1 guarantees that bins do not overflow.

Also, LayeredSSE is selectively secure and has standard setup leakage N , such as search and update leakage qp, where qp is the query pattern7 . This can be shown with a simple hybrid argument. We sketch the proof here and refer to Appendix D for more details. For setup, the simulator Sim receives N , recomputes m and initializes m empty bins B 1 , ..., B m of size p • c log log log(λ) log log(N/p) each. Sim then outputs EDB = (Enc K Enc (B i ) m i=1 ) for some sampled key K Enc . As Enc is IND-CPA secure (and bins do not overflow in the real experiment except with negligible probability), the output EDB is indistinguishable from the output of Setup in the real experiment. For a search query on keyword w, Sim checks the query pattern qp whether w was already queried. If w was not queried before, Sim a new uniformly random keyword w . Otherwise, Sim responds with the same keyword w from the previous query. As we assume that keywords are preprocessed by the client via a PRF, the keywords w and w are indistinguishable. For an update query on keyword w, the client output in the first flow is the same as in a search query and thus, Sim can proceed as in search. For the second flow, Sim receives two bins B α1 , B α2 from the adversary, directly reencrypts them and sends them back to the adversary. This behaviour is indistinguishable, as the bins are encrypted and again, bins do not overflow except with negligible probability.

For adaptive security, the adversary can issue search and update queries that depend on previous queries. As Theorem 1 assumes selectively chosen InsertBall and UpdateBall operations, there is no guarantee that bins do not overflow anymore in the real game. Thus, the adversary can potentially distinguish update queries of the simulated game from real update queries if she manages to overflow a bin in the real game, as she would receive bins with increased size only in latter case. Fortunately, we can just add a check in Update whether one of the bins overflows after the L2C.UpdateBall operation. In that case, the client reverts the update and send back the (reencrypted) original bins. Now, Theorem 1 still guarantees that bins overflow only with negligible probability after Setup and we can show that the simulated game is indistinguishable from the real game as before. (Note that LayeredSSE is still correct after this modification, since queries are chosen selectively for correctness.) Note that when the client remarks that a bin overflowed in an Update in a real world environment, this is due malicious Update operations. The client can adapt his reaction accordingly, whereas the server learns no information about the attack without being notified by the client.

We can show that LayeredSSE with the adjustement of Update is correct L len-hid -adaptively secure. The same simulator Sim suffices and we omit the details.

A.3 Extensions

Handling Long Lists. We now adapt LayeredSSE to handle arbitrary lists L (with potentially more than p identifiers). We proceed similarly to the static scheme Pluto from [BBF + 21] and extend the ideas to updates. For this, we split L into sublists of size at most p. The (encrypted) full sublists of size p can be stored in a hash table T full on the server and the incomplete sublists are handled by LayeredSSE as before. For search, the client needs to know the number of sublists in order to fetch the right amount from the server. This information is also required for update queries in order to know when to insert another full list into T full . This information can be outsourced in a table T len . Here, the client stores for each keyword w (with matching identifiers) the number of sublists T len [w] = /p in encrypted format. In the following, we describe the updated Setup, Search and Update of LayeredSSE in more detail.

Setup. For setup, let L i be a list of i identifiers matching keyword w i and PRF be a secure pseudo-random function mapping to {0, 1} log(N ) . We set x i = i /p . The client splits L i into sublists L i,1 , ..., L i,xi-1 of size p and sublist L i,xi of size at most p. She evaluates m i ← PRF K PRF (w i ), where K PRF is a key for PRF sampled in KeyGen. The mask m i is used to encrypt the content of T len . After initializing the table T len with N random entries of size log(N ) bits and T full with N/p (arbitrary) lists of size p, she sets

T len [w i ] = x i ⊕ m i and T full [w || i] = L i,j for j ∈ [1, x -1]. Next, she generates (B i ) m
i=1 as before with the incomplete lists L i,xi except that the bin choices for list L i,xi are (α i,1 , α i,2 ) ← H(w i || x i ). Note that we need to also hash the counter x i , as after some updates, the incomplete sublist of w i might become full and a new incomplete sublist has to be started. When the new incomplete sublist gets inserted with L2C, it is interpreted as a new ball and new bins need to be chosen. Finally, she encrypts the content of T full and returns EDB = (T len , T full , (B enc i ) m i=1 ). Search. For search queries on keyword w, the client outputs mask m ← PRF K PRF (w) in addition to w. The server uses this mask to decrypt the number of sublists x ← T len [w] ⊕ m, retreives x -1 encrypted sublists L i ← T full [w || i] from the table for i ∈ [1, x-1] and the two bins B enc α1 and B enc α2 via (α 1 , α 2 ) ← H(w || x). Finally, the server sends the encrypted bins and sublists to the client. Clearly, the client obtains all matching identifiers after decrypting the received lists and bins.

Update. For update queries on keyword w and list L of (at most p) new identifiers8 , the client generates mask m as before and sends (w, m) to the server. The server again decrypts x from T len and sends B enc α1 , B enc α2 to the client. In addition, the server already sends the bins B enc α3 , B enc α4 for α 3 , α 4 ← H(w || x + 1) to the client (in case the incomplete list overflows). The client now retrieves the old (incomplete) list L of identifiers matching w from the decrypted bins B α1 , B α2 . We distinguish two cases:

1. If L ∪ L contains more than p identifiers, the client sets L new = L ∪ L and marks (w, L) as a residual ball inside B α1 , B α2 . Then, she splits L new into two sublists L =p with p identifiers and L ≤p of at most p identifiers. The client then inserts list L ≤p into bins B α3 , B α4 via L2C.InsertBall((w, L ≤p ), B α3 , B α4 )

and sends the updated (reencrypted) bins {B enc i } 4 i=1 such as encrypted list L enc = Enc K Enc (L =p ) to the server. 2. Otherwise, the client proceeds as before, i.e. adds the new identifieres L to ball (w, L) via UpdateBall and reencrypts the received bins.

Finally, the server replaces the old bins with the reencrypted bins, and if she received an encrypted list L new , she stores the received list in T full [w || x + 1] = L enc and updates T len [w] = x + 1.

Leakage profile. Now, search and update queries LayeredSSE leak the number of sublists x = /p for a given keyword w with matching identifiers. Further, updates leak when a list was completed (so also the value ( + |L |)/p ). This is exaclty the leakage modeled by L len-hid . As tables T len and T full are encrypted, it is straigthforward to adapt the security analysis in Appendix A.2 to the extended scheme with respect to leakage function L len-hid .

Handling Deletes. We apply the generic solution from [Bos16] to handle deletes. We use two instantiations of LayeredSSE, Σ add for added items and Σ del one for deletes. For adding identifiers L to a keyword w, the client adds list L to Σ add via Σ add .Update(K, (w, L ), add; EDB). For deleting identifiers L from a keyword w, the client adds list L to Σ del via Σ del .Update(K, (w, L ), add; EDB). For a search query, the client fetches the identifiers w from both Σ add and Σ del and removes the set of items L del received from Σ del from the set of items L add received from Σ add , i.e. sets L ← L add \ L del .

Optimized RTT. Search queries of LayeredSSE need only 1 RTT, whereas update queries unfortunately require 2 RTTs. We can use "piggybacking" in order to reduce the update RTT to 1 as follows. Instead of sending the second flow of the update query directly to the server, the client stashes the response and waits for the next query (either update or search). On the next query, the client sends the stashed response in addition to the query. The server then finishes the pending update query (by storing the received bins and updating the tables) and responds the query subsequently.

A.4 Efficiency

We now inspect the efficiency of LayeredSSE. Let w max = N/p. The server stores m = w max /(log log log λ • log log w max ) bins of size O (p log log log(λ) log log(w max ))• O (λ) each, tables T len with N entries of size log(N ) and T full with N/p entries of size p•O (λ) each. (Recall that a single identifier has size O (λ).) As N = poly(λ), the storage efficiency is O (1) in total. There is no client stash required 9 . Further, the server looks up 4 bins of capacity O (p log log(N/p)) and x-1 encrypted lists of p identifiers from T full for a search query on word w, where x is the number of pages needed to store the document indices matching keyword w in plaintext. Thus, the page efficiency is O log log N p . This further implies that LayeredSSE has O (1) locality if only lists up to size p are inserted.

Theorem 6 (LayeredSSE). Let N be an upper bound on the size of database DB and p be the page size. Let p ≤ N 1-1/ log log λ . The scheme LayeredSSE is correct and L len-hid -adaptively semantically secure if Enc is IND-CPA secure and H is modeled as a random oracle. It has constant storage efficiency and O (log log N/p) page efficiency. If only lists up to size p are inserted, LayeredSSE has constant locality.

Proof. Efficiency and security follow from the discussions above.

B Unconditional Static Local SSE

In this section, we present our unconditional SSE scheme UncondSSE with constant locality, constant storage efficiency and O (log ε N ) read efficiency for any ε > 0. For this, we first present a local ORAM construction in Appendix B.1. Then we construct a static SSE scheme with O (log ε λ) page efficiency in Appendix B.2 that works for large page sizes and has constant client storage. Finally, we use those schemes in order to construct UncondSSE in Appendix B.3

B.1 Local ORAM

Let c ∈ N be arbitrary. We now construct an ORAM LocORAM with amortized constant locality and O β • n 1/c log 2 (n) bandwith, where n is the size of the memory array and β = Ω(n (c-1)/c ) is the block size. As c is arbitrary, we can instantiate LocORAM with bandwith overhead O (n ε ) for any ε > 0 and constant locality, if the block size is sufficiently large. Our scheme follows the blueprint of the scheme of [DPP18]. The reader may find it helpful to refer to their scheme first.

More Preliminaries. Before detailing the construction, we introduce some additional preliminaries.

Definition 11 (ORAM).

-Initialize ORAM (1 λ , M): Client take as input security parameter λ such as memory array M of n values {(i, v i )} n i=1 of O (λ) bits each. Outputs client state st and encrypted memory EM.

-Access ORAM (st, i; EM): The client takes as input its state and index i. The server takes as input encrypted memory EM. Outputs value v i assigned to i and updated state st to the client such as updated encrypted memory EM to the server.

We require read-only ORAM with zero-failure probability for our construction. We say that an ORAM scheme is correct, if for any access sequence on block i, the retrieved block via Access ORAM is (i, v i ). We say that an ORAM scheme is (adaptively) secure, if for any two (adaptively chosen) access sequences S 1 and S 2 of the same length, their access patterns A(S 1 ) and A(S 2 ) are computationally indistinguishable by anyone but the client. We refer to [DPP18] for formal definitions.

Lemma 1 (Local Oblivious Sort [Goo11,GM11,DPP18]). Given an array X containing n comparable elements, we can sort X with a data-oblivious external-memory protocol OblSort that uses O n b log 2 n b I/O operations and local memory of 4b chunks, where an I/O operation is defined as the read/write of b consecutive chunks of X.

We set chunk size b = n 1/c log 2 n in our ORAM scheme. This suffices for O(1) locality. We implicitly assume that the sorted array is reencrypted (under the same encryption key as the input array).

The Scheme. We now describe our construction LocORAM of a read-only ORAM (based on [DPP18]). Let c be a constant. We write β for the ORAM blocksize. Essentially, LocORAM is a hierarchical ORAM with c levels. For n blocks of memory, it has constant locality and a bandwith of

O β • n 1/c log 2 (n) with O β • n 1/c log 2 (n) temporary client storage, if β = Ω(n (c-1)/c
). Now, we give an overview of the construction. A detailed description is given in Algorithm 7.

LocORAM.Initialize ORAM (1 λ , M). The client receives memory M = {k, v k } n k=1 with blocksize |k, v k | = β. She allocates c arrays A 1 , A 2 , ..., A c with space for n i blocks each, where n 1 = n 1/c and n i = n i/c + n (i-1)/c . Let π i : [1, n i ] → [1, n i ] be pseudorandom permutations. Initially, the client stores all blocks (k, v k ) in A c at position π c (k). Later on, blocks will also be stored in other levels. Note that while A c can hold all blocks, lower levels A i can only store up to n i/c blocks (and the remaining space is reserved for dummy queries). We would still like to store block (k, v k ) at a pseudorandom position. For this, we initialize tables

T i , i ∈ [2, c-1], which store a scaled index T i [k] ∈ [1, n i/c
] for block k (if the block is stored in level i). (Note that we do not require table T 1 for the first level, as the client always retrieves the entire array A 1 each read and thus, no pseudorandom accesses is required for the first level.) The block k is later stored at location π i (T i [k]). Further, the client initializes sets R i that store the blocks mapped to level A i . Initially, R c = M and the other sets are empty. Levels are later rebuilt (with a new pseudorandom permutation) after a certain number of reads such that each item is only accessed once per level before the next rebuild (and thus resemble a random access to A i ). The client keeps track of the number of reads cnt i at level i after the last rebuild, initialized to 0. The client finally encrypts A i , R i and T i and sends them to the server and stores the encryption key, cnt i , and π i in its state.

LocORAM.Access ORAM (st, k; EM). The client receives index k of the block to be retrieved and its state st which she parses as {π i } c i=2 , {cnt i } c i=2 , K Enc . The server receives the encrypted memory EM which she parses as

({A enc i } c i=1 , {R enc i } c-1 i=2 , {T enc i } c-1 i=2 ).
First, the client increments the counts cnt i . Next, the client retrieves tables T enc i and array A enc 1 from the server10 . After decryption, the client looks for the first level A i * in which (k, v k ) is stored. This level is the first for which the table T i has a non-zero entry T i [k] = 0. She performs a dummy query for all other levels A i (by accessing a random and unqueried position in A i using π i ) and retrieves (k, v k ) from level A i * (either by scanning

A 1 if i * = 1 or from A i * at position π i (T i [k]
)) with the help of the server. Next, the client writes (k, v k ) to A 1 . Note that later, A 1 will be merged with upper levels and thus, we already prepare T i [k] = cnt i+1 and add an encryption of block (k, v k ) to the set R i of blocks stored in the i-th level. Last, the client rebuilds (some of) the levels if necessary. For this, she takes the highest i * such that cnt i * > n (i * -1)/c . If i * ≥ 2, all levels A i below A i * are emptied and filled with dummy blocks. Then, she chooses new pseudorandom permutations π i for i ∈ [2, i * ] and merges all blocks from the lower levels into A i * via a local oblivious sort OblSort (see Lemma 1). Concretely, the client and server interactively sort R i * with respect to the new π i * . The array R i * is temporarily filled up to n i * blocks with zeros in order to obtain array A i * of size n i * . For the oblivious sort, we choose a chunk size of n 1/c log 2 n (which is sufficient for O (1) locality). Lastly, the server and client empty the lower levels (and its auxiliary data structures) A i , R i , T i for i ∈ [2, i * -1] and A 1 . (Note that an empty and encrypted array A i can be constructed iteratively with the same method as R i .) Finally, the client updates its state, reencrypts the received data structures, and sends them back to the server (who updates EM accordingly).

Theorem 7 (LocORAM). Let n be the size of the memory array, β = Ω(n c-1 c ) the blocksize. The scheme LocORAM is correct and secure, if the π i 's are secure pseudorandom permutations and Enc is an IND-CPA secure encryption scheme. Further, LocORAM has amortized constant locality and bandwith of O β • n 1/c log 2 (n) , and requires O β • n 1/c log 2 (n) temporary client storage (during a rebuild). The client state st has constant size.

Proof. We show that scheme LocORAM is correct (1), secure (2) and analyze its efficiency (3).

(1) We need to show that for all indices k ∈ [1, n], the server retrieves the block (k, v k ) via the access protocol when executing an adaptive access sequence after the initialization. For this, we observe that

(k, v k ) is either in A 1 , A i [π i (T i [k])] (for the minimal i ∈ [2, c -1] such that T i [k] = 0) or A c [π c (c)] (if no such i exists). This is because if (k, v k ) has been accessed in the last n 1/c
operations, the block will be stored in A 1 . If (k, v k ) has been accessed in the last n i/c operations but not in the last n (i-1)/c operations, it was shuffled into array A i at position T i [k] during a previous rebuild of level A i . Also, as it has not been accessed recently, we have T j [k] = 0 for j < i as tables below are emptied during a rebuild. Otherwise, it was never accessed before and is located in A c at initial position π c (k). These values are retrieved by the client and thus, the scheme is correct.

(2) We give an simulator Sim. For initialization, the simulator receives |M|, the block size β and the security parameter λ. Sim outputs LocORAM.Initialize ORAM (1 λ , M ) for M = {i, 0} n i=1 where the zeros are of size β. Under the IND-CPA security, this output is indistinguishable from the real game, as the output is encrypted. For simulating an access, Sim retrieves A 1 and the tables T i from the server. First, Sim increments cnt i . Then, Sim outputs r i ← Enc K Enc (0) and random indices index i that were not yet queried in A i (since A i was last emptied). Lastly, Sim and the server rebuild the largest level A i if cnt i ≥ n (i-1)/c for some i ≥ 2. For this, Sim simply checks (and updates) cnt i accordingly and simulates the oblivious search with the server. It follows by inspection that if π i are pseudorandom permutations and Enc is IND-CPA secure, the interaction with Sim is indistinguishable from the game.

(3) As c is a constant, the client state is O (1). Further, the client requires O n 1/c log 2 n blocks of temporary storage for the oblivious sort (see Lemma 1). We now inspect the bandwith and locality. Over the course of n accesses, the following holds for the i-th access.

-The client reads array A 1 of size O β • n 1/c , one block from each other level A i and tables

T i of size O n (c-1)/c • log(n) = O (β • log n), as β = Ω(n (c-1)/c ). In total, this incurs O β • n 1/c bandwith and O (1) locality. -If i mod n (i-1)/c = 0 ∧ i ≥ 2,
the client performs a rebuild of array A i via an oblivious sort with chunk size n 1/c log 2 n. According to Lemma 1 and as A i contains O n i/c blocks, the sort requires O n (i-1)/c I/O operations. In total, this incurs O β • n i/c log 2 n bandwith and O n (i-1)/c locality and happens n (c-i+1)/c times during n accesses.

In total, the amortized bandwith B and locality L are

L = nO β • n 1/c + c i=2 n (c-i+1)/c O β • n i/c log 2 n n = O β • n 1/c log 2 n , B = nO (1) + c i=2 n (c-i+1)/c O n (i-1)/c n = O (1) .
Remark 1 (On Deamortization). Generally, hierarchical ORAMs can be deamortized by continuously reshuffling the layers each operation [GMOT11]. Indeed, our ORAM is an iterated version of [DPP18] which uses this technique for their deamortization. We believe that LocORAM can be deamortized in the same manner but leave the details for future work.

B.2 Tethys without Stash.

Now, we introduce a page-length-hiding static SSE scheme OramTethys that has O (log ε λ) page efficiency, constant storage efficiency and contant client storage.

We will later use it in the local transformation.

More Preliminaries. Again, we require some additional preliminaries.

Definition 12 (Binpacking). We define the algorithm Binpack that takes at most N keyword-identifier pairs Stash and a size p as input. Binpack proceeds as follows. Allocate bins B 1 , ..., B 2N/p and table T pos . Then, take list L of identifiers matching keyword w and insert the identifiers one-by-one into the bin with the smallest index that is not full yet. Set T pos [w] = i, where i is the smallest index of a bin containing an identifier matching w. Finally, fill the bins up to size p with zeros. Finally, output (M, T pos ).

Clearly, if there are at most p identifiers matching keyword w, the identifiers will all fit into B i , B i+1 for i ← T pos [w]. Also, note that Binpack can always fit all N identifiers into the bins.

Lemma 2 (Tethys [BBF + 21]). The SSE scheme Tethys is correct and L len-hidadaptively secure in the random oracle model (under the assumption that there exists an IND-CPA secure encryption scheme and a secure pseudo-random function). It has a client storage ω(log λ)/ log N pages, and O (1) storage and page efficiency.

We call the client storage of Tethys its stash. In this work, a stash size of O log 1+δ (λ) = ω(log λ)/ log N ) pages is sufficient for our construction, for some arbitrary δ > 0.

The Scheme. We now define the static SSE scheme OramTethys with client storage O (1). Let p = Ω(λ), c ∈ N and δ > 1. Essentially, we use Tethys (see Lemma 2) and outsource its stash using LocORAM. We define the static SSE scheme OramTethys for given page size p as follows:

OramTethys.KeyGen(1 λ ). Simply output K ← Tethys.KeyGen(1 λ ).

OramTethys.Setup(K, N, DB). The client generates encrypted database EDB and stash Stash using (EDB , Stash) ← Tethys.Setup(K, N, DB). The stash contains the remaining keyword-identifier pairs (w i , id i ) that could not be allocated directly in Tethys. We want to outsource Stash using LocORAM with c levels and blocksize β = p. The items in Stash are not necessarily lists of size p. Thus, we group Stash into pages of p identifiers using (M, T pos ) ← Binpack(Stash, p). Let n = O log 1+δ (λ) . After the binpacking, M consists of n pages with p identifiers each (see Lemma 2) and we can access the identifiers matching keyword w in page i = T pos [w], as there is at most one such page 11 . As this binpacking process is not data-oblivious, we can not leak i to the server. Thus, the client sets T enc pos ← Enc K Enc (T pos ) (after padding T pos to n entries of log n bits). Further, she applies (EM, st) ← LocORAM.Initialize ORAM (1 λ , M). Finally, she outputs EDB = (EDB , EM, T enc pos ) and stores state st locally.

OramTethys.Search(K, w; EDB). The client initiates protocol Tethys.Search(K, w; EDB) with the server from which she receives some of the identifiers matching keyword w. Next, the client retrieves i enc = T enc pos [w] from the server and decrypts the index of the page containing the remaining identifiers via i ← Dec K Enc (i enc ). The client retrieves this page via LocORAM.Access ORAM (st, i; EM).

Lemma 3 (OramTethys). The SSE scheme OramTethys is correct and L len-hidadaptively secure. Let ε > 0 and p = Ω(λ). There are constants δ > 1 and c ∈ N such that it has constant client storage, constant storage efficiency and O (log ε λ) page efficiency. Further, the scheme has O (1) locality if each list fits into a constant number of pages.

Proof. We first show that OramTethys is correct and L len-hid -adaptively secure. Then, we analyze the efficiency for arbitrary constants c and δ from which we conclude the existence of ε.

(1) As Tethys is correct, it remains to show that all remaining identifiers are fetched from the stash when searching a keyword w. First, note that we store

n = O log 1+δ (λ) blocks in LocORAM. The scheme LocORAM is correct if the blocksize p is Ω n c-1 c = Ω log 1+δ(c-1) c
λ which holds as δ, c are constant and p = Ω(λ) by assumption. As Binpack packs the stash into bins of size p and the accessed index i = T pos [w] corresponds to the bin containing the identifiers matching keyword w, the scheme OramTethys is correct.

(2) The security follows directly as Tethys is L-adaptively secure, LocORAM is adaptively secure (with zero-failure probability) and the fact that T pos is encrypted.

(3) We now analyze the efficiency of OramTethys. As the client state of LocORAM is O (1) and the instantiation of Tethys only stores its keys on the client side (as the stash is stored on the server), OramTethys only requires constant client storage. The storage efficiency of OramTethys is O (1) because Tethys has constant storage efficiency, and EM and T pos have size n = O log 1+δ (λ) pages and entries respectively. We now inspect the page efficiency. First, note that Tethys has constant page efficiency and the access to T pos requires (at most) one page access. The access of the stash through LocORAM requires bandwith

O β • n 1/c log 2 (n) = O p • log 1+δ
c +δ λ for some arbitrary δ > 0. As c, δ and δ are arbitrary constants, scaling them accordingly yields the desired result. Constant locality follows directly from the fact that LocORAM has constant locality and that Tethys accesses at most O ( /p) pages for a search on keyword w, where is the length of the list of identifiers matching w. (Recall that we assume that O ( /p) is constant for all lists.)

B.3 The Scheme

Finally, we describe our unconditional static SSE scheme UncondSSE with O (log ε (N )) locality, for abitrary ε > 0. We follow the high level idea of [DPP18] to handle lists with different schemes depending on the list size. For d ∈ N, we split the interval [1, N ] of possible list lengths into four different subintervals.

1. For the subinterval [1, N 1-1/ log log λ ), the lengths are sufficiently for LayeredSSE and can simply store the lists using Local [LayeredSSE]. Here, the read efficiency is O (log log N ). 2. For the subinterval [N 1-1/ log log λ , N/ log d N ), the lengths are simultaneously small enough for the local transformation and large enough for OramTethys. Thus, we store the lists using Local[OramTethys] with O (log ε N ) read efficiency. 3. We further split the subinterval [N/ log d N, N/ log ε N ) into a constant number of subintervals, such that OramTethys has O (log ε N ) read efficiency. 4. For the subinterval [N/ log ε N, N ], lists are large enough to read the entire database. Thus, we simply encrypt DB and fetch it entirely from the server for these lists.

We now present how to divide the interval [N/ log d N, N/ log ε N ) into subintervals in more detail.

Handling the Remaining List Sizes. Note that for lists of size in [N/ log ε N, N ), we can just store an encrypted copy of the database on the server and retrieve the entire copy for each read. We now sketch how we handle the remaining lists of size in S = [N/ log d N, N/ log ε N ) for some arbitrary d ∈ N and ε ∈ (0, 1) R . For this, we split the interval S into a constant number of subintervals S i such that the borders of each interval differ by a factor log ε N . Concretely, we set

S i = [N/ log d-iε N, N/ log d-(i+1)ε N ) for i ∈ [0, d/ε ].
For each S i , we store lists of size in S i via OramTethys with page size p = max(S i ). Note that each list has at most size p. Thus, OramTethys has O (1) locality and O (log ε λ) read efficiency (see Lemma 3). Note that page efficiency directly translates to read efficiency in this case, as each list is at most a factor of log ε λ smaller than the page size.

UncondSSE. We now present our static SSE scheme UncondSSE. For a given ε > 0, it has unconditionally O (log ε N ) read efficiency, constant locality and constant storage efficiency. Let d ∈ N be the parameter of the local transformation chosen appropriately.

UncondSSE.KeyGen(1 λ ). Generate key K 1 for Local [LayeredSSE], key K 2 for Local[OramTethys], key K 3 for OramTethys and encryption key K 4 for Enc. Also, generate key K PRF for pseudorandom function PRF mapping to {0, 1} log (N ) .

Output K = (K 1 , K 2 , K 3 , K 4 , K PRF ).
UncondSSE.Setup(K, N, DB). First, we initialize a table T len that stores the encrypted length i ⊕ m i of each list DB(w i ) at position T len [w], where m i ← PRF K PRF (w i ) is a mask. Then, we pad T len up to size N (with random values of log N bits). We split the interval of possible list lengths [1, N ] into four different subintervals and handle each subinterval seperately. For each subinterval, we define four databases DB i containing a subset of the keyword-identifier pairs of the given database DB (chosen with respect to the lists length). We set

DB 1 = DB(w i ) | i ∈ 1, N 1-1 log log N , DB 2 = DB(w i ) | i ∈ N 1-1 log log N , N/ log d N , DB 3 = DB(w i ) | i ∈ N/ log d N, N/ log ε N , DB 4 = {DB(w i ) | i ∈ [N/ log ε N, N ]} .
The

S i = [N/ log d-iε N, N/ log d-(i+1)ε N ] R for i ∈ [0, d • ε -1 ] as described above. We then set DB 3,i = {DB(w i ) | i ∈ S i } and EDB 3,i ← OramTethys.Setup(K 3 , N, DB 3,i ). Finally, set EDB 3 = (EDB 3,1 , • • • , EDB 3, d•ε -1
). Lastly, lists in DB 4 are large enough that we can scan entire database each read. For this, we pad DB 4 up to size N and set EDB 4 ← Enc K Enc (DB 4 ). Outputs EDB = (EDB 1 , EDB 2 , EDB 3 , EDB 4 , T len ).

UncondSSE.Search(K, w; EDB). For retreiving the identifiers matching keyword w, the client sends w and m ← PRF K PRF (w) to the server. The server decrypts the length ← T len [w] ⊕ m i of the list to be fetched and then checks in which subinterval lies. We distinguish four cases: ( 1 The proof sets α and κ to be constants. The fact that γ and κ are constant is not essential to the argument, and is only used in two places in the proof.

The first place is the end of Section 2.3, when upper-bounding the probability of activation of a pruned witness tree by m -κ+1+o(1) . The final step of that upper-bound requires α•κ = m o(1) , which is obviously true for a pair of constants.

The other, more important place where the choice of having constant α and κ comes into play is in the final derivation. The proof shows that, except with probability at most m -κ+1+o(1) + m -α , the number of items in the most loaded bin is at most:

L + O(h) ≤ log log m + log(1 + α) + κ + O(h) = log log m + O(1) + O(h) = log log m + O(h).
In that final computation, the fact that α and κ are constant makes it possible to absorb the log(1 + α) + κ term into the O(h) term. The other term is only log log m, which is optimal. If we set α = κ = δ(m) log log m instead, we get:

L + O(h) ≤ log log m + log(1 + α) + κ + O(h) ≤ 3δ(m) log log m + O(h).
In the case δ = 1, this worsens the constant in front of the log log term, which is likely why the authors chose α and κ to be constant. (A better constant than 3 is possible, we choose 3 for simplicity.) On the other hand, the probability of failure becomes at most m -κ+1+o(1) + m -α = m -Ω(δ(m) log log m) as claimed. Note that the condition α • κ = m o(1) is still fulfilled.

The next lemma is a direct application of Markov's inequality. Lemma 6. For any random variable X ∈ [0, N ] R and any R > 0 (which may depend on N ):

Pr [X > R] = negl(λ) iff E[max(X -R, 0)] = negl(λ) . Lemma 7 (Weigthed 1C [BFHM08].
). Let m ∈ [0, 1] R be some maximal weight. Let x = (m) i≤n and x = (w i ) i≤n be (non-negative) weight vectors. Let

n i=1 w i ≤ n • m and w i ≤ m for all i ∈ {1, ..., n } 12 . Let R ∈ R + . Then it holds that E[max(X mlb -R, 0)] ≥ E[max(X mlb -R, 0)],
where X mlb (X mlb ) are a random variable indicating the load of the most loaded bin after throwing n balls with weights x (n balls with weights x ) uniformly and independently at random into m bins 13 . operation can be replaced by an InsertBall(b * , 2 i-1 / log m, (B α * ,1 , B α * ,2 ) operation. Thus, for ball b * with final weight w j , we have to insert k additional balls in order to replace all update operations on ball b * with inserts. The total weight of these additional balls is

k i=1 2 i-1 / log m ≤ 2 k / log(m) ≤ 2w j ,
since w j ≥ 2 k-1 / log(m). Thus, the total weight is increased at most by a factor 3 per ball.

This way, we can iteratively remove all UpdateBall operations at the cost of a factor 3 in the total weight. The remaining operations are InsertBall operations, where each ball b i is inserted at most once per subinterval and the bin choices are drawn uniformly and independently random per ball. Clearly, if O (3 log log w max ) is an upper bound on the load of the most loaded bin for the modified sequence S , then O (3 log log w max ) is an upper bound for the initial sequence S. In the following, we only consider modified sequences S of n such InsertBall operations.

Part 2 -Light balls: Here, we show that the most loaded bin has load at most 3δ(λ) log log w max when only considering balls of at most weight 1/ log m. Let w ≤ w max be the total weight of all such light balls. Without loss of generality, assume that w max = w. At first, we assume that all such balls have weight exactly 1/ log m each. We will then reduce the case with arbitrary weights in [0, 1/ log m] R to the above.

Since we initially assume all balls have weight 1/ log m, the number of balls is at most n = w log m. Let X i be the random variable that denotes the number of balls in bin B i . Recall that m = w δ(λ) log log w . We observe that InsertBall behaves like 1C in this case and thus, we have E[X i ] = n /m = δ(λ) log log w • log m. Applying Chernoff's bound (Lemma 10), we get:

Pr[X i ≥ (1 + γ) E[X i ]] ≤ exp - γ 2 E[X i ] 2 .
We insert γ = 2 in the equation above and receive:

Pr[X i ≥ 3δ(λ) log log w•log m] ≤ exp(-2δ(λ) log log w•log m) = m -Ω(δ(λ) log log w) .

A union bound yields that the most loaded bin contains at most 3δ(λ) log log w • log m balls with probability at most m -Ω(δ(λ) log log w) = negl(λ). As each ball has size 1/ log m, the most loaded bin has a maximal load of 3δ(λ) log log w with overwhelming probability. Now, we show this bound is preserved when allowing arbitrary weights of at most 1/ log m. We define the weight vectors x = (1/ log m) w log m i=1 and x = (w i ) i∈I . Let X mlb and X mlb be the random variable indicating the load of the most loaded bin with weights x and with weights x respectively. We want to show that Pr[X mlb > 3δ(λ) log log w] = negl(λ). Lemma 12 implies that the above holds iff E[max(X mlb -3δ(λ) log log w), 0)] = negl(λ). This expectancy can be upper bound by E[max(X mlb -3δ(λ) log log w), 0)] as x and x fulfill the requirements of Lemma 7. As we showed above that Pr[X mlb > 3δ(λ) log log w)] = negl(λ), we can conclude from another application of Lemma 12.

Part 3 -Heavy balls: So far, we have shown that the most loaded bin has load at most 3δ(λ) log log w with overwhelming probability, when only considering balls of weight smaller or equal to 1/ log m, for any (modified) sequence S. We will now show that when considering the remaining balls of weight in (1/ log m, 1] R , a maximal load of O (w max /m + δ(λ) log log w ) = O (δ(λ) log log w ) is preserved.

For i ∈ [1, log log m], let n i be the number of balls in each subinterval A i = (2 i-1 / log m, 2 i / log m] R . Recall that each ball b i has two bin choices that are drawn uniformly and independently random at the first insertion. These choices are reutilized across the subintervals A i , if b i is inserted in multiple subintervals. But note that per subinterval, b i is only inserted once. Thus, L2C behaves like unweighted 2C on all balls with weights in A i (independent from the balls in other subintervals). By Lemma 5, the bin with the highest number of balls (of weights in A i ) contains at most O (n i /m + δ(λ) log log m) balls with overwhelming probability. (Note that there are at most w log m balls and that m -Ω(δ(λ) log log w) = negl(λ).)

Each ball has weight at most max(A i ) = 2 i / log m and thus, the load of the most loaded bin is at most 2 i / log m(O (n i /m + δ(λ) log log m)) when considering balls with weights in A i . Summing over all A i 's, when considering only balls with weights in (1/ log m, 1], the load of the most loaded bin is at most

log log m i=1 2 i log m O (n i /m + δ(λ) log log m) = log log m i=1 O 2 n i 2 i-1 m log m + log log m i=1 2 i log m O (δ(λ) log log m) ≤O w max m + δ(λ) log log w max ,
as m = O (w max ) and w max is an upper bound on the total weight. The above holds with overwhelming probability, since the probability that 2C fails is negl(λ), and there are only log log m subintervals.

As we showed in the first part that is suffices to look at the modified sequence (with only InsertBall operations), we conclude that the load of the most loaded bin is at most O (log log w max ).

D Security Analysis of LayeredSSE

Lemma 8 (Correctness). The scheme LayeredSSE is correct if at most p identifiers are associated to each keyword and H is modeled as a random oracle.

Proof. We use L2C to insert (and update) the lists of identifiers DB(w) of length ≤ p into m bins. Each list is interpreted as a ball of weight /p ∈ [0, 1]. Theorem 1 implies that the maximal loaded bin has load at most c log log log(λ) log log(N/p) for some appropriate constant c ∈ N (for δ(λ) = log log log(λ)), since the bin choices via H are uniformly and independently random by assumption. That means, it contains at most p • c log log log(λ) log log(N/p) identifiers (as we scaled weights by a factor p). Consequently, the bins only overflow with negligible probability. Further, it follows from inspection that one of the two bins returned by the search algorithm on input w contains all the identifiers matching keyword w.

Lemma 9 (Selective Security). Let L Stp (DB, N ) = N , L Srch (w) = qp and L Updt (op, w, L ) = qp, where qp is the query pattern and op = add. Let L = (L Stp , L Srch , L Updt ). The scheme LayeredSSE is L-selectively semantically secure if at most p identifiers are associated to each keyword, Enc is IND-CPA secure and H is modeled as a random oracle. Note that L = L len-hid because we restrict ourselves to lists of size at most p.

Proof. Let Sim denote the simulator and A an abitrary honest-but-curious PPT the adversary.

Initially, Sim receives L Stp (DB, N ) = N and a series of search and update requests with input L Updt (op i , w i , L i ) = L Srch (w i ) = qp. First, Sim initializes m = (N/p)/(log log(N/p) log log log(λ)) bins B 1 , ..., B m zeroed out up to size p • c log log log(λ) log log(N/p), and outputs EDB = (Enc K Enc (B 1 ), ..., Enc K Enc (B m )) for some encryption key K Enc sampled by Sim. Next, Sim simulates the search and update queries.

For search queries, Sim receives sp. If the query pattern sp indicates that the keyword was already queried, Sim outputs the keyword w from the previous query. Otherwise, Sim outputs a new uniformly random keyword w (that has not been queried yet).

For update queries, Sim receives sp. First, Sim proceeds as in search for generating the first output w . After sending w to the adversary A, Sim receives two encrypted bins. Sim simply reencrypts both bins and sends them back to the server.

We now show that the real game is indistinguishable from the ideal game. For this, we define four hybrid games.

-Hybrid 0 is identical to the real game.

-Hybrid 1 is the same as Hybrid 0 except the simulated keywords w are output. By assumption Hybrid 0 and Hybrid 1 are indistinguishable. -Hybrid 2 is the same as Hybrid 1 except a flag FAIL is raised when a bin overflows (i.e. contains more than p • c log log N/p identifiers after Setup or Update). Theorem 1 implies that this happens only with negligible probability. Thus, Hybrid 1 and Hybrid 2 are indistinguishable. -Hybrid 3 is the same as Hybrid 2 except that the encrypted database EDB is replaced with the simulated EDB and bins are just reencrypted and sent back to the adversary in the second flow of Update. Since Enc is IND-CPA secure (and a flag FAIL is only raised with negligible probability), it follows that Hybrid 2 and Hybrid 3 are indistinguishable.

-Hybrid 4 is the same as the ideal experiment. The server's view in the ideal experiment and in Hybrid 3 are identically distributed, so we conclude inductively that the ideal game and the real game are indistinguishable.

E Proof Of ClipOSSE

In this section, we prove Theorem 3. Recall that it is assumed all lists have length at most N/ log d λ for d ≥ 2. This is a limitation of the result, and it is inherent (lists of length close to N/ log λ can create too many overflowing elements, and must be handled separately.)

The proof is divided into two parts. First, we show that the result holds when all lists have size exactly N/ log d λ. Second, we show that the result still holds as long as all lists have size at most N/ log d λ. The second part is the hard part.

E.1 Proof Part 1: All Lists Have Size N/ log d λ.

We recall one of the standard formulations of the Chernoff-Hoeffding bound.

Lemma 10 (Chernoff-Hoeffding). Let X = i≤n X i where the X i 's are i

.i.d. 0-1 random variables, with p = E [X i ]. Pr [X > (p + ε)n] < e -1 2 ε 2 n/(p+ε) Pr [X < (p -ε)n] < e -1 2 ε 2 n/p .
The following lemma is a direct corollary.

Lemma 11. Throw n balls into m bins u.i.r. Let µ = n/m be the average load of a bin. Then the probability that a given bin contains more than γµ balls is at most: e -Θ(γ)µ .

Proof. Use Lemma 10 with p = 1/m, ε = (γ -1)p.

Let τ = β log log λ be the threshold at which a bin starts to overflow. By construction, 1C with all lists of size N/ log d λ is exactly a balls-andbins game with n = log d λ balls (each ball is a list) and m = n/ log log λ bins. By Lemma 11, the most loaded bin contains less than log λ log log λ elements, except with negligible probability. We now want to bound the number of bins that overflow. Using the previous lemma again, the probability that a given bucket overflows is e -Ω(β) log log λ = log -Ω(β) λ.

Let (X i ) i≤m denote the indicator variables that are equal to 1 iff the i-th bucket overflows, 0 otherwise. The number of overflowing buckets is X = X i . We know that E [X i ] = log -Ω(β) λ. We want to show that X cannot be much higher than m log -Ω(β) λ.

For that purpose, we use the notion of negative association. Because that notion is only used briefly to establish that Chernoff-Hoeffding bounds apply, we do not develop the theory here, and instead refer the reader to [DR96] for an excellent survey on the topic. By [DR96, Proposition 13], the occupancy numbers (vector (B n,m [i]) i≤m where B n,m [i] is the number of balls in the i-th bin) are negatively associated. By [DR96, Proposition 7.2], since X i = 1 Bn,m[i]≥τ , and x → 1 x≥τ is non-decreasing, the X i 's are also negatively associated. By [DR96, Proposition 5], it follows that we can apply Chernoff-Hoeffding bounds to X = X i . Hence, using Lemma 10 with p = ε = E [X i ] = log -Ω(β) λ, we get:

Pr X > 2m log -Ω(β) λ = e -1 4 εm = e -1 4 m log -Ω(β) λ .
The above quantity is negligible as soon as d -Ω(β) ≥ 2.

Since at most 2m log -Ω(β) λ buckets overflow, and the most loaded bucket contains at most log λ log log λ items, we get that with overwhelming probability, the number of overflowing balls is less than:

log d λ log 1-Ω(β) λ.
Since each ball corresponds to a list containing N/ log d λ items, with overwhelming probability the number of overflowing items is:

N log 1-Ω(β) λ so we can make it O(N/ log c λ) for any constant c of our choice by picking β suitably (and then picking d to satisfy the condition d -Ω(β) ≥ 2 encountered earlier).

E.2 Proof Part 2: General Case

Let L denote an arbitrary multiset of list lengths, with max L ≤ N/ log d λ, and L = N . Let X L be (the random variable denoting) the number of overflowing elements after inserting the lists in L.

In Part 1 of the proof, we have seen that Pr [X L > R] = negl (λ), for a suitable R, when all lists have size N/ log d λ. Our goal is to show a similar result for arbitrary L.

Preliminary groundwork. We are going to work with E [max(X L -R, 0)], rather than Pr [X L > R]. This is made possible by the following lemma.

Lemma 12. For any integral random variable X ∈ [0, N ] and any R ≥ 0:

Pr [X > R] = negl(λ) ⇔ E [max(X -R, 0)] = negl(λ) .

Proof. By a classic inequality, for any positive integral random variable

Y , E [Y ] = i≥0 Pr [Y > i]. It follows that Pr [Y > 0] ≤ E [Y ]. On the other hand, if Y ≤ N , we get E [Y ] ≤ N Pr [Y > 0]. Hence: Pr [Y > 0] ≤ E [Y ] ≤ N Pr [Y > 0] . Since N = poly (λ) (λ), it follows that Pr [Y > 0] is negligible iff E [Y ] is negli- gible.
The lemma is obtained by applying that observation to Y = max(X -R, 0).

The following simple lemma will also be useful.

Lemma 13. Let X, Y be two random variables defined on the same sample space. Let E be a set of events that forms a partition of the sample space (i.e. pairwise disjoint events whose union is the whole space). If the conditional expectations satisfy E Recall that we are trying to show that the number of overflowing items is bounded by some R = O(N/ log c N ), except with negligible probability, for a constant c of our choice. In Part 1 of the proof, we have already seen that this is true when all lists are of size N/ log d N , for some suitable constant d. In Part 2, we want to prove the same for an arbitrary multiset L of list sizes, assuming max L ≤ N/ log d N . Recall that L = N . Let τ = β log log λ be the threshold at which buckets are cut off. For a given bucket load vector b = (b[i]) i≤m , let over(b) denote the number of overflowing items: over

[X : E] ≤ E [Y : E] for all E ∈ E, then E [X] ≤ E [Y ].

Notation

(b) = max(b[i] -τ, 0).
Fix a multiset L of list sizes, with max L ≤ N/ log d N . Let N denote the number of lists of size = 2 i . Note N = N . Recall that the number of buckets is m = N/ log log λ.

Let D(L) be (the random variable denoting) the load of buckets at the output of algorithm 1C, on input L. By abuse of notation, we still write D(L) for a random variable distributed according to D(L). Our goal is to show Pr

[over(D(L)) > R] = negl(λ). By Step 1, this is equivalent to E [max(over(D(L)) -R, 0))] = negl(λ).
To simplify notation, write F (L) = max(over(D(L)) -R, 0)).

Proof outline. Starting from L, let µ = min L be the smallest list size in L. We will merge all N µ lists of size µ pairwise into N µ /2 lists of size 2µ. This increases the size of the smallest list in L from µ to 2µ. We can repeat this process as long as the minimum list size µ is less than the maximum list size N/ log d N . Eventually, all lists have size N/ log d N . At that point, we will be able to apply the result from Part 1 of the proof, which deals precisely with the case that all lists have size N/ log d N . This will show that E [F (L final )] is negligible for the final list L final , obtained after all merging operations are done. In order to show that E [F (L)] is negligible for the list L we start from, we will show that if E [F (L i+1 )] is negligible for a list L i+1 obtained after a merging operation, then E [F (L i )] is also negligible for the list L i before the merging operation. By induction, this will imply that since E [F (L final )] is negigible, then E [F (L)] is also negligible for the original list L.

Thus, it suffices to show that if E [F (L)] is negligible after merging, then it was negligible before merging. This fact is the core of the proof, and involves several techniques. For now, we outline these techniques at a high level, and will provide more details when each technique is introduced. Let m µ = m/µ be the number of superbuckets of size µ. Let us regard lists of size µ as balls, and superbuckets of size µ as bins. Inserting the lists of size µ amounts to throwing N µ balls into m µ bins i.u.r. After merging, a list of size 2µ is viewed as two connected balls. Each pair of connected balls is thrown i.u.r. into two adjacent bins (where the two adjacent bins correspond to one superbucket of size 2µ). When bins are inserted by pairs in that manner, one feature of the resulting distribution is that the bins with even indices (bins number 0, 2, 4, etc) must contain the same total number of balls as the bins with odd indices (bins number 1, 3, 5, etc). When that property is satisfied, let us say that the bins are balanced. To recap: inserting merged lists will always yield balanced bins. On the other hand, if we insert lists before the merging step, there is no particular reason that the resulting bins should be balanced. The first main proof technique is to show the following: if we insert lists before the merging step, and condition the resulting distribution of bin occupancies being balanced, then the merging operation can only increase E [F (L)]. This step relies on a convexity argument, and uses a special auxiliary operator . We leave a detailed discussion of those points for later, and continue to focus on the global outline of the proof.

Insofar as merging can only increase E [F (L)],

we get what we want: if E [F (L)] is negligible after merging, then it was necessarily negligible before merging. However, to apply that argument, we need bins to be balanced. As mentioned earlier, there is no special reason that inserting N µ balls into m µ bins i.u.r. should result in balanced bins. This leads to the next proof technique, which is a stochastic dominance argument. Although the distribution obtained by throwing N µ balls into m µ bins i.u.r. is not balanced, we show that it is stochastically dominated by balanced distribution, namely the distribution obtained by throwing N µ + φ(µ) balls into m µ bins i.u.r. conditioned on being balanced. Here, φ(µ) is a carefully chosen small quantity. Intuitively, what happens is that although the original distribution may not be balanced, the difference 2δ = |n 0 -n 1 | be-tween the number n 0 of balls in bins with even indices, and the number n 1 of balls in bins with odd indices, must be less than φ(µ) (except with negligible probability). As a consequence, by adding less than 2δ balls, we can "correct" the distribution into a balanced one, at the cost of slightly increasing the total number of balls. Since adding new balls can only increase the output of over(•), this new transformation has the desired property that if E [max(over(•) -R, 0)] is negligible for the distribution at the output of the transformation, it was necessarily negligible before the transformation. On the other hand, because we add new balls, we need to be mindful that each merging increases the total number of balls in the system. However, we show that the total number of balls remains O(N ) throughout, which completes the proof. Proof. Let a ∈ N t be defined by a i = max(a i -τ, 0), so that a i is the number of overflowing elements in bucket i for vector a. (Recall that τ is the threshold at which buckets are cut off.) Define b in the same way. Observe that f : x → max(x-R, 0) is a convex function, which implies that for all x, y, f (x/2+y/2) ≤ (f (x) + f (y))/2. As a consequence: Proof. In the scope of this proof, µ is set to min L. Let m µ = m/µ be the number of superbuckets of size µ. Say that a superbucket is flat iff all the buckets it contains have the same number of items. Say that a vector of occupancies b ∈ N m is k-flat if all superbuckets of size k are flat. By construction of 1C, and that fact that µ = min L, after inserting lists in L, bucket occupancies are µ-flat. The load of a bucket is entirely determined by the number of items in the superbucket of size µ that contains it. As a consequence, there is never a reason to consider superbuckets of size smaller than µ. For that reason, instead of working with N m , where each entry corresponds to the load of a bucket, we will work with N mµ , where each entry corresponds the load of a superbucket of size µ, divided by µ (so that an entry is the load of one bucket within the superbucket). To avoid creating confusion about whether a "bucket" or "items" refers to the original occupancy vectors in N m , or the ones just introduced in N mµ , we reserve the term "bucket", "superbucket", and "item" to the former setting, so that the meaning of those terms is unchanged. When working in N mµ , we use balls-and-bins terminology: m µ is the number of bins, and they are occupied by balls. Thus, each bin corresponds to a superbucket of size µ, and each ball corresponds to a list of µ items.

2F (a b) = 2 max a i + b i -R, 0 = 2f a i + b i ≤ f 2 a i + f 2 b i = F (
We now have all the tools to prove Lemma 19. Let L ∩ = L ∩ merge(L) be the lists common to L and merge(L). Observe that the order lists are inserted by the algorithm does not matter, hence we are free to assume lists in L ∩ are inserted first.

Let a ∈ N mµ denote an arbitrary load vector obtained after inserting the lists in L ∩ . Recall that lists in L ∩ are multiples of 2µ, so the load vector after inserting the lists is 2µ-flat. If follows that a may be written in the form a = a a for some a ∈ N mµ/2 . Let us denote by E a the event that the outcome of inserting L ∩ is equal to a.

We want to prove E [F (L)] ≤ E [F (merge(L))] + negl(λ). By Lemma 13, it suffices to prove the inequality when conditioning on E a , for every possible a.

Given E a , all that remains to do to compute D(L) is to insert N µ lists of length µ. In consequence, we have that D(L) conditioned on E a is equal to a + B Nµ,mµ . The lemma can then be established as follows.

In the computation, we multiply the output of over by µ, to reflect the fact that each ball in N mµ represents a list of µ items. If we start from an arbitrary L, by applying Lemma 19 and computing merge(L) as in the statement of the lemma, we strictly increase the minimum size of the list. Eventually, all lists have size N/ log d N , while the total number of items remains O(N ) (Lemma 18). Hence, the analysis from Part 1 applies, and we are done.

F Applications of L2C

As mentioned in the introduction, the two-choice process is a staple in the resource allocation literature, with applications that range from job allocation to circuit routing. A survey may be found in [RMS01], which also presents some of the underlying analytical techniques. To further illustrate the range of applications, Azar, Broder, Karlin, Mitzenmacher and Upfal have recently received the 2020 ACM Paris Kenallakis Theory and Practice Award for the discovery and analysis of the two-choice process, highlighting in particular its "extensive applications to practice" [ABK + 20]. An overview of the two-choice process was given in Section 2. In this section, we explain how our result on L2C fits within that broader context, beyond cryptographic applications.

Let us first recall the two-choice allocation process itself. Suppose that n balls are inserted into n bins as follows: for each ball in succession, two bins are sampled uniformly at random among all bins. The ball is then inserted into whichever bin currently contains fewer items. The central analytical result regarding this process as that, once all balls have been inserted, the most loaded bin contains O (log log n) items with high probability.

Since typical applications include job allocation or memory management, it is natural to consider the weighted case, where each ball i is assigned some weight w i ∈ R (or w i ∈ N). The weighted variant of the two-choice process inserts each ball into whichever of two uniformly random bins currently contains the least weight in total (rather than the least number of balls, in the unweighted case). One would hope that, for instance, if the weights lie in the real interval [0, 1], then the load of the most loaded bin is O (log log W ), where W = w i is the total weight of the balls.

At STOC 2007, Talwar and Wieder analyzed the weighted two-choice process. They showed that when the weights of the balls are drawn independently from a fixed distribution of expectation 1, with some mild smoothness assumptions, the load of the most loaded bin is indeed O (log log n) (which is also O (log log W ), if W is defined to be the expectation of the total weight). In fact, they show a much stronger result that the gap between the expected load of each bin and the load of the most loaded bin is bounded by O (log log m) with high probability, even when inserting an unbounded number of balls m n into n bins, inspired by a seminal paper by Berenbrink et al. showing the same result in the unweighted case [BCSV06]. A simpler proof of a variant of the result was later given in [TW14], again assuminig weights drawn independently from a suitable distribution. To our knowledge, all existing analyses of the weighted two-choice process rely on a distributional assumption of that form15 .

It seems quite natural to want to consider the case that there is no distributional assumption: the sequence of ball weights is instead an arbitrary sequence, subject only to an upper bound on the weight of an individual ball. Indeed, in many cases, the weights of the balls (coresponding e.g. to the cost of a job in a job allocation application, or the size of an object in a memory management application) may be determined by a client, and need not be drawn from a consistent distribution, and may not be independent of each other. To our knowledge, a distribution-free result of that form has only been shown for the one-choice process (which has a O (log) overhead, rather than O (log log)) by Berenbrink et al. [BFHM08], but the same article argues that their analysis technique cannot extend to the two-choice process.

In that context, our result on L2C (Theorem 1) shows that such a distributionfree result holds for the two-choice process, at the cost of slightly tweaking the process. In a nutshell, in L2C, instead of allocating a given ball to whichever of two uniformly sampled bins currently contains the lowest weight in total, we allocate the ball to whichever of the two bins currently contains the fewest balls within the same weight range, where weight ranges are defined by partitioning the set of possible weights into O (log log n) sub-intervals. While this slightly alters the process, the computation determining which of the two bins to choose remains trivial. On the other hand, it allows for a distribution-free upper bound on the load of the most loaded bin.

A notable feature of L2C is that it is built essentially by superposing O (log log n) instances of a standard unweighted two-choice process. This makes it possible to reduce its analysis to results on the unweighted process. Although we only use this to show a simple upper bound on the most loaded bin, we conjecture that many deeper results known about the unweighted process (e.g. the "memoryless" properties from [BCSV06]), could be shown to extend to the weighted case for L2C in a similar manner.

We conjecture that a result of the same form as Theorem 1 would also hold for the standard weighted two-choice process considered in prior literature. However, such a result has remained elusive so far (some obstacles related to that question are discussed in [BFHM08]). We view this question as a compelling open problem. Let πj be a new pseudorandom permutation for j ∈ [1, i] 5:

Set cntj ← 0 for j ∈ [2, i] 6:

Server updates Ai with the result of OblSort(πi, ni, n 1/c log 2 n; Ri)

7:

Empty A1 and Tj, such as Aj and Rj on the server, for j ∈ [2, i -1] 8: Store updated client state 9: send reencrypted (A enc 1 , {T enc i } c-1 i=2 ) to server Server:

1: Update the encrypted memory EM accordingly

  a scheme with O (1) storage efficiency, O (1) locality, and O (log N ) read efficiency, where N is the size of the database [ANSS16]. At Crypto 2018, Demertzis et al. improved the read efficiency to O log 2/3+ε N [DPP18]

  [a, b] R the interval {x ∈ R | a ≤ x ≤ b} and extend this naturally to intervals of the form [a, b) R , (a, b] R , (a, b) R .

4 :

 4 Update the weight of b old to wnew directly 5: else 6: Mark b old as residual ball (it is still considered as a ball of weight w old ) 7: InsertBall(b old , wnew, Bα 1 , Bα 2 ) L2C.UpdateBall receives old ball (w, L), identifiers L and bins (B α1 , B α2 ), and updates ball (w, L) to ball (w, L ∪ L ) as before, while merging both identifier lists L and L . (The weight of the updated ball is |L ∪

  Efficiency. LayeredSSE has constant storage efficiency, as the server stores m = (N/p)/(log log log λ • log log N p ) bins of O p log log log λ • log log N p identifiers each. There is no client stash required. Each search and update query, the server looks up 2 bins, and thus LayeredSSE has O (log log(N/p)) page efficiency. Note that LayeredSSE has O (1) locality if only lists up to size p are inserted.

  ← clip ∪ (w, , C) 16: Let B Enc [i] = EncK (Bi) for each i 17: return EDB = (T, (B Enc [i])), clip ClipOSSE.Search(K, w, st; EDB) Client: (search token)

  B = EncK (B) Server: 1: B Enc [i] ← B Client: 2: return clip 6.4 The Generic Local Transform The Generic Local Transform takes as input a page-length-hiding page-efficient SSE scheme PE-SSE. It outputs a local SSE scheme Local[PE-SSE].

  -L2C.InsertBall((w, L), B α1 , B α2 ): Insert ball (w, L) into either bin B α1 or bin B α2 as in Algorithm 1. -L2C.Update((w, L), L , B α1 , B α2 ): Update the weight of ball (w, L) to weight |L ∪ L |/p as in Algorithm 1 and add identifiers L to list L. One of the bins now contains the ball (w, L ∪ L ). If the new weight lies in a different subinterval, one bin contains a residual ball (w, L) that we consider to not match w anymore.

  Global parameters: constant c ∈ N, page size p LayeredSSE.KeyGen(1 λ )1: Sample K Enc for Enc with input 1 λ 2: return K = K Enc LayeredSSE.Setup(K, N, DB) 1: Set τ ← p • clog log log(λ) log log(N/p) 2: Sample bins B1, ..., Bm via L2C.Setup with input ({(wi, DB(wi))} W i=1 , N/p) 3: Fill B1, ..., Bm up to size τ with zeros 4: Set B enc i ← Enc K Enc (Bi) for i ∈ [1, m] 5: return EDB = (B enc 1 , ..., B enc m ) LayeredSSE.Search(K, w; EDB) Client:

  ) If ∈ [1, N 1-1 log log N ), the client retrieves the identifiers from the server via Local[LayeredSSE].Search(K 1 , w; EDB 1 ). (2) If ∈ [N 1-1 log log N , N/ log d N ), the client runs Local[OramTethys].Search(K 2 , w; EDB 2 ) with the server. (3) If ∈ [N/ log d N, N/ log ε N ), the server sets i ∈ [0, d • ε -1 ] such that ∈ S i .Then, server and client run OramTethys.Search(K 3 , w; EDB 3,i ).(4) Otherwise, we have ≥ N/ log ε N and the server sends the entire encrypted database EDB 4 to the client (from which he fetches the corresponding list). Theorem 8 (UncondSSE). The scheme UncondSSE is correct and L len-rev -adaptively secure. It has constant client storage, O (1) locality and O (log ε N ) read efficiency for any ε > 0. Proof. Security (and correctness) directly follow from the security of Local[LayeredSSE], Local[OramTethys] and OramTethys. The efficiency properties of UncondSSE can

  Let a = (a i ) i≤t and b = (b i ) i≤t be two vectors in N t . Then a b denotes the following vector in N 2t :a b = (a 1 , b 1 , a 2 , b 2 , ..., a t , b t ).The notation is extended in the usual way to combine two sets of vectors (A B = {a b : a ∈ A, b ∈ B}), and two distributions of vectors (D 1 D 2 = a b where a ← D 1 , b ← D 2 }). The point of is the next lemma, which is essentially a convexity argument. Lemma 14. Let a = (a i ) i≤t and b = (b i ) i≤t be two vectors in N t . We have: 2F (a b) ≤ F (a a) + F (b b).

  a a) + F (b b). Given a load vector b ∈ N m , let n 0 (b) = i:i mod 2=0 b i (resp. n 1 (b) = i:i mod 2=1 b i ) be the total number of balls in bins with even (resp. odd) index. Let n(b) = n 0 (b)+n 1 (b) be the total number of balls. Let δ(b) = max(n 0 (b), n 1 (b))n(b)/2 .Recall that B n,m [δ = 0] denotes the distribution B n,m conditioned on the event δ = 0, that is, the bins with even indices contain the same total number of balls as the bins with odd indices. The proof of the following lemma is immediate. Let µ = min L. Assume N µ is even. If µ < N/ log 2 N , then:E [F (L)] ≤ E [F (merge(L))] + negl(λ) .

E

  [F (L) : E a ] = E [max(µ • over(D(L) -R, 0) : E a ] = E [max(µ • over(a + X -R, 0)] where X ← B Nµ,mµ ≤ E [max(µ • over(a + X -R, 0)] + N negl(λ)where X ← B Nµ,mµ,φ(µ) by Lemma 1614 .≤ E [max(µ • over(a + Y -R, 0)] + negl(λ) where Y ← B Nµ+2φ(µ),mµ [δ = 0] by Lemma 17 = E max(µ • over(a + Y 1 Y 2 ) -R, 0) + negl(λ)where Y 1 , Y 2 ← B (Nµ+2φ(µ))/2,mµ/2 by Lemma 15≤ E max(µ • over(a + Y 1 Y 1 ) -R, 0) /2 + E max(µ • over(a + Y 2 Y 2 ) -R, 0) /2 + negl(λ)by Lemma 14= E max(µ • over(a + Y 1 Y 1 ) -R, 0) + negl(λ) = E max(µ • over((a + Y 1 ) (a + Y 1 )) -R, 0) + negl(λ) = E max(2µ • over(a + Y 1 ) -R, 0) + negl(λ)= E [F (merge(L)) : E a ] + negl(λ) .

Algorithm 7 1 :

 71 Local Oblivious RAM (LocORAM) LocORAM.Initialize ORAM (1 λ , M) 1: Parse M as {i, vi} n i=1 , where |i, vi| = β 2: Let n1 = n Let Ai be an empty array of size ni fori ∈ [1, c] 4: Let πi : [1, ni] → [1, ni] be pseudorandom permutation for i ∈ [2, c] 5: for all i ∈ [1, n] do 6: Store (i, vi) at locations πc[i] in Ac 7: Encrypt A enc i ← Enc K Enc (Ai) for i ∈ [1, c] 8: Let Ri be an empty set (of maximal size n i/c blocks for i ∈ [2, c -1]) and Rc = M 9: Set cnti ← 0 for i ∈ [2, c] 10: Let Ti be an empty hash table of size n for i ∈ [2, c -1] 11: Encrypt R enc i ← Enc K Enc (Ri) and T enc i ← Enc K Enc (Ti) for i ∈ [2, c -1] 12: Set st = ({πi} c i=2 , {cnti} c i=2 , K Enc ) 13: Set EM = ({A enc i } c i=1 , {R enc i } c-1 i=2 , {T enc i } c-1 i=2 ) 14: return st, EM LocORAM.Access ORAM (st, k; EM) Client: 1: Retreive (A enc 1 , {T enc i } c-1 i=2) from the server and decrypt to (A1,{Ti} c-1 i=2 ) 2: Set fnd ← f alse and cnti ← cnti + 1 for i ∈ [2, c] 3: if (k, v k ) ∈ A1 then 4: fnd ← true 5: for all i ∈ [2, c -1] do 6: if fnd or Ti[k] = 0 then 7: indexi ← πi(n i/c + cnti) K Enc (cnti+1, v k ) 13: if fnd then 14: indexc ← πc[n + cntc] 15: else 16: indexc ← πc[k] 17: A1[cnt2] ← (k, v k ) 18: send {indexi} c i=2 and {ri} c-1 i=2Server:1: Set Ri ← Ri ∪ ri for i ∈ [2, c -1] 2: send {A enc i [indexi]} c i=2Client: Retreive block (k, v k ) from either A1 or (decrypted) Ai[indexi] for some i ∈ [2, c] 2: Choose i ∈ (c, ..., 2) maximal such that cnti > n

  the end, ClipOSSE achieves storage efficiency O (1), locality O (1), and read efficiency O (log log N ), with O N/ log d N overflowing elements (for any fixed constant d of our choice), under the condition that the maximum list size is O (N/polylog N ). All applications of the Generic Local Transform in this article use ClipOSSE as the underlying OSSE. (That is why we write Local[PE-SSE] for the Generic Local Transform applied to the page-efficient scheme PE-SSE, and do not put the underlying OSSE as an explicit parameter.)

	2.4 Dynamic Local SSE with O (log log N ) Overhead
	By using the Generic Local Transform with ClipOSSE as the underlying OSSE,
	and LayeredSSE as the page-efficient scheme, we obtain Local[LayeredSSE]. The
	Local[LayeredSSE] scheme has storage efficiency O (1), locality O (1), and read
	efficiency O (log log N ). This result follows from the main theorem regarding the
	Generic Local Transform, and does not require any new analysis.

  The client receives as input the secret key K, keyword w and state st. The server receives as input the encrypted database EDB. Outputs some data d and updated state st for the client. Outputs updated encrypted database EDB for the server.-Σ.Update(K, (w, L), op, st; EDB): The client receives as input the secret key K, a pair (w, L) of keyword w and list L of identifiers, an operation op ∈ {del, add} and state st. The server receives as input the encrypted database EDB. Outputs updated state st for the client. Outputs updated encrypted database EDB for the server.

	Outputs encrypted database
	EDB and client state st.
	-Σ.Search(K, w, st; EDB):

  lists in DB 1 are sufficiently small for LayeredSSE and thus, we can apply the local transformation and run EDB 1 ← Local[LayeredSSE].Setup(K 1 , N, DB 1 ). Note that we still pad the encrypted database to size O (N ) and not O (|DB 1 |) because we can not reveal the distribution of lists amongst each subinterval. The lists in DB 2 are sufficiently large for OramTethys. Consequently, we can set EDB 2 ← Local[OramTethys].Setup(K 2 , N, DB 2 ). For DB 3 , we further split the interval [N/ log d N, N/ log ε N ] into the constant number of subintervals

-

  Let B(p) denote the Bernoulli distribution with mean p: that is, a sample ofB(p) is a 0-1 random variable X such that Pr [X = 1] = p and Pr [X = 0] = 1 -p. -LetBin(p, n) denote the Binomial distribution with n trials, each with probability p: that is, a sample of Bin(p, n) is distributed like i≤n X i , where the X i 's are i.i.d. sampled from B(p). -Suppose we throw n balls i.u.r. into m buckets. Let B n,m [i] be the (random variable denoting the) load of the i-th bucket. Let B If D is a distribution, and E is an event, then D[E] denotes the distribution D conditioned on the event E.-If X is a random variable, and E is an event, then E [X : E] denotes the conditional expectation of X, conditioned on the event E. -If D is a distribution, X 1 , ..., X n ← D denotes that X 1 , ..., X n are i.i.d. random variables, each distributed according to D.

n,m = (B n,m [i]) i ≤m be the vector of the load of buckets. Observe that B n,m [i] is distributed according to Bin(1/m, n). Also note that the B n,m [i]'s are not independent, e.g. they are linked by B n,m [i] = n. -

Note that we allow for inserting more than one identifier per keyword in a single update operation in this work. Thus, the server will also learn (limited) information about the number |L| of added or deleted identifiers.

This condition is needed for the requirement m ≥ λ 1/ log log λ of L2C which guarantees negligible failure probability (see Theorem 1). In practice, we have p N .

For arbitrary lists sizes, we can split lists into sublists of size at most p and deal with each sublist separately as before. Some care has to be taken, for example with the random choices of the bins, but details are mostly straightforward.

This is equivalent to page length hiding leakage L len-hid , as we only restrict ourselves to lists of size at most p.

The same table exists in ClipOSSE. In an actual implementation, they would be the same table, but using ClipOSSE in black box eases the presentation.

This is equivalent to page length hiding leakage L len-hid , as we only restrict ourselves to lists of size at most p.

For updates with more than p identifiers, the client can perform multiple updates.

The version of LayeredSSE with 1 RTT updates requires a stash of size O (p log log(N/p)) to temporarily store the second flow of the update query until the next query.

Downloading all encrypted Ti incurs a bandwith of O(n (c-1)/c • log(n)). As we require β = Ω(n (c-1)/c ) this cost vanishes in the total access bandwith.

Without loss of generality, we can assume that there are at most p identifiers per keyword in the stash. For this, we can keep full lists inside a table T full such as in LayeredSSE. This version of Tethys was already described in [BBF+ 21] (see their scheme Pluto). Note further that the binpacking algorithm Binpack packs a list of identifiers into at most two consecutive bins. Thus, knowledge of i sufficies to fetch bin i and i + 1. We assume in the following that the list of identifiers is in at most one bin for simplicity.

[BFHM08] requires that x majorizes x . This is implied by our condition on x and x .

[BFHM08] shows that E[X mlb ] ≥ E[X mlb ]. As f (X) = max(X -R, 0) is convex, their proof can be adapted to our formulization.

The fact that the condition d = Ω( √ n log λ) from Lemma 16 is satisfied follows from Lemma 18.

A partial exception may exist: the result on the so-called (1 + β)-choice process studied in [PTW10] is written in the same distributional form, but upon closer inspection, it appears that the core potential function argument could be written without the need of a distributional assumption, as long as the weights are bounded. However, as noted also in [TW14], this technique can only prove a logarithmic bound, rather than the O (log log) bound we are hoping for, so it is insufficient for our purpose.

Acknowledgments

The authors would like to thank Raphael Bost for his helpful comments. This work was supported by the ANR JCJC project SaFED.

also be derived from the efficiency properties of the used SSE schemes (see discussion above).

Remark 2 (On RTT and Deamortization). The scheme UncondSSE uses LocORAM and thus, the efficiency properties are amortized. Also, this introduces a large round trip time for some operations. We note that if LocORAM is deamortized, we can adapt UncondSSE in order to have a constant RTT and deamortized efficiency.

C Analysis of L2C

Here, we proof Theorem 1. First, we introduce some additional preliminaries.

Lemma 4 (Chernoff 's Bound). Suppose that X 1 , ..., X n are independent random variables taking values in {0, 1}. Let X denote their sum and let µ = E[X] denote the expectancy of X. Then for any δ > 0, it holds that

In the next lemma, we consider a sequence of ball insertions and deletions of arbitrary length, such that the total number of balls in the bins at any point in time is bounded by n = h • m. A ball insertion is a standard 2-choice insertion: pick two bins i.u.r., and insert the ball into the least loaded bin. A deletion removes one previously inserted ball. The sequence of additions and deletions is fixed at the input of the problem.

Lemma 5 (2C). Let δ(m) be an arbitrary map such that 1 ≤ δ(m) ≤ log m for all m ≥ 1. At the outcome of the sequence of additions and deletions, the most loaded bin contains O(h + δ(m) log log m) items, except with probability m -Ω(δ(m) log log m) .

In particular, by setting δ = 1, we get that if m ≥ λ, then the failure probability from the claim is negligible. By setting δ = log log log m, we get that if m ≥ λ 1/ log log λ , then the failure probability from the claim is negligible.

Proof. We adapt the proof of [Vöc03], which proves a bound O(h) + log log m with probability m -α , for an arbitrary constant α. The proof uses witness trees. The existence of a bin containing more than Ch + L items implies the existence of a witness tree of height L + C , for some suitable constants C, C . Thus, in order to bound the probability that a bin contains more than Ch + L items, it suffices to bound the probability that a witness tree of height L + C exists. In more detail, the proof shows that the probability that a witness tree of height L + 3 exists is upper-bounded by

where κ, α are certain parameters (to be discussed later), with:

In words, for 1C, the load above threshold R of the most loaded bin is higher with balls of weight x than with balls of weight x .

We are now ready to prove Theorem 1.

Proof. Note that the load of a bin is never decreasing, so it is sufficient to analyze the final load of bins B 1 , ..., B m . Also, note that we can replace Setup with n InsertBall operations. Thus, we can assume without loss of generality that bins B 1 , ...B m are initially empty after L2C.Setup. Also, note that m -Ω(δ(λ) log log w) = negl (λ) under the given requirements (see lemma 5). As H is modeled as a random oralce, we assume that the bin choices α 1 , α 2 of ball b are chosen independently and uniformly at random from [1, m] 2 . We split the proof into three parts:

(1) First, we will modify the sequence S such that we can reduce the analysis to only (sufficiently independent) L2C.InsertBall operations, while only increasing the final bin load by a constant factor.

(2) Second, we analyze the maximal bin load when only considering balls of weight at most 1/ log m. Here, L2C.InsertBall proceeds exactly as weighted 1C. Since uniform weights of value 1/ log m are the worst case for the most loaded bin in 1C, the bound follows from a Chernoff's bound as balls are sufficiently small.

(3) Last, we inspect the maximal bin load considering items in the remaining subintervalls (2 i-1 / log m, 2 i / log m] R for i ∈ {1, ..., log log m}. Per interval, L2C.InsertBall behaves like unweighted two-choice (independent of other subintervals) and inherits the log log m bin load direclty, as balls with different weights differ only by a constant factor per interval. Summing up the maximal bin load per interval will yield the desired result.

Part 1 -Adapting the sequence: We observe that update operations updating the weight inside the same subinterval can be ignored. More concretely, let op i = UpdateBall be some update operation on ball b i with old weight o i and new weight w i . If o i , w i ∈ ( 2 k-1 log m , 2 k log m ] R for some k, the operation op i replaces the old weight o i of ball b i with the new weight w i direclty (inside the same bin). Thus, we can simply remove op i and replace the previous operation op j = (b i , o j , o i ) = (b j , o j , w j ) on the same ball with op j = (b i , o j , w i ) directly. Clearly this does not change the final load of the bins. (Note that operations between op j and op i make the same choices as the concrete weight inside a subinterval never impacts which bin is chosen.) Now, let (op i ) i∈I be all remaining update operations for some fixed ball b * , so b * = b i and op i = UpdateBall for i ∈ I. As we removed consecutive update operations in the same subinterval, operation op i marks the ball b * as residual ball and calls InsertBall(b * , w i , B α * ,1 , B α * ,2 ). Let j = max(I) be the index of the last update operation op j on b * and k be minimal such that w j ≤ 2 k / log m. As there are only k subintervals below the last interval (2 k-1 / log m, 2 k / log(m)] R , there are at most k such update operations, i.e. |I| ≤ k, and one insert ball operation. Assume without loss of generality that all k + 1 operations exist. The residual ball left by the i-th update operation has at most size 2 i-1 / log m and thus, this UpdateBall Lemma 15. For all even n, m:

Lemma 16. If d = Ω( √ n log λ), then the statistical distance between B n,m and B n,m,d is negligible.

Proof. By a simple Chernoff bound, the probability that the condition that defines B n,m,d is not satisfied in B n,m is negligible. Further, if two distributions are identical conditioned on an event with negligible probability not happening, then their statistical distance is negligible.

Given two distributions D 1 , D 2 on a set equipped with an order relation , recall that D 1 is said to be stochastically dominated by D 2 if there exists a coupling (X 1 , X 2 ) of D 1 and D 2 (i.e. a random variable (X 1 , X 2 ) such that the marginal distribution of

Lemma 17. For all n, m, d, B n,m,d is stochastically dominated by B n+2d,m [δ = 0] (with respect to the product order on N m ).

Proof. If we sample from B n,m,d , then add n/2 + 2d -n 0 (resp. n/2 + 2d -n 1 ) balls uniformly at random into buckets of even (resp. odd) indices, we obtain a sample from B n+d,m [δ = 0]. Hence, there exists a suitable coupling of the two distributions.

Let φ( ) = N/ log λ. If L is a multiset of list sizes, let µ = min L. Define merge(L) by removing all N µ instances of µ from L, and adding instead N µ /2 + φ(µ) instances of size 2µ.

Let N 1 = N 1 + √ N log λ. By induction, for i in {1, ..., log N } and = 2 i , define:

Lemma 18. For all ≤ N/ log 2 λ, N = O(N/ ).

Proof. A straightforward induction gives: