**Definition 7 (Correctness).** A wORAM scheme is said to be *correct* if, given a legal setup and any sequence of legal access operations, a read access at address **a** outputs the data last written to address **a**, except with negligible probability.

**Definition 8 (Security).** A wORAM scheme is said to be *secure* if, given any two legal sequences of operations of the same length ($\text{Setup}(N, B, D)$, $\text{Access}(\text{op}_1, \mathbf{a}_1, \mathbf{data}_1)$, ..., $\text{Access}(\text{op}_k, \mathbf{a}_k, \mathbf{data}_k)$) and ($\text{Setup}(N, B, D')$, $\text{Access}(\text{op}'_1, \mathbf{a}'_1, \mathbf{data}'_1)$, ..., $\text{Access}(\text{op}'_k, \mathbf{a}'_k, \mathbf{data}'_k)$), the views of the server arising from each sequence are computationally indistinguishable.

A few remarks are in order. First, although we have defined **Setup** and **Access** as general client-server protocols, it is common in ORAM to require that the server behave like a passive memory, allowing only read and write accesses. That is, the client only ever asks the server to read or write specific data at a specific address. The server performs no computation of its own. Although this is not required in the previous definition, the wORAM schemes in this work are in that model.

Second, it is assumed that the contents of all memory locations on the server are encrypted using IND-CCA encryption, with a key known only to the client. Whenever the client accesses a memory location, they can reencrypt the data at that location, so that the server cannot learn the contents of any memory location, or whether it was changed during the access. As a result, the only way the server can infer information is by observing which locations the client queries in server memory. That is why the security definition of wORAM (following that of ORAM) focuses only on memory locations.

Finally, note that standard ORAM is the special case of wORAM where all addresses store data of the same size $B$. If the total amount of data is $N$, then such a scheme contains $n = N/B$ blocks. Throughout this chapter, the letter $N$ is reserved for the total amount of data. In the case of standard ORAM, the letter $n$ is used for the number of blocks, with $n = N/B$.

### 4.3.2 Tree ORAM

We build wORAM by altering standard ORAM schemes following the *Tree ORAM* paradigm. In this section, we provide a high-level algorithmic view of that paradigm. That view is purposefully designed to accomodate several existing Tree ORAM schemes. It will also lay the groundwork for the construction of wORAM in the next section.

Existing Tree ORAM schemes are standard ORAMs, designed to store items of fixed size. In a Tree ORAM, to store $n$ items of size $B$, the server creates a full binary tree with $n$ leaves. (From now on, we assume $n$ is a power of 2, increasing to the next power of 2 if necessary.) Throughout the chapter, the root of the tree is viewed as being at the top, and leaves as being at the bottom of the tree. Given a leaf $l$ of the tree, the path from the root to the leaf $l$ is denoted by $\mathcal{P}(l)$.

Each node of the tree, also called a *bucket*, can store up to $Z$ data blocks of size $B$. Nodes are always padded to be of size $ZB$ before being stored (encrypted) on the server.

In addition to the tree, the server may also store a *stash*, which may contain additional data blocks that could not fit in the tree. In the remainder, we view the stash as a special node directly above the root. This is relevant in two situations. First, there may be cases where a node is full (i.e it contains $Z$ items), and where additional items need to be pushed to the parent node; if this happens at the root level, overflowing items are pushed to the stash. Second, whenever we consider the path $\mathcal{P}(l)$ from some leaf $l$ to the root in the tree, we implicitly (and slightly abusively) also consider the stash to be part
of the path. The stash is always padded to some upper bound $R$, before being stored (encrypted) on the server.

To each item with address $a$ is associated a leaf of the tree $\text{pos}(a)$. The array mapping each address $a$ to the corresponding leaf $\text{pos}(a)$ is called a *position map*. For now, we will assume the position map is stored by the client. By design, Tree ORAMs maintain the following invariant at all times: the item at address $a$ is stored in one of the nodes on the path $\mathcal{P}(\text{pos}(a))$ from the root to the leaf $\text{pos}(a)$ (including the stash, as noted earlier).

During setup, each item with address $a$ is stored in the leaf $\text{pos}(a)$; or if it is full, in the lowest parent of $\text{pos}(a)$ that is not yet full. To access item $a$, the client retrieves $\text{pos}(a)$ from the position map, then reads the path $\mathcal{P}(\text{pos}(a))$ on the server. Thanks to the invariant, that path contains the item $a$. Item $a$ is then assigned a new uniformly random leaf. Finally, a special *eviction* procedure is called, which re-inserts item $a$ somewhere on the path to its newly assigned leaf, and may also move other items.

Pseudo-code for the Access procedure is given in Algorithm 1, with additional parameters $Z$ (the number of blocks per bucket, specified by the Tree ORAM scheme; to reflect the fact that $Z$ is an internal parameter of the ORAM construction, and not part of its interface, it is written between brackets), and random coins $r$. It makes use of the following subroutines:

* `ReadBucket bucket)` retrieves a set of pairs $(a_i, \text{data}_i)$ from the tree node `bucket`.

* `RemoveBlock bucket, a)` removes the item with address $a$ from the tree node `bucket`.

* `ChooseEvictionPath` outputs a path for eviction, which differs depending on the specific Tree ORAM scheme.

<caption>**Algorithm 1** Access algorithm of a Tree-ORAM.</caption>

Access[$Z$; $r$](op, $a$, newdata):
1: leaf $\leftarrow \text{pos}[a]$
2: $\text{pos}[a] \leftarrow$ uniformly random leaf
3: **for** bucket in $\mathcal{P}(\text{leaf})$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** ($a, \text{data}) \in \text{ReadBucket}(\text{bucket})$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;RemoveBlock($\text{bucket}, a$)
6: &nbsp;&nbsp;&nbsp;&nbsp;**if** op = write **then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;data = newdata
8: &nbsp;&nbsp;&nbsp;&nbsp;stash $\leftarrow$ stash $\cup$ $\{(a, \text{data})\}$
9: &nbsp;&nbsp;&nbsp;&nbsp;path $\leftarrow$ ChooseEvictionPath(leaf)
10: Evict[$Z$; $r$]($\text{path}$)
11: **return** data

Pseudo-code for the Evict procedure is given in Algorithm 2, with additional parameters $Z$ (the number of blocks per bucket, specified by the Tree ORAM scheme), and random coins $r$. It makes use of the following subroutines:

* `Size($X$)` returns the number of items $|X|$ in $X$.

* `ChooseNextBlock(stash, bucket, path)` pops an item from the stash, to be stored in the bucket, or outputs $\perp$.
**Algorithm 2** Generic eviction algorithm.

Evict[Z; r](path):

1: Move all blocks in *path* to the stash

2: for *bucket* in *path* do

3: $X \leftarrow \emptyset$

4: while Size($X$) < $Z$ do

5: block $\leftarrow$ ChooseNextBlock(stash, *bucket*, *path*)

6: if *block* = $\perp$ then

7: break

8: else

9: $X \leftarrow X \cup \{\text{block}\}$

10: WriteBucket(*bucket*, $X$, $Z$)

11: return

* WriteBucket(*bucket*, $X$, $Z$) writes the items in $X$ to the node *bucket*, padding the node to size $Z$ if needed.

We will discuss in Section 4.5 how several existing Tree ORAM schemes are captured by the above paradigm.

### Correctness of Tree ORAM

Since Tree ORAM is a special case of ORAM, the correctness definition remains the same (Definition 7). However, because of the specificities of Tree ORAM, it can be reformulated in a more convenient manner. That is, the only correctness failure that can occur in a Tree ORAM scheme is that the stash overflows. (The reader familiar with Tree ORAM may object that some Tree ORAM schemes do not use a stash; that case will be handled in Section 4.5.)

Recall that the stash is always padded to size $RB$, i.e. it can store up to $R$ items. Hence, correctness amounts to the following statement: at the outcome of any sequence of legal accesses (`Setup`, `Access`$_1$, ..., `Access$_k$`), it holds that

$$ \Pr[\text{Size}(\text{stash}) > R] = \text{negl}(\lambda). $$

### 4.3.3 The $\infty$-ORAM Model

Consider a Tree ORAM instantiation $\text{ORAM}^Z \leftarrow \text{Setup}[Z](N, B, D)$, with bucket capacity $Z$. If $s$ is a sequence of accesses, we call $\text{st}(\text{ORAM}^Z[s])$ the stash usage, that is, the number of items in the stash at the outcome of the accesses.

In Path ORAM and many Tree ORAM schemes derived from it, the proof of correctness follows similar steps:

* Consider an *infinite* ORAM structure $\text{ORAM}^\infty$, which is the same protocol, except buckets have infinite capacity (that is, $Z = \infty$).

* Define a post-processing algorithm $G_Z$ that moves items in the tree produced by running $\text{ORAM}^\infty$ (arranging in particular that each tree node contains at most $Z$ items). Denote the stash usage of the post-processed $\infty$-ORAM by $\text{st}^Z(\text{ORAM}^\infty[s])$.
• Prove that $st(\mathit{ORAM}^Z[\mathbf{s}]) = st^Z(\mathit{ORAM}^\infty[\mathbf{s}])$ when using the same random coins on both sides.

• Prove that $\Pr[st^Z(\mathit{ORAM}^\infty[\mathbf{s}]) > R] = \mathrm{negl}(N)$.

The last two points imply that $\Pr[st(\mathit{ORAM}^Z[\mathbf{s}]) > R] = \mathrm{negl}(N)$, i.e. the original ORAM scheme is correct. We say that such a protocol admits a *proof via infinite ORAM*.

## 4.4 Generic Construction of wORAM from Tree ORAM

Our goal is to give a generic way to transform an existing standard Tree ORAM design into one that supports blocks of variable size. The transformation presented in this section is perhaps the most natural transformation one could imagine for that purpose. The main challenge is not the transformation itself, but rather proving that it preserves correctness.

Still, there is one aspect of the transformation whose necessity may not be immediately apparent. Namely, if the original ORAM has bucket capacity $Z$, then its weighted version will have bucket capacity $Z + 1$. This change is not necessary for the main theorem of this section to hold. However, it will be necessary when applying the main theorem to specific ORAMs, notably Path ORAM: see the discussion at the end of Section 4.5.2. In practice, experiments in Section 4.4.4 suggest that this increase in bucket capacity can be heuristically dispensed with.

### 4.4.1 The Weighted Transform

We define a general transform *Weighted* that takes as input a standard Tree ORAM scheme $\mathit{ORAM}^Z = (\mathit{Setup}, \mathit{Access})$ following the framework of Section 4.3.2, and outputs a weighted ORAM scheme $\mathit{Weighted}(\mathit{ORAM}^Z) = \mathit{ORAM}^{*Z} = (\mathit{Setup}^*, \mathit{Access}^*)$.

Let us first consider the setup. We say that the starting scheme $\mathit{ORAM}^Z$ has a *regular* setup if its setup procedure is equivalent to creating an empty tree with all items in the stash, then doing repeated evictions towards every leaf in the tree from left to right. Here, by “equivalent” we mean that the output of this process and the output of the normal setup process are identically distributed. In our main theorem, we will require that the starting Tree ORAM $\mathit{ORAM}^Z$ has a regular setup. Although that notion of regularity is non-standard, it has the benefit that the behavior of the setup process can be deduced from that of the eviction process. For our purpose, this means it will be enough to explain how to transform the eviction process to handle blocks of variable size.

$\mathit{ORAM}^{*Z}$ is defined in the following way, making only minimal modifications to $\mathit{ORAM}^Z$ to handle items of variable size.

• $\mathit{Setup}^*(N, B, D)$ initializes a tree with $N$ leaves, whose nodes can each hold data of size $(Z+1)B$, and a stash of the same size $RB$ as the standard instance $\mathit{ORAM}^Z$. It initializes a position map where each address $a$ in $D$ is mapped to a uniformly random leaf. Finally, it performs a *regular* setup: that is, all items in $D$ are placed in the stash, and the $\mathit{Evict}^*$ procedure is called on the path from the root to each leaf, from left to right.

• $\mathit{Access}^*$ is identical to $\mathit{Access}$, except that it calls the modified subroutine $\mathit{Evict}^*$.

• $\mathit{Evict}^*$ is identical to $\mathit{Evict}$, except that it calls the modified subroutines $\mathit{Size}^*$ and $\mathit{WriteBucket}^*$.
• $Size^*(X)$ returns the sum of the sizes of all items in $X$ divided by $B$, instead of the number of items in $X$.

• $WriteBucket^*(bucket, X, Z)$ still writes the items in $X$ to node *bucket*, the only difference is that it pads the bucket to size $Z+1$ instead of $Z$.

### 4.4.2 Suitable Tree ORAM Schemes

For the Weighted transform to preserve correctness, the original standard ORAM scheme must satisfy certain conditions. This section serves to define those conditions.

Given a sequence of accesses $s$, some fixed random coins $r$ used during those accesses, and a subset $S$ of nodes in an $\infty$-ORAM scheme ORAM$^*$, define the usage of $S$, written $u^S(\text{ORAM}^{*\infty}[s; r])$, to be the total number of items assigned to the nodes in $S$. For a wORAM scheme, the usage of $S$ is defined to be the total size of the items assigned to nodes in $S$, divided by the block size $B$.

As discussed in Section 4.3.2, a correctness failure for a Tree ORAM scheme ORAM occurs if and only if, at the outcome of a series of accesses $s$ with random coins $r$, the stash receives strictly more than $R$ elements. Using the notation from Section 4.3.3, this translates to $st(\text{ORAM}^Z[s; r]) > R$. We say that a subset $S$ of nodes witnesses the failure if, in the corresponding $\infty$-ORAM scheme ORAM$^*$ when performing the same sequence of accesses using the same random coins (viz. the choices of fresh uniformly random leaves for the position of each accessed item remain the same), $u^S(\text{ORAM}^{*\infty}[s; r]) > |S| \cdot Z + R$. Intuitively, since the nodes in $S$ can store at most $|S| \cdot Z$ items, it is clear that more than $R$ items must be reassigned to the stash in the original ORAM, which breaks correctness: that is why we say that $S$ witnesses the failure.

**Definition 9** ($F \Rightarrow W, W \Rightarrow F$). We say that ORAM satisfies the $F \Rightarrow W$ property (read: "failure implies witness") with respect to a set $\mathcal{S}$ of subset of nodes, iff for all access sequences $s$ and all choices of random coins $r$, $st(\text{ORAM}^Z[s; r]) > R$ implies $\exists S \in \mathcal{S}, u^S(\text{ORAM}^{*\infty}[s; r]) > |S| \cdot Z + R$. We say that ORAM satisfies the $W \Rightarrow F$ (read: "witness implies failure") property if the converse is true.

Moreover, we say that ORAM satisfies the $F \Rightarrow W$ (resp. $W \Rightarrow F$) property via union bound if the scheme also satisfies that $\sum_{S \in \mathcal{S}} \text{Pr}[u^S(\text{ORAM}^{*\infty}_L[s]) > |S| \cdot Z + R] = \text{negl}(\lambda)$. Informally, this means the statement "the probability that a failure witness exists is negligible" can be proved via a union bound over all possible witnesses $S \in \mathcal{S}$.

The definitions remain the same for a wORAM scheme. In particular, for a wORAM scheme ORAM$^*$, a subset $S$ witnesses a failure if $u^S(\text{ORAM}^{*\infty}_L[s]) > |S| \cdot Z + R$ (and not $|S| \cdot (Z+1) + R$, even though our construction of wORAM uses buckets of size $(Z+1)B$).

**Definition 10** (Suitable Tree ORAM). We say that a Tree ORAM scheme is *suitable* if it satisfies the following conditions.

1. It admits a proof via infinite ORAM. That is, for all access sequence $s$ and random coins $r$, $st(\text{ORAM}^Z[s; r]) > R$ iff $st^Z(\text{ORAM}^\infty[s; r]) > R$.

2. ORAM satisfies the $W \Rightarrow F$ property with respect to some set $\mathcal{S}$, via union bound.

3. $\text{Weighted}(\text{ORAM})$ satisfies the $F \Rightarrow W$ property with respect to the same $\mathcal{S}$.
4. ORAM allows *free evictions*. That is, if the client is allowed to trigger evictions on uniformly random leaves at will during a sequence of accesses, correctness still holds.

Requiring all those properties may seem demanding, but they naturally hold for several existing Tree ORAM schemes, including Path ORAM and Simple ORAM. This will be shown in more detail in Section 4.5. Intuitively, this is because many schemes admit a proof via infinite ORAM, either explicitly (in the case of Path ORAM), or trivially (in the case of Simple ORAM, where the ORAM and its infinite variant are identical up to correctness failures). Similarly, the $F \Rightarrow W$ property is either already known, or trivial; and the *free eviction* property is immediate. The only property that requires some care is to show that *Weighted(ORAM)* satisfies the $F \Rightarrow W$ property. However, it is much more tractable than trying to analyze the correctness of a wORAM scheme directly.

### 4.4.3 Main Result

**Theorem 4.4.1 (Main Theorem).** Let ORAM be any suitable Tree ORAM scheme. If ORAM is a correct ORAM scheme, then Weighted(ORAM) is a correct wORAM scheme.

Before diving into the proof proper, we sketch the underlying approach. Because of the $F \Rightarrow W$ and $W \Rightarrow F$ properties required by the suitability assumption, showing the wORAM scheme is correct essentially amounts to showing that no set $S \in \mathcal{S}$ witnesses a failure (except with negligible probability). We wish to analyze the function that maps the sizes of items to the usage of $S$ (i.e. the sum of sizes of all items in $S$). Ultimately, we want to show that the probability that the usage of $S$ exceeds $|S| \cdot Z + R$ is negligible, regardless of item sizes.

The proof strategy is to upper-bound the previous probability by a Schur-convex function (Section 4.2.1), and show that this function is negligible. The idea behind this strategy is that if a function of item sizes is Schur-convex, then in order to upper bound the function for all possible vectors of item sizes, it is enough to upper-bound it for a set of maximal vectors for the majorization order. Luckily, due to the requirement that item are of size at most $B$, and that the sum of items sizes is at most $NB$, a single weight vector majorizes all others, namely the vector $(B, \dots, B, 0, \dots, 0)$. Hence, it is enough to upper-bound the function for that specific vector. This is quite convenient, because that weight vector essentially amounts to having all items be of the same size, which reduces to the correctness of the original (unweighted) ORAM instance.

To instantiate the proof idea outlined above, the core argument is to show that there exists a suitable Schur-convex function. This is done via a first-moment argument (Lemma 4.4.2), which allows us to work with expectations instead of probabilities. Expectations are much better behaved with respect to convexity (due to the linearity of expectation). Eventually, we get the upper bound to metamorphosize into a suitable Schur-convex function (in the proof, this is the map $w \mapsto E[X_{s,L,S}(w)])$, and show it is convex essentially by showing that it is structured as a composition of convex maps. Using Lemma 4.2.1, we deduce that it is Schur-convex.

*Proof.* We start with a small self-contained lemma.

**Lemma 4.4.2.** Let $X$ be an integral random variable defined over $[0, t] \subset \mathbb{N}$, with $t \in \text{Poly}(\lambda)$. Then $\text{Pr}[X > R] = \text{negl}(\lambda)$ if and only if $E(\max(0, X - R)) = \text{negl}(\lambda)$.
*Proof.* Recall that the expectation of a positive integral variable $Y$ can be written as:

$$ \mathbb{E}(Y) = \sum_{i \ge 0} \Pr[X > i]. $$

As a corollary, for any integral variable $Y$ satisfying $0 \le Y \le t$:

$$ \Pr[Y > 0] \le \mathbb{E}(Y) \le t \Pr[Y > 0]. \quad (4.1) $$

Observe that the event $X > R$ is equivalent to $\max(0, X - R) > 0$. Using that observation, and applying (4.1) to the variable $Y = \max(0, X - R)$, we get:

$$ \Pr[X > R] \le \mathbb{E}(\max(0, X - R)) \le t \Pr[X > R]. $$

Since $t \in \mathrm{Poly}(\lambda)$, we are done. ■

<figure><img src="image_7.png" /></figure>

Let ORAM be a suitable and correct Tree ORAM scheme. Let $\mathrm{ORAM}^* \leftarrow \mathrm{Weighted}(\mathrm{ORAM})$. Let $\mathbf{s}$ be a legal sequence of accesses for $\mathrm{ORAM}^*$. We need to show that $\Pr[\mathrm{st}(\mathrm{ORAM}^*[\mathbf{s}]) > R] = \mathrm{negl}(\lambda)$.

Since ORAM satisfies the $F \Rightarrow W$ property with respect to some set $\mathcal{S}$, it suffices to show that the probability that there exists $S \in \mathcal{S}$ witnessing the failure is negligible, i.e. $\Pr[\exists S \in \mathcal{S}, u^S(\mathrm{ORAM}^{*\infty}_L[\mathbf{s}]) > |S| \cdot Z + R]$ is negligible.

Let us fix $S \in \mathcal{S}$. We want to show that $\Pr[u^S(\mathrm{ORAM}^{*\infty}_L[\mathbf{s}]) > |S| \cdot Z + R]$ is negligible. (This is not enough to imply that the probability that there exists such an $S$ is negligible, since $\mathcal{S}$ may have superpolynomial cardinality; we will come back to this point later.) A crucial observation is that in $\mathrm{ORAM}^{*\infty}_L$, the sizes of data items plays no role. In particular, given an access sequence $\mathbf{s}$ and associated random coins $r$, the location of each item in the tree is entirely determined *independently of the size of the data items*.

Given an access sequence $\mathbf{s}$ with $m$ items in total, and a size allocation vector $\mathbf{w} = (w_i)_{i \le m} \in [0, 1]^m$, define $\mathbf{s}(\mathbf{w})$ to be the access sequence $\mathbf{s}$, modified such that at the outcome of the sequence the $i$-th item has size $w_i$. Let $\Pi$ be the set of permutation matrices of size $m$. Let $X_{\mathbf{s},L,S}(\mathbf{w}) = \max_{\mathbf{P} \in \Pi}(\max(0, u^S(\mathrm{ORAM}^{*\infty}_L[\mathbf{s}(\mathbf{P}\mathbf{w})]) - (|S| \cdot Z + R)))$. By Lemma 4.4.2, $\mathbb{E}[X_{\mathbf{s},L,S}(\mathbf{w})]$ is an upper bound on $\Pr[u^S(\mathrm{ORAM}^{*\infty}_L[\mathbf{s}]) > |S| \cdot Z + R]$, so it is enough to show that $\mathbb{E}[X_{\mathbf{s},L,S}(\mathbf{w})]$ is negligible. This will follow from the next lemma.

**Lemma 4.4.3.** Let $\mathbf{s}$ be a legal sequence of accesses, and let $S \in \mathcal{S}$. Then the map $f: \mathbf{w} \mapsto \mathbb{E}[X_{\mathbf{s},L,S}(\mathbf{w})]$ is Schur-convex.

*Proof.* First, we show that $X_{\mathbf{s},L,S}$ is convex when the random coins used in the ORAM construction are fixed. Until further notice, we assume that all random coins are fixed. Only $\mathbf{w}$ varies. Let $\lambda \in [0, 1]$, and let $\mathbf{v}, \mathbf{w}$ be two size allocation vectors. Observe that the map $g: \mathbf{w} \mapsto u^S(\mathrm{ORAM}^{*\infty}_L[\mathbf{s}(\mathbf{P}\mathbf{w})])$ is linear. This is because, as already noted, whether an item is stored in a node from $S$ or not is independent of the weight of the items. As a consequence, $g(\mathbf{w})$ is equal to the sum of the weights of items stored in $S$, i.e. it is a fixed linear combination of $w_i$'s (with binary coefficients). Since $g$ is linear, it is trivially convex.

Also observe that for any constant $C$, the map $h: x \mapsto \max(0, x - C)$ is increasing and convex. Since the composition of an increasing convex function with a convex function is convex, we deduce that the map $h \circ g$ is convex. Since $X_{\mathbf{s},L,S}(\mathbf{w}) = \max_{\mathbf{P} \in \Pi} h \circ g(\mathbf{P}\mathbf{w})$, it is a maximum of convex maps, so it is also convex.
On the other hand, $X_{s,L,S}(\mathbf{w})$ is symmetric by construction, since it takes the maximum over all permutations of $\mathbf{w}$. By Lemma 4.2.1, since $X_{s,L,S}(\mathbf{w})$ is both symmetric and convex, it is Schur-convex.

It remains to show that Schur convexity still holds when considering the expectation of $X_{s,L,S}(\mathbf{w})$. (From now on, we no longer assume that random coins are fixed.) However, it is straightforward to show that if a probabilistic map is Schur-convex for every fixed choice of random coins (sometimes called stochastical Schur-convexity), then its expectation is also Schur-convex [MOA79]. We conclude that $\mathbf{w} \mapsto \mathbb{E}[X_{s,L,S}(\mathbf{w})]$ is Schur-convex. ■

**Corollary 4.4.4.** Let $\mathbf{s}$ be a legal sequence of accesses with weight vector $\mathbf{w}$, and let $S \in \mathcal{S}$. Then $\mathbb{E}[X_{s,L,S}(\mathbf{w})]$ is negligible.

*Proof.* For an access sequence to be legal, its weight vector $\mathbf{w}$ must satisfy that $w_i \le B$ for all $i$, and $\sum w_i \le NB$. Observe that all such vectors are majorized by the vector $\mathbf{v} = (B, \dots, B, 0, \dots, 0)$ containing $N$ initial $B$'s. Since $\mathbb{E}[X_{s,L,S}(\mathbf{w})]$ is Schur-convex, it follows that $\mathbb{E}[X_{s,L,S}(\mathbf{w})] \le \mathbb{E}[X_{s,L,S}(\mathbf{v})]$; in order to upper bound $\mathbb{E}[X_{s,L,S}(\mathbf{w})]$, it suffices to focus on the weight vector $\mathbf{v}$. (This is the point of using a Schur-convexity argument.)

But in the case of the vector $\mathbf{v}$, all items are of the same size $B$, or of size $0$.<fnref n="1" /> In that case, $\mathbf{ORAM}^*$ behaves exactly like $\mathbf{ORAM}$, except that accesses to items of size 0 translate to evictions without any prior item access. In particular, the usage of $S$ is the same for $\mathbf{ORAM}^*$ and $\mathbf{ORAM}$. Since we assume that $\mathbf{ORAM}$ has the free eviction property, it remains correct when allowing eviction queries by the client. Since it is also assumed to be correct and to satisfy $W \Rightarrow F$, it follows that the usage of $S$ cannot exceed $|S| \cdot Z + R$ except with negligible probability, hence the same holds for $\mathbf{ORAM}^*$, and we are done. ■

So far, we have shown that the probability that any given $S$ witnesses a failure in $\mathbf{ORAM}^*$ is negligible. To conclude the proof, it remains to show that the probability that there exists an $S \in \mathcal{S}$ witnessing a failure is negligible. This does not follow immediately from the previous statement, because $|\mathcal{S}|$ may be superpolynomial. However, looking at the proof of Lemma 4.4.2, we see that when switching from expectation to probability and back, we only lose a factor $t$. In our case, the stash size is a random variable bounded by $NB$, so we have that for every $S$,

$$ \Pr[u^S(\mathbf{ORAM}^*_{L,\mathcal{S}}[\mathbf{s}(\mathbf{v})]) > |S| \cdot Z + R] \le NB \Pr[u^S(\mathbf{ORAM}^*_{L,\mathcal{S}}[\mathbf{s}]) > |S| \cdot Z + R]. $$

Since $\mathbf{ORAM}$ is assumed to satisfy $W \Rightarrow F$ via union bound, and $NB \in \text{poly}(\lambda)$, we know that the sum of the latter quantity over all $S \in \mathcal{S}$ is negligible, hence $\mathbf{ORAM}^*$ inherits the same union bound property. It follows that the probability that there exists a failure witness $S$ for $\mathbf{ORAM}^*$ is negligible. Since $\mathbf{ORAM}^*$ satisfies the $F \Rightarrow W$ property, we conclude that $\mathbf{ORAM}^*$ is correct. □

### 4.4.4 Experimental Results

To test empirically the correctness of our weighted ORAM, we implemented a Path ORAM structure and performed simulated accesses. We did two experiments: one with $N$ objects

<footnote n="1">¹The reader may observe that items of size 0 are not technically legal per the earlier definition of wORAM, which asks that items are of size at least 1; however, Weighted(ORAM) remains well-defined even for items of size 0, so nothing stops us from using them within the proof—the reason we forbade items of size 0 is that they would allow for an unbounded number of items, which would require a position map of unbounded size, but this is irrelevant for the current line of reasoning.</footnote>
of the same size (which simulates the standard case) and one with objects of variable sizes (the sizes are uniformly random, but sum to $N$). Our results are presented as graphs in Figure 4.1.

We took inspiration from the experiment in Section 7 of [SvS$^{+}$13b]. The experiment went as follows:

* We generated ORAM structures for $N$ objects, with $N = 2^L$ and $L \in \{10, 11, \dots, 22\}$. The bucket size is $Z \in \{3, 4\}$

* We chose the maximum block size to be $B = 512$.

* For the standard ORAM simulation, all blocks were of size $B$. For the weighted ORAM simulation, blocks were taken uniformly at random in $[B]$, with the total sum of the sizes being $N \cdot B$. The number $m$ of blocks generated is roughly $2 \cdot N$.

* We start with the Path ORAM loaded randomly with the objects at its leaves, and perform between $10 \cdot m$ and $50 \cdot m$ accesses in the order $\{1, 2, \dots, m, 1, 2, \dots\}$.

Figure 4.1 suggests that objects of variable size are even less prone to stash overflows than the standard case. Regarding bucket size, we make an observation similar to that of [SvS$^{+}$13b]: even though the correctness of the ORAM was proved for $Z + 1 = 6$, the construction appears resilient enough to work correctly even when $Z + 1 = 4$. In [SvS$^{+}$13b], the empirical results suggest that Path ORAM can be used with $Z$ as low as 4.

# 4.5 Application to Existing Tree ORAMs

In this section we present several concrete constructions: a weighted Simple ORAM, based on Chung and Pass's Simple ORAM [CP13], and a weighted Path ORAM, based on the seminal work by Shi et al. [SvS$^{+}$13b]. The construction for Path ORAM can be easily adapted to build a weighted *Random-Index ORAM* from the one presented in [HK22], as the block-holding structure is virtually the same. We also sketch the application to Circuit ORAM [WCS14] and OPRAM [CCS17]. By Theorem 4.4.1, in each case, it suffices to show that the scheme is suitable. The weighted variant is then obtained by applying the *Weighted* transformation.

## 4.5.1 Weighted Simple ORAM [CP13]

In *SimpleOram*, each bucket has a capacity of $Z = O(\log N)$, and the ORAM overflows if and only if there is a bucket with more than $Z$ items: there is no stash. From the perspective of the Tree ORAM framework from Section 4.3.2, a stash does exist, however, it is required that it is empty at the outcome of any (legal) sequence of accesses. That is, we set the stash bound $R$ to 0.

In *SimpleOram*:

* The `ChooseEvictionPath(leaf)` method is implemented by choosing a path uniformly at random (the *leaf* argument is ignored).
<figure><img src="image_8.png" /><figcaption>Figure 4.1: Experimental results for $Z \in \{3, 4\}$</figcaption></figure>
* The `ChooseNextBlock(stash, bucket, path)` method is implemented by returning the first item among items whose position is such that its meet with the current path is exactly *bucket*. (In other words, all items are stored as low as possible along the eviction path, while preserving the invariant that they are stored above their associated leaf.) The correctness of `SimpleOram` relies on the fact that all such items will fit in the current bucket; items are never pushed somewhere else in case a bucket is full.

We want to show that `SimpleOram` is suitable. Define $\mathcal{S}$ to be the set containing the singleton $\{\text{bucket}\}$ for each tree node *bucket*. The fact that the correctness of `SimpleOram` is equivalent to the fact that no element of $\mathcal{S}$ witnesses a failure is immediate, since the correctness of `SimpleOram` requires precisely that no node overflows. Hence, `SimpleOram` satisfies $W \Rightarrow F$ (and $F \Rightarrow W$) with respect to $\mathcal{S}$. The fact that `Weighted(SimpleOram)` satisfies $F \Rightarrow W$ is immediate for the same reason. `SimpleOram` also satisfies the union bound requirement, because its analysis in [CP13] relies on just such a union bound. The fact that it supports free evictions also follows directly the analysis in [CP13] (additional evictions translate to more success chances in the dart game argument at the center of the analysis). We conclude that `SimpleOram` is suitable.

**Theorem 4.5.1.** *Weighted(SimpleOram) is a correct wORAM scheme.*

## 4.5.2 Weighted Path ORAM [SvS$^{+}$13b]

Let $\text{ORAM}^Z \leftarrow \text{PathOram}$. Setup($N, Z$) be an instance of Path ORAM. The bucket capacity $Z$ for Path ORAM is a small constant; the scheme is proven correct for $Z = 5$, we shall use this value. The stash capacity is $R = \mathcal{O}(\log N)$.

In PathOram:

* `ChooseEvictionPath(leaf)` simply returns $\mathcal{P}(leaf)$.

* `ChooseNextBlock(stash, bucket, path)` returns an item from the buffer such that its associated leaf is below *bucket*, and the meet between the position of the item and *path* is lowest among such items.

**Theorem 4.5.2.** *Weighted(PathOram) is a correct wORAM scheme.*

*Proof.* Define $\mathcal{S}$ to be the set of all subtrees of the ORAM tree, where a *subtree* is defined to be a subset of nodes closed for the *parent relation* (i.e. if the set contains a node, it also contains its parent). The analysis of [SvS$^{+}$13b] proves that `PathOram` satisfies both $F \Rightarrow W$ and $W \Rightarrow F$ with respect to $\mathcal{S}$, via a union bound. The fact that `PathOram` supports free evictions also follows from the analysis. In the remainder, we focus on showing that `PathOram*` $\leftarrow$ `Weighted(PathOram)` satisfies $F \Rightarrow W$.

We follow a similar approach to the initial part of the analysis in [SvS$^{+}$13b]. Let us define a post-processing algorithm $G_Z$, which is applied to $\text{ORAM}^{*\infty}$ after a sequence of accesses. Like in the original analysis of Path ORAM, the $G_Z$ algorithm is a “thought experiment”: that is, the algorithm is used within the proof, but never actually run by any party in the ORAM protocol. As a consequence, we can allow $G_Z$ to perform operations that are not normally allowed within the wORAM framework. In particular, we let $G_Z$ “split” any object of size $w$ in two objects of sizes $w_1$ and $w_2$ such that $w_1 + w_2 = w$, storing the two chunks at distinct locations. $G_Z$ repeats the following process, as long as there are overfull buckets (i.e. whose size is strictly more than $Z$—to avoid cluttering the notation, all sizes are implicitly divided by the block size $B$):
1. Select a bucket $b$ that has load strictly more than $Z$. Remove blocks from the bucket (splitting if needed) so that it ends up having load exactly $Z$. Removed blocks are stored in a temporary buffer.

2. Find the nearest ancestor of $b$ that has load strictly less than $Z$. Store items from the buffer into this ancestor, until its load is exactly $Z$ (or the buffer is empty), splitting if needed.

3. As long as the buffer is not empty, repeat the previous step, working our way up the path $P(b)$, until reaching the stash. At that point, any remaining items in the buffer is stored in the stash.

First, let us prove that the stash usage (i.e. the cumulated size of all items in the stash) of the post-processed $\infty$-ORAM is greater than the stash usage of $ORAM^{*Z}$:

$$st^Z(ORAM^{*\infty}[\mathbf{s}]) \geq st(ORAM^{*Z}[\mathbf{s}]). \qquad (4.2)$$

First, notice that the order in which overfull blocks are processed by $G_Z$ has no bearing on the final occupancy of the nodes and stash. In particular, $st^Z(ORAM^{*\infty}[\mathbf{s}])$ is well-defined, even though we put no restriction on the order in which $G_Z$ processes overfull buckets. To show this, we can generalize the argument from [SvS$^{+}$13b]: assume that $G_Z$ processes blocks from the bucket $\beta_1$ at level $l_1$ on path $p_1$, then blocks from the bucket $\beta_2$ at level $l_2$ on path $p_2$. We want to show that the loads in the buckets in $p_1 \cup p_2$ do not change if we let $G_Z$ process $\beta_2$ before $\beta_1$. Without loss of generality, we can assume that those buckets are siblings (i.e. $l_1 = l_2 = l$), since only $p_1 \cap p_2$ will be affected by a change in the order. Assume that the post-processed blocks from $\beta_1$ (resp. $\beta_2$) are of total size $W_1$ (resp. $W_2$). $G_Z$ first distributes a “mass” of size $W_1$ in the buckets from level $l-1$ to $-1$ in $p_1 \cap p_2$, and then a mass of size $W_2$ in those same buckets. Before the distribution, let us call $V_i$ the available space in the bucket at level $i \in \{-1, 0, \dots, l-1\}$ on path $p_1 \cap p_2$. When distributing a mass $W$, $G_Z$ performs Algorithm 3 (we assume that $V_{-1} = \infty$): The $\{V_i\}$ are the same after a successive application of Algorithm 3 on $W_1$

<caption>**Algorithm 3 Distribution of mass of blocks**</caption>

**Distribution(W):**

1: $i \leftarrow l$

2: **while** $W > 0$ **do**

3: $i \leftarrow i - 1$

4: **if** $V_i \geq W$ **then**

5: $V_i \leftarrow V_i - W$

6: $W \leftarrow 0$

7: **else**

8: $V_i \leftarrow 0$

9: $W \leftarrow W - V_i$

then $W_2$ or after its application on $W_2$ then $W_1$.

*Remark.* We wish to draw the reader's attention to one point: in what precedes, we consider for simplicity that blocks are taken in bulk from the buckets, whereas in what follows it is more convenient to assume that $G_Z$ processes them individually. It doesn't make a difference for the same reason that the order doesn't matter.
We can finally prove (4.2). Informally, we can see that during the accesses, $ORAM^{*Z}$ stores blocks in buckets and in the stash in a more lenient way than $G_Z$, since it allows blocks to “stick out” of the buckets. More precisely, after the accesses of $\mathbf{s}$ in $ORAM^{*\infty}[\mathbf{s}]$, there exists a way to move blocks from the buckets they reside in to their final destination from $ORAM^{*Z}[\mathbf{s}]$ (in another bucket or the stash). Since the order in which we post-process blocks from the buckets does not matter, we can assume that this particular order is accessed by $G_Z$. If that is the case, after the processing of each block, $G_Z$ puts that block in the bucket where it belongs according to $ORAM^{*Z}[\mathbf{s}]$. However, should a part of the block (or its entirety) stick out of the bucket (i.e. causes the load to become $\ge$ Z), this part will be moved to a higher block or the stash. Thus the processing of each block by $G_Z$ causes the stash size to either stay the same or to increase. Thus at the end of the processing, $st^Z(ORAM^{*\infty}[\mathbf{s}]) \ge st(ORAM^{*Z}[\mathbf{s}])$.

We are now ready to show that Weighted(PathOram) satisfies $F \Rightarrow W$. By (4.2), if correctness fails for Weighted(PathOram), then it also fails (with the same random coins) for the post-processed $\infty$-ORAM variant. That is, $st^Z(ORAM^{*\infty}[\mathbf{s}]) > R$. Let us define $T$ to be the maximal subtree that only contains buckets of size at least $Z$ after the post-processing. If a bucket $b$ is not in $T$, it has an ancestor $b'$ that has usage strictly less than $Z$, so the blocks of $b$ cannot go to the stash. Thus all blocks in the stash came from buckets in $T$, and thus $u^T(ORAM^{*\infty}[\mathbf{s}]) > n(T) \cdot Z + R$. This shows that $T$ is a failure witness. $\square$

**Discussion.** In the proof above, a “splitting” variant of wORAM was introduced. In that splitting variant, items can be split into pieces of arbitrary sizes, and each piece can be stored at a different tree node (still maintaining the invariant that all pieces belonging to the same item are stored somewhere along the path from the root to the leaf associated with the item). Splitting is a convenient intermediate abstraction, because of its “continuous” behavior, which avoids rounding issues.

It is worth noting that splitting is not just a proof abstraction, but could also be used in actual tree-based wORAM algorithms. In fact, we could have defined our weighted transformation to allow splitting. In that case, the proof above shows that the weighted variant of Path ORAM would have the same bucket capacity $Z$ as the original Path ORAM.

By contrast, our actual construction, which does not use splitting, needs to increase the bucket capacity to $Z + 1$ to avoid “rounding” issues. Intuitively, without splitting, if a bucket of capacity $ZB$ words contains data of total size $(Z - 1)B + 1$, and the client wants to insert a block of maximum size $B$, it cannot fit in that bucket. This means each bucket can have up to $B - 1$ words of “wasted” space. Note that this cannot happen in standard ORAM, where all items have size $B$: it is an issue specific to weighted ORAM (and weighted allocation mechanisms in general). Splitting solves the issue without the need to increase bucket capacity: the ability to split avoids any wasted space.

Our construction solves the issue differently, without splitting, by increasing bucket capacity to $(Z+1)B$ words (or $Z+1$ full blocks). This guarantees that if a bucket cannot receive a new block, then it already contains at least $ZB$ words. In short, the reason we increase bucket capacity to $Z + 1$ in our constructions is to resolve rounding issues inherent to fitting weighted items into buckets of fixed capacity.

As noted, we could have chosen to define our Weighted transformation to allow splitting. We avoided that option, because it complicates implementation in practice, and may require significantly more metadata (each piece needs an identifier tag). Nevertheless, it
is a valid option, and may be preferable if a slightly lower $Z$ is desirable.

### 4.5.3 Weighted Oblivious Parallel RAM [BCP16]

Boyle, Chung, and Pass's protocol [BCP16] is based on Simple ORAM. Their framework present ORAM protocols for parallel algorithms, i.e. with multiple processors (clients). The Weighted function is not impacted by the fact that there are several clients: The modifications to the subroutines still capture this case, and the correctness analysis holds. The only new component is the broadcast routine, where one of the CPUs broadcasts information about a certain block to the other CPUs. These messages are bounded by the size of the block. That could lead to a leakage however: we need to index every block, in the weighted case there are $m$ objects and $\log m \ge \log N$. Thus, we can lower bound the size of the messages by $O(\log N)$: their size will not leak information on the block. This yields a correct weighted ORRAM.

### 4.5.4 Weighted Circuit ORAM [WCS14]

Circuit ORAM is a variant of Path ORAM, where the client only needs local space to hold one block. To achieve this, the eviction algorithm is slightly different and the stash is stored by the server (as the parent of the root node) instead of locally.

<figure><img src="image_9.png" /><figcaption>Figure 4.2: A block of size $< B$ in 2 chunks</figcaption></figure>

The correctness analysis of this scheme is based on the same principles as the one for Path ORAM. The function Weighted yields a correct ORAM here too. To prove this, we only need to show how we can adapt for the fact that the stash is stored on top of the tree. Figuring out which way to do this is not obvious since, because of the varying block size, the client cannot simply stream the content of the stash block by block: it would leak block size information. We propose a simple fix, which we also use when dealing with Trivial ORAM:

* We allow the client to store an additional space of size $B$ (the maximal size of a block). This gives the client a local space of at least $2 \cdot B$.

* Whenever the client needs to access the stash, the client streams the content of the stash *chunk by chunk*, where each chunk is of size $B$. That way, since a block must always reside inside at most 2 chunks (see Figure 4.2), the client will read every object at the end of the stash stream.
• When the client wishes to write back a block, it is done locally among two chunks.

This way, the scheme stays correct and secure even with objects of variable size. The
application of the suitability criterion shows that Circuit ORAM is compatible with blocks
of variable size.

4.6 Searchable Encryption from Weighted ORAM

With Searchable Symmetric Encryption (SSE), a client can delegate the storage of a
database to a honest-but-curious server. The client is then able to perform searches on
the database by issuing **Search** queries to the server. In the case of *dynamic* SSE, the
client may also update the database by issuing **Update** queries to the server. The security
goal is that the information leaked to the server during these operations should be limited,
in a sense that will be defined soon.

Here, we focus on the case of single-keyword search. In that setting, the client's
database consists of a collection of documents, and **Search** queries ask to retrieve all
documents that contain a given keyword. In modern SSE schemes, this functionality is
realized efficiently by building a reverse index: For each keyword *w*, a list of the identifiers
of documents matching the keyword, written DB(*w*), is maintained on the server side
in some encrypted form. *Response-revealing* SSE allows the server to learn the list of
document identifiers, while response-hiding SSE does not: they are sent back to the client
in encrypted form. Once having retrieved the desired document identifiers, the client may
perform some additional computation, such as intersecting the results with other queries,
or may fetch the documents on the same or a different server. In the case of response-
revealing SSE, if the same server stores the reverse index and the documents, the server
can immediately send back the documents without the need of an additional roundtrip,
at the cost of possibly leaking additional information to the server. We note that the
documents could be stored in an ORAM to avoid additional leakage, and that a weighted
ORAM would reduce the performance cost of this approach. However, as in most SSE
literature, we focus on the reverse index.

For efficiency reasons, SSE typically does not seek to have minimum leakage, but
rather to strike a compromise between security and performance by allowing a controlled
amount of leakage. In the security model, the leakage allowed by the scheme is expressed
by a leakage function $\mathcal{L} = \{\mathcal{L}_{\text{Setup}}, \mathcal{L}_{\text{Search}}, \mathcal{L}_{\text{Update}}\}$. The security model asks that during
a **Setup** operation (resp. **Search**, **Update**) with input *x*, the information leaked to the
server is included in $\mathcal{L}_{\text{Setup}}(x)$ (resp. $\mathcal{L}_{\text{Search}}(x)$, $\mathcal{L}_{\text{Update}}(x)$). More formally, it is required
that there must exist a simulator $\mathcal{S}$ such that the view of the server during **Setup**($x$) (resp.
**Search**($x$), **Update**($x$)) should be indistinguishable from $\mathcal{S}(\mathcal{L}_{\text{Setup}}(x))$ (resp. $\mathcal{S}(\mathcal{L}_{\text{Search}}(x))$,
$\mathcal{S}(\mathcal{L}_{\text{Update}}(x)))$.

Response-revealing SSE schemes leak the *access pattern*: That is, the server learns the identifiers of all documents matched by a query. In some use cases, access pattern leakage can be quite damaging, and allow the server to infer a sizable amount of information about the database [CGPR15, GLMP19]. Even in the case of response-hiding SSE, the server can typically learn the *query pattern*: that is, the server can learn whenever the client repeats the same query. In many cases, the server can learn the *volume* of the answer: that is, the number of documents matched by the query.

In some use cases, these different types of information leakage can be quite damag-
ing, as shown by so-called *leakage-abuse* attacks [CGPR15, GSB+17]. To thwart those
<table><caption>Figure 4.3: Overhead of ORAM-based SSE constructions. U is an upper bound on the longest list size, $W \le N$ is the number of keywords, B is the ORAM block size.</caption><thead><tr><th>Scheme</th><th>client storage</th><th>bandwidth overhead</th></tr></thead><tbody><tr><td>TWORAM [GMP16]</td><td>O(1)</td><td>O(λ log<sup>2</sup> N)</td></tr><tr><td>ZeroSSE</td><td>O(W)</td><td>O(log(N/U))</td></tr><tr><td>ZeroSSE'</td><td>O(1)</td><td>O(log<sup>2</sup> W + log(N/U))</td></tr><tr><td>BlockSSE</td><td>O(W)</td><td>O(log(N/B))</td></tr><tr><td>BlockSSE'</td><td>O(1)</td><td>O(log<sup>2</sup> W + log(N/B))</td></tr></tbody></table>

attacks, recent works have developed various protections, such as volume-hiding SSE [KM19, PPYY19], and the line of work on leakage suppression [KMO18]. The strongest form of protection, considered for instance in [GMP16, MM17, KMO18], involves the use of ORAM, or specialized variants of ORAM. This raises some questions about how to optimize the use of ORAM, in order to preserve the high efficiency goal of SSE. In particular, as discussed e.g. in [GMP16], since reverse indexes contain lists that can greatly vary in size, it is not obvious how to fit them into a (fixed-block size) ORAM. Our main point in this section is that the weighted construction introduced here fits this setting perfectly. Concretely, we propose two SSE constructions based on weighted ORAM: ZeroSSE and BlockSSE. A brief overview is given Figure 4.3. We note that the main point of TWORAM, not reflected in the table, is to reduce the number of roundtrips in the iterative version of Path ORAM, thanks to a clever use of garbled circuits. However garbled circuits add a considerable overhead in practice.

### 4.6.1 Preliminaries

We follow the standard definition of SSE. A dynamic SSE scheme $\Sigma$ consists of four protocols, defined as follows.

* $\Sigma.KeyGen(1^{\lambda})$: Takes as input the security parameter $\lambda$. Outputs the master secret key $K$.

* $\Sigma.setup(K, N, DB)$: Takes as input the client secret key $K$, an upper bound on the database size $N$, and a database $DB$. Outputs an encrypted database $EDB$.

* $\Sigma.search(K, w, st; EDB)$: The client receives as input the secret key $K$, and keyword $w$. The server receives as input the encrypted database $EDB$. Outputs the list of document identifiers associated with the keyword $w$.

* $\Sigma.update(K, (w, e); EDB)$: The client receives as input the secret key $K$, and a pair $(w, e)$ of keyword $w$ and document identifier $e$. The server receives as input the encrypted database $EDB$. Outputs updated encrypted database $EDB'$ for the server, where the list of documents identifiers associated with $w$ has $e$ appended to it.

The security model expresses that the view of the server can be simulated by an efficient simulator, receiving as input only the output of the leakage function. In more detail, 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 $S$ on input
$\mathcal{L}_{\text{Setup}}(\text{DB}, N)$. After receiving EDB, the adversary can issue search and update queries. In SSEReal, queries are answered using the real-world protocol. In SSEideal, the Search queries (resp. Update, Setup) on input $x$ are simulated by $S$ on input $\mathcal{L}_{\text{Search}}(x)$ (resp. $\mathcal{L}_{\text{Update}}(x)$, $\mathcal{L}_{\text{Setup}}(x)$). Finally, the adversary outputs a bit $b$.

The scheme is said to be $\mathcal{L}$-secure (i.e. secure with respect to the leakage function $\mathcal{L}$) if for all PPT adversaries, there exists a PPT simulator such that the transcripts in the real and ideal world are computationally indistinguishable.

### 4.6.2 ZeroSSE

A line of recent works has aimed to hide volume leakage: that is, to hide the number of identifiers matching a given query [KM19, PPYY19]. Hiding volume leakage seems sensible when using ORAM techniques to hide the query pattern, since volume leakage reveals information about the repetition of queries. This leads to the question of building an ORAM that also hides volume. For that purpose, an upper bound $U$ is assumed on the volume of the longest list (that is, the longest query answer). As discussed in [GMP16], the first approach one may think of is to use an ORAM with block size $U$; however, this would require padding all lists to $U$, which would be prohibitive in many use cases, since the longest list may be several orders of magnitude larger than the average list size. In the worst case, the blowup in storage is $\Omega(U)$, even before considering ORAM overheads. Another approach would be to use a smaller block size, at the cost of a larger ORAM overhead.

The idea of ZeroSSE is simply to use the weighted variant of Path-ORAM, Weighted(PathOram) with $B = U$ as the block size upper bound. Relative to the previous two approaches, this minimizes both the overhead due to padding, which is nonexistent since no padding is necessary, and the overhead due to ORAM, since we use the largest block size possible. In fact, since our main result is that Path ORAM can handle items of variable size at essentially no overhead, we contend that this is both the most natural and most efficient solution to building SSE with minimum leakage.

We define ZeroSSE in more details as follows. We note that Setup takes as input additional parameters $U$, which is an upper bound on the longest list size, and $W$, an upper bound on the number of keywords.

* ZeroSSE.setup(K, N, DB, U): Initializes Weighted(PathOram) with block size $U$ and number of leaves $[N/U]$, containing as (variable-size) blocks DB($w$) for each keyword $w$. The position map, of size $O(W)$ memory words, is stored on the client side.

* ZeroSSE.search(K, w; EDB): The client queries the ORAM for keyword $w$ to retrieve DB($w$).

* ZeroSSE.update(K, (w, e); EDB): The client queries the ORAM for keyword $w$ to retrieve DB($w$), and simply writes back $DB(w) \cup \{e\}$. (Recall that our weighted construction allows modifying the size of blocks on the fly.)

ZeroSSE uses the non-iterative variant of Path-ORAM. This is because a client storage of $O(W)$, while undesirable in general, is often accepted in forward-secure SSE [BF19]. Alternatively, we define ZeroSSE' to use the fully iterative version of Path-ORAM, which reduces the client storage to $O(1)$ memory words, at the cost of additional roundtrips, and an additional $O(\log^2 W)$ bandwidth overhead. (In theory, this could be reduced to
$\mathcal{O}(\log W)$ using an optimal ORAM for the position map, but current constructions of optimal ORAM are not practical.)

**Theorem 4.6.1 (Security of ZeroSSE).** *Assuming Path-ORAM is a correct and secure ORAM scheme, ZeroSSE is $\mathcal{L}$-secure with respect to the leakage function $\mathcal{L} = \{\mathcal{L}_{Setup}, \mathcal{L}_{Search}, \mathcal{L}_{Update}\}$, with $\mathcal{L}_{Setup} = \{N, U\}$ and $\mathcal{L}_{Search} = \mathcal{L}_{Update} = \emptyset$.*

A proof of Theorem 4.6.1 is given in Appendix B.1.

### 4.6.3 BlockSSE

An interesting property of ZeroSSE is that updates are indistinguishable from searches. In fact, addition and deletion of an arbitrary number of documents in a list can be performed in a single interaction at no additional cost. However, this also means that adding a single document to a keyword incurs an $\mathcal{O}(U \log^2 U)$ bandwidth cost. If cheaper updates for single documents are desirable, an alternative solution is to use a smaller block size. A smaller block size (linearly) reduces the cost of updates, while (logarithmically) increasing the cost of searches.

BlockSSE offers that trade-off, by storing the reverse index in a wORAM with parametrizable maximum block size $B$. An interesting feature of BlockSSE is that we can choose the block size $B$ such that the size of a Path-ORAM tree node $ZB$ is one memory page (or an integral number of memory pages). This optimizes the IO-efficiency of the resulting SSE, as discussed e.g. in [BBF+21]. This results in the first SSE with both high memory efficiency and no access pattern leakage.

While BlockSSE may perform significantly better than ZeroSSE in update-heavy workloads, the fact that searches and updates are indistinguishable, regardless of the number of documents added or deleted during an update, is lost. BlockSSE also does not support deletions by default, although they can be added generically at some additional cost, as in [Bos16].

To reduce the size of the position map, we borrow the pointer idea introduced in [WNL+14]. Namely, each block belonging to the same list $DB(w)$ contains the position of the previous block. This allows the position map, stored on the client, to only store the position of the last block, resulting in $\mathcal{O}(W)$ storage.

We define BlockSSE in more details as follows. Note that Setup takes as input additional parameters $B$, which is the desired block size, and $W$, and upper bound on the number of keywords. Update takes as additional parameter $U$, which is an upper bound on the longest list size.

*   **BlockSSE Gibbous (K, N, DB, U):** Initializes Weighted(PathOram) with block size $B$ and number of leaves $n = \lceil N/B \rceil$. For each keyword $w$, the list $DB(w)$ is split into $\lceil DB(w)/B \rceil$ chunks of size at most $B - \lceil \log n \rceil$, with no padding. The $i$-th chunk for keyword $w$ is inserted into the ORAM at a random position, together with the position of the $(i-1)$-th chunk. The position $l_w$ of the last chunk is stored on the client side.

*   **BlockSSE Search (K, w, U; EDB):** The client queries the ORAM at position $l_w$, retrieves the last chunk $DB(w)$, together with the position of the penultimate chunk. The client iteratively retrieves the position of each previous chunk in the same manner. Each chunk $i$ is assigned a new position uniformly at random, updating the position stored within the next chunk accordingly.
* BlockSSE.update(K, (w, e); EDB): If $l_w$ is not a multiple of $B - \lfloor \log n \rfloor$, the client accesses the ORAM at position $p_w$, adds $e$ to the data, replaces $p_w$ by a new uniformly random position, and updates the ORAM according to this new data and position. If $l_w$ is a multiple of $B - \lfloor \log n \rfloor$, a new block is inserted at a new uniformly random position, containing as data $\{e\}$ together with the position $p_w$ of the previous last block. On the client side, $p_w$ is updated to the position of the newly inserted block.

**Theorem 4.6.2 (Security of BlockSSE).** BlockSSE is $\mathcal{L}$-secure with respect to the leakage function $\mathcal{L} = \{\mathcal{L}_{Setup}, \mathcal{L}_{Search}, \mathcal{L}_{Update}\}$, with $\mathcal{L}_{Setup} = \{N, B\}$, $\mathcal{L}_{Search}(w) = \lfloor|\mathrm{DB}(w)|/B\rfloor$, and $\mathcal{L}_{Update} = \emptyset$.

A proof of Theorem 4.6.2 is given in Appendix B.1. BlockSSE' is the same as BlockSSE, except the iterative variant of Path-ORAM is used.
Publication

This work was in an article published at the EUROCRYPT 2023 conference, under the
following title [AM23]:

Weighted Oblivious RAM, with Applications to Searchable Symmetric Encryption.

by Léonard Assouline and Brice Minaud.

Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference
on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part I Apr 2023 Pages 426–455
# Structural Cryptanalysis of Implicit White-Box Implementations

## 5.1 Introduction

The promise of white-box cryptography is to hide key material from an adversary who has full access to the implementation of a cipher. Using the implementation, the adversary can compute the cipher on any given input, she may observe all intermediate variables, and she may even modify them at will to inject faults. Still, the implementation should be obfuscated in such a way that the adversary cannot infer the encryption key. In this manner, a white-box implementation of a cipher offers a functionality similar to running the encryption algorithm within a trusted enclave in hardware: it allows the user to execute the algorithm, without leaking sensitive key material contained in the code. The difference is that white-box cryptography aims to hide information in software.

This goal is quite attractive within industry. Historically, the concept was introduced by Chow *et al.* in two seminal articles, proposing white-box implementations of AES and DES [CEJvO02a, CEJvO02b]. Since then, white-box cryptography has been instrumental in Digital Rights Management solutions (e.g. for iTunes, or pay TV services), and payment applications. It also offers an alternative solution for third parties who often cannot access proprietary trusted computing units (e.g. in iOS).

While the demand for secure white-box cryptography is high within industry, all public white-box constructions have so far been proven insecure (see Section 5.1.2). In some cases, short-term security may be enough, as the goal of practical deployments may be to dissuade or slow down attackers, in conjunction with frequent rekeying of sensitive white-box implementations. Nevertheless, a secure white-box implementation of a block cipher would be a major breakthrough.

Towards that end, an innovative approach was proposed at Crypto 2022 by Ranea, Vandersmissen, and Preneel [RVP22]. The authors of [RVP22] show that by using so-called *implicit* representations of round functions, it is possible to realize white-box implementations of SPN and ARX ciphers with rich *non-linear* encodings. The use of non-linear encodings in white-box cryptography is not new, but previous uses of non-linear encodings were very restricted, while the approach of Ranea *et al.* allows for a much wider range of encodings. As an illustration of that point, Ranea *et al.* introduce the first white-box implementation technique suitable for ARX ciphers. To our knowledge, no prior technique applied to that setting.

To understand why non-linear encodings matter, it is helpful to look back to existing attacks on white-box cryptography. Roughly, published attacks fit into three families:
ad-hoc attacks, structural attacks, and gray-box attacks.

**Ad-hoc attacks.** Ad-hoc attacks target a specific white-box construction. The earliest attacks on white-box cryptography were of that type [BGE04, GMQ07, WMGP07]. While they show that the targeted design is insecure, they are restricted to that design.

**Structural attacks.** Structural cryptanalysis was introduced by Biryukov and Shamir, before the invention of white-box cryptography [BS01]. In brief, given black-box access to a function with some hidden structure, the goal of structural cryptanalysis is to recover that structure. In their original work, Biryukov and Shamir consider the so-called SASAS structure, where the function of composed of three S-box layers, interleaved with affine layers $A$. Because existing white-box approaches for white-box cryptography rely on hiding intermediate components of a block ciphers (typically, its round functions) behind low-degree (typically affine) encodings, it is naturally amenable to structural cryptanalysis. Indeed, structural attacks allow the attacker to peel off the encodings, and recover the original round function.

Structural cryptanalysis provides considerable insight: for instance the structural cryptanalysis of ASA contained in [BS01] implies that it is essentially impossible to hide the round function of an SPN cipher behind affine encodings. In fact, the authors of [DFLM18] argue that many ad-hoc attacks on white-box constructions can be recast as special cases of the structural attack on ASA. It is worth noting that structural attacks are also interesting outside of white-box cryptography—the notion even predates white-box cryptography. The work of [BS01] was meant to provide insight on SPN ciphers, and the structural attack of [MDFK18] applies to a multivariate public-key encryption scheme. (Some other attacks on multivariate cryptography are also naturally viewed as structural attacks, even if they do not use the terminology, such as [DFKYZD99].)

**Gray-box attacks.** Gray-box attacks use techniques inspired by side-channel cryptanalysis to break the security of white-box encryption [SMG16, GRW20]. After all, white-box security is intended to be a stronger requirement than resisting side channels: the attacker has full access to the implementation. This approach has been quite effective in automatically breaking constructions such as in the WhiBox challenge [BDG$^{+22}$, BBD$^{+22}$]. Nevertheless, it does not suffice to break the most secure variants, and is experimental in nature. Compared to structural attacks, it has the advantage of being more easily automatable for real-world deployment, but it does not provide the same kind of insight as structural attacks, which can be understood as general impossibility results.

### 5.1.1 Our Contributions

At Crypto 2022, Ranea, Vandersmissen, and Preneel have proposed a new technique for white-box cryptography: implicit encodings [RVP22]. A compelling aspect of their proposal is that it enables rich non-linear input encodings. This circumvents the structural cryptanalysis results of [BS01, DFLM18], which show that it is generically impossible to hide the round function of an SPN cipher behind affine or linear encodings. A limitation of [RVP22] is that output encodings must still be affine, and input encodings must be of low degree. This raises the question of a structural cryptanalysis of the ISA structure, where a layer of S-boxes is composed with a low-degree layer $I$ at its input, and an affine
layer A at its output. That is, given black-box access to a function $F$ of the form ISA, is it generically possible to recover the three inner layers $I$, $S$, $A$, such that $F = A \circ S \circ I$? Since the work of [RVP22] also applies to ARX ciphers, the same question applies to the IMA structure, where the S-box layer $S$ is replaced with modular addition.

As our main result, we give a *structural* cryptanalysis of both ISA and IMA. In particular, this breaks the white-box proposal of [RVP22]. Beyond that, it shows that it is generically impossible to hide an S-box layer (or modular addition) behind encodings, if only the input encoding is non-linear. Because the implicit function technique of [RVP22] inherently requires affine output encodings, our work implies that it does not suffice to build secure white-box cryptography.

In terms of techniques, our structural cryptanalysis of ISA is similar in essence to the structural cryptanalysis of ASASA in [MDFK18]. Our structural cryptanalysis of IMA introduces interesting new techniques, which can be viewed as a generalization of linearization attacks. A practical validation of the attack is presented in Section 5.6.

### 5.1.2 Related Work

In 2002, Chow, Eisen, Johnson and van Oorschot introduced a white-box implementation of the Advanced Encryption Standard (AES) [CEJvO02a], and the Data Encryption Standard (DES) [CEJvO02b]. Those seminal contributions introduced the idea of white-box cryptography, but quickly proved insecure. In 2004, Billet et al. [BGE04] proposed an algebraic attack against the AES white-box implementation of [CEJvO02a]. Further attacks were proposed in [MGH09, LRdM$^{+13}$]. Using differential cryptanalysis, [WMGP07] and [GMQ07] broke the DES S-box of the white-box implementation from [CEJvO02b] and [LN04]. These attacks led to a new proposal of white-box design in [XL09], but their attempt was thwarted by the attack from [MRP12]. In 2014, [BBK14] presented a new AES white-box implementation based on an Affine-S-box-Affine (ASASA) structure, which was broken by [MDFK18], using structural cryptanalysis. In [VRP22], the authors break a white-box implementation of the cipher SPECK based on self-equivalence encodings, using a Gröbner basis approach. So-called gray-box attacks have also been proposed, including Differential Fault Analysis (DFA), and Differential Computer Analysis (DCA). These attacks offered new ways of attacking white-boxes, especially suited for automatic tools. Those techniques were repurposed from Side-Channel Attacks [BHMT16]. Enhancements of the DCA attacks were proposed in [BRVW19].

Beyond symmetric cryptography, the ability to hide a secret symmetric key from the users of a program is related to general obfuscation [DLPR13]. The most demanding form of program obfuscation, called virtual black-box obfuscation, has been proven to be impossible in [BGI$^{+01}$]. This does not preclude the possibility that secure white-box cryptography may be possible, because white-box cryptography attempts to obfuscate a specific class of functions, namely symmetric ciphers. The diagonalization argument from [BGI$^{+01}$] does not apply to that class of function. Nevertheless, obfuscating specific programs remains a hard task: all publicly available white-box schemes have been broken so far.

In a work published in TCHES 2023, Biryukov, Lambin and Udovenko present a cryptanalysis of the same white-box system we are studying in this chapter [BLU23]. Their attack is of a more practical nature than ours: their paper targets key recovery on the specific white-box construction of Ranea et al., only in the case of ARX ciphers. To our understanding, it does not contain a general structural cryptanalysis of ISA or IMA
(Section 5 of their work comes the closest, but it leaves many details to later sections, and those later sections use specificities of the construction of Ranea *et al.*). By contrast, our work is a general structural cryptanalysis of ISA and IMA. It applies to the framework of Ranea *et al.*, by showing that the non-linear input encodings are not enough for security. It is not limited to their specific construction.

## 5.2 Technical Overview

At a high level, structural attacks in the literature follow the same general steps (including those in [BS01, BBK14, DFLM18]). We begin by outlining those steps. Then we will explain how our own technique proceeds. For now, we purposefully remain at a high level of abstraction.

Recall that the attacker has black-box access to a function with a known structure (such as ASA or SASAS). The goal is to recover the inner components.

**Step 1:** Model some part of the target structure as polynomial unknowns in a judicious manner. Then find a way to use the black-box oracle to derive low-degree equations over those unknowns.

This is typically the “clever” part of the attack. The cryptanalyst needs to find a way to exploit the properties of the target structure to derive equations.

*Examples:* In the first stage of the SASAS attack [BS01], unknowns are entries in the table of the inverse S-box (from the last S-box layer). Equations are derived using ideas from integral cryptanalysis. In the first stage of the ASASA attack [DFLM18], unknowns are entries in the matrix representing the last linear layer. Equations are derived via a modified cube attack.

**Step 2:** Solve the equation system by linearization.

In general, the equations from Step 1 may not be linear. On the other hand, in existing attacks, it is easy to derive new equations by repeating Step 1 as needed. The point is that, while solving even quadratic systems is NP-hard when the number of equations is limited, the problem becomes easy if the attacker has access to as many (random enough) equations as they want. Indeed, in that case, the linearization technique can be applied [BS01, AG11]. We refer the reader to Section 5.3.5 for more information on linearization, and do not discuss it here to continue focusing on the overall structure of the attack.

**Step 3:** Repeat the same general process to recover each one of the other components of the target structure. (Each time a component is recovered, the process of recovering the other components typically becomes easier, as the attacker has access to more and more information.)

In a typical attack, Step 1 and 2 recover the first or last layer of the structure. For example, Step 1 and 2 of the ASASA attack in [DFLM18] recover the last A layer. By composing the inverse of that layer with the black-box oracle, the attacker now has oracle access to an ASAS structure. Since it is a “simpler” structure, recovering the next layer is expected to be easier. (This is indeed the case in all structural attacks to our knowledge: peeling layers becomes progressively easier.)
This chapter contains two structural attacks: one on each of the new structures proposed for white-box protection in [RVP22]. Namely, the ISA structure (“low degree–S box–affine”), and the IMA structure (“low degree–modular addition–affine”).

ISA attack.

For the ISA structure (unlike the IMA structure later on), our attack follows the blueprint presented earlier. In fact, our ISA attack is a direct generalization of the structural cryptanalysis of ASASA in [MDFK18], and shares much of the same main ideas. For that reason, we only sketch it here, and refer to the full description in Section 5.4 for more information.

In an IS structure, where the first layer has degree $d$, and the S-box is over $s$ bits, a bit of the output has degree (at most) $d(s - 1)$ over the input variables (see [MDFK18, Lemma 2]). A key observation is that the product of two output bits arising from the same S-box still has degree $d(s - 1)$, whereas if the two bits arise from distinct S-boxes, the degree rises to $2d(s - 1)$. The other key observation is that such a disparity in the behavior of the degree can be exploited by a cube attack. In more details, notice that in the ISA structure, the value of one bit at the output of the first two IS layers is a linear combination of output bits of the ISA function. Defining the coefficients of that linear combination as unknowns, it is possible to obtain (via a cube attack) a quadratic equation over those unknowns. From there, the general strategy outlined at the start of the section can be implemented.

IMA attack.

In prior work that followed the general steps outlined at the start of the section [BS01, BBK14, DFLM18], as well as in our own ISA attack, a crucial fact the attacks implicitly rely on is that the overall function has low algebraic degree<fnref n="1" />. Indeed, they rely on the key lemma of cube attacks, namely that the sum of a Boolean function of algebraic degree $d$ over an affine space of dimension $d + 1$ is zero (cf. Lemma 5.3.1)<fnref n="2" />. The number of summands is exponential in the degree $d$ of the function, so this approach is only viable for low-degree functions.

An immediate problem when tackling the IMA structure is that modular addition over $n$ bits has algebraic degree $n$. In particular, the IMA structure does not have low algebraic degree. For that reason, we do not directly use the cube attack approach of previous work. Instead, we rely on the iterative structure of modular addition: if modular addition is computed in the “elementary school” way by using carries, each output of the addition can be expressed as a quadratic polynomial in the input and in the value of the carry. That is, if we compute the modular addition $z = x \oplus y$ in $\mathbb{Z}_{2^n}$, then denoting by $z_i$ the $i$-th bit of $z$ (likewise for $x$ and $y$), we have:

$$z_i = x_i + y_i + c_i,$$

where $c_i$ denotes the carry coming from the addition of the first $i - 1$ bits, and “+” is addition in $\mathbb{Z}_2$. From there, a straightforward computation yields:

$$z_i = x_i + y_i + x_{i-1}y_{i-1} + c_{i-1}(x_{i-1} + y_{i-1}).$$

<footnote n="1">¹More exactly, the attack of [BS01] relies on the SASAS function minus the last layer having low degree, while the attacks in [BBK14, DFLM18] rely on the whole function having low degree.</footnote>

<footnote n="2">²This analysis is done differently in [BS01], but in retrospect, it could also have been done via a cube attack—except they did not exist yet [DS09].</footnote>
What is interesting about this equation is that if the attacker has recovered the expression of the first $i-1$ bits of $x, y$, then the attacker can compute $c_{i-1}$. The attacker can then look for a linear relation between $z_i$ (linear combination of output bits of the black-box function with unknown coefficients), $c_{i-1}(x_{i-1} + y_{i-1})$ (a known quantity times a linear combination of input bits with unknown coefficients), and the vector of pairwise products of the bits of $x_{i-1}$ and $y_{i-1}$ (again with unknown coefficients). To do so, the attacker creates a matrix whose rows are the concatenation of : input bits, input bits times $c_{i-1}$, output bits, and finally pairwise products of input bits—for random input bits. Because the previous relation, the kernel of the matrix must be non-trivial, and essentially reveals the unknown coefficients of $x_{i-1}$ and $y_{i-1}$ (we refer to Section 5.5 for more details).

To sum up, the attacker finds the coefficients of $x_{i-1}$ and $y_{i-1}$ iteratively, by using the recursive structure of modular addition. At each step, we note that there exist several possible solutions, forcing the attacker to guess. However, our experiments show that when the attacker makes a wrong guess, the very next step of the iteration always fails, meaning that wrong guesses are corrected immediately. We have validated the attack with a full implementation in the Sage programming language, discussed in Section 5.6. The implementation is available as supplementary material.

## 5.2.1 Structure of the chapter

We present our notation, the white-box framework, and structural cryptanalysis in Section 5.3. In Section 5.4, we show an attack on protocols white-boxing ciphers based on S-boxes using implicit implementations. Our main result is in Section 5.5, where we show an attack on implicit white-box implementations of ciphers based on modular additions. The techniques of polynomial factorization used as a subroutine of our attacks are detailed in Section 5.7.

# 5.3 Preliminaries

## 5.3.1 Notation

**Boolean vectors.** $\mathbb{F}_2$ denotes the field with two elements. Given a vector $v \in \mathbb{F}_2^n$, its $i$-th coordinate is denoted by $v[i]$, for $1 \le i \le n$. We may write $v = (v[1], \dots, v[n])$. The dot product between two vectors $v, w \in \mathbb{F}_2^n$ is denoted by $\langle v|w \rangle = \sum_{i=1}^n v[i]w[i]$. The concatenation of two vectors $x, y \in \mathbb{F}_2^n$ is written $x \parallel y \in \mathbb{F}_2^{2n}$. Let $e_1, \dots, e_n$ denote the canonical basis of $\mathbb{F}_2^n$; that is, $e_i[i] = 1$ and $e_i[j] = 0$ for $j \ne i$. The vector space spanned by a set of vectors $v_1, \dots, v_k \in \mathbb{F}_2^n$ is called the *span* of those vectors, written $\text{span}(v_1, \dots, v_k)$. Addition over $\mathbb{F}_2^n$ will simply be denoted by $+$. Modular addition over $\mathbb{Z}/k\mathbb{Z}$ will be written as $\oplus$.

**Affine subspaces.** An *affine subspace* of $\mathbb{F}_2^n$ is a subset of $\mathbb{F}_2^n$ of the form $v+S = \{v+s : s \in S\}$, where $v \in \mathbb{F}_2^n$ is an arbitrary vector, and $S \subseteq \mathbb{F}_2^n$ is a linear subspace. An *affine map* $\mathbb{F}^m \to \mathbb{F}^n$ is a map of the form $x \mapsto f(x) + v$, where $v \in \mathbb{F}_2^n$ is an arbitrary vector, and $f: \mathbb{F}^m \to \mathbb{F}^n$ is linear. We will sometimes say that certain objects are affine: for example, affine layers, affine encodings. This means that the relevant object is an affine map.
**Boolean functions.** A Boolean function is a map $F: \mathbb{F}_2^n \to \mathbb{F}_2$. Recall that any Boolean function is functionally equivalent to a polynomial $P$ in $\mathbb{F}_2[X_1, \dots, X_n]$. That is, for all $x \in \mathbb{F}_2^n$, $F(x)$ is equal to the evaluation of $P$ where $X_i$ is substituted with $x[i]$. The polynomial $P$ can be chosen to be square-free: that is, it is a linear combination of monomials of the form $X_1^{\epsilon_1} \cdots X_n^{\epsilon_n}$ with $\epsilon_i \in \{0, 1\}$. In the remainder, in accordance with the literature on algebraic attacks, we only consider square-free polynomials, which are identified with their class in $\mathbb{F}_2[X_1, \dots, X_n]/\langle X_i^2 - X_i \rangle$. Note that the square-free polynomial associated with $F$ is unique, i.e. the space of Boolean functions $\mathbb{F}_2^n \to \mathbb{F}_2$ is isomorphic to the space of square-free polynomials $\mathbb{F}_2[X_1, \dots, X_n]/\langle X_i^2 - X_i \rangle$.

**Algebraic degree.** The algebraic degree of a function $F$ is the degree of the associated (square-free) polynomial. For a $k$-bit function $F: \mathbb{F}_2^n \to \mathbb{F}_2^k$, the algebraic degree of $F$ is by convention the maximum of the algebraic degrees of the bit functions $F[i] : \mathbb{F}_2^n \to \mathbb{F}_2$, $1 \le i \le k$. Throughout this chapter, the term degree exclusively refers to the algebraic degree. The degree of $F$ will be denoted by $\deg(F)$.

### 5.3.2 Round encodings

Consider a block cipher $E$ composed of $r$ rounds:

$$E = E_r \circ \dots \circ E_1.$$

In most block ciphers, the round key is added to the inner state. In that case, given black-box access to a round function $E_i$, it is trivial to recover the round key. Indeed, all round operations are public and invertible, save for key addition. For that reason, white-box compilers typically attempt to obfuscate each round function by composing $E_i$ with a so-called *input encoding* $I_i$, and *output encoding* $O_i$. The encoded round function can be expressed as:

$$\overline{E_i} = O_i \circ E_i \circ I_i.$$

In a typical white-box scheme, consecutive encodings cancel out, that is: $I_{i+1} \circ O_i = \text{Id}$.

The white-box implementation of the block cipher $E$ only gives access to the encoded round functions $\overline{E_1}, \dots, \overline{E_r}$. Taking advantage of the cancellation property $I_{i+1} \circ O_i = \text{Id}$, a honest user can compute:

$$\begin{aligned} \overline{E_r} \circ \dots \circ \overline{E_1}(x) &= O_r \circ E_r \circ E_{r-1} \circ \dots \circ E_1 \circ I_1(x) \\ &= O_r \circ E \circ I_1(x). \end{aligned}$$

If $O_r$ and $I_r$ are not the identity, the previous computation is not equivalent to an encryption of $x$. In most white-box schemes, it is accepted that the input $x$ is encoded as $x = I_1^{-1}(p)$, where $p$ is the plaintext the user wishes to encrypt. Likewise, the output of the encryption is encoded with $O_r$. Non-trivial $I_1$ and $O_r$ are called *external encodings*.

**Implicit representations.** In the actual implementation of the white-box block cipher, the round function may be represented in various ways. In the original CEJO framework, the white-box implementation of $\overline{E}_i$ consists of a series of lookup tables. Given an input $x$ to the encoded round function, the user can compute its output $\overline{E}_i(x)$ directly using those tables (combining them in a predefined way). The recent work of Ranea et al. introduces a different representation of the round function, which they call *implicit representations*.
Implicit representations of the round function provide a series of equations that the user
can solve to compute the round function in the forward direction. That is, given an input
$x$, the user computes its output $y = \bar{E}_i(x)$ by solving an equation system $f(x, y)$ in $y$.
The description of the round function consists of a description of the equation system $f$.
The point of implicit representations is that it allows Ranea et al. to build, for the first
time: (1) white-box implementations with complex non-linear input encodings; and (2)
white-box implementations of ARX ciphers.

Nevertheless, all attacks in this chapter are oblivious to how the encoded round func-
tion is represented—whether it is an implicit representation or otherwise. This is because
our attacks will only require black-box access to the encoded round function. That is,
given $x$ and some arbitrary representation of $\bar{E}_i$, the only thing we need is that it is
possible to efficiently compute $\bar{E}_i(x)$. Note that it is necessary for the honest user to be
able to perform those computations, so this requirement is essentially free. All white-box
implementations that we know of satisfy it. To stress this point once more: attacks in
this chapter do not depend on the type of representation. For that reason, we omit a full
description of implicit representations, and refer the curious reader to [RVP22].

5.3.3 Structural Cryptanalysis

Structural cryptanalysis was introduced by Biryukov and Shamir [BS01]. In the setting of structural cryptanalysis, an attacker is given oracle access to a function $F$. The attacker is able to query the oracle on input $x$, and gets as output $F(x)$.

Assume the function $F$ has some known structure, but the components of that struc-
ture are unknown. For example, $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ is known to be composed of an $n$-bit affine
layer $A_1$, followed by a layer $S$ of $k$ parallel $s$-bit S-boxes with $n = ks$, followed again by
an $n$-bit affine layer $A_2$. We can write $F = A_2 \circ S \circ A_1$: this is the so-called ASA structure.

Given only black-box access to $F(x)$ via the oracle, the goal of the attacker is to find
the hidden components $A_1, S, A_2$. More precisely, since $F$ may not uniquely define $A_1$,
$S, A_2$, the goal of the attacker is to find $k$ $s$-bit S-boxes forming a layer $S'$, and two affine
layers $A'_1, A'_2$, such that $F = A'_2 \circ S' \circ A'_1$.

The previous example corresponds to the ASA structure, which stands for “Affine →
S-box layer → Affine”. The original article by Biryukov and Shamir presents the struc-
tural cryptanalysis of the SASAS structure, including as a sub-component, the structural
cryptanalysis of SAS [BS01]. Later on, the ASASA structure was introduced in [BBK14],
and a structural cryptanalysis of ASASA was given in [MDFK18]. Intuitively, the struc-
tural cryptanalysis of SAS, SASAS and ASASA show that it is exceedingly difficult to
“hide” a layer of S-boxes using linear or affine encodings. In fact, even though many
of the earlier attempts to build white-box schemes were originally broken in an ad-hoc
fashion, it was noted in [DFLM18] that they can be broken generically via the structural
cryptanalysis of ASA.

In this work, we extend structural cryptanalysis to non-linear encodings. Non-linear
encodings will be represented by the letter *I*, for higher-order layer. (We have favored a
vowel, for ease of pronunciation.) If arbitrary non-linear encodings are allowed, structural
cryptanalysis becomes vacuous. To illustrate that point, consider any specific structure $\Sigma$
followed by an arbitrary non-linear encoding *I*. Then the mapping $F = I \circ \Sigma$ contains no
information about $\Sigma$. Indeed, *I* can be equal to $F' \circ \Sigma^{-1}$ for any arbitrary $F'$. In practice,
existing white-box proposals only use low-degree non-linear encodings. Accordingly, in
this work, the letter *I* should be understood as standing for a low-degree nonlinear layer.
In practice, we will often assume that any non-linear layer $I$ is of lower degree than its surrounding layers.

Another subtlety worth noting is that we only assume that $I$ is low-degree in the forward direction. That is, $x \mapsto I(x)$ is of low algebraic degree. The inverse $x \mapsto I^{-1}(x)$ may be of high degree.

Since our attacks also target ARX ciphers, we introduce the letter $M$ to stand for modular addition. The map $M: (\mathbb{F}_{2^n})^2 \to (\mathbb{F}_{2^n})^2$ is defined by $M: (x, y) \mapsto (x, x \oplus y)$, where $\oplus$ denotes modular addition. Since surrounding layers are defined over $\mathbb{F}_{2^n}$, a standard little-endian conversion between $\mathbb{F}_{2^n}$ and $\mathbb{F}_{2^n}$ will implicitly be assumed throughout this work: we will treat quantities in $\mathbb{F}_{2^n}$ and $\mathbb{F}_{2^n}$ as if they belong to the same space. The authors of [RVP22] use the “permuted addition” mapping $M': (x, y) \mapsto (x \oplus y, y)$ instead of $M$. This makes no difference, because the two mappings $M$ and $M'$ are equivalent up to permutations of their inputs and outputs, and permutations are linear maps: the structural cryptanalysis of IMA is equivalent to that of IM'A.

**Remark.** In this work, all mappings within a structure are implicitly assumed to be invertible. This is because we target block ciphers, which are invertible by definition. Nevertheless, the invertibility assumption is mainly for convenience: most attacks can be adapted to dispense with it.

### 5.3.4 Cube attacks

Cube attacks were introduced by Dinur and Shamir [DS09]. We briefly recall the key lemma behind cube attacks, which will be useful in this work.

A starting observation is that for any non-zero $F: \mathbb{F}_2^n \to \mathbb{F}_2$ and any non-zero constant $\delta \in \mathbb{F}_2^n$:

$$ \deg(x \mapsto F(x) + F(x + \delta)) = \deg(F) - 1, $$

with the convention $\deg(0) = -1$. Intuitively, the operation $x \mapsto F(x) + F(x + \delta)$ may be thought of as a differential of $F$ along $\delta$, and affects the degree similarly.

Differentiating $F$ along multiple linearly independent vectors $\delta_1, \dots, \delta_k$ amounts to summing $F$ over the space spanned by the $\delta_i$'s. Since differentiating along each new $\delta_i$ decreases the degree by one, we obtain the key lemma of cube attacks (see [DS09] for a more detailed proof).

**Lemma 5.3.1.** Let $F: \mathbb{F}_2^n \to \mathbb{F}_2$, and let $E$ be an affine subspace of $\mathbb{F}_2^n$ of dimension $\deg(F) + 1$. Then:

$$ \sum_{x \in E} F(x) = 0. $$

In line with the literature on cube attacks, an affine subspace of $\mathbb{F}_2^n$ will sometimes be called a *cube*. Lemma 5.3.1 states that any function of degree $d$ sums to zero over a cube of dimension $d + 1$.

### 5.3.5 Linearization

In the course of this chapter, we will be repeatedly confronted with the problem of solving non-linear equation systems over $\mathbb{F}_2$. This is an NP-complete problem even for quadratic systems, and average-case instances are believed to be intractable. Generic algorithms
(such as Gröbner bases [FP06], or approaches based on the polynomial method [Din21]) yield exponential-time algorithms for the average case.

Nevertheless, when the equations are of degree bounded by $d$ over $n$ unknowns, and the number of available equations is $\Omega(n^d)$, the system can be solved in polynomial time $O(n^{3d})$ using the linearization technique. In effect, solving non-linear systems is only difficult when the number of available equations is limited. Throughout this work, we will use the strategy of reducing algorithmic problems to solving non-linear systems, but always in settings where we can freely sample a number of equations exponential in $n$; in particular, linearization will be applicable.

For the sake of completeness, we briefly sketch the linearization process. A more detailed treatment may be found in [AG11, MDFK18]. Assume we have a system of $m$ independent equations of degree (at most) $d$ over $n$ unknowns $x_1, \dots, x_n$. As discussed in Section 5.3.1, without loss of generality, we can restrict our attention to equations with square-free monomials, i.e. all monomials are of the form $x_1^{\epsilon_1} \cdots x_n^{\epsilon_n}$ with $\epsilon = \epsilon_1 \cdots \epsilon_n$. The fact that the monomials are of degree at most $d$ translates to the fact that at most $d$ of the $\epsilon_i$'s are non-zero. Hence, the number of possible monomials is bounded by:

$$ \sum_{i=0}^{d} \binom{n}{i} \le \left(\frac{ne}{d}\right)^d = O(n^d). $$

For each $\epsilon$, replace all occurrences of the monomial $x_1^{\epsilon_1} \cdots x_n^{\epsilon_n}$ in the equation system by a new unknown $t_\epsilon$. There are $O(n^d)$ such unknowns $t_\epsilon$, and the equation system is now linear in the $t_\epsilon$'s. Hence, we can solve the system using any linear system solving algorithm. If we use Gaussian elimination, the time complexity of this step is $O(n^{3d})$. We obtain the values of all $t_\epsilon$'s.

It remains to deduce the values of the original variables $x_i$'s from the $t_\epsilon$'s. Recall that $e_i \in \mathbb{F}_2^n$ is defined by $e_i[i] = 1$ and $e_i[j] = 0$ for $j \ne i$. If all $t_{e_i}$ appear in the equation system, recovering the $x_i$'s is trivial, because $x_i = t_{e_i}$. If the equation system has specific properties such that the $t_{e_i}$'s do not appear in the equations (for example, if the equations are homogeneous of degree $d$), some extra work is needed. Nonetheless, in practice, this step incurs a negligible cost in time complexity compared to linear system solving in the previous step. The reader is referred to [AG11, MDFK18] for detailed algorithms.

## 5.4 Structural cryptanalysis of ISA

In [RVP22], the authors introduce implicit representations of encoded round functions. This allows the authors the freedom to use non-linear input encodings, but for technical reasons, output encodings must be affine (see [RVP22] for the reasoning). In this section, we show that this approach cannot hide an inner S-box layer. To that end, we give a structural cryptanalysis of the ISA structure.

### 5.4.1 Problem statement

Let $I: \mathbb{F}_2^n \to \mathbb{F}_2^n$ be a non-linear map of degree $d$. Let $S$ be a layer of $k$ (not necessarily identical) $s$-bit S-boxes, with $n = ks$. For simplicity, S-boxes are assumed to be of maximal degree $s-1$. (The attack can easily be adapted otherwise, but the cost of the attack grows with $s$, so $s-1$ is the worst case.) Let $A: \mathbb{F}_2^n \to \mathbb{F}_2^n$ be an affine mapping. Let $F = A \circ S \circ I$. The goal of the attacker is to find a non-linear layer $I'$, an affine layer $A'$, and a layer $S'$ of $k$ parallel $s$-bit S-boxes such that $F = A' \circ S' \circ I'$.
## 5.4.2 Equivalent keys

Since $F$ does not uniquely define the triple $(I, S, A)$, the goal of the attacker is to find a triple $(I', S', A')$ such that $F = A' \circ S' \circ I'$, as stated above. Such a triple is called an *equiv-alent key*. A few remarks about equivalent keys will prove helpful for the cryptanalysis of ISA.

First, we can freely assume that $A'$ is a linear layer, rather than an affine layer. To see this, take an arbitrary equivalent key $(I, S, A)$ with an affine layer $A(x) = L(x) + c$, for some linear map $L : \mathbb{F}_2^n \to \mathbb{F}_2^n$ and constant $c \in \mathbb{F}_2^n$. Then the triple $(I, S', L)$ with $S'(x) = S(x) + L^{-1}(c)$ is also an equivalent key. This follows from the fact that both triple compute the same function, and that $S'$ can still be represented as $k$ parallel $s$-bit S-boxes. In the remainder, we assume without loss of generality that $A$ is linear.

In fact, the last linear layer $A$ is only defined as far as determining the output space of each S-box. More precisely, let $V_i = \text{span}(e_{s(i-1)+1}, \dots, e_{s(i-1)+s})$ be the vector space spanned by the bits of the $i$-th S-box. Let $L_i$ be an arbitrary invertible linear map $V_i \to V_i$. Given an equivalent key $(I, S, A)$, we can freely compose the output of the $i$-th S-box with $L_i$, and compose $A$ with $L_i^{-1}$, to obtain another equivalent key. Thus, we cannot hope to recover more information from $A$ than the output space $A(V_i)$ of each S-box through $A$.

Conversely, if we know the spaces $A(V_i)$, then for each $A(V_i)$, we can arbitrarily pick a basis of the space, then assign the $k$-th bit of the $i$-th S-box to the $k$-th element of that basis. Letting $L'$ be the map computed in that manner, $L^{-1} \circ F = (L^{-1}A) \circ S \circ I$ has the IS structure, so we have effectively peeled off the linear layer $A$. Indeed, $L^{-1}A$ operates independently on each $V_i$, and hence can be folded into the S-box layer.

In conclusion, in order to peel off the $A$ layer, it is necessary and sufficient to recover the output spaces $A(V_i)$ of each S-box through $A$. Note that the spaces $A(V_i)$ can be recovered in any order. Indeed, given an equivalent key $(I, S, A)$, we are free to permute the S-boxes, up to applying the inverse permutation to $I$ and $A$ (which does not affect their degree).

## 5.4.3 Peeling off the A layer: from ISA to IS

Our approach is similar to [MDFK18]. Consider two bits $b_1$ and $b_2$ at the output of two *distinct* S-boxes in the mapping $S \circ I$. When viewed as a function of the input $x$ of $S \circ I$, each of those bits is of degree at most $d(s-1)$. Hence their product $b_1b_2$ is of degree at most $2d(s-1)$. On the other hand, let $b_{1'}$ denote a bit at the output of the *same* S-box as $b_1$. Then by [MDFK18, Lemma 2], the product $b_1b_{1'}$ is of degree only at most $d(s-1)$.

The idea of the attack is to detect this difference in degree through the last affine layer $A$. For that purpose, for $i = 1, 2$, define $\lambda_i \in \mathbb{F}_2^n$ such that:

$$b_i(x) = \sum_{j=1}^{n} \lambda_i[j] F(x)[j] = \langle \lambda_i | F(x) \rangle.$$

Such $\lambda_i$'s necessarily exist, because $b_1$ and $b_2$ are bits at the output of $S \circ I = A^{-1} \circ F$, and $A^{-1}$ is linear (because we have assumed that $A$ is linear).

By Lemma 5.3.1, the fact that $b_1b_2$ is of degree at most $d(s-1)$ implies that $b_1b_2$ sums to zero over any cube of dimension $d(s-1)+1$. Let $C$ be such a cube. We obtain the equation:

$$\sum_{x \in C} \langle \lambda_1 | F(x) \rangle \cdot \langle \lambda_2 | F(x) \rangle = 0. \qquad (5.1)$$
Note that $C$ can be freely chosen by the attacker. Hence, all quantities $F(x)$'s in (5.1) can be computed by querying the $F$ oracle. The only unknowns in the equation are the $\lambda_i[j]$'s.

Observe that (5.1) is an equation of degree 2 over the $\lambda_i[j]$'s. We can sample one new equation for each choice of cube $C$ of dimension $d(s-1)$. Provided $d(s-1) < n$, there are many more choices of cubes than quadratic monomials, hence the system can be solved by linearization (cf. Section 5.3.5).

Solving the system yields pairs of linear masks $\lambda'_1, \lambda'_2$ such that $\langle \lambda'_1 | F(x) \rangle$ and $\langle \lambda'_2 | F(x) \rangle$ are equal to two bits (or linear combination of bits) at the output of the same S-box. Taking one such solution $\lambda'_1, \lambda'_2$, fixing $\lambda_1 = \lambda'_1$ in (5.1), and solving for $\lambda_2$, we can recover the linear space spanned by all other bits at the output of the same S-box. In the notation of Section 5.4.2, we recover the output space $A(V_i)$ of one S-box.

By repeating the same process, we eventually recover the output spaces $A(V_i)$ for $1 \le i \le k$, i.e. we obtain the output space of all S-boxes. Following the discussion in Section 5.4.2, this is enough to peel off the last linear $A$ of $F$. We are left with a new structural cryptanalysis problem of the form $F' = S \circ I$.

### 5.4.4 Recovering the remaining layers: structural cryptanalysis of IS

In this section, we are given $F = S \circ I$, with the promise that $S$ is a layer of $k$ parallel $s$-bit S-boxes, and $I: \mathbb{F}_2^n \to \mathbb{F}_2^s$ is of degree at most $d$. The goal is to find $S'$, $I'$ with the same features as $S$, $I$, such that $F = S' \circ I'$.

Let $S_i$ denote the $i$-th S-box in the layer $S$. Since we are able to observe separately the outputs of each S-box $S_i$, let $F_i$ denote the restriction of $F$ to the bits at the output of the $i$-th S-box. That is, $F_i = (F[(s-1)i+1], \dots, F[(s-1)i+s])$. Likewise, let $I_i$ denote restriction of $I$ to the $i$-th S-box. Then $F_i = S_i \circ I_i$. Observe that recovering an equivalent key $S'$, $I'$ for $F$ is exactly equivalent to recovering $S'_i: \mathbb{F}_2^s \to \mathbb{F}_2^s$ and $I'_i: \mathbb{F}_2^n \to \mathbb{F}_2^s$ of degree at most $d$ such that $F_i = S'_i \circ I'_i$, for each S-box separately. As a consequence, from now on, we restrict our attention to finding $S'_i$, $I'_i$ given black-box access to $F_1$. To do so, we borrow an idea from [BS01].

For each $x \in \mathbb{F}_2^s$, let $t_x = S^{-1}(x)$. We view the $t_x$'s as unknown. Since $I$ is of degree at most $d$, by Lemma 5.3.1, for any cube $C$ of dimension $d+1$, we get an equation:

$$ \sum_{x \in C} t_{F(x)} = 0. $$

Thus, by sampling sufficiently many cubes, we obtain a linear system of equations on the $t_x$'s, which we can solve to obtain $S'_1^3$. We can then let $I'_1 = (S'_1)^{-1} \circ F_1$.

### 5.4.5 Attack complexity

The complexity of the attack is determined by the number of bits $n$ of the cipher's internal state, the number of bits $s$ of the S-boxes, and the degree $d$ of the input encoding. In parameter regimes that correspond to typical real-world scenarios (e.g. AES parameters), the complexity bottleneck is to solve Equation (5.1) (Section 5.4.3). This amounts to

<footnote n="3">³Note that any $S'_1$ of the form $S_1 \circ B$ for affine $B$ is a solution. One may wonder if the attack might recover other solutions, but in practical experiments, this does not appear to be the case [BS01].</footnote>
solving a linear system in $O(n^2)$ unknowns over $\mathbb{F}_2$. This costs roughly $O(n^6)$ operations (using Gaussian elimination for simplicity; the exponent can be reduced using more advanced matrix inversion algorithms). In practice, note that this quantity counts the number of bit operations, whereas linear algebra over $\mathbb{F}_2$ can naturally take advantage of word-level operations, resulting in a lower complexity. A secondary bottleneck is to collect $O(n^2)$ cubes to derive the equations of the previous system. Each cube is of dimension $d(s-1)$, resulting in a total of $2^{d(s-1)}$ calls to the encoded round function. Both computation must be performed for each bit. In the end, the total complexity is $O(n^7 + n^2 2^{d(s-1)})$. Observe that for AES parameters and reasonable $d$ (say, $d < 5$), the first term $O(n^7)$ dominates: linear system solving is the bottleneck.

5.4.6 Application to white-box key recovery

The attacks presented in previous sections belong to the family of structural attacks. The output of the attack is an equivalent key, in the sense of structural attacks: that is, for an ISA structure, suitable non-linear layer $I'$, S-box layer $S'$, and affine layer $A'$, such that the function $F$ under attack satisfies $F = A' \circ S' \circ I'$. When applying this technique to attack a white-box encoded round function with the appropriate structure (e.g. ISA), a white-box attacker (as opposed to a structural attacker) would like to go one step further, and recover the encryption key.

That goal is made possible by the fact that the white-box attacker knows more information than the structural attacker. Contrary to the structural attacker, the white-box attacker knows the full description of the round function, including specific descriptions of the S-boxes and linear layer. The only information the white-box attacker does not have are the round encodings, and the round keys. Compared to the structural attacker, the white-box attacker also has a more specific goal, which is to recover the round keys (and from there the overall encryption key).

This section is to bridge the gap between the two models, and show how a key-recovery
attack in the white-box model can be deduced from a structural attack.

**Reduction to a simple problem**

At the outcome of the structural attacks from Section 5.4.4, the attacker has access to the input and output of every S-box, up to affine equivalence. More precisely, for each S-box $S$ appearing in a round function of the underlying block cipher, the attacker can read the input and output of the S-box up to fixed affine encodings (fixed in the sense that they are always the same for a given S-box; they need not be the same between different S-boxes). Note that S-boxes belonging to the same round may also be permuted, in the sense that the structural attack may not present the S-boxes in the same order that they would be presented in a traditional description of the underlying cipher. In addition to reading the input and output of S-boxes up to affine equivalence, the attacker may also choose to modify those values at will, and observe the effect on later encryption rounds.

Thus, building a white-box attacker from a structural attacker can be neatly reduced
to a stand-alone problem: given full read and write access to the input and output of
every S-box in a particular SPN cipher, up to affine equivalence for each S-box, and up to
permutation of the S-boxes in a given round, recover the round keys. (If the key schedule
is invertible, recovering the round keys is equivalent to recovering the encryption key.)
## Solving the problem

We now explain how to solve the problem outlined just above. We note that it is not particularly difficult. Intuitively, this is because the “heavy lifting” was done by the structural attack: deducing a white-box key-recovery attack from the structural attack is relatively straightforward.

Let $S_i$ be a particular S-box recovered by the structural attack. The white-box attacker knows the actual S-box $S_{orig}$ in the original SPN block cipher (assuming for simplicity that all S-boxes are the same). Hence, $S_i$ and $S_{orig}$ are affine-equivalent: there exist affine maps $A_i, B_i$ such that $S_i = B_i \circ S_{orig} \circ A_i$. Given as input $S_i$ and $S_{orig}$, recovering suitable $A_i, B_i$ is the so-called *affine equivalence problem*. Efficient algorithms for typical S-box sizes are given in [BCBP03, Din18].

The affine equivalence problem may have more than one solution: there may exist $(A_i, B_i) \neq (A'_i, B'_i)$ such that $S_i = B_i \circ S_{orig} \circ A_i = B'_i \circ S_{orig} \circ A'_i$. In that case, we have:

$$S_{orig} = (B_i^{-1} \circ B'_i) \circ S_{orig} \circ (A'_i \circ A_i^{-1}).$$

The pair $(B_i^{-1} \circ B'_i, A'_i \circ A_i^{-1})$ is said to be an *affine self-equivalence* of $S_{orig}$.

If $S_{orig}$ admits only the trivial self-equivalence ($\mathit{Id}, \mathit{Id}$), the affine equivalence problem has a single solution. After computing that solution for each S-box using the efficient algorithms from [BCBP03, Din18], the attacker has (read and write) access to the *plaintext* input and output of every S-box. The only remaining unknown is the permutation of the S-boxes in a given round. At this stage, recovering the round key for any real-world cipher is trivial.<fnref n="4" />

For an S-box sampled uniformly from permutations on a given number of bits, with high probability, there is no self-equivalence beside the trivial one, and we are done. However, we note that specific ciphers may use S-boxes with special non-random features, whose self-equivalence group may be non-trivial. This is in particular the case of the AES S-box, which is affine-equivalent to modular inversion in $\mathbb{F}_{2^8}$, hence has as many self-equivalences as modular inversion. Concretely, the AES S-box has $2040 \approx 2^{11}$ self-equivalences [BCBP03]. Nevertheless, recovering the encryption key from read-write access to all S-boxes up to self-equivalence is still an easy problem. An algorithm for that purpose is given in [DFLM18, Section 4.2].

## 5.5 Structural cryptanalysis of IMA

As we have seen in the previous section, the introduction of implicit representations of round functions in [RVP22] makes it possible to create non-linear input encodings for SPN cipher: the ISA structure. Another benefit of implicit representations, and their most novel application, is that they make it possible to apply white-box techniques to ARX ciphers, which was not possible before. More precisely, the authors show how to hide one layer of modular addition, which is the non-linear building brick of ARX ciphers. (For clarity, “linearity” here should be understood as linearity over $\mathbb{F}_2^n$; modular addition in $\mathbb{Z}/k\mathbb{Z}$ is of course $\mathbb{Z}/k\mathbb{Z}$-linear.)

<footnote n="4">⁴We do not propose a way to do so generically here. This is because the permutation symmetry between S-boxes might be broken only by the key schedule. Since the key schedule of a block cipher can take an arbitrary form, it does not lend itself to a generic structural analysis. On the other hand, for any concrete block cipher, if the cipher leaks plaintext values at the outcome of every S-boxes layer in every round, up to permutation of S-boxes, we contend that breaking the cipher is quite easy.</footnote>
As earlier, the main limitation remains that only input encodings can be non-linear; the techniques of [RVP22] do not support non-linear output encodings. The construction of [RVP22] thus amounts to an IMA structure. In this section, we give a structural crypt-analysis of IMA. The attack we present also applies to AMA. This shows that the use of a low-degree input encoding is not enough to hide an inner modular addition. At the end of the section, we discuss how the structural cryptanalysis result translates to a white-box key-recovery attack on white-box ARX ciphers.

5.5.1 Problem statement

Let $I: \mathbb{F}_2^n \to \mathbb{F}_2^n$ be a non-linear map of degree $d$. We allow the case $d=1$ in the attack, i.e. the attack also applies to affine input layers. Let $M: (x,y) \mapsto (x, x \oplus y)$ be the modular addition addition, as discussed in Section 5.3.3.

Let $A: \mathbb{F}_2^n \to \mathbb{F}_2^n$ be an affine mapping. Let $F = A \circ M \circ I$. The goal of the attacker is to find a non-linear layer $I'$ of degree at most $d$, and an affine layer $A'$, such that

$F = A' \circ M \circ I'$.

5.5.2 Equivalent keys

Our algorithm for the structural cryptanalysis of IMA will sometimes make guesses. For instance, at the end of Section 5.5.3, the algorithm will identify a few possible candidates for the map $I[2n - 1]$. In those cases, the algorithm will simply guess that one of the candidates is the correct one. The attack continues as if the guess was correct. At some later points in the attack, the algorithm will test that certain vector spaces have the right dimension. If that is not the case, it reveals that one of the previous guesses was wrong. The algorithm then simply backtracks to the latest guess for which not all possibilities have been exhausted, and takes a different guess.

It is important to note that whenever the algorithm reaches a branching point (i.e. a guess), it is often the case that multiple choices will be correct. This is because the solution to the structural analysis problem is not unique: modular addition admits many affine self-equivalences [RVP22]. Thus, our algorithm has two types of branching points. Some branching points will arise from the fact that there are multiple solutions: all choice are equally correct, and will not lead to any backtracking. Other branching points will only have one correct choice, and will lead to backtracking if the guess was incorrect. Our experiments show that the same branching point in the algorithm can be of either type, depending on the problem instance and previous choices. This is because equivalent keys for modular addition have a rather complex structure: see [RVP22, Section 5.2]. Interestingly however, our algorithm does not care about the exact structure of equivalent keys, or about which branching point is of which type: it simply makes guesses when necessary, and backtracks when it encounters an inconsistency. In practical experiments, incorrect choices lead to inconsistencies quickly (typically at the next consistency check), so the performance cost of wrong choices is low.

5.5.3 Peeling off the | layer: from IMA to MA

Step 1: recovering affine bits

A starting point is that most bits at the output of the modular addition $M: (x,y) \mapsto (x, x \oplus y)$ are affine in the input of $M$: namely, the bits of $x$, and the last bit $(x \oplus y)[n]$ of
$x \oplus y$, which is equal to $x[n] + y[n]$. (Recall that modular addition is denoted by $\oplus$, while $+$ denotes addition over $\mathbb{F}_2$.) The image of the space of affine bits through the outer affine layer $A$ can be detected using the fact that those bits have degree $d$ in $F = A \circ M \circ I$, whereas other bits have higher degree.

To do so, take any cube $C$ of degree $d+1$ over the input of $F$. Suppose $\lambda_0 \in \mathbb{F}_2^{2n}$ is such that $\langle \lambda_0 | F \rangle$ is equal to a linear combination of affine bits before the last affine layer (formally: $\langle \lambda_0 | F \rangle = \langle \mu_0 | M \circ I \rangle + \gamma_0$ where $\gamma_0$ is a constant and $\mu_0[i] = 0$ for $i \in [n+1, \dots, 2n-1]$). Then the following equation holds:

$$ \sum_{c \in C} \langle \lambda_0 | F(c) \rangle = 0 \quad \text{whenever } \dim(C) = 2. \qquad (5.2) $$

Equation (5.2) yields a linear constraint on $\lambda_0$, viewed as a vector of binary unknowns $\lambda_0[1], \dots, \lambda_0[2n]$. Each choice of $C$ yields an equation. Sampling sufficiently many $C$'s allows us to solve the system and recover $\lambda_0$. More exactly, since $\lambda_0$ is not unique, we recover the space $S_0$ of dimension $n+1$ of all $\lambda_0$'s that correspond to affine bits of $M$, in the sense given earlier.

### Step 2: recovering $(x \oplus y)[n-1]$

The only bit of degree 2 in $M$ is $M[2n-1]$, i.e. the $n-1$-th bit of $x \oplus y$. Hence the only bit of degree $2d$ in $M \circ I$ is $(M \circ I)[2n-1]$. If $\lambda_1$ now denotes the linear mask corresponding to $M[2n-1]$ through the last affine layer $A$ (that is: $\langle \lambda_1 | F \rangle = (M \circ I)[2n-1] + \gamma_1$ where $\gamma_1$ is a constant), then $\lambda_1$ satisfies the following equation:

$$ \sum_{c \in C} \langle \lambda_1 | F(c) \rangle = 0 \quad \text{whenever } \dim(C) = 2d + 1. \qquad (5.3) $$

As before, each $C$ yields an equation. By sampling sufficiently many $C$'s, we can solve the system. However, the system is not satisfied only by $\lambda_1$: all masks $\lambda_0$ recovered in Section 5.5.3 also satisfy it. Solving (5.3) yields a solution space $S_1$ of dimension $n+2$, spanned by $S_0$ and $\lambda_1$. (This, and other steps of the attacks, has been confirmed experimentally). For now, to recover $\lambda_1$, we simply sample an element of $S_1 \setminus S_0$. This can be done by taking the non-zero element of the quotient $S_1/S_0 \sim \mathbb{F}_2$, and lifting it back to $S_1$. (Alternatively, because half of the elements of $S_1$ are in $S_0$, sampling a uniformly random element of $S_1$, and testing that it does not belong to $S_0$, succeeds within two tries in expectation.)

Note that the previous computation does not “truly” recover $\lambda_1$; rather, it recovers $\lambda'_1 = \lambda_1 + \lambda_0$ for some $\lambda_0 \in S_0$. This is good enough for our next computation. We have:

$$ \langle \lambda'_1 | F \rangle = \langle \lambda_1 | F \rangle + \langle \lambda_0 | F \rangle = (M \circ I)[2n-1] + \langle \mu_0 | M \circ I \rangle + \gamma_1 $$

where $\langle \mu_0 | M \rangle$ is linear, while $M[2n-1]$ has degree two. On the other hand, observe that:

$$ M(x, y)[2n-1] = (x \oplus y)[n-1] = x[n]y[n] + x[n-1] + y[n-1] $$

where the first term is the carry of the modular addition. Reinjecting into the previous computation, we get:

$$ \langle \lambda'_1 | F \rangle = I[n]I[2n] + I[n-1] + I[2n-1] + \langle \mu_0 | M \circ I \rangle + \gamma_1. \qquad (5.4) $$
Let $P$ denote the polynomial of degree $2d$ in $\mathbb{F}_2[X_1, \dots, X_{2n}]/\langle X_i^2 - X_i \rangle$ coinciding with $\langle \lambda'_1 | F \rangle$. Because $\lambda'_1$ is known to the attacker, and $d$ is small (typically, in [RVP22], $d=2$), $P$ can be computed explicitly by the attacker. Looking at the right-hand side of Equation (5.4), the only term of degree $2d$ is $I[n]I[2n]$; other terms are of degree at most $d$. Let $B$ and $C$ denote the polynomials of degree $d$ corresponding to $I[n]$ and $I[2n]$ respectively. Let $A$ denote the polynomial of degree $d$ corresponding to the other terms of the expression. Then Equation (5.4) can be rewritten as:

$$P = A + B \cdot C \tag{5.5}$$

where $A, B, C$ are of degree $d$. This leads to the following problem.

**Factorization Problem.** Given $P \in \mathbb{F}_2[X_1, \dots, X_{2n}]/\langle X_i^2 - X_i \rangle$ such that $P = A+B \cdot C$, where $\deg(A) = \deg(B) = \deg(C) = d$, find $A', B', C'$ with $\deg(A') = \deg(B') = \deg(C') = d$ such that $P = A' + B' \cdot C'$.

In other words, we want to solve a particular kind of structural cryptanalysis problem, for the structure $P = A + B \cdot C$. As is often the case with structural cryptanalysis, the solution is not unique: if $(A, B, C)$ is a solution, then so is $(A + B, B, B + C)$, for instance. In general, any two linearly independent vectors in the linear span of $B, C, 1$ can be chosen for $B'$ and $C'$. Unless $P$ has a special structure, there are no other solutions (confirmed by experiments).

In fact, the factorization problem above was already considered in [MDFK18], in the special case $d=2$. The authors of [MDFK18] give an efficient algorithm for that case. A polynomial-time algorithm for the case of arbitrary constant $d$ can be found in [Bha14]. In fact, the work of [Bha14] applies to a much more general class of problems, and is quite complex as a result, and less efficient in practice. In Section 5.7, we generalize the algorithm from [MDFK18] for $d > 2$, which suffices for our purpose.

At the outcome of running either one of the previous algorithms on $\langle \lambda'_1 | F \rangle$, we recover the linear span of $I[n], I[2n], 1$, viewed as polynomials in their inputs. Up to the contribution of 1 in that span, which only affects the constant in the polynomial, $I[n]$ can be recovered by observing that it also lies in the span of polynomials generated by elements of $S_0$. For $I[2n]$, we simply take one of the other two non-zero elements in the span of $I[n], I[2n]$, which can be either $I[2n]$ or $I[2n] + I[n]$ (again, up to the constant 1). If we happened to pick $I[2n] + I[n]$, our guess was wrong. Nevertheless, we continue with the rest of the attack. As discussed in Section 5.5.2, the algorithm will backtrack to this point if it detects an inconsistency later on.

**Step 3: recovering the $(x \oplus y)[i]$'s**

In the previous step, we isolated the penultimate bit of the modular addition $(x \oplus y)[n-1]$, by using the fact that it is the only bit of degree two in $M$. This required using cubes of dimension $2d+1$.

We then factorized the polynomial expression of that bit to obtain the polynomial expressions of $I[n]$ and $I[2n]$.

A simple approach would be to repeat this process: starting from the observation that $(x \oplus y)[n-i]$ is the only bit of degree $i+1$ in $M$, for $i > 1$, we could isolate each bit and somehow factorize it, as before. This runs into two issues. First, to isolate a bit of degree $i+1$, we would need to sum over cubes of dimension $i+2$. The number of summands grows exponentially with $i$, and $i$ goes up to $n$, so this is not feasible. Second,
the polynomial expression of $(x \oplus y)[n-1]$ is simple, which led to a simple factorization problem; but for $(x \oplus y)[n-i]$, the polynomial expression becomes increasingly complex as $i$ grows, and so would the associated factorization problem.

We use a different approach, based on the following observation. Consider for a moment the expression $x \oplus y = z$ over $\mathbb{F}_2^n$. Let $c_i$ denote the value of the carry coming into the $(n-i)$-th bit of $x \oplus y$, that is:

$$ (x \oplus y)[n-i] = x[n-i] + y[n-i] + c_i. $$

The a straightforward computation shows that the following recursive relation holds:

$$ c_i = x[n-i-1]y[n-i-1] + c_{i-1}(x[n-i-1] + y[n-i-1]). $$

Hence, if we know $c_{i-1}$, then we have:

$$ (x \oplus y)[n-i] = x[n-i-1]y[n-i-1] + c_{i-1}(x[n-i-1] + y[n-i-1]) + x[n-i] + y[n-i]. \quad (5.6) $$

Going back to our problem, we proceed by induction. For the $i$-th inductive stage, assume we have recovered $I[n-j]$ and $I[2n-j]$ for $j \le i$. Note that Step 2 in Section 5.5.3 initialized that induction for $i=0$. Then using our knowledge of $I[n-j]$ and $I[2n-j]$ for $j \le i$, we know the inputs of the last $i+1$ inputs of the modular addition $M$ in $F$. This means that for any given input $v$ of $F$, we can compute the value of the carry $c_{i-1}(v)$ coming into $(M \circ I(v))[2n-i-1]$. Using (5.6), we can thus write:

$$ (M \circ I(v))[2n-i] = B(v)C(v) + c_{i-1}(v)A(v) + D(v) \quad (5.7) $$

where $A, B, C, D$ have algebraic degree $d$.

Equation (5.7) may seem difficult to exploit, since it depends on $c_{i-1}$, which may be of high degree. For that reason, we no longer rely on cubes, and propose a different technique. For $v \in \mathbb{F}_2^n$ and $S = \{s_1, \dots, s_\ell\} \subseteq [1, n]$, let $v_S = v[s_1] \dots v[s_\ell]$. For $k \le n$, let $v^{\le k}$ denote the vector of length $\sum_{i=0}^k \binom{n}{i}$ whose coordinates are equal to $v_S$ for each $S \subseteq [1, n]$ of cardinality at most $\ell$ (with the convention $v_\emptyset = 1$). Observe that a map $f(v)$ is of algebraic degree at most $k$ if and only if $f(v)$ is a linear combination of elements of $v^{\le k}$. (Algebraically, we are moving into the tensor space $T^{\le k}(\mathbb{F}_2^n)$, but we prefer to describe our algorithm in more concrete terms.) Applying this observation to $A$ in (5.7), there exists $\lambda_A$ such that $A(v) = \langle \lambda | v^{\le d} \rangle$, and likewise for $D$, and for the product $B \cdot C$. Reinjecting into (5.7), we have:

$$ (M \circ I(v))[2n-i] = \langle \lambda_{B \cdot C} | v^{\le 2d} \rangle + \langle \lambda_A | c_{i-1}(v) \cdot v^{\le d} \rangle + \langle \lambda_D | v^{\le d} \rangle. \quad (5.8) $$

Given $v$, the attacker can compute all elements $v^{\le 2d}$, $v^{\le d}$, and $c_{i-1}(v) \cdot v^{\le d}$ on the right-hand side of (5.8). Here, we use the fact that $c_{i-1}(v)$ can be computed for any $v$ by induction hypothesis, discussed earlier. Letting $\lambda_i$ be such that $\langle \lambda_i | F \rangle = (M \circ I(v))[2n-i]$, we have:

$$ \langle \lambda_i | F \rangle = \langle \lambda_{B \cdot C} | v^{\le 2d} \rangle + \langle \lambda_A | c_{i-1}(v) \cdot v^{\le d} \rangle + \langle \lambda_D | v^{\le d} \rangle. \quad (5.9) $$

Each choice of $v$ yields a new equation of this form. We obtain a linear system in the $\lambda_*$'s, viewed as vectors of binary unknowns. Without loss of generality, we set $\lambda_D = 0$, since its coefficients can be folded in $\lambda_{B \cdot C}$. Solving the system, and discarding the subspaces where either $\lambda_A$ is zero, or the coefficients of degree higher than $d$ in $\lambda_{B \cdot C}$ are zero, yields a solution. In fact, experiments show that the solution space is sometimes of dimension
2, even for valid solution, which requires a guess. On the other hand, if the solution space has dimension 0, it reveals that one of our previous guesses was wrong, and we backtrack to a previous guess, as discussed in Section 5.5.2.

At the outcome of this computation, we recover $\lambda_{B,C}$, which reveals the coefficients of $B \cdot C + D$. Recovering the coefficients of $B$ and $C$ from there is a new instance of the factorization problem from Section 5.5.3, for the same degree $d$. Solving the problem yields the coefficients of $B$ and $C$, i.e it reveals the polynomial expressions of $I[n - i]$ and $I[2n - i]$. This sets us up for the next stage of the induction. Eventually, all $I[i]$ are recovered: we have peeled off the initial $I$ layer.

**Remark.** Taking a step back, the use of the inductive definition of modular addition via carries allows the attack to only have to consider equations of degree at most $2d = O(d)$, as opposed to $O(nd)$ for a naive approach. The technique we use involving the vectors $v \le k$ can be viewed as a variant of the linearization technique from Section 5.3.5. In essence, what we show is that if we have equations that are of low degree with respect to some input $v$, except for some term in the equation (here, $c_{i-1}(v)$) that may be of high degree, but whose value can be computed by the attacker, then it is still possible to solve the equation system with a linearization-like approach. Generalizing this idea, while normal linearization techniques allow an attacker to solve a system of low degree, given enough equations, our variant allows to solve a system of equations that are low degree in $v$ and in other quantities $f_i(v)$, as long as the $f_i$'s are known—even if the equations may be of arbitrarily high degree when expressed using only $v$.

### Step 4: wrapping up the attack

At the outcome of the previous step, we have removed the initial non-linear layer $I$, and are left with the structural cryptanalysis of MA. Contrary to the case of SA, the cryptanalysis of MA is trivial, since $M$ is a fixed function. To recover $A$, it suffices to compose the function with $M^{-1}$.

## 5.5.4 Attack complexity

The complexity of the attack is determined by the number of bits $n$ of the cipher's internal state, and the degree $d$ of the input encoding. Similar to Section 5.4.5, the complexity bottleneck comes from solving Equation (5.9). This amounts to solving a linear system in $\binom{n}{2d} \le n^{2d}$ unknowns over $\mathbb{F}_2$. Using Gaussian elimination for simplicity, this costs $O(n^{6d})$ bit operations. Since this must be repeated for each of the $n/2$ bits targeted by the attack, the total complexity is $O(n^{6d+1})$. To provide some perspective, note that simply representing an arbitrary input layer of degree $d$ requires $O(n^d)$ bits. (Implicit representations in [RVP22] are also of size $O(n^d)$.)

## 5.5.5 Application to white-box key recovery

In a white-box key-recovery scenario, two aspects of the attack differ.

First, it is usually the case that the round function of an ARX cipher involves several modular additions. Our technique targets the case of a single modular addition. The SPECK cipher contains a single modular addition, and our structural cryptanalysis directly applies. More generally, it is not clear how the implicit encoding technique of [RVP22] would perform for more complex round functions. It would likely be implemented
separately for each modular addition, which would again enable our attack. Even if it
did not, we suspect that very similar techniques would apply. In any case, our struc-
tural cryptanalysis problem focuses on the simplest and cleanest case of a single modular
addition. This also avoids becoming dependent on a specific round function.

A second point where the structural cryptanalysis approach differs from white-box
key-recovery is that, as in Section 5.5.5, a white-box attack aims to recover a secret key,
not just equivalent descriptions of inner encryption layers. In the case of modular addition,
at the outcome of structural cryptanalysis, we recover an equivalent key. In practice, our
attack recover the input and output of the modular addition layer *up to self-equivalences
of the modular addition*. An (affine) self-equivalence of modular addition is a pair of affine
layers (*A*, *B*) such that *M* = *B* ◦ *M* ◦ *A*. By executing the cipher on a given input, and
using the output of our structural cryptanalysis, we can observe the values of bits after
the modular addition layer, for every round, up to self-equivalence. If it was not up to
self-equivalence, recovering round keys would be trivial, since all operations other than
key addition are public and invertible.

Similar to the treatment in Section 5.5.5, applying the structural cryptanalysis result
to white-box key recovery comes down to solving the following problem. Assume we have
access to the full inner state of the cipher after every modular addition layer, but those
inner states may be modified by an affine map arising from a self-equivalence (always
the same for a given round). The goal is to recover the encryption key. The problem
may appear difficult, because modular addition has many self-equivalences. But in fact,
those self-equivalences mainly differ in the values of the first few and last few bits of the
modular addition output (*x* ⊕ *y*). For the vast majority of bits, namely (*x* ⊕ *y*)[*i*] for
2 < *i* < *n* − 2, the self-equivalent encodings behave like the identity matrix, up to the
addition of a vector confined to a space of dimension 4 (see [RVP22, Section 5.2]). Recall
that this information is available at every round. Recovering the secret key from there
is not amenable to a general analysis, since it depends on the specific key schedule of a
cipher. Nevertheless, we believe that for any concrete block cipher, it is not difficult to
recover the round keys given that much leakage.

**5.6 Practical validation**

As noted in Section 5.4.3, our attacks on ISA are similar in spirit to the attack on ASASA
in [MDFK18]. On the other hand, the attack on IMA is quite new, and relies on a
backtracking mechanism whose practical behavior is not obvious. For that reason, we
have decided to fully implement the IMA attack in the case $d = 1$, aiming especially to
observe the behavior of the backtracking process. Our implementation is available in the
appendix.

The implementation is in the Sage language (release 9.8), an open-source Python
variant suited to formal computation. The implementation can be run simply with the
command `sage full.sage`. It generates a random instance of the problem for $n$ bits,
where $n$ can be specified in the `full.sage` file. We have run the program up to $n = 64$
bits. The attack always succeeds, and does so on a laptop in 95 minutes on inputs of size
$n = 64$ bits.

Our main observation is that (to our surprise), the attack never needs to backtrack
more than one step. To elaborate on that point, recall that the algorithm from Section 5.5
needs to make some choices when recovering each bit of the input layer, due to the fact that
the Factorization problem (in Section 5.5.3) has multiple solutions. What our experiments observe is that any time a choice is incorrect (i.e., the choice will not lead to a correct solution for the overall problem), an inconsistency is detected at the very next step of the computation. That is, the computation of the next bit immediately fails. As a consequence, the algorithm essentially follows a linear path, recovering the expression of one bit after the other. It never needs to revisit choices made for bits before the current one.

Because affine self-equivalences of the modular addition have a complex structure (see [RVP22, Section 5]), one might have expected that a non-trivial amount of backtracking may be necessary. It turns out that this is not the case. As a consequence, recovering the input (and output) encodings is much simpler than one might have expected. The main computational cost is to solve the linear system in each step, as discussed in Section 5.5.4.

## 5.7 Polynomial factorization

In this section, we focus on the factorization problem identified in Section 5.5.3. To solve the problem efficiently, we sketch a generalization of the polynomial factorization algorithms from [MDFK18, Section 5.3].

The problem is: given a polynomial $P = A + B \cdot C$, where $P$ is known and $A, B, C$ are of degree $d$, find $A', B', C'$ of degree $d$ such that $P = A' + B' \cdot C'$.

In [MDFK18], the problem is solved when $d = 2$. The solution can be generalized as long as $d$ remains small, as we discuss in what follows. For simplicity, we first present the algorithm in the case $d = 3$, and discuss its generalization to $d > 3$ later on.

### 5.7.1 Notation

Let $D$ be a degree-3 polynomial in $Q = \mathbb{F}_2[X_0, \dots, X_{n-1}]/\langle X_i^2 - X_i \rangle$. For $(i, j, k)$ three pairwise distinct elements of $[n]^3$, let $D_{i,j,k}$ denote the coefficient of $X_i X_j X_k$ in $D$.

Let $D_{i,j,*}$ denote the vector $(D_{i,j,0}, D_{i,j,1}, \dots, D_{i,j,n-1}) \in \mathbb{F}_2^n$, and let $D_{i,*,*}$ denote the $n \times n$ matrix whose $j$-th row is $D_{i,j,*}$, for $j \in [n]$.

### 5.7.2 Algorithms to recover the polynomials

We focus on homogeneous monomials of $P$ degree $2 * d = 6$. Lower-degree monomials can be recovered in a similar way, as in [MDFK18]. The value of $A$ can be deduced from the values of $P, B, C$ using the equation $A = P - B \cdot C$. Thus, we focus on recovering $B, C$. More precisely, following the approach of [MDFK18], we recover $\text{span}(B, C)$. For polynomials of degree $d = 2$, $\text{span}(B, C)$ is computed from the knowledge of $\text{span}(B_{i,*}, C_{i,*})$ for all $i \in [n]$. In our case, it is likewise possible to compute $\text{span}(B, C)$ from the knowledge of $\text{span}(B_{i,*,*}, C_{i,*,*})$.

We first need an algorithm that will decide if, given $(i, j, k)$, $B_{i,j,k} = C_{i,j,k} = 0$. This can be done in instant time with a low probability of failure: we use Algorithm 4, then recursively use variants that take a smaller number of indices as inputs.

Algorithm 4 may output an incorrect answer, with (very) low probability. If this happens, the factorization algorithm will fail at a later stage. Since this happens with low probability, in the event of a failure, the algorithm can simply be run again. Using Algorithm 4, we can build an algorithm that takes as input $i \in [n]$ and returns $(j, k, l)$
**Algorithm 4 ZeroOracle**

1: **Input:** distinct $i, j, k, l, g \in [n]$

2: **Output:** True if $B_x = C_x = 0$ for all possible triples $x$ in $\{i, j, k, l, g\}$.

3: **for** $h \in [n] \setminus \{i, j, k, l, g\}$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $P_{i,j,k,l,g,h} = 1$ **then**

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** False

6: &nbsp;&nbsp;&nbsp;&nbsp;**return** True

such that $(B_{j,k,l}, C_{j,k,l}) \neq (0,0)$ but $B_x = C_x = 0$ for all other triples $x$ in $\{i, j, k, l\}$. This is analogous to the algorithm "FindGood" in [MDFK18]:

**Algorithm 5 FindGood**

1: **Input:** $i \in [n]$

2: **Output:** $j, k, l \in [n]$ such that $(B_{j,k,l}, C_{j,k,l}) \neq (0,0)$ and $B_x = C_x = 0$ for all other triples $x$ in $\{i, j, k, l\}$.

3: **while** True **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;$j \leftarrow [n] \setminus \{i\}$

5: &nbsp;&nbsp;&nbsp;&nbsp;$k \leftarrow [n] \setminus \{i, j\}$

6: &nbsp;&nbsp;&nbsp;&nbsp;$l \leftarrow [n] \setminus \{i, j, k\}$

7: &nbsp;&nbsp;&nbsp;&nbsp;**if** not ZeroOracle($j, k, l$) and ZeroOracle($x$) for all other triples in $\{i, j, k, l\}$ **then**

8: &nbsp;&nbsp;&nbsp;&nbsp;**return** $(j, k, l)$

With such a triple $(j, k, l)$ for some $i \in [n]$, let $(\mu, \lambda) = (B_{j,k,l}, C_{j,k,l})$. Then, $\forall g, h$, we have $P_{i,j,k,l,g,h} = \lambda B_{i,g,h} + \mu C_{i,g,h}$. Without loss of generality, we can assume that $(\mu, \lambda) = (0, 1)$, since we are looking for $\mathbf{span}(B, C)$.

We gain knowledge of $B_{i,g,h}$ by evaluating $P_{i,j,k,l,g,h}$, thus for every $i \in [n]$, we can recover $\mathbf{span}(B_{i,*,*}, C_{i,*,*})$ by evaluating $P_{i,j,k,l,g,h}$ for all $g, h$. This step is analogous to the algorithm "GetSpace" in [MDFK18].

**Algorithm 6 GetSpace**

1: **Input:** $i \in [n]$

2: **Output:** $\mathbf{span}(B_{i,*,*}, C_{i,*,*})$

3: Let $v \in \mathbb{F}_2^{n_2^2}$

4: Let $E = \{0\} \subseteq \mathbb{F}_2^{n_2^2}$

5: **while** $\dim(E) < 2$ **do**

6: &nbsp;&nbsp;&nbsp;&nbsp;$(j, k, l) \leftarrow \text{FindGood}(i)$

7: &nbsp;&nbsp;&nbsp;&nbsp;**for** $g, h \in [n]$ **do**

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$v_{g,h} \leftarrow P_{i,j,k,l,g,h}$

9: &nbsp;&nbsp;&nbsp;&nbsp;$E \leftarrow E + \mathbf{span}(v)$

10: **return** $E$

We can now build $\mathbf{span}(B, C)$ step by step: we first build $\mathbf{span}(B_{i,*,*}, C_{i,*,*})$, and we create a basis by selecting a random pair of vectors from this space. For $i > 1$, we check that the $i$-th vector space is consistent with the spaces from steps $i-1$ and $i-2$. If there is an inconsistency at some point, we backtrack and select a fresh random pair of vectors.

In the end, we obtain $\mathbf{span}(B, C)$. Let $B', C'$ be two linearly independent vectors in
$span(B, C)$, and let $A' = P - B'C'$. Then $A', B', C'$ is a solution to the factorization problem.

5.8 Conclusion

Our results show that any function of the form “low-degree layer, S-box layer, affine layer”
can be efficiently decomposed into its inner components (up to equivalence) using only
*black-box* access to the function. Moreover, the same is true of functions of the form
“low-degree layer, modular addition, affine layer”. An immediate consequence is that the
white-box encryption framework of [RVP22] is insecure, both for SPN and ARX ciphers.
A broader consequence is that low-degree input encodings cannot hide a structured inner
round function. If the round-encoding-based approach to white-box cryptography initi-
ated by [CEJvO02a, CEJvO02b] is to ever succeed in producing *cryptographically* secure
schemes (as opposed to schemes meant to heuristically slow down real-world attackers),
it must use non-trivial non-linear encodings for both input and output encodings.

Unfortunately, we are not aware of a general framework to embed non-linear encodings
in both the input and output of the round. Simple non-linear encodings have been used
in the past on specific schemes, but were severely restricted (operating over a few bits
only, in the manner of S-boxes) [CEJvO02a, CEJvO02b]. A more flexible way to embed
non-linear encodings is a compelling goal for white-box cryptography. It might lead to
cryptographically secure designs, which would be a major breakthrough. Indeed, having
to structurally recover non-linear layers at both the input and output of a cipher relates
to polynomial decomposition problems, which is NP-hard in the multivariate case [Dic93,
FP09] (polynomial-time algorithms are known in the univariate case [Bla14]).
Publication

This work has been submitted for publication at the time of writing this thesis.
Conclusion

In this thesis, we have studied different problems related to computing in association with untrusted agents. Cryptography is a great tool because it spares us the faith and time needed to build trust: we build protocols and prove that they are secure: this is enough to ensure that our information is protected. This is of course in theory: in practice the implementation of a cryptosystem is a potential liability, a small oversight can prove catastrophic. Nevertheless, even when dealing with theoretical designs of cryptosystems, security might not be proven to the highest degree of certainty, save for perfect secrecy, also called information theoretical security. Cryptanalysis can be devastating to a cipher with no solid security ground to stand on.

In Chapter 3, we present new constructions of PSM protocols, that achieve information
theoretical security. In our model however, no party (except the referee) can become
corrupted. We can use such protocols to achieve a variant where parties collude with
the referee, called non-interactive MPC [BKN18]. By expanding the cube approach of
[BKN18], we create a framework where we see functions and inputs as tensors. With it,
we get a better view the information that the parties can securely send to the referee.
Some of this information contains the output we want the referee to learn. When the right
conditions are met, the garbling around this output can be cancelled, and the referee learns
the cleartext value. This framework yields PSM protocols for all functions, however not
for any number k of parties: only prime powers for now. An interesting question is: can
we expand this construction to handle k as a composite of two primes, then eventually
as any composite number (and thus all of N)? Other techniques exist: in [SESN23],
Shinagawa et al build PSM protocols based on quadratic residues. Not all functions fit
this framework, but for k parties and any symmetric function f : {0, 1}^k → {0, 1}, they
achieve a communication cost of O(k^2), improving on the O(k^2 · log(k)) upper bound of
[BIKK14].

In Chapter 4, we show how to build weighted-ORAM protocols: ORAM for objects of variable sizes. This is done by modifying existing ORAM protocols to make them handle weighted items. In our construction, no added cost in bandwidth is needed when done on a large subset of tree-ORAM protocols, including Path-ORAM which is used in practical applications [SvS+13a]. In other ORAMs however, a small blowup is needed. An interesting direction to explore would be to search for a natural way to expand the hierarchical method to handle weighted items. Then no blowup would be needed. We also present new single-keyword SSE protocols based on weighted tree-ORAMs. This method is more efficient than previous attempts at constructing SSE using ORAM. This work is part of a broader wish for secure encrypted databases, although improvements are being made, it remains an open problem to achieve functionalities on par with plaintext databases while retaining some notion of security.

In Chapter 5, we cryptanalyze white-box constructions based on implicit implementa-
tions from [RVP22]. We show that the attack on the ASASA structure from [MDFK18]
still applies when the first affine layer is replaced by a low-degree nonlinear layer. We
also attack the structure behind the white-box based on an ARX cipher. [BLU23] shows
a decomposition-based key recovery attack on the same white-box, however without the
structural aspect. Because of a flaw in the structure, we do not have suggestions to repair
the system. The search for provably secure white-box cryptography continues. An open
question is to analyze an *ISI* or an *IMI* construction: we prove that having a low-degree
non-linear input layer is not enough, but while it is not clear how one could build a
white-box where that layer is combined with a low-degree non-linear output layer, it is
not clear either if one could find a (structural) attack. If we can keep building white-
box schemes based on polynomial decomposition, we can hope to base them off of hard
problems [Dic93, FP09].
# Supplementary material on PSM

## A.1 Proof of Equation (3.9) and (3.10)

*Proof of Equation (3.9).* By definition:

$$ \sum_{(*)} \langle \mathbf{F}, \bar{\mathbf{X}}(P) \rangle = \sum_{(*)} \langle \mathbf{F}, \bar{\mathbf{X}}_{S_1} \otimes \dots \otimes \bar{\mathbf{X}}_{S_t} \rangle $$

where (*) denotes “for all unordered $E = \{S_1, \dots, S_t\}$ being a partition of $[2k]$ such that $\{|S_1|, \dots, |S_t|\} = P$”. Thus,

$$ \begin{aligned} \sum \langle \mathbf{F}, \bar{\mathbf{X}}(P) \rangle &= \sum_{(*)} \left\langle \mathbf{F}, \bigotimes_{i \in [t]} (\mathbf{R}_{S_i} + \bigotimes_{j \in S_i} \mathbf{x}_j) \right\rangle \\ &= \sum_{(*)} \sum_{G \subseteq E} \left\langle \mathbf{F}, \bigotimes_{S \in G} \mathbf{R}_S \otimes \bigotimes_{j \notin \bigcup_{S \in G} S} \mathbf{x}_j \right\rangle \\ &= \sum_{Q \subseteq P} \sum_{\substack{G = \{S_1, \dots, S_t\} \text{ s.t.} \\ \{|S_1|, \dots, |S_t|\} = P \setminus Q}} \beta(P, G) \cdot \left\langle \mathbf{F}, \bigotimes_{i \in [t]} R_{S_i} \otimes \bigotimes_{j \notin \bigcup_{i \in [t]} S_i} \mathbf{x}_j \right\rangle, \end{aligned} $$

where $\beta(P, G)$ accounts for the redundancy: define $\beta(P, G)$ as the number of unordered partitions $E$ of $[2k]$ such that $G \subseteq E$ and $P$ is the shape of $E$. It is equivalent to count the number of $F := E \setminus G$. That is, $\beta(P, G)$ also equals the number of unordered partitions $F$ of $[2k] \setminus \bigcup_{S \in G} S$ such that $Q$ is the shape of $F$. Thus by definition, $\beta(P, G) = \alpha(Q)$. The proof is concluded by

$$ \begin{aligned} \sum \langle \mathbf{F}, \bar{\mathbf{X}}(P) \rangle &= \sum_{Q \subseteq P} \sum_{\substack{G = \{S_1, \dots, S_t\} \text{ s.t.} \\ \{|S_1|, \dots, |S_t|\} = P \setminus Q}} \alpha(Q) \cdot \left\langle \mathbf{F}, \bigotimes_{i \in [t]} R_{S_i} \otimes \bigotimes_{j \notin \bigcup_{i \in [t]} S_i} \mathbf{x}_j \right\rangle \\ &= \sum_{Q \subseteq P} \alpha(Q) \cdot \sum \langle \mathbf{F}, \mathbf{R}(P \setminus Q) \rangle. \end{aligned} \quad \square $$

*Proof of Equation (3.10).* Let $n = \text{sum}(Q)$. By definition, $\alpha(Q)$ is the number of unsorted partitions $E = \{S_1, \dots, S_t\}$ of $[n]$ such that the multiset $\{|S_1|, \dots, |S_t|\}$ (i.e. the shape of $E$) equals $Q$.

To compute $\alpha(Q)$, we count the number of ways to arranging $1, \dots, n$ into a sequence.

* First, pick an unsorted partitions $E$ of $[n]$ s.t. the shape of $E$ equals $Q$. The number of choices is $\alpha(Q)$.
* Then, sort the sets in the partition $E = \{S_1, \dots, S_t\}$. Sort them by their sizes, i.e. $|S_1| \le |S_2| \le \dots \le |S_t|$. For any $m$, if several sets are of the size $m$, their order has to be specified, the number of such choices is (number of $m$'s in $Q$)!.

* Finally, arrange the elements in each $S_i$ into a sub-sequence, the number of possible sequences is $|S_i|!$. Concatenate these sub-sequences in order.

$$ \alpha(Q) \cdot \prod_{m \in \mathbb{Z}^+} (\text{number of } m\text{'s in } Q)! \cdot \prod_{i \in Q} i! = n! \quad \square $$

# A.2 Auxiliary PSM Protocols for $\langle \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k, \mathbf{Y} \rangle + s$

## A.2.1 The Multi-party Variant

In this section, we present an auxiliary PSM protocol that is used as a subroutine by our multi-party PSM in Section 3.3.

The functionality is $\langle \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k, \mathbf{Y} \rangle + s$. It is a $(k+1)$-party functionality where the $i$-th party has as input $\mathbf{x}_i \in \mathbb{F}^N$ for $i \in [k]$, and the $(k+1)$-th party has as inputs $\mathbf{Y} \in \mathbb{F}_{k \text{ times}}^{N \times \dots \times N}$ and $s \in \mathbb{F}$. We will present a PSM protocol for this functionality with a communication complexity of $O(\text{poly}(k) \cdot N^k)$ field elements. This protocol is implicitly used in [BKN18].

First, we consider the special case when $k = 1$. That is, there are only two parties. Say we call them Alice and Bob. Alice has $\mathbf{x} \in \mathbb{F}^N$, Bob has $\mathbf{y} \in \mathbb{F}^N$, $s \in \mathbb{F}$. The functionality output is $\langle \mathbf{x}, \mathbf{y} \rangle + s$. The PSM protocol works as follows:

* Random $\mathbf{a}, \mathbf{b} \in \mathbb{F}^N$, $c \in \mathbb{F}$ are sampled from the common random string, which is known by both Alice and Bob.

* Alice sends $\bar{\mathbf{x}} := \mathbf{x} + \mathbf{a}, z := c - \langle \mathbf{b}, \mathbf{x} \rangle$ to the referee.

* Bob sends $\bar{\mathbf{y}} := \mathbf{y} + \mathbf{b}, w := s - c - \langle \mathbf{a}, \mathbf{y} \rangle - \langle \mathbf{a}, \mathbf{b} \rangle$ to the referee.

* The referee outputs $\langle \bar{\mathbf{x}}, \bar{\mathbf{y}} \rangle + z + w$.

For the case $k \ge 2$, the first $k$ parties need to jointly emulate Alice. The protocol works as follows:

* Random $\mathbf{A}, \mathbf{B}, \mathbf{C} \in \mathbb{F}^{N \times \dots \times N}$ are sampled from the common random string. Define $c \in \mathbb{F}$ as the sum of entries in $\mathbf{C}$.

* The $(k+1)$-th party sends $\bar{\mathbf{Y}} := \mathbf{Y} + \mathbf{B}, z := s - c - \langle \mathbf{A}, \mathbf{Y} \rangle - \langle \mathbf{A}, \mathbf{B} \rangle$ to the referee.

* The first $k$ parties jointly reveal $\bar{\mathbf{X}} := \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k + \mathbf{A}, w := c - \langle \mathbf{B}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k \rangle$ to the referee.

Since every coordinate of $\bar{\mathbf{X}}$ can be computed by an arithmetic formula of size $O(k)$, each of these coordinates can be computed by the referee by using a PSM protocol with communication complexity of $O(\text{poly}(k))$ field elements [IK00]. The referee learns $\bar{\mathbf{X}}$ after receiving $O(\text{poly}(k) \cdot N^k)$ field elements.
The term $w := c - \langle \mathbf{B}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k \rangle$ equals the sum of all entries in $\mathbf{W} := \mathbf{C} - \mathbf{B}_{\circ p.w.}(\mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k)$, where $\circ_{p.w.}$ denotes the point-wise product. In other words, we defines $\mathbf{W} \in \mathbb{F}^{N \times \dots \times N}$ as

$$ \mathbf{W}[i_1, \dots, i_k] = \mathbf{C}[i_1, \dots, i_k] - \mathbf{B}[i_1, \dots, i_k] \mathbf{x}_1[i_1] \dots \mathbf{x}_k[i_k]. $$

Due to the randomness of $\mathbf{C}$, we know $\mathbf{W}$ is a randomized encoding of $w$. Thus, it is equivalent for the first $k$ parties to jointly reveal $\mathbf{W}$ to the referee. Since every coordinate of $\mathbf{W}$ can be computed by an arithmetic formula of size $O(k)$, each of them can be revealed by using the Ishai-Kushilevitz PSM protocol [IK00], which has a communication complexity of $O(\text{poly}(k))$ field elements. The referee learns $w$ after receiving $O(\text{poly}(k) \cdot N^k)$ field elements.

* The referee outputs $\langle \bar{\mathbf{X}}, \bar{\mathbf{Y}} \rangle + z + w$.

The correctness of the protocol can be verified in the following equation:

$$ \begin{aligned} & \langle \bar{\mathbf{X}}, \bar{\mathbf{Y}} \rangle + z + w \\ &= \langle \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k + \mathbf{A}, \mathbf{Y} + \mathbf{B} \rangle + s - c - \langle \mathbf{A}, \mathbf{Y} \rangle - \langle \mathbf{A}, \mathbf{B} \rangle + \\ & \qquad c - \langle \mathbf{B}, \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k \rangle \\ &= \langle \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k, \mathbf{Y} \rangle + s. \end{aligned} $$

The privacy is guaranteed by the following simulator:

* Simulate $\bar{\mathbf{X}}, \bar{\mathbf{Y}}, \mathbf{W}$ as uniform random, since they are one-time-padded by $\mathbf{A}, \mathbf{B}, \mathbf{C}$.

* Given $\bar{\mathbf{X}}, \bar{\mathbf{Y}}, \mathbf{W}$ and the function output, $w, z$ are uniquely determined since $w = \sum(\mathbf{W})$ and $\langle \bar{\mathbf{X}}, \bar{\mathbf{Y}} \rangle + z + w = \text{output}$.

* Simulate the transcripts of the inner Ishai-Kushilevitz PSM protocols using its own simulator, which takes $\bar{\mathbf{X}}, \mathbf{W}$ as input.

### A.2.2 The 2-party Variant

In this section, we present an auxiliary PSM protocol that is used as a subroutine by our unbalanced 2-party PSM in Section 3.4.

The functionality is $\langle \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k, \mathbf{Y} \rangle + s$. It is a 2-party functionality where the first party, namely Alice, has as inputs $\mathbf{x}_1, \dots, \mathbf{x}_k \in \mathbb{F}^N$ and the second party, namely Bob, has as inputs $\mathbf{Y} \in \mathbb{F}_{k \text{ times}}^{N \times \dots \times N}$ and $s \in \mathbb{F}$. We will present a PSM protocol for this functionality with unbalanced communication complexity, where Alice sends $O(kN)$ field elements and Bob sends $(N+1)^k$ field elements.

As the first step, we consider a harder problem instead. Bob's input is replaced by a multi-affine function $f: \mathbb{F}^N \times \dots \times \mathbb{F}^N \to \mathbb{F}$. Corresponding, the functionality is replaced by $f(\mathbf{x}_1, \dots, \mathbf{x}_k)$. Every multi-affine function $f$ can be uniquely represented by its coefficient tensor $\mathbf{F} \in \mathbb{F}^{(N+1) \times \dots \times (N+1)}$ such that for any $\mathbf{z}_1, \dots, \mathbf{z}_k \in \mathbb{F}^N$,

$$ f(\mathbf{z}_1, \dots, \mathbf{z}_k) = \langle \mathbf{z}_1 \| 1 \otimes \dots \otimes \mathbf{z}_k \| 1, \mathbf{F} \rangle. $$

Here $\mathbf{z}_i \| 1$ denotes the concatenation of $\mathbf{z}_i$ and $1$, which is a dimension-$(N+1)$ vector. Notice that, if we let the “first” $N \times \dots \times N$ subtensor of $\mathbf{F}$ equal $\mathbf{Y}$, let its “last” entry $\mathbf{F}[N+1, \dots, N+1] = s$, and let all other entries in $\mathbf{F}$ be 0, we have

$$ f(\mathbf{x}_1, \dots, \mathbf{x}_k) = \langle \mathbf{x}_1 \| 1 \otimes \dots \otimes \mathbf{x}_k \| 1, \mathbf{F} \rangle = \langle \mathbf{x}_1 \otimes \dots \otimes \mathbf{x}_k, \mathbf{Y} \rangle + s. $$

The protocol works as follows:
* Random $\mathbf{r}_1, \dots, \mathbf{r}_k \in \mathbb{F}^N$ and a random multi-affine function $g$ are sampled from the common random string.

* Alice sends $\bar{\mathbf{x}}_i = \mathbf{x}_i + \mathbf{r}_i$ to the referee, for all $i \in [k]$.

* Bob computes the multi-affine function $g$, such that

$$g(\mathbf{z}_1, \dots, \mathbf{z}_k) := f(\mathbf{z}_1 - \mathbf{r}_1, \dots, \mathbf{z}_k - \mathbf{r}_k).$$

Bob sends $\bar{g} = g + h$ to the referee.

* Alice additionally sends $s = h(\bar{\mathbf{x}}_1, \dots, \bar{\mathbf{x}}_k)$ to the referee.

* The referee outputs $\bar{g}(\bar{\mathbf{x}}_1, \dots, \bar{\mathbf{x}}_k) - s$.

The correctness follows directly from the following equation:

$$\begin{aligned}
\bar{g}(\bar{\mathbf{x}}_1, \dots, \bar{\mathbf{x}}_k) - s &= g(\bar{\mathbf{x}}_1, \dots, \bar{\mathbf{x}}_k) + h(\bar{\mathbf{x}}_1, \dots, \bar{\mathbf{x}}_k) - h(\bar{\mathbf{x}}_1, \dots, \bar{\mathbf{x}}_k) \\
&= g(\bar{\mathbf{x}}_1, \dots, \bar{\mathbf{x}}_k) \\
&= f(\mathbf{x}_1 - \mathbf{r}_1 + \mathbf{r}_1, \dots, \mathbf{x}_k - \mathbf{r}_k + \mathbf{r}_k) \\
&= f(\mathbf{x}_1, \dots, \mathbf{x}_k).
\end{aligned}$$

The privacy is guaranteed by the following simulator:

* Simulate $\bar{\mathbf{x}}_1, \dots, \bar{\mathbf{x}}_k, \bar{g}$ as uniform random, since they are one-time padded by $\mathbf{r}_1, \dots, \mathbf{r}_k, h$.

* Given $\bar{\mathbf{x}}_1, \dots, \bar{\mathbf{x}}_k, \bar{g}$ and the function output, simulate $s$ by computing $s$ from the equation $\bar{g}(\bar{\mathbf{x}}_1, \dots, \bar{\mathbf{x}}_k) - s = \text{output}$.
B

Additional proofs for weighted
ORAM

B.1 SSE Proofs

B.1.1 Proof of ZeroSSE

The simulator $\mathcal{S}$ for ZeroSSE behaves as follows.

*   **Setup:** on input $\mathcal{L}_{\text{Setup}} = (N, U)$, $\mathcal{S}$ creates a wORAM instance `Weighted(PathOram)` instance with block size $U$ and number of blocks $\lceil N/U \rceil$, initialized with $\lceil N/U \rceil$ items containing dummy data of size $B$. Let $a$ denote the address of one of these items.

*   **Search** and **Update**: in both cases, $\mathcal{S}$ queries the wORAM instance on item $a$ with $op = \text{read}$.

We claim that the resulting transcript is indistinguishable from the real transcript. In fact, this follows immediately from the security of `Weighted(PathOram)`, since the guarantees of a wORAM scheme is that any two sequence of accesses of the same length are indistinguishable, and the simulator makes the same number of accesses as the client in the real game. Moreover, Theorem 4.4.1 implies that `Weighted(PathOram)` is a correct wORAM scheme.

Note that the analysis relies on the fact that Path ORAM is correct for the given parameters, which in turn implies that we require $N/U = \Omega(\lambda)$. If $N/U < \lambda$, it may not be worth using an elaborate ORAM scheme, since the overhead of trivial ORAM is less than $\lambda$.

B.1.2 Proof of BlockSSE

The simulator $\mathcal{S}$ for BlockSSE behaves as follows.

*   **Setup:** on input $\mathcal{L}_{\text{Setup}} = (N, B)$, $\mathcal{S}$ creates a wORAM instance `Weighted(PathOram)` instance with block size $B$ and number of blocks $\lceil N/B \rceil$, initialized with $\lceil N/B \rceil$ items containing dummy data of size $B$. Let $a$ denote the address of one of these items.

*   **Update**: $\mathcal{S}$ queries the wORAM instance on item $a$ with $op = \text{read}$.

*   **Search**: on input $\mathcal{L}_{\text{Search}} = x$, $\mathcal{S}$ queries the wORAM instance $x$ times on item $a$ with $op = \text{read}$.
We claim that the resulting transcript is indistinguishable from the real transcript. Again, this follows immediately from the security of Weighted(PathOram), since the guarantees of a wORAM scheme is that any two sequence of accesses of the same length are indistinguishable, and the simulator makes the same number of accesses as the client in the real game. Moreover, Theorem 4.4.1 implies that Weighted(PathOram) is a correct wORAM scheme. As with ZeroSSE, that last point assumes that $N/B = \Omega(\lambda)$.

## B.2 A General Transformation

In this section we present a way to transform any standard ORAM into a variable ORAM, at the cost of some blowup in the overhead. We have $m$ objects, of individual size $w_i \in [0, B]$ for $i \in [k]$ such that the sum of the sizes is $N$. The idea is:

* We create a standard ORAM structure for $N$ objects, each of the same size higher than $B$ (we discuss the size we need later). Let us call these $N$ objects in the standard ORAM super objects.

* We want to store our $m$ objects of varying sizes inside of the super objects. To do so, we map every object $i \in [m]$ to a super object $H(i) \in [N]$.

* When we wish to access the object $i$, we make a standard ORAM access to the super object $H(i)$, and read the object from the super object.

This technique yields the same computational, storage and bandwidth metrics as the ORAM we are modifying, with the caveat that the object size must be bigger.

The crucial part here is the function $H$. We must choose a way of hashing the $m$ objects into the $N$ super objects while having the following properties:

* A super object cannot overflow, except with negligible probability.

* The hash table should be modified as little as possible, so as to save bandwidth.

* The super objects should be as small as possible.

We present two hash algorithms based on the balls-in-bins problem that can be used to achieve this type of weighted ORAM.

### B.2.1 One-Choice Process: $O(\log N)$ blowup

We let each object be associated with a super object uniformly at random. In other words, $H: [m] \to [N]$ is a random function. At each access, to get object $i$ we call the access algorithm of the ORAM on super object $H(i)$, modify object $i$ in it, re-encrypt the super-object with fresh randomness, and write back the super object. It suffices to have each super object be of size $B \cdot \log N$.

*Proof.* Let $m$ balls, each of weight $w_i \in [0, 1]$ such that $\sum_{i=1}^m w_i = N$, be stored in $N$ bins, which we associate uniformly at random. Let us call $S$ the bin with the highest load. Let us call $\mathbf{w}$ the current weight distribution of the balls, and $\mathbf{u}$ be the weight distribution when we have only $N$ balls of size 1, that is:

$$ \mathbf{u} = \underbrace{(1, \dots, 1, 0, \dots, 0)}_{N}, \underbrace{\dots}_{m-N} $$
From the majorization argument in [BFHM05], we know that for any $\mathbf{w}$, $\mathbb{E}(\sum_{i \in S} w_i) \le \mathbb{E}(\sum_{i \in S} u_i)$. Since the max function is convex and the expectancy is linear, we have $\mathbb{E}(\max(0, (\sum_{i \in S} w_i) - \log N)) \le \mathbb{E}(\max(0, (\sum_{i \in S} u_i) - \log N))$. From now on, we will let the random variable $X(\mathbf{v})$ denote $\max(0, (\sum_{i \in S} u_i) - \log(N))$.

We have $\mathbb{P}(X(\mathbf{w}) > 0) \le \mathbb{E}(X(\mathbf{w}))$. The event $X(\mathbf{w}) > 0$ is exactly the event of having at least one overflow in a given bin, so to prove that it happens with negligible probability, it suffices to prove that $\mathbb{E}(X(\mathbf{u}))$ is negligible. We have:

$$ 
\begin{aligned}
\mathbb{E}(X(\mathbf{u})) &= \sum_{k=0}^{\infty} \mathbb{P}(X(\mathbf{u}) > k) \\
&\le N \cdot \mathbb{P}(X(\mathbf{u}) > 0) \\
\mathbb{P}(X(\mathbf{u}) > 0) &= \mathbb{P}[\text{a given bin has more than } k \text{ balls}] \text{ with } k = \log N \\
&\le \binom{N}{k} \cdot \frac{1}{N^k} \\
&\le \frac{N^k}{k!} \cdot \frac{1}{N^k} \\
&= \frac{1}{k!} \\
&= \text{negl}(N) \text{ via Stirling's formula.} \quad \square
\end{aligned}
$$

### B.2.2 Layered Two-Choice Process: $O(\log \log N)$ blowup

The Layered 2-choice method of hashing $m$ balls into $N$ bins was introduced in [MR22, Section 4]. The idea is to split the $m$ objects into “layers” according to their sizes. Then we can store them in the super objects by running standard (unweighted) 2-choice balls-in-bins allocation separately for each layer. Such an allocation is achievable with overhead $O(\log \log N)$.

However this algorithm does not support offline modification of the bins. This means that after an access for object $i$, we must update the ORAM by selecting 2 new super objects uniformly at random and write $i$ in one of those super objects. The first consequence is that we double the bandwidth. Another problem is that the hash table has to be modified. To prevent client side spatial blowup, we must store the hash table (effectively a position map) on the server. This may be realized using a second ORAM (which need not use the same ORAM protocol).

Overall, while this approach is generic, it is significantly less efficient in practice than our main construction, which incurs almost no overhead relative to standard Tree ORAM.

## B.3 A Flaw in DivORAM

DivORAM was introduced in [LHL+18]. The DivORAM construction is (essentially) a weighted ORAM following a Tree ORAM structure: blocks are stored in buckets, and each bucket is located at the node of a binary tree. The blocks are decomposed into so-called splinters, which are stored in the buckets. A bucket at level $i \in [\log N]$ can store up to $2^i$ splinters.

Stash analysis is given in [LHL+18, Section 5.3]. Whenever a splinter cannot be stored in a tree bucket, it ends up in the stash. The worst case is when an entire block, composed
of log N splinters, cannot be stored in the tree: all splinters are then moved to the stash.
The stash capacity is 2 log(N) − 1. To avoid overflows, the content of the stash is written
back into the tree whenever its size exceeds log N.

Such a behavior reveals to the server when the stash size passes the log N threshold.
Unfortunately, leaking when the stash size passes a threshold breaks Path ORAM security,
because certain access patterns fill the stash faster than others. For more information, we
refer the reader to [RYF+13, Section 3.1.1], where this exact point is discussed. Because
of this leakage, the DivORAM construction of [LHL+18] is insecure.

B.4 Weighted Hierarchical ORAM

Our work focuses on Tree ORAMs, mainly because of their higher practical efficiency.
It is natural to ask whether similar results can be obtained for hierarchical ORAM. We
briefly discuss this question here.

As shown in chapter 4, there is a natural way to adapt Tree ORAM algorithms to
handle weighted items. The problem of building weighted Tree ORAM is not so much an
algorithmic problem as a combinatorial one: we need to prove that the “natural” weighted
variant of Tree ORAM creates no overflow.

With hierarchical ORAMs, this first step is already a challenge. There is no obvious
natural algorithmic modification of hierarchical ORAMs that handles weighted items.
Indeed, we would first need weighted oblivious hash tables. That is, we need oblivious
hash tables that can handle items of variable size. We also need those tables to support
oblivious sorting, or at least oblivious compaction, in a way that is compatible with
variable-size items. Building such a data structure looks quite challenging, and we do not
know of a natural candidate.

In more details, we know of two constructions that come close to that goal in the
literature, but neither quite reaches it. The first is two-choice hashing for weighted items
[TW07, MR22]. Two-choice hashing is easy to realize obliviously. The problem is that we
would have to pay (at least) a log log overhead, and efficient oblivious compaction seems
difficult. An alternative approach is to use the “Data-Independent Packing” primitive
from [BBF+21]. But the only known instantiation requires computing a maximum flow
algorithm. It is not clear how to compute that algorithm in quasilinear time, let alone in
an oblivious manner.
<figure><img src="image_10.png" /></figure>

Bibliography

[AA18]
Benny Applebaum and Barak Arkis. On the power of amortization in secret sharing: d-uniform secret sharing and CDS with constant information rate. In Amos Beimel and Stefan Dziembowski, editors, *Theory of Cryptography - 16th International Conference, TCC 2018, Panaji, India, November 11-14, 2018, Proceedings, Part I*, volume 11239 of *Lecture Notes in Computer Science*, pages 317-344. Springer, 2018. 26

[AARV17]
Benny Applebaum, Barak Arkis, Pavel Raykov, and Prashant Nalini Vasudevan. Conditional disclosure of secrets: Amplification, closure, amortization, lower-bounds, and separations. *Electronic Colloquium on Computational Complexity (ECCC)*, 24:38, 2017. 26

[ABF+19]
Benny Applebaum, Amos Beimel, Oriol Farràs, Oded Nir, and Naty Perter. Secret-sharing schemes for general and uniform access structures. In Yuval Ishai and Vincent Rijmen, editors, *Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part III*, volume 11478 of *Lecture Notes in Computer Science*, pages 441-471. Springer, 2019. 26

[ABMT18]
Estuardo Alpirez Bock, Chris Brzuska, Wil Michiels, and Alexander Treff. On the ineffectiveness of internal encodings - revisiting the DCA attack on white-box cryptography. In Bart Preneel and Frederik Vercauteren, editors, *ACNS 18*, volume 10892 of LNCS, pages 103-120. Springer, Heidelberg, July 2018. 10, 19

[AG11]
Sanjeev Arora and Rong Ge. New algorithms for learning in presence of errors. In Luca Aceto, Monika Henzinger, and Jirí Sgall, editors, *Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I*, volume 6755 of Lecture Notes in Computer Science, pages 403-415. Springer, 2011. 76, 82

[AHMS20]
Benny Applebaum, Thomas Holenstein, Manoj Mishra, and Ofer Shayevitz. The communication complexity of private simultaneous messages, revisited. *J. Cryptol.*, 33(3):917-953, 2020. 6, 16, 21

[AKL+18]
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Persico, and Elaine Shi. OptORAM: Optimal oblivious RAM. Cryptology ePrint Archive, Report 2018/892, 2018. https://eprint.iacr.org/2018/892. 8, 18
[AKL+20] Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Perserico, and Elaine Shi. OptORAMa: Optimal oblivious RAM. In Anne Canteaut and Yuval Ishai, editors, *EUROCRYPT 2020, Part II*, volume 12106 of LNCS, pages 403–432. Springer, Heidelberg, May 2020. 49

[AL21] Leonard Assouline and Tianren Liu. Multi-party psm, revisited: Improved communication and unbalanced communication. In Kobbi Nissim and Brent Waters, editors, *Theory of Cryptography*, pages 194–223, Cham, 2021. Springer International Publishing. 6, 16, 43

[AM23] Léonard Assouline and Brice Minaud. Weighted oblivious ram, with applications to searchable symmetric encryption. In *Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part I*, pages 426–455, Berlin, Heidelberg, 2023. Springer-Verlag. 9, 18, 71

[AMR19] Alessandro Amadori, Wil Michiels, and Peter Roelse. A DFA attack on white-box implementations of AES with external encodings. In Kenneth G. Paterson and Douglas Stebila, editors, *SAC 2019*, volume 11959 of LNCS, pages 591–617. Springer, Heidelberg, August 2019. 10, 19

[ANSS16] Gilad Asharov, Moni Naor, Gil Segev, and Ido Shahaf. Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. In Daniel Wichs and Yishay Mansour, editors, *48th ACM STOC*, pages 1101–1114. ACM Press, June 2016. 46, 48

[BBD+22] Guillaume Barbu, Ward Beullens, Emmanuelle Dottax, Christophe Giraud, Agathe Houzelot, Chaoyun Li, Mohammad Mahzoun, Adrián Ranea, and Jianrui Xie. ECDSA white-box implementations: Attacks and designs from WhibOx 2021 contest. *Cryptology ePrint Archive*, 2022. 74

[BBF+21] Angèle Bossuat, Raphael Bost, Pierre-Alain Fouque, Brice Minaud, and Michael Reichle. SSE and SSD: Page-efficient searchable symmetric encryption. In Tal Malkin and Chris Peikert, editors, *CRYPTO 2021, Part III*, volume 12827 of LNCS, pages 157–184, Virtual Event, August 2021. Springer, Heidelberg. 46, 47, 48, 69, 106

[BBK14] Alex Biryukov, Charles Bouillaguet, and Dmitry Khovratovich. Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key (extended abstract). In Palash Sarkar and Tetsu Iwata, editors, *Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C.*, December 7-11, 2014. *Proceedings, Part I*, volume 8873 of Lecture Notes in Computer Science, pages 63–84. Springer, 2014. 75, 76, 77, 80

[BCBP03] Alex Biryukov, Christophe De Cannière, An Braeken, and Bart Preneel. A toolbox for cryptanalysis: Linear and affine equivalence algorithms. In Eli Biham, editor, *Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques*,
Warsaw, Poland, May 4-8, 2003, Proceedings, volume 2656 of Lecture Notes in Computer Science, pages 33–50. Springer, 2003. 86

[BCP16] Elette Boyle, Kai-Min Chung, and Rafael Pass. Oblivious parallel RAM and applications. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part II, volume 9563 of LNCS, pages 175–204. Springer, Heidelberg, January 2016. viii, 65

[BDG$^{+22}$] Sven Bauer, Hermann Drexler, Maximilian Gebhardt, Dominik Klein, Friederike Laus, and Johannes Mittmann. Attacks against white-box ECDSA and discussion of countermeasures-a report on the WhibOx contest 2021. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022. 74

[BF19] Raphael Bost and Pierre-Alain Fouque. Security-efficiency tradeoffs in searchable encryption. PoPETs, 2019(4):132–151, October 2019. 68

[BFHM05] Petra Berenbrink, Tom Friedetzky, Zengjian Hu, and Russell Martin. On weighted balls-into-bins games. In Volker Diekert and Bruno Durand, editors, STACS 2005, pages 231–243, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. 105

[BFHM08] Petra Berenbrink, Tom Friedetzky, Zengjian Hu, and Russell Martin. On weighted balls-into-bins games. Theoretical Computer Science, 409(3):511–520, 2008. 48

[BGE04] Olivier Billet, Henri Gilbert, and Charaf Ech-Chatbi. Cryptanalysis of a white box AES implementation. In Helena Handschuh and M. Anwar Hasan, editors, Selected Areas in Cryptography, 11th International Workshop, SAC 2004, Waterloo, Canada, August 9-10, 2004, Revised Selected Papers, volume 3357 of Lecture Notes in Computer Science, pages 227–240. Springer, 2004. 74, 75

[BGI$^{+01}$] Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Joe Kilian, editor, Advances in Cryptology — CRYPTO 2001, pages 1–18, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. 75

[Bha14] Arnab Bhattacharyya. Polynomial decompositions in polynomial time. In European Symposium on Algorithms, pages 125–136. Springer, 2014. 89

[BHI$^{+20}$] Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, and Tal Malkin. On the complexity of decomposable randomized encodings, or: How friendly can a garbling-friendly PRF be? In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 86:1–86:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. 21

[BHMT16] Joppe W Bos, Charles Hubain, Wil Michiels, and Philippe Teuwen. Differential computation analysis: Hiding your white-box designs is not enough. In International Conference on Cryptographic Hardware and Embedded Systems, pages 215–236. Springer, 2016. 75
[BIK17] Amos Beimel, Yuval Ishai, and Eyal Kushilevitz. Ad hoc PSM protocols: Secure computation without coordination. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, *Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part III*, volume 10212 of Lecture Notes in Computer Science, pages 580-608, 2017. 26

[BIKK14] Amos Beimel, Yuval Ishai, Ranjit Kumaresan, and Eyal Kushilevitz. On the cryptographic complexity of the worst functions. In *TCC*, pages 317-342, 2014. 6, 7, 16, 22, 23, 26, 33, 97

[BKN18] Amos Beimel, Eyal Kushilevitz, and Pnina Nissim. The complexity of multiparty PSM protocols and related models. In Jesper Buus Nielsen and Vincent Rijmen, editors, *Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II*, volume 10821 of Lecture Notes in Computer Science, pages 287-318. Springer, 2018. 6, 16, 22, 23, 26, 33, 42, 97, 100

[Bla14] Raoul Blankertz. A polynomial time algorithm for computing all minimal decompositions of a polynomial. *ACM Communications in Computer Algebra*, 48(1/2):13-23, 2014. 95

[BLU23] Alex Biryukov, Baptiste Lambin, and Aleksei Udovenko. Cryptanalysis of arx-based white-box implementations. *IACR Transactions on Cryptographic Hardware and Embedded Systems*, 2023(3):97-135, Jun. 2023. 75, 98

[Bos16] Raphael Bost. Σφος: Forward secure searchable encryption. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, *ACM CCS 2016*, pages 1143-1154. ACM Press, October 2016. 69

[BR22] Marshall Ball and Tim Randolph. A note on the complexity of private simultaneous messages with many parties. In Dana Dachman-Soled, editor, *3rd Conference on Information-Theoretic Cryptography (ITC 2022)*, volume 230 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:12, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 6, 16, 21

[BRVW19] Andrey Bogdanov, Matthieu Rivain, Philip S. Vejre, and Junwei Wang. Higher-order DCA against standard side-channel countermeasures. In Ilia Polian and Marc Stöttinger, editors, *Constructive Side-Channel Analysis and Secure Design - 10th International Workshop, COSADE 2019, Darmstadt, Germany, April 3-5, 2019, Proceedings*, volume 11421 of Lecture Notes in Computer Science, pages 118-141. Springer, 2019. 75

[BS01] Alex Biryukov and Adi Shamir. Structural cryptanalysis of SASAS. In Birgit Pfitzmann, editor, *Advances in Cryptology - EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic*
*Techniques, Innsbruck, Austria, May 6-10, 2001, Proceeding*, volume 2045 of *Lecture Notes in Computer Science*, pages 394–405. Springer, 2001. 74, 76, 77, 80, 84

[BSS<sup>+</sup>13] Ray Beaulieu, Douglas Shors, Jason Smith, Stefan Treatman-Clark, Bryan Weeks, and Louis Wingers. The SIMON and SPECK families of lightweight block ciphers. Cryptology ePrint Archive, Report 2013/404, 2013. https://eprint.iacr.org/2013/404. 10, 19

[CCS17] T.-H. Hubert Chan, Kai-Min Chung, and Elaine Shi. On the depth of obliv-
ious parallel RAM. In Tsuyoshi Takagi and Thomas Peyrin, editors, *ASI-
ACRYPT 2017, Part I*, volume 10624 of LNCS, pages 567–597. Springer,
Heidelberg, December 2017. 60

[CEJv03] Stanley Chow, Philip A. Eisen, Harold Johnson, and Paul C. van Oorschot. White-box cryptography and an AES implementation. In Kaisa Nyberg and Howard M. Heys, editors, *SAC 2002*, volume 2595 of LNCS, pages 250–270. Springer, Heidelberg, August 2003. 9, 19

[CEJvO02a] Stanley Chow, Philip A. Eisen, Harold Johnson, and Paul C. van Oorschot. White-box cryptography and an AES implementation. In Kaisa Nyberg and Howard M. Heys, editors, *Selected Areas in Cryptography, 9th Annual International Workshop, SAC 2002, St. John's, Newfoundland, Canada, August 15-16, 2002. Revised Papers*, volume 2595 of *Lecture Notes in Computer Science*, pages 250–270. Springer, 2002. 73, 75, 95

[CEJvO02b] Stanley Chow, Philip A. Eisen, Harold Johnson, and Paul C. van Oorschot. A white-box DES implementation for DRM applications. In Joan Feigenbaum, editor, *Security and Privacy in Digital Rights Management, ACM CCS-9 Workshop, DRM 2002, Washington, DC, USA, November 18, 2002, Revised Papers*, volume 2696 of *Lecture Notes in Computer Science*, pages 1–15. Springer, 2002. 73, 75, 95

[CFV19] Federico Cioschi, Nicolò Fornari, and Andrea Visconti. *White-Box Cryptography: A Time-Security Trade-Off for the SPNbox Family*, pages 153–166. 01 2019. 5, 15

[CGO21] Michele Ciampi, Vipul Goyal, and Rafail Ostrovsky. Threshold garbled circuits and ad hoc secure computation. Cryptology ePrint Archive, Report 2021/308, 2021. https://eprint.iacr.org/2021/308. 26

[CGPR15] David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. Leakage-abuse attacks against searchable encryption. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, *ACM CCS 2015*, pages 668–679. ACM Press, October 2015. 46, 47, 66

[Con22] Graeme Connell. Technology deep dive: Building a faster oram layer for enclaves. https://signal.org/blog/building-faster-oram/, 2022. 5, 14
[CP13] Kai-Min Chung and Rafael Pass. A simple ORAM. Cryptology ePrint Archive, Report 2013/243, 2013. https://eprint.iacr.org/2013/243. viii, 8, 18, 48, 60, 62

[DCRS12] Kevin P. Dyer, Scott E. Coull, Thomas Ristenpart, and Thomas Shrimp-
ton. Peek-a-boo, i still see you: Why efficient traffic analysis counter-
measures fail. In *2012 IEEE Symposium on Security and Privacy*, pages
332–346. IEEE Computer Society Press, May 2012. 47

[DFKYZD99] Ye Ding-Feng, Lam Kwok-Yan, and Dai Zong-Duo. Cryptanalysis of “2R” schemes. In *Annual International Cryptology Conference*, pages 315–325. Springer, 1999. 74

[DFLM18] Patrick Derbez, Pierre-Alain Fouque, Baptiste Lambin, and Brice Minaud. On recovering affine encodings in white-box implementations. *IACR Trans. Cryptogr. Hardw. Embed. Syst.*, 2018(3):121–149, 2018. 74, 76, 77, 80, 86

[Dic93] Matthew T Dickerson. General polynomial decomposition and the s-1-decomposition are np-hard. *International Journal of Foundations of Computer Science*, 4(02):147–156, 1993. 95, 98

[Din18] Itai Dinur. An improved affine equivalence algorithm for random permutations. In Jesper Buus Nielsen and Vincent Rijmen, editors, *Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I*, volume 10820 of *Lecture Notes in Computer Science*, pages 413–442. Springer, 2018. 86

[Din21] Itai Dinur. Improved algorithms for solving polynomial systems over GF(2) by multiple parity-counting. In Dániel Marx, editor, *Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021*, pages 2550–2564. SIAM, 2021. 82

[DLPR13] Cécile Delerablée, Tancrède Lepoint, Pascal Paillier, and Matthieu Rivain. White-box security notions for symmetric encryption schemes. Cryptology ePrint Archive, Paper 2013/523, 2013. https://eprint.iacr.org/2013/523. 75

[DS09] Itai Dinur and Adi Shamir. Cube attacks on tweakable black box polynomials. In Antoine Joux, editor, *Advances in Cryptology - EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings*, volume 5479 of *Lecture Notes in Computer Science*, pages 278–299. Springer, 2009. 77, 81

[FKN94] Uriel Feige, Joe Kilian, and Moni Naor. A minimal model for secure computation (extended abstract). In Frank Thomson Leighton and Michael T. Goodrich, editors, *Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada*, pages 554–563. ACM, 1994. 6, 16, 21, 22, 23, 42
[FP06] Jean-Charles Faugère and Ludovic Perret. Polynomial equivalence problems: Algorithmic and theoretical aspects. In Serge Vaudenay, editor, *Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings*, volume 4004 of Lecture Notes in Computer Science, pages 30-47. Springer, 2006. 82

[FP09] Jean-Charles Faugère and Ludovic Perret. An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography. *Journal of Symbolic Computation*, 44(12):1676-1689, 2009. 95, 98

[GKW15] Romain Gay, Iordanis Kerenidis, and Hoeteck Wee. Communication complexity of conditional disclosure of secrets and attribute-based encryption. In *CRYPTO (II)*, pages 485-502, 2015. 26

[GLMP18] Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, and Kenneth G. Patterson. Pump up the volume: Practical database reconstruction from volume leakage on range queries. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, *ACM CCS 2018*, pages 315-331. ACM Press, October 2018. 47

[GLMP19] Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, and Kenneth G. Patterson. Learning to reconstruct: Statistical learning theory and encrypted database attacks. In *2019 IEEE Symposium on Security and Privacy*, pages 1067-1083. IEEE Computer Society Press, May 2019. 45, 46, 66

[GMO01] Karine Gandolfi, Christophe Mourtel, and Francis Olivier. Electromagnetic analysis: Concrete results. In Çetin Kaya Koç, David Naccache, and Christof Paar, editors, *CHES 2001*, volume 2162 of LNCS, pages 251-261. Springer, Heidelberg, May 2001. 9, 19

[GMP16] Sanjam Garg, Payman Mohassel, and Charalampos Papamanthou. TWORAM: Efficient oblivious RAM in two rounds with applications to searchable encryption. In Matthew Robshaw and Jonathan Katz, editors, *CRYPTO 2016, Part III*, volume 9816 of LNCS, pages 563-592. Springer, Heidelberg, August 2016. 46, 67, 68

[GMQ07] Louis Goubin, Jean-Michel Masereel, and Michaël Quisquater. Cryptanalysis of white box DES implementations. In Carlisle M. Adams, Ali Miri, and Michael J. Wiener, editors, *Selected Areas in Cryptography, 14th International Workshop, SAC 2007, Ottawa, Canada, August 16-17, 2007, Revised Selected Papers*, volume 4876 of Lecture Notes in Computer Science, pages 278-295. Springer, 2007. 74, 75

[GO96] Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. *J. ACM*, 43(3):431-473, May 1996. 8, 17, 45, 49

[GRW20] Louis Goubin, Matthieu Rivain, and Junwei Wang. Defeating state-of-the-art white-box countermeasures with advanced gray-box attacks. *IACR Transactions on Cryptographic Hardware and Embedded Systems*, 2020(3):454-482, 2020. 74
[GSB+17] Paul Grubbs, Kevin Sekniqi, Vincent Bindschaedler, Muhammad Naveed, and Thomas Ristenpart. Leakage-abuse attacks against order-revealing encryption. In *2017 IEEE Symposium on Security and Privacy*, pages 655–672. IEEE Computer Society Press, May 2017. 66

[HK22] Shai Halevi and Eyal Kushilevitz. Random-index oblivious ram. Cryptology ePrint Archive, Paper 2022/982, 2022. 60

[IK97] Yuval Ishai and Eyal Kushilevitz. Private simultaneous messages protocols with applications. In *Fifth Israel Symposium on Theory of Computing and Systems, ISTCS 1997, Ramat-Gan, Israel, June 17-19, 1997, Proceedings*, pages 174–184. IEEE Computer Society, 1997. 6, 16, 21

[IK00] Yuval Ishai and Eyal Kushilevitz. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In *41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA*, pages 294–304. IEEE Computer Society, 2000. 33, 100, 101

[KM19] Seny Kamara and Tarik Moataz. Computationally volume-hiding structured encryption. In Yuval Ishai and Vincent Rijmen, editors, *EURO-CRYPT 2019, Part II*, volume 11477 of LNCS, pages 183–213. Springer, Heidelberg, May 2019. 67, 68

[KMO18] Seny Kamara, Tarik Moataz, and Olga Ohrimenko. Structured encryption and leakage suppression. In Hovav Shacham and Alexandra Boldyreva, editors, *CRYPTO 2018, Part I*, volume 10991 of LNCS, pages 339–370. Springer, Heidelberg, August 2018. 46, 49, 67

[Koc96] Paul C. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In Neal Koblitz, editor, *CRYPTO'96*, volume 1109 of LNCS, pages 104–113. Springer, Heidelberg, August 1996. 9, 18

[LHL+18] Zheli Liu, Yanyu Huang, Jin Li, Xiaochun Cheng, and Chao Shen. DivORAM: Towards a practical oblivious RAM with variable block size. *Information Sciences*, 447:1–11, 2018. 50, 105, 106

[Lin20] Yehuda Lindell. Secure multiparty computation (mpc). Cryptology ePrint Archive, Paper 2020/300, 2020. https://eprint.iacr.org/2020/300. 4, 13

[LN04] Hamilton E. Link and William D. Neumann. Clarifying obfuscation: Improving the security of white-box encoding. Cryptology ePrint Archive, Paper 2004/025, 2004. https://eprint.iacr.org/2004/025. 75

[LN18] Kasper Green Larsen and Jesper Buus Nielsen. Yes, there is an oblivious RAM lower bound! In Hovav Shacham and Alexandra Boldyreva, editors, *CRYPTO 2018, Part II*, volume 10992 of LNCS, pages 523–542. Springer, Heidelberg, August 2018. 49
[LRdM$^{+13}$] Tancrède Lepoint, Matthieu Rivain, Yoni de Mulder, Bart Preneel, and Peter Roelse. Two Attacks on a White-Box AES Implementation. In *SAC 2013 - 20th International Conference Selected Areas in Cryptography*, volume 8282 of *Selected Areas in Cryptography – SAC 2013*, pages 265–285, Burnaby, British Columbia, Canada, August 2013. Springer. 75

[LVW17] Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee. Conditional disclosure of secrets via non-linear reconstruction. In *CRYPTO Part I*, pages 758–790, 2017. 26

[MDFK15] Brice Minaud, Patrick Derbez, Pierre-Alain Fouque, and Pierre Karpman. Key-recovery attacks on ASASA. In Tetsu Iwata and Jung Hee Cheon, editors, *ASIACRYPT 2015, Part II*, volume 9453 of LNCS, pages 3–27. Springer, Heidelberg, November / December 2015. 10, 19

[MDFK18] Brice Minaud, Patrick Derbez, Pierre-Alain Fouque, and Pierre Karpman. Key-recovery attacks on ASASA. *Journal of Cryptology*, 31(3):845–884, 2018. 10, 19, 74, 75, 77, 80, 82, 83, 89, 92, 93, 94, 98

[MGH09] Wil Michiels, Paul Gorissen, and Henk D. L. Hollmann. Cryptanalysis of a generic class of white-box implementations. In Roberto Maria Avanzi, Liam Keliher, and Francesco Sica, editors, *Selected Areas in Cryptography*, pages 414–428, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. 75

[MLS$^{+13}$] Martin Maas, Eric Love, Emil Stefanov, Mohit Tiwari, Elaine Shi, Krste Asanovic, John Kubiatowicz, and Dawn Song. PHANTOM: practical oblivious computation in a secure processor. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, *ACM CCS 2013*, pages 311–324. ACM Press, November 2013. 46

[MM17] Ian Miers and Payman Mohassel. IO-DSSE: Scaling dynamic searchable encryption to millions of indexes by improving locality. In *NDSS 2017*. The Internet Society, February / March 2017. 46, 67

[MOA79] Albert W Marshall, Ingram Olkin, and Barry C Arnold. *Inequalities: theory of majorization and its applications*, volume 143. Springer, 1979. 51, 59

[MR22] Brice Minaud and Michael Reichle. Dynamic local searchable symmetric encryption. In Y. Dodis and T. Shrimpton, editors, *Advances in Cryptology – CRYPTO 2022*, Lecture Notes in Computer Science. Springer, 2022. 46, 47, 48, 105, 106

[MRP12] Yoni De Mulder, Peter Roelse, and Bart Preneel. Cryptanalysis of the Xiao - Lai white-box AES implementation. In Lars R. Knudsen and Huapeng Wu, editors, *Selected Areas in Cryptography, 19th International Conference, SAC 2012, Windsor, ON, Canada, August 15-16, 2012, Revised Selected Papers*, volume 7707 of *Lecture Notes in Computer Science*, pages 34–49. Springer, 2012. 75

[NS06] Arvind Narayanan and Vitaly Shmatikov. How to break anonymity of the netflix prize dataset. *CoRR*, abs/cs/0610105, 2006. 4, 13
[PPYY19] Sarvar Patel, Giuseppe Persiano, Kevin Yeo, and Moti Yung. Mitigating leakage in secure cloud-hosted data structures: Volume-hiding for multi-maps via hashing. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, *ACM CCS 2019*, pages 79–93. ACM Press, November 2019. 67, 68

[RAC16] Daniel S. Roche, Adam J. Aviv, and Seung Geol Choi. A practical oblivious map data structure with secure deletion and history independence. In *2016 IEEE Symposium on Security and Privacy*, pages 178–197. IEEE Computer Society Press, May 2016. 49, 50

[RVP22] Adrián Ranea, Joachim Vandersmissen, and Bart Preneel. Implicit white-box implementations: White-boxing ARX ciphers. In *Crypto*, 2022. 10, 19, 73, 74, 75, 77, 80, 81, 82, 86, 87, 89, 91, 92, 93, 95, 98

[RW19] Matthieu Rivain and Junwei Wang. Analysis and improvement of differential computation attacks against internally-encoded white-box implementations. *Cryptology ePrint Archive*, Report 2019/076, 2019. https://eprint.iacr.org/2019/076. 10, 19

[RYF+13] Ling Ren, Xiangyao Yu, Christopher W Fletcher, Marten Van Dijk, and Srinivas Devadas. Design space exploration and optimization of Path Oblivious RAM in secure processors. In *Proceedings of the 40th Annual International Symposium on Computer Architecture*, pages 571–582, 2013. 106

[SESN23] Kazumasa Shinagawa, Reo Eriguchi, Shohei Satake, and Koji Nuida. Private simultaneous messages based on quadratic residues. *Designs, Codes and Cryptography*, pages 1–18, 2023. 97

[SMG16] Pascal Sasdrich, Amir Moradi, and Tim Güneysu. White-box cryptography in the gray box. In *International Conference on Fast Software Encryption*, pages 185–203. Springer, 2016. 74

[SvS+13a] Emil Stefanov, Marten van Dijk, Elaine Shi, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. Path ORAM: An extremely simple oblivious RAM protocol. *Cryptology ePrint Archive*, Report 2013/280, 2013. https://eprint.iacr.org/2013/280. 8, 18, 97

[SvS+13b] Emil Stefanov, Marten van Dijk, Elaine Shi, Christopher W. Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. Path ORAM: an extremely simple oblivious RAM protocol. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, *ACM CCS 2013*, pages 299–310. ACM Press, November 2013. viii, 48, 60, 62, 63

[Swe00] Latanya Sweeney. Simple Demographics Often Identify People Uniquely. 1 2000. 4, 13

[TW07] Kunal Talwar and Udi Wieder. Balanced allocations: the weighted case. In David S. Johnson and Uriel Feige, editors, *39th ACM STOC*, pages 256–265. ACM Press, June 2007. 48, 106
[VRP22] Joachim Vandersmissen, Adrián Ranea, and Bart Preneel. A white-box Speck implementation using self-equivalence encodings. In Giuseppe Ateniese and Daniele Venturi, editors, *Applied Cryptography and Network Security - 20th International Conference, ACNS 2022, Rome, Italy, June 20-23, 2022, Proceedings*, volume 13269 of *Lecture Notes in Computer Science*, pages 771-791. Springer, 2022. 75

[WCS14] Xiao Wang, Hubert Chan, and Elaine Shi. Circuit ORAM: On tightness of the Goldreich-Ostrovsky lower bound. Cryptology ePrint Archive, Report 2014/672, 2014. https://ia.cr/2014/672. viii, 60, 65

[WHS12] Michael Weiß, Benedikt Heinz, and Frederic Stumpf. A cache timing attack on AES in virtualization environments. In Angelos D. Keromytis, editor, *FC 2012*, volume 7397 of LNCS, pages 314-328. Springer, Heidelberg, February / March 2012. 45

[Wik23] Wikipedia contributors. Empress (cracker) — Wikipedia, the free encyclopedia. https://en.wikipedia.org/w/index.php?title=Empress_(cracker)&oldid=1170884992, 2023. [Online; accessed 28-August-2023]. 6, 15

[WMGP07] Brecht Wyseur, Wil Michiels, Paul Gorissen, and Bart Preneel. Cryptanalysis of white-box des implementations with arbitrary external encodings. In *Selected Areas in Cryptography*, pages 264-277. Springer, 2007. 74, 75

[WNL+14] Xiao Shaun Wang, Kartik Nayak, Chang Liu, T.-H. Hubert Chan, Elaine Shi, Emil Stefanov, and Yan Huang. Oblivious data structures. In Gail-Joon Ahn, Moti Yung, and Ninghui Li, editors, *ACM CCS 2014*, pages 215-226. ACM Press, November 2014. 69

[XL09] Yaying Xiao and Xuejia Lai. A secure implementation of white-box aes. *2009 2nd International Conference on Computer Science and its Applications*, pages 1-6, 2009. 75

[Yao82] Andrew Chi-Chih Yao. Protocols for secure computations (extended abstract). In *23rd FOCS*, pages 160-164. IEEE Computer Society Press, November 1982. 4, 13
<figure><img src="image_11.png" /></figure>
<figure><img src="image_12.png" /></figure>
# RÉSUMÉ

Dans cette thèse, nous étudions différentes méthodes permettant de faire des calculs sur de l'information cachée. Nous présentons de nouvelles constructions de protocoles, allant de l'amélioration des complexités de l'état de l'art à l'ajout de fonctionnalités. Nous analysons également la sécurité d'autres protocoles, et présentons des attaques dessus.

En premier lieu, nous nous intéressons au Private Simultaneous Messages, où un groupe d'individus souhaite faire apprendre à une entité externe le résultat d'un calcul sur leurs données privées. En utilisant un nouveau cadre, nous montrons de nouvelles constructions avec un coût en communication plus bas que celles déjà existantes. Ensuite, nous étudions des protocoles d'Oblivious RAM, qui dissimulent le motif d'accès qu'un client fait lorsqu'il accède à des données privées stockées sur un serveur non fiable. Nous présentons les premières constructions permettant au client d'enregistrer des objets de tailles arbitrairement différentes. Nous montrons également comment ces constructions permettent de construire des protocoles de Chiffrement Recherchable. Enfin, nous nous intéressons à la cryptographie en boîte-blanche, qui a pour objectif de donner à un appareil non fiable un accès sans restrictions à un algorithme de chiffrement, tout en empêchant la fuite de la clé secrète. Nous présentons une cryptanalyse de la construction de Ranea et al. de CRYPTO 2022, où des cryptosystèmes en boîte blanche sont donnés à partir de chiffrements symétriques basés sur des SPN et ARX. Nous prouvons que ce système n'est pas sûr en présentant une attaque structurelle de récupération de clé.

# MOTS CLÉS

PSM, MPC, Boîte-Blanche, ORAM, SSE, Cryptanalyse

# ABSTRACT

In this thesis, we study different methods of computing on hidden information. We present new constructions of protocols, which either improve on their state-of-the-art complexities or enable them to do more. We also analyse the security of other protocols and give attacks on them.

The first subject we consider is that of Private Simultaneous Messages, where a group of individuals wish to have an external entity learn the output of a computation on their private data. Using a new framework, we show new constructions with a smaller communication cost than existing ones. We then study Oblivious RAM protocols, that hide the access pattern that a client makes when accessing private data stored on an untrusted server. We give the first constructions that allow the client to store data items of arbitrarily different sizes. We also show how using these constructions yield new protocols for Searchable Encryption. We finish by studying white-box cryptography, where the goal is to give an untrusted device unrestricted access to an encrytpion algorithm, while preventing the secret key from leaking. We present a cryptanalysis of Ranea et al's construction from CRYPTO 2022, where they give white-box ciphers from SPN and ARX based symmetric cryptosystems. We show that this scheme is insecure by providing a structural key-recovery attack.

# KEYWORDS

PSM, MPC, White-Box, ORAM, SSE, Cryptanalysis