Linear-Time Secure Merge in O(loglog n) Rounds

The relationship between secure merging and secure sorting can be traced back to [3], which built a sorting network of size $O(n{\log }^{2}n)$ from $\log n$ merging networks, each of size $O(n\log n)$. There are $(2n)!=2^{O(n\log n)}$ permutations on $2n$ elements, but $\left(\genfrac{}{}{0pt}{}{2n}{n}\right)=2^{O(n)}$ possible ways two sorted lists can be merged together. This gives combinatorial lower bounds of $\mathrm{\Omega }(n\log n)$ and $\mathrm{\Omega }(n)$ comparators for sorting and merging networks, respectively. Although an asymptotically optimal sorting network of size $O(n\log n)$ was later achieved by Ajtai, Komlos, and Szemeredi [1], merging networks cannot achieve the combinatorial lower bound of $n$ comparators. A merging network on lists of size $\mathrm{\Theta }(n)$ require $\mathrm{\Omega }(n\log n)$ comparators, as shown by Yao and Yao [26], and depth of $\mathrm{\Omega }(\log n)$, as shown by Hong and Sedgewick [16].

The classical merge algorithm requires $O(n)$ work on a RAM machine, see e.g., [21]. As discussed below, [10] uses an approach that is inspired by this classical merge algorithm, and achieves matching asymptotic work (albeit with $O(n)$ round-complexity).

A parallel RAM machine (PRAM) allows multiple processors to act on the same set of memory in parallel. We are in particular interested in Concurrent-Read-Exclusive-Write (CREW) PRAM, where all processors can read the same memory simultaneously, but processors cannot write to the same memory address at the same time, see e.g., [4] for more formal definitions and a discussion of various PRAM models. For PRAM machines, Valiant showed in [25] that $O(n)$ processors could merge two lists of size $O(n)$ in time $O(\log \log n)$. This was improved by Borodin and Hopcroft [4] to $O(n/\log \log n)$ processors, who also showed that the time bound of $O(\log \log n)$ is optimal when limited to $O(n)$ processors. As a rough heuristic, we expect the number of processors and total work done by a PRAM algorithm to serve as a lower bound for the round complexity and communication complexity of a corresponding secure protocol, motivating the following:

Notice that if the above conjecture is valid, then our secure merge protocol (§4) is asymptotically optimal in all three key metrics. To lend weight to this conjecture, we note that if a 2-party protocol $\mathrm{\Pi }$ securely realizes some functionality $ℱ$ in $R$ rounds and $C$ communication, and each party can execute each round of the protocol in $O(1)$ time on a CREW PRAM with $C$ processors, then there exists an algorithm $A$ that realizes $ℱ$ on a single CREW PRAM machine with $C$ processors, $O(RC)$ total work, and $O(R)$ time. Indeed, $A$ merely executes $\mathrm{\Pi }$, playing the role of all parties. If a protocol for secure merge existed with $C=n$, $R=o(\log \log n)$, this would immediately imply an insecure merge algorithm with $O(n)$ processors and $o(\log \log n)$ time, contradicting the lower bound of [4] cited above. Thus the conjecture is true for the special case of secure merge protocols where each round of the protocol can be executed in $O(1)$ time on a CREW PRAM with $O(n)$ processors.

Both the Valiant and the Borodin-Hopcroft algorithms rely on the following basic construction: Split each list into blocks of size $\sqrt{n}$, with $\sqrt{n}$ medians. Running all pairwise comparisons between medians identifies which block of the opposite list each median is mapped to; then another round of pairwise comparisons identifies the exact position the median is mapped to within that block. This creates $\sqrt{n}$ subproblems of size $\sqrt{n}$, giving the recurrence $c(n)=\sqrt{n}\cdot c(\sqrt{n})$, if $c(n)$ is the cost of merging two lists of length $n$. With sufficiently many processors, this recurrence yields $O(\log \log n)$ run-time. Our protocols in §4 use similar techniques as a starting point, though many additional ideas are needed to handle the secure setting, e.g. securely handling the case where blocks from one list potentially span more than one block of the other list.

To aid the comparison to prior work, we introduce the following constants: $\kappa$ is a computational security parameter (e.g., $\kappa =128$ is standard), ${\beta }_{{}_{\text{HE}}}$ (resp. ${\beta }_{{}_{\text{FHE}}}$) is the ciphertext expansion of an additively homomorphic (resp. fully homomorphic) cryptosystem, $\gamma$ is the cost of decryption, and $\mu$ is the cost of multiplication in the FHE cryptosystem.

The parameters ${\beta }_{{}_{\text{HE}}}$, ${\beta }_{{}_{\text{FHE}}}$, $\gamma$, and $\mu$ depend on the cryptosystem and on $\kappa$. Asymptotically, $\kappa \gg \log n$ is necessary so that a random bit-string of length $\kappa$ cannot be guessed in the time it takes to traverse the list, and (for suitable choice of cryptosystems) ${\beta }_{{}_{\text{HE}}}$ and ${\beta }_{{}_{\text{FHE}}}$ approach $1$ as the plaintext size grows. In practice, fully homomorphic encryption schemes are more costly than additive-only homomorphic ones, so we expect ${\beta }_{{}_{\text{FHE}}}>{\beta }_{{}_{\text{HE}}}$ and $\mu >\gamma$.

We assume the objects to be sorted are contained in $O(1)$ memory words of size $W$ bits. Unless explicitly stated otherwise, our communication and computational complexity numbers are given in terms of memory words and primitive operations on memory words.

We explore here two naïve solutions for transforming an insecure merge algorithm to a secure one (see Table 1 for a succinct comparison of our secure merge protocol to these naïve solutions):

Garbled Circuits. By choosing any (insecure) sorting algorithm that can be represented as a circuit, the parties can use garbled circuits to (securely) sort their list in $O(1)$ rounds. As discussed above in §2, for comparison-based merging networks, $\mathrm{\Omega }(n\log n)$ comparisons and $\mathrm{\Omega }(\log n)$ depth are necessary, and achievable by the Batcher merging network [3].

We note that obtaining $\kappa$ bits of computational security when merging lists whose elements have size $W$ bits requires $\kappa \cdot W$ bits, or $\kappa$ words of communication for each comparison. Thus, obtaining secure merge via a garbled circuit approach (for a circuit representing a merging network) would result in a constant-round protocol with $\mathrm{\Omega }(\kappa \cdot n\log n)$ communication.

On the other hand, using GMW-style circuit evaluation (see [12]) instead of garbled circuits can reduce the overhead of each comparison (from $\kappa$ down to constant), but it incurs a hit in round complexity (proportional to the depth of the circuit instead of constant-round).

Fully Homomorphic Encryption (FHE). An $O(1)$ round protocol can also be constructed by having one party encrypt their inputs under FHE and send the result to the other party, who performs the desired calculations on ciphertexts. The other party then subtracts a vector of random values $𝐫$ from the (encrypted) merged list and sends the result back to the first party, who decrypts to obtain the merged list shifted by $𝐫$. Now the parties hold an additive sharing of the sorted list.

As with garbled circuits, however, the calculations the second party performs on the ciphertexts must be input-independent (in order to avoid information leakage), and so the calculation must be represented by a circuit. This means that communication is (asymptotically) lower than the garbled circuit approach, since the first party need only provide ciphertexts of his list (which correspond to inputs to the circuit), as opposed to providing information for each gate. Therefore the communication required for FHE is $O({\beta }_{{}_{\text{HE}}}n)$.

However, while communication in the FHE approach may be (asymptotically) reduced (compared to the garbled circuit approach), notice that the computation is still $\mathrm{\Omega }(\mu n\log n)$, where $\mu$ is the cost of a multiplication under FHE, as the circuit requires $\mathrm{\Omega }(n\log n)$ comparison (multiplication) operations. Additionally, since the circuit has depth $\mathrm{\Omega }(\log n)$, FHE will require bootstrapping to avoid ciphertext blowup, which will be expensive in practice.

ORAM and GRAM. ORAM incurs at least an $\mathrm{\Omega }(\log n)$ overhead [13, 19]. Currently known GRAM constructions are built using ORAM as a building block. Therefore, if one is to take an insecure merge implementation and try to compile it into a secure circuit using ORAM or GRAM, both the computational and communication complexity will be $O(n\log n)$, and thus these techniques are inapplicable if we aim to achieve linear complexity.

One challenge facing any comparison-based secure merge (or sort) protocol is that the results of each comparison must be kept secret from each party, or else security is lost. One approach to allowing the results of the comparisons to be known without information leakage is to first shuffle (in an oblivious manner) the input lists. However, since shuffling will destroy the property that the input lists are pre-sorted, this approach reduces a secure merge problem to a secure sort problem, hence incurring the $\log n$ efficiency loss.

Comparison-based sorting has $O(n\log n)$ communication and computation and $O(\log n)$ rounds, while secure shuffling requires $O(n)$ communication and $O(1)$ rounds, see e.g., [11, 15]. Therefore, a secure sort using the shuffle-sort paradigm requires $O(n\log n)$ communication and computation and $O(\log n)$ rounds, which is worse than our results in all three metrics.

Because the constant from [1] is too large for practical applications, a number of other approaches to secure sorting have been explored. The shuffle-sort paradigm mentioned above is one example of a large family of oblivious sort protocols, which allow for a variable memory access pattern as long as it is independent of the underlying list values, or data oblivious. We mention here the radix sort of Hamada et al. [14], which achieves $O((W\log W+W)n+n\log n)$ communication (in memory words) and $O(1)$ round complexity in the three-party honest majority setting with constant bit lengths of elements. The communication complexity was later improved by Chida et. al [8], to $O(n\log n)$ memory words. However, the round complexity depends linearly on $W$, so when $W\approx \log n$, this matches the round complexity of the other protocols.

There are several works that investigate secure merge directly. The first, due to Falk and Ostrovsky [11], achieves $O(n\log \log n)$ communication complexity with $O(\log n)$ round complexity. The second, due to Falk, Nema, Ostrovsky [10], achieves the asymptotically optimal $O(n)$ communication complexity (with small constants), but requires $O(n)$ rounds of communication. For many cryptographic applications, a high round complexity causes more of a bottleneck than a high communication complexity due to network latency. Therefore, the secure merge protocol of [10], while both simple and asymptotically optimal in terms of communication, may still not be practical due to high round complexity.

In a subsequent work [6], Chakraborty et al. present a series of secure merge protocols, optimizing for concrete efficiency. Some of their protocols use similar machinery to our work presented here – and indeed, their paper cites our work here as inspiring some of their ideas. In [6], the authors explore the trade-offs between communication and rounds, giving protocols with worse asymptotic performance than our protocols. See the full version for a discussion of the concrete efficiency of our protocols and comparisons with standard (insecure) merge protocols.

The three party honest majority setting is a natural fit for real-world protocols in the client-server model, including ORAM and PSI protocols. Prior work in this area has shown how the use of three parties facilitates more efficient protocols, including through the use of one party to generate randomness for the other parties and more efficient shuffling protocols (see e.g., [11]). The oblivious sort protocols mentioned above [14, 8] use three parties for shuffling and to enable the use of a Shamir secret sharing scheme. In [7] Chan et al. give a three-server merge protocol in the course of building a three-server ORAM scheme. This merge protocol, which requires three servers and an honest client, is most similar to the FNO protocol [10], and similarly requires $O(n)$ round complexity.

The security of the ${𝚷}_{\mathrm{𝐒𝐒𝐌}}(n)$ protocol follows immediately from the security of the underlying ${𝚷}_{\mathrm{𝐃𝐮𝐩}}$, ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}$, ${𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime }}$, and ${𝚷}_{\mathrm{𝐒𝐀𝐌}}$ protocols.

Assuming correctness of ${𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime }}(n/k)$, ${𝚷}_{\mathrm{𝐒𝐀𝐌}}(k,n)$, ${𝚷}_{\mathrm{𝐃𝐮𝐩}}$, and ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}$ subprotocols, we need only demonstrate that the concatenation done in Step 4 above is correct, that is, that the blocks “align” as per the partitioning. Namely, this follows from Lemma 2, which demonstrates that lists $L_1^{\prime \prime }$ and $L_2^{\prime \prime }$ have the same list of $2k$ medians (both equal ${ℳ}_{1,k}⨆{ℳ}_{2,k}$).

Step (1) invokes the ${𝚷}_{\mathrm{𝐒𝐀𝐌}}(k,n)$ protocol (Figure 5) twice; Step (2) invokes the ${𝚷}_{\mathrm{𝐃𝐮𝐩}}(k,n/k)$ protocol twice; Step (3) invokes the ${𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime }}(n/k)$ protocol $2k$ times; and Step (4) invokes the secure ordered extract ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}(4n,2n)$ protocol. Using the ${𝚷}_{\mathrm{𝐃𝐮𝐩}}(k,n/k)$ and the ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}(4n,2n)$ protocols, and assuming constant-round and linear secure protocols for ${𝚷}_{\mathrm{𝐂𝐨𝐦𝐩}}$, ${𝚷}_{\mathrm{𝐑𝐞𝐯𝐞𝐚𝐥}}$, and ${𝚷}_{\mathrm{𝐒𝐡𝐮𝐟𝐟𝐥𝐞}}$, adding up these costs yields:

Using ${𝚷}_{\mathrm{𝐒𝐌}-\mathrm{𝐅𝐍𝐎}}$ for ${𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime }}(n/k)$, and using for ${𝚷}_{\mathrm{𝐒𝐀𝐌}}(k,n)$ our protocol of Fig. 5 – with subprotocols ${𝚷}_{\mathrm{𝐒𝐒𝐌}-\mathrm{𝐅𝐍𝐎}}$ for ${𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime }}(n/k)$ and ${𝚷}_{\mathrm{𝐒𝐒𝐌}\text{-}\log \log }$ for ${𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime \prime }}(k)$ – and using $k=n/\log \log n$, the cost becomes:

For Steps 1, 2a, 2b, 2c, 3a, and 3b: security follows from the security of the underlying subprotocols. Namely, a simulator for the protocol for either party calls the simulator for each subprotocol: ${𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime \prime }}$, ${𝚷}_{\mathrm{𝐂𝐨𝐦𝐩}}$, ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}$, ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐁𝐢𝐧}}$, ${𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime \prime }}$, and ${𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime }}$, respectively. Meanwhile, the correctness property ensures that the indices revealed in Step 4 are unique and are a (random) permutation of the values in $[1,\mathrm{\dots },(k+n)]$. Therefore, the simulator for Step 4 generates a random permutation of $(k+n)$ elements.

We first clarify that the merges done in Steps 1, 3a, and 3b are done “in-place”: rather than actually constructing an output merged list, these merges instead determine each element’s index in what would be the merged list, and then append (shares of) this index as a tag applied to the element (in its original list). In this way, we may manipulate (add, subtract, etc.) the indices produced by the merges in Steps 1, 3a, and 3b, to compute each element’s index in the final merged list based on its indices in the outputs of the earlier “in-place” merges.

To verify correctness, it will be useful to set notation corresponding to the formula in Step 4 of Figure 5 as follows:

where $Block\mathrm{\_}Index=Y+Z$ denotes the index of an element in its own block. Thus, any element’s final index in the merged list is: $U+V+W+X+Y+Z$. This quantity can be computed for each element based on information available from Steps 1-3, as follows:

$L_1.WA$:

$(U+V+Y)$ is available from each element’s original position in $L_1$; $(W+X)$ is available as $j\cdot n/k$, where $j$ is the block of $L_2$ that this element maps to (from Step 1); $(Y+Z)$ is the output index from Step 3b; and -$Y$ is this element’s position after merging its well-aligned block (Step 2c).

$L_2.WA$:

$(U+V)$ is available from Step 2a; $(W+X)$ is available as $j\cdot n/k$, where $j$ is the block of $L_2$ that this element lies in; and $(Y+Z)$ is the output index from Step 3b.

$L_1.PA$:

$(U+V+Y)$ is available from each element’s original position in $L_1$; $(W+X)$ is available as $j\cdot n/k$, where $j$ is the block of $L_2$ that this element maps to (from Step 1); $(V+X+Y+Z)$ is the output index from Step 3a; $(-V-Y)$ is from Step 2b; and $-X$ is $n/k$ times the number of poorly-aligned blocks to the left, which is computable from the info in Step 2a.

$L_2.PA$:

$(U+V)$ is available from Step 2a, while $-V$ is available by using the information from Step 1 applied just to the poorly-aligned items extracted in Step 2b; $(W+X)$ is available as $j\cdot n/k$, where $j$ is the block of $L_2$ that this element lies in; $(V+X+Y+Z)$ is the output index from Step 3a; and $-X$ is $n/k$ times the number of poorly-aligned blocks to the left, which is computable from the info in Step 2a.

It remains to show that the pre-conditions of the ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}$ and ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐁𝐢𝐧}}$ protocols are satisfied. Namely, how to (efficiently) construct the input parameters $C$ and $T^{\prime }$ of the ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐁𝐢𝐧}}$ protocol; and that at most $n/k$ elements are extracted from each list into each well-aligned block and at most $k$ elements are extracted from each list into the poorly-aligned block. These are stated and proved in the following observations:

For each $i\in [1..k]$, let ${\iota }_i$ denote the position of the $k^{th}$ median of $L_2$ in the output list of Step 1; and let ${\delta }_i$ be an indicator on whether $t_i>0$. Then formulas for $C=\{c_j\}$ can be expressed iteratively as: $c_1={\delta }_1\text{and}{c}_{j+1}={\delta }_{j+1}\cdot (1+{\sum }_{i\le j}{t}_i^{\prime })$; and for $T^{\prime }=\{t_j^{\prime }\}$ as: $t_1^{\prime }={\iota }_1-1\text{and}{t}_{j+1}^{\prime }={\iota }_{j+1}-j-{\sum }_{i\le j}{t}_i^{\prime }$. While these expressions can be computed securely without introducing additional overhead to the overall protocol, the multiplication by ${\delta }_i$ in the expression of $c_{j+1}$ would require a secure (non-local) computation. However, we leverage the fact that the ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐁𝐢𝐧}}$ protocol (see full version) works correctly even if $c_j$ is an arbitrary value when $t_j^{\prime }=0$. Thus, the ${\delta }_i$ terms can be dropped from the above expression, and then, by linearity of the secret-sharing scheme, each party can locally compute their shares of $C$ and $T^{\prime }$ by using their shares of the relevant variables on the RHS of each of the above expressions for $t_j^{\prime }$ and $c_j$. $◀$

Since $L_1$ has size $k$, this statement is trivially true for $L_1$. Meanwhile, for each poorly-aligned segment of $L_2$, by definition there are at least $n/k+1$ elements from $L_1$ that are assigned this segment. Thus, the $k$ elements of $L_1$ can cause at most poorly-aligned segments. Since each segment has size $n/k$, this corresponds to at most elements of $L_2$. $◀$

Blocks are defined as the $n/k$ elements to the left of (and including) each (of the $k$) median of $L_2$, so this is trivially true for $L_2$. Meanwhile, for $L_1$, any block that contains more than $n/k$ elements of $L_1$ will be a poorly-aligned block, and consequently the corresponding elements from $L_1$ will all be labelled “poorly-aligned,” which means no elements from $L_1$ will be extracted by ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐁𝐢𝐧}}$ in Step 2c for this block. $◀$

• $\mathrm{■}$

  Step (1) has $\text{RCost}({𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime \prime }}(k))$ and $\text{CCost}({𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime \prime }}(k))$.

• $\mathrm{■}$

  Step (2a) has $\text{RCost}({𝚷}_{\mathrm{𝐂𝐨𝐦𝐩}})$ and $\mathrm{\Theta }(k)\cdot \text{CCost}({𝚷}_{\mathrm{𝐂𝐨𝐦𝐩}})$.

• $\mathrm{■}$

  Step (2b) has $\text{RCost}({𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}(k,k))+\text{RCost}({𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}(n,k))$ and
  $\text{CCost}({𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}(k,k))+\text{CCost}({𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}(n,k))$.

• $\mathrm{■}$

  Step (2c) has $\text{RCost}({𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐁𝐢𝐧}}(k,k,n/k))+k\cdot \text{RCost}({𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}(n/k,n/k))$
  and $\text{CCost}({𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐁𝐢𝐧}}(k,k,n/k))+k\cdot \text{CCost}({𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}(n/k,n/k))$.

• $\mathrm{■}$

  Step (3a) has $\text{RCost}({𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime \prime }}(k))$ and $\text{CCost}({𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime \prime }}(k))$.

• $\mathrm{■}$

  Step (3b) has $\text{RCost}({𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime }}(n/k))$ and $k\cdot \text{CCost}({𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime }}(n/k))$.

• $\mathrm{■}$

  Step (4) has $\text{RCost}({𝚷}_{\mathrm{𝐄𝐱𝐭𝐫𝐚𝐜𝐭}}(2(k+n),k+n))+\text{RCost}({𝚷}_{\mathrm{𝐑𝐞𝐯𝐞𝐚𝐥}})$ and
  $\text{CCost}({𝚷}_{\mathrm{𝐄𝐱𝐭𝐫𝐚𝐜𝐭}}(2(k+n),k+n))+(k+n)\cdot \text{CCost}({𝚷}_{\mathrm{𝐑𝐞𝐯𝐞𝐚𝐥}})$.

Using the costs of subprotocols ${𝚷}_{\mathrm{𝐄𝐱𝐭𝐫𝐚𝐜𝐭}}$, ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐎𝐫𝐝}}$, and ${𝚷}_{\mathrm{𝐄𝐱𝐭}\text{-}\mathrm{𝐁𝐢𝐧}}$, and assuming constant-round and linear secure protocols for ${𝚷}_{\mathrm{𝐂𝐨𝐦𝐩}}$, ${𝚷}_{\mathrm{𝐑𝐞𝐯𝐞𝐚𝐥}}$, and ${𝚷}_{\mathrm{𝐒𝐡𝐮𝐟𝐟𝐥𝐞}}$, we add up the contributions from each step to obtain:

Using ${𝚷}_{\mathrm{𝐒𝐌}-\mathrm{𝐅𝐍𝐎}}$ for ${𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime }}(n/k)$ and ${𝚷}_{\mathrm{𝐒𝐒𝐌}\text{-}\log \log }$ for ${𝚷}_{{\mathrm{𝐒𝐒𝐌}}^{\prime \prime }}(k)$, the cost is: