Fully Oblivious Differential Privacy for Frequency Estimation in the Augmented Shuffle Model with Trusted Processors
arXiv:2606.09402v1 [cs.CR] 8 Jun 2026
Takao Murakami ISM/ROIS/AIST/RIKEN AIP
Abstract In the shuffle model of DP (Differential Privacy), a shuffler randomly permutes users’ data to achieve high accuracy and privacy. Recent studies show that most existing shuffle protocols are vulnerable to collusion attacks by the data collector and users. They address this issue by introducing the augmented shuffle model that incorporates random sampling and dummy data addition into the shuffler. However, it remains open how to ensure the shuffler follows the protocol and does not collude with the data collector in this model. We address this trust issue by thoroughly exploring the augmented shuffle model with TEEs (Trusted Execution Environments). We first introduce a new privacy notion, FODP (Fully Oblivious DP), which strengthens DP to prevent various TEE side-channel attacks based on external/internal memory access patterns and control flows. We propose a general framework for FODP algorithms based on memory-size obfuscation and three concrete algorithms within it. We also improve the efficiency of our algorithms by using the countmin sketch and optimizing the number of hashes. We evaluate our algorithms on Intel SGX and demonstrate their effectiveness through comparisons with nine baselines.
1
Introduction
DP (Differential Privacy) [28] enables data analysis with strong privacy, especially when a parameter called the privacy budget ε is small. Depending on its underlying architecture, DP can be divided into some models, such as the central [28], local [46], and shuffle models [29]. In the central model, a single data collector holds all users’ raw data and adds noise to their statistics (e.g., histograms, heavy hitters). A drawback of this model is that all data can be leaked from the data collector through data breaches or cyberattacks [59]. The local model prevents data leakage by adding noise to a user’s data before sending it to the data collector. However, it suffers from low accuracy due to large local noise. The shuffle model addresses this issue by introducing a shuffler, which does not
Yuichi Sei UEC
Reo Eriguchi AIST
collude with the data collector. In this model, each user sends noisy data to the shuffler. Then, the shuffler randomly shuffles the noisy data and sends the shuffled data to the data collector. The random shuffling amplifies privacy; i.e., it significantly reduces the value of ε. Thus, the shuffle model significantly improves the local model’s accuracy at the same value of ε. However, most existing protocols assume a pure shuffle model, where the shuffler only shuffles noisy values sent from users, and are vulnerable to collusion attacks by the data collector and some malicious users (abbreviated as collusion with users) [60, 76]. Specifically, the data collector may obtain noisy data from some users by colluding with them or compromising their accounts. As a result, the pure shuffle model suffers from an increase of ε (or suboptimal accuracy when attempting to prevent it); see Section 3.3 for details. To prevent collusion with users, some recent studies [60,76] introduce an augmented shuffle model, which incorporates additional operations (e.g., random sampling, adding dummies) into the shuffler. For example, [76] proposes the UD (Uniform Dummies) protocol, in which the shuffler adds dummies uniformly randomly sampled from the space of noisy data. [76] shows that the uniform dummies significantly improve the robustness against collusion with users. [60] proposes the LNF (Local-Noise-Free) protocol, in which users do not add noise and the shuffler performs random sampling and dummy data addition. This protocol achieves ideal robustness against collusion with users in that the value of ε is not increased by the collusion. [60] also shows that the LNF protocol provides much higher accuracy than other shuffle DP protocols. Trust Issue. The story does not end there, as one important trust issue remains in the augmented shuffle model. Specifically, we must ensure that the shuffler follows the protocol and does not collude with the data collector. For example, we must ensure that the shuffler randomly shuffles data sent from users and does not leak non-shuffled data to the data collector. One promising solution to achieve this is to use a TEE (Trusted Execution Environment) [70], which protects data and the running code by memory encryption. The TEE guarantees data confidentiality by preventing entities outside the
TEE from reading raw data. It also guarantees integrity by providing a cryptographic proof that the running code is genuine [7]. Therefore, we can prevent the shuffler from deviating from the protocol or leaking non-shuffled data by implementing it within the TEE [6, 18]. In this case, users communicate with a single server; i.e., the TEE inside the server serves as a shuffler, and the data collector is outside the TEE. Side-Channel Attacks. However, recent studies show that TEEs are vulnerable to various side-channel attacks based on external/internal memory access patterns [6, 19, 49] and control flows (e.g., if statements, loops) [50, 58]. Note that although external memory-based attacks can be prevented by oblivious shuffling [6, 18, 65], adversaries can also obtain internal memory access patterns and control flows through state-of-the-art attacks; see [68] for surveys of these attacks. In addition, the shuffler performs not only shuffling but also random sampling and dummy data addition in the augmented shuffle model. Thus, we arrive at the following question: how can we prevent all of the side-channel attacks explained above in the augmented shuffle model with TEEs?
1.1
Our Approaches
We comprehensively study the above question in frequency estimation [56, 60, 75, 76], a fundamental data analysis task that estimates the frequency of each item. We first introduce a new privacy notion called FODP (Fully Oblivious DP). FODP strengthens DP based on the notion of full obliviousness [68, 69], which guarantees that no information about secret data is leaked from external/internal memory access patterns and control flows. Specifically, FODP provides DP guarantees for all of the algorithm’s output, external/internal memory access patterns, and control flows. We use FODP as a privacy notion for internal adversaries (i.e., server administrators) who can obtain side-channel information, and DP for external adversaries (i.e., everyone) who can access the published frequency distribution. Then, we propose a general framework for FODP algorithms. At a high level, our framework obfuscates the memory size to be allocated by adding bots “⊥” for each item. It also makes control flows dependent only on the obfuscated memory size. Our key insight is that the memory access patterns and control flows in our framework depend on users’ data only through bot counts, i.e., the number of ⊥ for each item (Lemma 1). This enables us to reduce FODP of our framework to the privacy of shuffled data and bot counts. Based on this insight, we propose three concrete algorithms in our framework: FOUD, FOLNF, and FOLNF∗ . FOUD and FOLNF are fully oblivious versions of the UD and LNF protocols, respectively. In FOUD, we modify the UD protocol so that the value of ε is not increased by collusion with users. Both FOUD and FOLNF set bot counts to constants and therefore provide FODP. FOLNF∗ is a variant of FOLNF that generates bot counts under DP. FOLNF∗ improves the efficiency
(runtime) of FOLNF at the same privacy budget in DP by increasing the privacy budget in FODP, i.e., by relaxing the privacy against internal adversaries. It also achieves pure DP (δ = 0) when using random sampling. For large-domain data, we further improve the efficiency of our algorithms by using the count-min sketch [25]. For our improved algorithms, we show an accuracy bound much tighter than [24, 33] and optimize the number of hashes in the count-min sketch based on our bound. Our Contributions. Our contributions are as follows: • We present a new privacy notion called FODP to provide privacy guarantees against adversaries who can obtain all of the randomized algorithm’s output, external/internal memory access patterns, and control flows. • We propose a general framework for FODP algorithms and three instantiations: FOUD, FOLNF, and FOLNF∗ . We prove that they achieve DP, FODP, and robustness against collusion with users. We also analyze the accuracy and runtime of these algorithms. • For large-domain data, we improve the efficiency of our algorithms using the count-min sketch. We show an accuracy bound much tighter than [24, 33] and propose a technique to optimize the number of hashes based on it. • We evaluate our algorithms on Intel SGX [7], a popular trusted processor (TEE implementation). We show the effectiveness of our algorithms through comparisons with nine baselines (eight state-of-the-art shuffle algorithms and a central DP algorithm explained later). The proofs of all statements are in Appendix E. Technical Novelty. In this paper, we introduce several new theoretical and algorithmic ideas, as explained below. First, we introduce not only a privacy notion called FODP but also two proof techniques for FODP. Specifically, we connect FODP to DP and full obliviousness for each user’s data (Theorem 1). Based on this, we introduce two proof techniques: (i) showing FODP via full obliviousness and (ii) directly showing FODP. We prove FODP of FOUD and FOLNF by (i) and that of FOLNF∗ by (ii). Second, among our three algorithms, FOLNF∗ presents the most novel ideas. Specifically, in FOLNF∗ , the numbers of dummies and bots for each item follow a dummy-count distribution D and a bot-count distribution D ′ , respectively. For (D , D ′ ), we propose a novel joint asymmetric geometric distribution, which is a pair of the positively skewed geometric distribution D and the negatively skewed geometric distribution D ′ . Although they are instantiations of the GDL (General Discrete Laplace distribution) [51], the existing studies that apply the GDL to DP [10,38] consider only a symmetric GDL. Our joint distribution is new in that it is a pair of positively and negatively skewed asymmetric GDLs and that the left/right curves are adjusted based on the sampling probability.
Finally, although we use the count-min sketch in the same way as [24,33], we present a new accuracy bound much tighter than [24, 33] and an optimization technique using our bound. Comparison with Other Models. Below, we emphasize the motivation for using the augmented shuffle model within TEEs by comparing it with other models. First, the pure shuffle model suffers from collusion with users, as explained above. Moreover, this model suffers from poisoning attacks from users [21, 23]. This issue is especially serious when ε is small, as honest users need to add a large amount of noise to their data (and malicious users do not). In contrast, our algorithms are robust against poisoning attacks, as noise is added on the shuffler side (see Appendix C.1). Second, it is possible to run a central DP algorithm (e.g., basic DP histogram [12, 27], stability histogram [20, 47]) within the TEE. However, it suffers from prohibitively large runtime, as it must access the entire memory to add each user’s data to the histogram [6]. For example, when there are 108 users and 108 items, it requires about 270 days, as shown in our experiments. In contrast, our algorithms require only 16 hours or less. We also note that sorting results in higher complexity than shuffling, as it must be fully oblivious [69].1 Third, the MPC (Multi-Party Computation)-DP model [73] requires multiple servers and communication between them. For example, the protocol in [17] requires two semi-honest servers and four rounds of interaction between the two. In contrast, our approaches need only a single server. Although it might be possible to simulate the MPC-DP model using the TEE, it is not obvious how to do that, as the size of the internal memory is typically limited (e.g., 93.5 MB [48]). Our algorithms need a small amount of memory and are efficient. We also note that there are advantages of the pure shuffle, central, and MPC-DP models. For example, the pure shuffle model can be implemented using the mix-net [18]. The central DP algorithm is more efficient than our algorithms when n (#users) and d (#items) are small, e.g., n = d ≤ 103 in our experiments. When multiple servers are available, the MPCDP model can be used to achieve accuracy comparable to the central model for general tasks. Therefore, we should use an appropriate model depending on the application.
2
Related Work
Shuffle Model. Starting from Google’s Prochlo [18], the shuffle model has been widely studied for various tasks, such as frequency estimation [11,24,56,60,76], graph analysis [30, 39], and federated learning [36, 55]. Most existing protocols assume the pure shuffle model and are vulnerable to collusion with users, as described in Section 1. 1 Additionally, if we can perform sorting, we can also perform shuffling by assigning a random value to each input and then sorting the random values. Thus, sorting cannot be more efficient than shuffling.
Some recent studies address this issue by introducing the augmented shuffle model. Protocols in this model include the UD [76] and LNF [60] protocols. We propose a general framework that includes fully oblivious versions of these protocols. A recent study [61] proposes the FME (Filtering-withMultiple-Encryption) protocol, which improves the efficiency of the LNF protocol for large-domain data. However, it (still) requires high communication costs due to the use of multiple encryptions. We show that our algorithms with the count-min sketch are much more efficient than the FME protocol, while achieving higher (or comparable) accuracy. Another important difference is that the FME protocol requires two rounds of communication between the shuffler and the data collector, whereas our algorithms need only one round. Some studies [6, 18] consider the shuffle model with TEEs and use oblivious shuffling to prevent external memory-based side-channel attacks. However, their approaches cannot be applied to our setting, as explained in Section 1. Oblivious Algorithms. Oblivious RAM [9, 71] has been widely studied to hide memory access patterns. The combination of DP and obliviousness for memory access patterns has also been introduced (e.g., ODP [6], DO [22]). However, they are not designed to prevent control flow-based attacks [50,58]. Sasy et al. [68, 69] introduce the notion of full obliviousness to prevent all of the attacks based on external/internal memory access patterns and control flows. They propose ORShuffle [68] and WaksShuffle [69] as fully oblivious shuffle algorithms. However, they do not consider random sampling, dummy data addition, or providing DP to the output. In this work, we use their algorithms as building blocks and propose algorithms that provide FODP for the entire process, including random sampling and dummy data addition.
3 3.1
Preliminaries Basic Notations
Below, we introduce our notations. Let R, R≥0 , N, Z, Z≥0 be the sets of real numbers, non-negative real numbers, natural numbers, integers, and non-negative integers, respectively. For a set Z , let Z ∗ be the set of all finite sequences of elements in Z . For a ∈ N, we denote the set {1, 2, . . . , a} by [a]. Let n ∈ N be the number of users, and ui be the i-th user. Let d ∈ N be the number of items. Each item is represented as an index from 1 to d. For i ∈ [n], let xi ∈ [d] be the input value of user ui . Let x = (x1 , . . . , xn ) be the database. For i ∈ [d], let fi ∈ [0, 1] be the relative frequency of item i in x such that ∑di=1 fi = 1. Let fˆi ∈ R be the estimate of fi . Let f = ( f1 , . . . , fd ) and f̂ = ( fˆ1 , . . . , fˆd ). Frequency estimation is the task of calculating f̂ as close to f as possible.
3.2
DP (Differential Privacy)
DP and LDP. DP is formally defined as follows:
Definition 1 ((ε, δ)-DP [28]). Let ε ∈ R≥0 and δ ∈ [0, 1]. Let R be a randomized algorithm with domain [d]n . Then, R provides (ε, δ)-DP (or ε-DP when δ = 0) if for any neighboring databases x = (x1 , . . . , xi , . . . , xn ) and x′ = (x1 , . . . , xi′ , . . . , xn ) that differ in one entry i ∈ [n] and any O ⊆ Range(R ), Pr[R (x) ∈ O] ≤ eε Pr[R (x′ ) ∈ O] + δ.
(1)
The parameters ε and δ should be small. For example, ε should ideally satisfy ε ≤ 1 and should not exceed 5 or 10 [52]. δ must satisfy δ ≪ 1/n [28]. Most shuffle protocols use an LDP (Local DP) algorithm, such as the GRR [41, 76], OUE [75], and OLH [75]. LDP is a variant of DP in the local model and is defined as follows: Definition 2 (ε-LDP [26, 46]). Let ε ∈ R≥0 . Let RL be a randomized algorithm (local randomizer) with domain [d]. RL provides ε-LDP if for any x, x′ ∈ [d] and any O ⊆ Range(RL ), Pr[RL (x) ∈ O] ≤ eε Pr[RL (x′ ) ∈ O]. Pure Shuffle DP Protocols. A shuffle DP protocol consists of a shuffler part (also called a shuffle algorithm) that, given input values, outputs shuffled values and an analyzer part that, given shuffled values, outputs analysis results. Below, we explain pure shuffle protocols using LDP algorithms. Assume that each user ui (i ∈ [n]) applies a local randomizer RL providing εL -LDP to her input value xi and sends the noisy value RL (xi ) to the shuffler. The shuffler randomly shuffles noisy values RL (x1 ), . . . , RL (xn ) and sends the shuffled values to the data collector. Then, the random shuffling serves as anonymization and amplifies privacy. Specifically, the shuffled values provide (ε, δ)-DP, where ε = g(n, εL , δ), and g(n, εL , δ) is monotonically decreasing (resp. increasing) with respect to n and δ (resp. εL ). ε is generally much smaller than εL . See Appendix A.1 for more details.
3.3
Robustness against Collusion with Users
Collusion with Users. A major drawback of the pure shuffle DP protocols is that they are vulnerable to collusion attacks between users and the data collector. Let Ω ⊂ [n] be indices of colluding users; i.e., users {ui |i ∈ Ω} share their noisy values {RL (xi )|i ∈ Ω} with the data collector. In this case, the value of ε after shuffling is increased from g(n, εL , δ) to g(n − |Ω|, εL , δ), as the data collector can remove |Ω| noisy values from n shuffled values. This results in a great increase in ε in some cases. For example, suppose that n = 6 × 105 , δ = 10−12 , and |Ω| = 6 × 104 , i.e., 10% of users are malicious. Then, ε can be increased from 1 to 7.2 (resp. from 4 to 20) after collusion attacks in the pure shuffle protocols using LDP mechanisms (resp. the protocol in [24]), as shown in [60]. We can prevent the increase in ε by estimating the number |Ω| of colluding users in advance. However, it is difficult to estimate the exact value of |Ω| in practice. For example,
in X (formerly Twitter), the estimates of the proportion of fake users range from 11% to 20% [15, 63] and can be even 43% during elections [63]. Although we can conservatively estimate |Ω|, this results in suboptimal accuracy. For example, when we estimate |Ω| to be 50%, the squared error can increase by a factor of four [60]. Note that this is a general issue, not limited to specific protocols or privacy parameters. Robustness. Shuffle DP protocols should be robust against collusion with users; i.e., ε and δ after shuffling should not be increased even if some users share their data sent to the shuffler with the data collector. Following [61], we say that a shuffle DP protocol is robust against collusion with users if the privacy parameters (ε, δ) are not increased by collusion with users; we give its formal definition in Appendix A.2. Note that pure shuffle DP protocols cannot provide this robustness for the following reason. First, they must add noise on the user side, because otherwise it merely shuffles input values and cannot provide (ε, δ)-DP. Then, they are not robust against collusion with users, because the adversary can increase ε from g(n, εL , δ) to g(n − |Ω|, εL , δ) by removing |Ω| noisy values from n shuffled values, as explained above.
3.4
Augmented Shuffle DP Protocols
The robustness against collusion with users can be achieved by introducing the augmented shuffle model, which allows the shuffler to perform additional operations: random sampling and adding dummies. The additional operations act as noise addition on the shuffler side, improving the robustness against collusion with users. Below, we briefly explain two existing augmented shuffle protocols: UD [76] and LNF [60]. UD (Uniform Dummies) Protocol [76]. In the UD protocol, each user ui (i ∈ [n]) sends a noisy value RL (xi ) to the shuffler, where RL is a local randomizer. Then, the shuffler adds λ ∈ Z≥0 dummy values y1 , . . . , yλ ∈ Range(RL ) uniformly randomly sampled from the range of RL . Finally, the shuffler randomly shuffles the values RL (x1 ), . . . , RL (xn ), y1 , . . . , yλ and sends the shuffled values to the data collector. It is proved in [76] that ε of the UD protocol in the presence of collusion with users is much smaller than that of the pure shuffle protocol. However, ε of the UD protocol still increases slightly [60], as it adds local noise on the user side. In this paper, we modify this protocol to achieve robustness against collusion with users by not adding local noise. LNF (Local-Noise-Free) Protocol [60]. In the LNF protocol, each user ui sends her input value xi to the shuffler without adding noise. Then, the shuffler performs three operations: random sampling, adding dummies, and shuffling. Specifically, the shuffler randomly samples each input value xi (i ∈ [n]) with probability β ∈ [0, 1]. In other words, it discards xi with probability 1 − β. Then, for each item i ∈ [d], the shuffler samples zi from a dummy-count distribution D over Z≥0 (zi ∼ D ) and adds the following dummy values:
1, . . . , 1, 2, . . . , 2, . . . , d, . . . , d . | {z } | {z } | {z } z1
z2
zd
Finally, it shuffles the sampled values and dummy values. It is proved in [60] that the LNF protocol provides DP and is robust against collusion with users if D provides DP. As the dummy-count distribution D , [60] introduces the asymmetric geometric distribution, whose left tail shrinks as β decreases. The LNF protocol with this distribution provides much higher accuracy than other existing shuffle DP protocols when β = 1. When β = 1 − e−ε/2 , the distribution becomes a one-sided geometric distribution (i.e., the left tail disappears). In this case, the LNF protocol achieves pure DP (δ = 0) at the cost of accuracy.
3.5
Full Obliviousness
Definition. Full obliviousness [68, 69] prevents side-channel attacks based on external/internal memory access patterns and control flows by making the memory access patterns and the sequence of executed instructions independent of secret data. Formally, an instruction trace of the randomized algorithm R is a sequence of indices (i1 , i2 , . . .) ∈ N∗ , where each index points to an instruction (e.g., line number) in R . A memory trace of R is a sequence of tuples (t, b, l), where t ∈ N represents that the memory is accessed during the t-th instruction execution, b ∈ {0, 1} indicates a read (0) or write (1), and l ∈ N represents the location of memory accessed. Assume that R leaks the instruction and memory traces along with its output. Throughout this paper, we denote by R M (resp. R I ) a randomized algorithm that outputs memory (resp. instruction) traces R leaks. Then, full obliviousness is defined as follows: Definition 3 (Full obliviousness [68, 69]). Let Λ ⊆ [n]. Let R be a randomized algorithm with domain [d]n . Then, R is fully oblivious to {xi }i∈Λ if there exists a simulator S such that for any database x = (x1 , . . . , xn ) and any (o, (oM , oI )) ∈ Range(R × (R M , R I )), h i Pr R (x), R M (x), R I (x) = (o, (oM , oI )) = Pr R (x), S (xi )i∈[n]\Λ , (|xi |)i∈Λ =(o, (oM , oI )) . (2) Definition 3 regards the input values (xi )i∈Λ as secrets. Full obliviousness guarantees that the memory traces R M (x) and instruction traces R I (x) are independent of (xi )i∈Λ and do not reveal any information about it beyond what is implied by non-secrets (xi )i∈[n]\Λ given to the simulator S . Note that the size |xi | is public for any input value i ∈ [n]. This applies to our scenario, as the number d of items is public (i.e., |xi | = log2 d). Following the convention in [68, 69], we also say that for any data A, an algorithm is fully oblivious to A if its memory and instruction traces are independent of A. Fully Oblivious Primitives. Following [68, 69], we make the following assumptions on fully oblivious primitives. We
assume that arithmetic and bitwise operations are fully oblivious to the input values. We also assume that random bits can be generated fully obliviously by simply reading them from a special memory region. Moreover, we assume that a comparison of two real values y1 ∈ R and y2 ∈ R is fully oblivious to y1 and y2 . Let [y1 ≥ y2 ] be a fully oblivious comparison that outputs 1 if y1 ≥ y2 and 0 otherwise. Other basic primitives include fully oblivious swapping, random number generators, and shuffling [68, 69]. We define these primitives. For m ∈ N, let C = (c1 , . . . , cm ) be an array of length m. Let ζ ∈ R≥0 be the size of each element in C. We denote a fully oblivious swap function by OSWAP(ci , c j , b), where i ̸= j and b ∈ {0, 1}. OSWAP(ci , c j , b) swaps the values of ci and c j if b = 1 and does nothing otherwise. OSWAP(ci , c j , b) is fully oblivious to the values ci , c j , and b, but not to the indices i and j. OSWAP(ci , c j , b) can be implemented using CMOV or XOR operations [64]. We denote fully oblivious random generators for real and natural values by ORAND_REAL() and ORAND_NATS(x), respectively, where x ∈ N. ORAND_REAL() randomly generates a real value r ∈ [0, 1). This can be implemented by generating γ (γ ∈ N) random bits, regarding them as a binary integer r0 ∈ [0, 2γ ), and dividing it by 2γ . ORAND_NATS(x) randomly generates a natural value r ∈ [x] and can be implemented by generating a ⌈log2 x⌉-bit binary integer r0 until r0 < x and outputting r = r0 + 1. Both ORAND_REAL() and ORAND_NATS(x) are fully oblivious to the random value r. Finally, we denote a fully oblivious shuffle algorithm by OSHUFFLE(c1 , . . . , cm ). OSHUFFLE(c1 , . . . , cm ) randomly shuffles c1 , . . . , cm and is fully oblivious to C. Examples of this algorithm include ORShuffle [68] and WaksShuffle [69]. The total runtime of ORShuffle and WaksShuffle is O(ζm log2 m) and O(m log3 m + ζm log m), respectively.
4
Fully Oblivious Differential Privacy
In this section, we introduce FODP, a fully oblivious version of DP. We first clarify our system model and threat model (Section 4.1). Then, we define FODP (Section 4.2) and show its relationship with full obliviousness (Section 4.3).
4.1
Assumptions
System Model. We consider the augmented shuffle DP model with TEEs. In this model, the TEE inside a server serves as a shuffler, and the data collector is outside the TEE. Thus, each user sends data to the TEE, which then performs augmented shuffling (i.e., random sampling, adding dummies, and shuffling) and places the shuffled data outside the TEE. Finally, the server (outside the TEE) calculates an estimate f̂ of the frequency distribution f and publishes f̂. The TEE provides data confidentiality and integrity. For example, Intel SGX [7] provides data confidentiality by allocating a hardware-protected container called an enclave. Data
in the internal memory (i.e., the memory inside the enclave) is encrypted, and keys used for encryption/decryption are not compromised. Thus, the data and code within the enclave are isolated from outside the enclave, including the main operating system. Note that the internal memory is often small (e.g., 93.5 MB [48]). Therefore, the code may store encrypted and integrity-protected data in a large external memory. Intel SGX also provides integrity of the running code through an attestation mechanism [7], which provides a cryptographic proof that the code is genuine. After the verification is complete, users can establish a secure channel with the enclave and communicate with it using cryptographic keys. Threat Model. In this paper, anyone except a single user ui (referred to as a victim) can be an adversary, e.g., other users, server administrators, or individuals who have obtained the published estimate f̂. We refer to adversaries comprising the server administrators as internal adversaries and to other adversaries as external adversaries. Following the conventions of the DP literature [27, 28], we consider the worst case for background knowledge of the adversaries; i.e., they may know all input values {x j | j ̸= i} other than the victim’s xi . We can ensure that the shuffler follows the protocol and does not collude with the data collector by using the TEE. However, the data collector can collude with some users or inject some fake user accounts [3, 4, 15, 72] to obtain their (plaintext) data sent to the shuffler. In addition, the internal adversaries (i.e., server administrators) can obtain external memory access patterns, as it is outside the TEE’s control [6]. They may also obtain internal memory access patterns and control flows by launching state-of-the-art attacks, such as [19, 49, 50, 58]. Remark. We exclude timing attacks [37, 40], which infer secret values based on the time to run the code, from our scope in the same way as [68, 69]. Our algorithms can easily be modified to be secure against timing attacks by making the runtime constant [37, 40]; we have also confirmed that the variance in the runtime of our algorithms is small. We also note that [74] proposes side-channel attacks for shuffle protocols with multiple rounds, multiple messages (per user), or variable-length messages. Our algorithms are secure against all of these attacks because they are singleround protocols with a single, fixed-length message.
4.2
FODP (Fully Oblivious DP)
Definition. To provide strong privacy guarantees against the internal adversary, we introduce FODP: Definition 4 ((ε, δ)-FODP). Let ε ∈ R≥0 and δ ∈ [0, 1]. Let R be a randomized algorithm with domain [d]n . Then, R provides (ε, δ)-FODP if for any neighboring databases x = (x1 , . . . , xi , . . . , xn ) and x′ = (x1 , . . . , xi′ , . . . , xn ) that differ in one entry i ∈ [n] and any (O, OM , OI ) ⊆
Users
Server (data collector) TEE (shuffler) Random sampling Adding dummies Shuffling
Internal adversary
External adversary
-FODP memory/instruction traces shuffled data Calculating
-DP Estimate
Figure 1: FODP/DP in our system model (εE ≤ εI , δE ≤ δI ). Range((R , R M , R I )), Pr[(R (x), R M (x), R I (x)) ∈ (O, OM , OI )] ≤ eε Pr[(R (x′ ), R M (x′ ), R I (x′ )) ∈ (O, OM , OI )] + δ. (3) Since FODP is defined using (3), it also holds under composition [28]. Chan et al. [22] introduce a notion of DO (Differential Obliviousness), which provides DP guarantees for only memory traces R M (x). Later, Allen et al. [6] introduce ODP (Oblivious DP), which provides DP for the output R (x) and the external memory traces. FODP is a generalization of DO and ODP in that it provides DP for all of the output R (x), memory traces R M (x), and instruction traces R I (x). FODP and DP. It is clear that FODP is stronger than DP; i.e., if an algorithm R running within the TEE provides (ε, δ)-FODP, then it also provides (ε, δ)-DP. Then, by the post-processing invariance [28], the estimate f̂ exposed to the external adversary also provides (ε, δ)-DP. Figure 1 shows the roles of FODP and DP in our system model. We use (εI , δI )-FODP as a privacy notion against the internal adversary and (εE , δE )-DP against the external adversary, where εE ≤ εI and δE ≤ δI . Note that it is reasonable to set smaller privacy parameters against the external adversary (e.g., εE = 0.1, εI = 1, δE = 0, 0 < δI ≪ 1/n) because everyone can be an external adversary after publishing f̂.
4.3
Relationship with Full Obliviousness
At first glance, the relationship between FODP and full obliviousness (Definition 3) may appear unclear, as the latter is defined using a simulator S . However, we can show that FODP is connected to DP and full obliviousness as follows: Definition 5 (Full obliviousness with respect to a single secret). We say that a randomized algorithm R with domain [d]n is fully oblivious to a single secret if R is fully oblivious to {x1 }, {x2 }, . . . , and {xn }. Theorem 1. Let R be a randomized algorithm with domain [d]n . If R provides (ε, δ)-DP and is fully oblivious to a single secret, then R provides (ε, δ)-FODP. Theorem 1 states that any (ε, δ)-DP algorithm can be modified to satisfy (ε, δ)-FODP by making it fully oblivious to a single secret. We make use of Theorem 1 to prove that our FOUD and FOLNF provide FODP. Meanwhile, it is important
Algorithm 1 2 foreach 3 ; 4 foreach 5
Random sampling
; do do
Adding dummies
;
6 end 7 end 8
Shuffling
9 return
Memory Instruction
Figure 2: Direct implementation of the LNF protocol [60]. to note that providing DP and full obliviousness with respect to a single secret is not a necessary condition (but a sufficient condition) for providing FODP. In fact, we prove FODP of our FOLNF∗ by directly showing the inequality (3).
5
Our FODP Algorithms
In this section, we propose a general framework and three concrete algorithms for FODP in the augmented shuffle model. We first explain our motivation and the overview of our algorithms (Section 5.1). We then present our general framework (Section 5.2) and three concrete algorithms (Sections 5.3-5.5). Finally, we compare our three algorithms (Section 5.6).
5.1
Overview
Technical Motivation. The goal of this work is to design FODP algorithms for frequency estimation in the augmented shuffle model with TEEs. However, directly implementing augmented shuffle algorithms within TEEs can result in the leakage of substantial side-channel information, thereby violating FODP. To explain this issue, we show pseudocode for the shuffler part of the LNF protocol [60] and a visualization of its memory usage and instruction traces in Figure 2. As shown in the top panel of Figure 2, the shuffler first samples input values x1 , . . . , xn with probability β and obtains selected values x̃1 , . . . , x̃ñ , where ñ ≤ n (line 1). Then, for each item i ∈ [d], the shuffler adds zi dummy values, where zi is generated from the dummy-count distribution D (lines 2-7). Finally, the shuffler randomly shuffles the input and dummy values and outputs (x̃π(1) , . . . , x̃π(ñ+∑d zi ) ), where π i=1
is a random permutation over [ñ + ∑di=1 zi ] (lines 8-9). The key insight here is that sampling and adding dummies, followed by shuffling, are equivalent to adding discrete noise to each histogram bin [60]. Thus, the output provides DP.
Memory
: random value in
Figure 3: Allocated memory in our general framework.
In this algorithm, the shuffler allocates memory of size ñ for selected input values and of size zi (i ∈ [d]) for dummy values i, as shown in the middle panel of Figure 2. Thus, the values ñ, z1 , . . . , zd can be leaked from the size of the allocated memory. In addition, the shuffler repeats the second “foreach” loop (lines 4-5) zi times. Thus, the instruction trace can be represented as a sequence of line numbers in the bottom panel of Figure 2, from which z1 , . . . , zd are also leaked. In summary, the values ñ, z1 , . . . , zd can be leaked from the memory and instruction traces. This leads to a privacy violation because the adversary who knows z1 , . . . , zd can remove dummy values from the shuffled values. Note that the number ñ of selected input values must also be kept secret to obtain privacy amplification by sampling [13, 53, 60]. Thus, the leakage of ñ also reduces privacy. Algorithm Overview. We propose a general framework for FODP that includes the UD [76] and LNF [60] protocols and addresses the leakage issue explained above. Our framework prevents the leakage of side-channel information by obfuscating the allocated memory size. Figure 3 shows the allocated memory in our framework. Specifically, we allocate memory of size n for input values, of size λ for uniform dummies, and of size κi (≥ zi ) for dummy values i. We call κi the bot count, as we initialize κi memory locations with ⊥. We transform each input value into ⊥ with probability 1 − β and store λ uniform dummies and zi dummy values i (i ∈ [d]) in the memory using fully oblivious primitives in Section 3.5. Our key insight is that an algorithm outputting memory and instruction traces in our framework can be expressed as an algorithm outputting bot counts (κ1 , . . . , κd ) followed by a randomized post-processing algorithm (Lemma 1). This lemma enables us to reduce FODP of our framework to the privacy of shuffled values and bot counts (κ1 , . . . , κd ). Based on this, we propose three instances: FOUD, FOLNF, and FOLNF∗ . FOUD and FOLNF output the same shuffled values as the UD and LNF protocols, respectively (after removing ⊥). Both FOUD and FOLNF set κi to a constant, thus providing full obliviousness with respect to a single secret. Then, by Theorem 1, FOUD and FOLNF provide FODP. FOLNF∗ is a variant of FOLNF that generates bot counts (κ1 , . . . , κd ) under DP. Specifically, it calculates κi as κi = zi +ωi , where ωi is generated from a bot-count distribution D ′ . For FOLNF∗ , we introduce a novel joint asymmetric geometric distribution. We prove that FOLNF∗ with this distribution provides FODP by directly showing (3). We compare FOUD, FOLNF, and FOLNF∗ in Section 5.6.
Input: Database x = (x1 , . . . , xn ), #items d ∈ N. Output: Shuffled values x̃ = (x̃π(1) , . . . , x̃π(n+λ+∑d κi ) ). i=1
/* Random sampling 1 foreach i ∈ [n] do 2 a1 ← xi ; a2 ← ⊥; 3 r ← ORAND_REAL(); 4 OSWAP(a1 , a2 , [r ≥ β]); 5 x̃i ← a1 ; 6 end /* Dummy data addition 7 foreach i ∈ [λ] do 8 r ← ORAND_NATS(d); 9 x̃n+i ← r; 10 end 11 foreach i ∈ [d] do 12 zi ← DummyCountGeneration(D ); 13 κi ← BotCountGeneration(zi , D ′ ); 14 (a1 , . . . , aκi ) ← (⊥, . . . , ⊥); 15 foreach k ∈ [κi ] do 16 OSWAP(ak , i, [zi ≥ k]); 17 end 18 (x̃n+λ+∑i−1 κ j +1 , . . . , x̃n+λ+∑i κ j ) ←
*/
*/
j=1
(a1 , . . . , aκi ); end /* Shuffling 20 x̃π(1) , . . . , x̃π(n+λ+ d ∑
j=1
19
i=1
*/ κi ) ←
OSHUFFLE(x̃1 , . . . , x̃n+λ+∑d
i=1 κi
21
);
return x̃ = (x̃π(1) , . . . , x̃π(n+λ+∑d
i=1 κi )
x̃n+λ+∑i κ j ) includes zi dummies for item i. j=1 Finally, we perform fully oblivious shuffling OSHUFFLE(x̃1 , . . . , x̃n+λ+∑d κi ) and output x̃ = (x̃π(1) , . . . , x̃π(n+λ+∑d κi ) ), i=1
i=1
)
Algorithm 1: Our general algorithm RD ,D ′ ,β,λ (D : dummy-count distribution with mean µ and variance σ2 ; D ′ : bot-count distribution; β ∈ [0, 1]: sampling probability; λ ∈ Z≥0 : #uniform dummies).
5.2
j=1
running OSWAP(ak , i, [zi ≥ k]) for each k ∈ [κi ] results in swapping between ⊥ and i for zi times. Thus, (x̃n+λ+∑i−1 κ j +1 , . . . ,
j=1
j=1
Then, we randomly generate λ uniform dummies from [d]. Specifically, for i ∈ [λ], we generate a natural value r ∈ [d] by ORAND_NATS(d) and copy r to x̃n+i (lines 7-10). As a result, λ uniform dummies are copied to (x̃n+1 , . . . , x̃n+λ ). We also generate dummies for each item based on the dummy-count distribution D . Specifically, for each item i ∈ [d], we call the function DummyCountGeneration, which generates a random sample zi from D (line 12). This function can be implemented via a CDF (Cumulative Distribution Function) [44] or arithmetic operations and is fully oblivious to zi ; see Appendix B.1 for details. Hereafter, we assume that this function is implemented via arithmetic operations. zi is used as the number of dummies for item i. After generating the number zi of dummies, we generate (a1 , . . . , aκi ) = (⊥, . . . , ⊥), where κi ∈ Z≥0 is generated by the function BotCountGeneration (lines 13-14). This function takes zi and the bot-count distribution D ′ as input and outputs κi . BotCountGeneration consists of generating a random sample from D ′ and arithmetic operations. Thus, it is also fully oblivious to zi . We introduce three instances of this function in Sections 5.3-5.5. Then, we perform swapping OSWAP(ak , i, [zi ≥ k]) for each k ∈ [κi ] and copy (a1 , . . . , aκi ) to (x̃n+λ+∑i−1 κ j +1 , . . . , x̃n+λ+∑i κ j ) (lines 15-18). Note that
Our General Framework
Algorithm. Algorithm 1 shows a general framework for our algorithms, denoted by RD ,D ′ ,β,λ . It has four parameters: a dummy-count distribution D over Z≥0 (mean: µ, variance: σ2 ), a bot-count distribution D ′ over Z≥0 , a sampling probability β ∈ [0, 1], and the number λ ∈ Z≥0 of uniform dummies. These parameters are public. In our framework, each user ui (i ∈ [n]) sends her input value xi to the TEE without adding noise. Then, the TEE runs Algorithm 1 as follows. First, for each input value xi (i ∈ [n]), we perform random sampling. Specifically, we randomly generate a real value r ∈ [0, 1) by ORAND_REAL() and perform swapping OSWAP(a1 , a2 , [r ≥ β]), where a1 = xi and a2 = ⊥ (lines 24). Then, we copy a1 to x̃i (line 5). These processes select xi (i.e., x̃i = xi ) with probability β and do not select xi (i.e., x̃i = ⊥) with probability 1 − β.
where π is a random permutation over [n + λ + ∑di=1 κi ] (lines 20-21). The output consists of shuffled values, where each input value is sampled with probability β, λ uniform dummies are added, and zi dummies are added to each item i ∈ [d]. Calculation of f̂. After our general algorithm RD ,D ′ ,β,λ outputs the shuffled values x̃ = (x̃π(1) , . . . , x̃π(n+λ+∑d κi ) ), the i=1 server (outside the TEE) discards ⊥ and counts the number ci ∈ Z≥0 of each item i in the shuffled values. Then, the server calculates an unbiased estimate f̂ of the frequency f as follows: 1 fˆi = βn (ci − dλ − µ) (i ∈ [d]),
(4)
where µ is the mean of the dummy-count distribution D . Privacy and Robustness. Our general algorithm RD ,D ′ ,β,λ is a combination of the UD and LNF protocols in that it samples each input value with probability β, adds λ uniform dummies over [d], adds zi dummies for each item i ∈ [d], and then shuffles them. Thus, RD ,D ′ ,β,λ provides DP. The remaining issue is side-channel information of RD ,D ′ ,β,λ . As shown in Figure 3 and Algorithm 1, our general algorithm RD ,D ′ ,β,λ obfuscates the allocated memory size with ⊥ and makes control flows (i.e., “foreach” loops) dependent only on the memory size. Based on this, we show our key insight that memory and instruction traces of RD ,D ′ ,β,λ depend on the database x only through bot counts (κ1 , . . . , κd ):
Lemma 1. Let RD⊥,D ′ ,β,λ be a randomized algorithm that, given a database x = (x1 , . . . , xn ), outputs (κ1 , . . . , κd ) in RD ,D ′ ,β,λ (Algorithm 1). Then, there exists a randomized postprocessing algorithm φ such that for any x ∈ [d]n , (RDM,D ′ ,β,λ (x), RDI ,D ′ ,β,λ (x)) = φ(RD⊥,D ′ ,β,λ (x)).
(5)
This is a key lemma that reduces FODP of our general algorithm to the privacy of shuffled values output by RD ,D ′ ,β,λ and bot counts (κ1 , . . . , κd ) output by RD⊥,D ′ ,β,λ . We call RD⊥,D ′ ,β,λ the bot-count algorithm. Our FOUD and FOLNF set κi to a constant, while FOLNF∗ generates κi under DP. In Theorems 3-5, we prove FODP of these algorithms using Lemma 1. Our general algorithm RD ,D ′ ,β,λ is also robust against collusion with users, as users do not add noise: Lemma 2. Let εE , εI ∈ R≥0 and δE , δI ∈ [0, 1]. If RD ,D ′ ,β,λ (Algorithm 1) provides (εE , δE )-DP and (εI , δI )-FODP, then it is robust against collusion with users; i.e., the values of (εE , δE ) and (εI , δI ) are not increased by collusion with users (see Appendix A.2 for the formal definition of the robustness). Furthermore, in Appendix C.1, we show that our general algorithm is robust against poisoning attacks [21, 23]. Specifically, it prevents output poisoning attacks [54], as users can change only their input values. See Appendix C.1 for details. Accuracy. We also show the accuracy of the estimate f̂. Following [41, 60, 76], we use the expected l2 loss as a metric: Theorem 2. The estimate f̂ in (4) is unbiased (i.e., E[ fˆi ] = fi for any i ∈ [d]) and achieves the following expected l2 loss: λ(d−1) σ2 d E[∑di=1 ( fˆi − fi )2 ] = 1−β βn + β2 n2 d + β2 n2 ,
where σ2 is the variance of the dummy-count distribution D . FOUD sets σ2 = 0 and achieves E[∑di=1 ( fˆi − fi )2 ] = λ(d−1) 1−β ∗ βn + β2 n2 d . FOLNF and FOLNF set λ = 0 and achieve 2 σ d E[∑di=1 ( fˆi − fi )2 ] = 1−β βn + β2 n2 , which is the same as [60].
Remark. Although our general algorithm RD ,D ′ ,β,λ adds both uniform dummies (Algorithm 1, lines 7-10) and dummies for each item (lines 11-19), our three concrete algorithms add either of the two. This is because λ uniform dummies over [d] can be approximated by binomial dummies for each item (i.e., zi ∼ Bin(λ, d1 ) dummies for each item i). We add uniform dummies in RD ,D ′ ,β,λ because they do not need any ⊥ and make FOUD more efficient than FOLNF with D = Bin(λ, d1 ).
5.3
FOUD (Fully Oblivious UD)
Algorithm. FOUD is an instance of our general algorithm, where β = 1 and zi = κi = 0 for any i ∈ [d]; i.e., D is a degenerate distribution at 0, and BotCountGeneration (line 13 in Algorithm 1) always outputs 0. In other words, FOUD
performs adding uniform dummies (lines 7-10) and shuffling (line 20). FOUD outputs the same data as the UD protocol [76] without LDP noise. We denote this algorithm by RλFOUD . Privacy and Robustness. RλFOUD provides the following privacy and robustness guarantees: Theorem 3. For any θ1 ∈ R≥0 and θ2 ∈ [0, 1), RλFOUD pro1 )λ vides (ε, δ)-DP and (ε, δ)-FODP, where ε = ln d+(1+θ (1−θ )λ and 2
2
2
δ = e−θ1 λ/((2+θ1 )d) + e−θ2 λ/(2d) . It is also robust against collusion with users. We prove FODP in Theorem 3 via full obliviousness (Theorem 1). In Appendix C.2, we also show that the bound on (ε, δ) in Theorem 3 is tighter than the bound in [76].
5.4
FOLNF (Fully Oblivious LNF)
Algorithm. FOLNF is an instance of our general algorithm, where λ = 0 and BotCountGeneration always outputs a predetermined value κ ∈ N, i.e., κi = κ for any i ∈ [d]. After discarding ⊥, the output of FOLNF is the same as that of the LNF protocol [60]. We denote this algorithm by RDFOLNF . ,β Privacy and Robustness. To show the privacy and robustness of RDFOLNF , we introduce the binary input mechanism in [60]: ,β Definition 6 (Binary input mechanism [60]). Let Ber(β) be the Bernoulli distribution with parameter β. A binary input mechanism MD ,β takes binary data x ∈ {0, 1} as input and outputs MD ,β (x) = αx + z, where α ∼ Ber(β) and z ∼ D .
MD ,β is a binary input version of the LNF protocol; i.e., it samples x with probability β and adds z dummies. If MD ,β provides ( 2ε , 2δ )-DP, then the LNF protocol provides (ε, δ)DP [60]. Note that (ε, δ) is doubled because neighboring databases x and x′ differ by 1 in two bins on their histograms. We show the privacy and robustness of RDFOLNF using the ,β binary input mechanism: Theorem 4. Let F : Z≥0 → [0, 1] be a CDF for the dummycount distribution D . If the binary input mechanism MD ,β provides ( 2ε , 2δ )-DP, then RDFOLNF provides (ε, δ + δ0 )-DP and ,β (ε, δ + δ0 )-FODP, where δ0 = 2(1 − F(κ − 1)), and is robust against collusion with users. We prove FODP in Theorem 4 via full obliviousness. Note that FOLNF introduces an additional term δ0 in DP, as it truncates the number zi of dummy values to κ when zi > κ. The parameter κ controls the trade-off between δ0 and the number of bots. In our experiments, we set δ = δ0 and then set κ so that δ + δ0 (= 2δ) does not exceed a required value. For D , we use the asymmetric geometric distribution: Definition 7 (Asymmetric Geometric Distribution [60]). Let ν ∈ Z≥0 , ql ∈ [0, 1], and qr ∈ [0, 1]. Let η = ql (1 − qνl )/(1 −
ql ) + 1/(1 − qr ). Let AGeo(ν, ql , qr ) be the asymmetric geometric distribution, and X be a random variable that follows AGeo(ν, ql , qr ). Then, the probability mass function at X = k is given by ( 1 ν−k q (if k = 0, 1, . . . , ν − 1) Pr[X = k] = η1 lk−ν (if k = ν, ν + 1, . . .). η qr The binary input mechanism with D = AGeo(ν, ql , qr ), −ε/2 −1+β
ql = e
β
( δ=
β , and qr = eε/2 −1+β provides ( 2ε , 2δ )-DP, where
2 ν ε/2 + βeε/2 ) η ql (1 − e
(if β > 1 − e−ε/2 )
0
(if β = 1 − e−ε/2 )
(6)
(see [60] for the proof). Thus, by Theorem 4, FOLNF with this distribution provides (ε, δ + δ0 )-DP and (ε, δ + δ0 )-FODP.
(a)
0.4
(b)
0.4 0.3
0.3
0.2
0.2
0.2
0.1
0.1
0.1
0
0 0
10
20
30
40
(c)
0.4
0.3
0 0
10
20
30
40
0
10
20
30
40
Figure 4: Examples of the joint asymmetric geometric distribution (D , D ′ ) = (AGeo(ν, ql , qr ), AGeo(ν′ , q′ l , q′ r )) (ε = 0.8, ε∗ = 1, ν = 10, ν′ = 20). We prove FODP in Theorem 5 by directly showing (3). Joint Asymmetric Geometric Distribution. The remaining issue is how to design (D , D ′ ) so that the joint binary input mechanism MD∗ ,D ′ ,β provides DP. To address this issue, we propose the joint asymmetric geometric distribution:
5.5 FOLNF∗ (Fully Oblivious LNF with Differentially Private Bot Counts)
Definition 9 (Joint asymmetric geometric distribution). Let ε ∈ R≥0 , ε∗ ∈ [ε, ∞), β ∈ [1 − e−ε/2 , 1], ν, ν′ ∈ Z≥0 , L(ε) =
Algorithm. FOLNF∗ is a modification of FOLNF that generates bot counts (κ1 , . . . , κd ) under DP. Specifically, FOLNF∗ is an instance of our general algorithm, where λ = 0 and BotCountGeneration generates a sample ωi from a botcount distribution D ′ over Z≥0 and outputs κi = zi + ωi ∗ (ωi ∼ D ′ ). We denote this algorithm by RDFOLNF ,D ′ ,β .
metric distribution is a pair of two asymmetric geometric distributions (AGeo(ν, ql , qr ), AGeo(ν′ , q′l , q′r )), where ql = L(ε), qr = R(ε), q′l = q1r R(ε∗ ), and q′r = q1l L(ε∗ ) if β > 1 − e−ε/2 and q′r = 0 otherwise.
∗
Privacy and Robustness. Privacy analysis of RDFOLNF ,D ′ ,β is non-trivial because κi (= zi + ωi ) depends on the number zi of dummies for item i. In other words, bot counts (κ1 , . . . , κd ) output by the bot-count algorithm depend on shuffled values ∗ FOLNF∗ output by RDFOLNF ,D ′ ,β . To enable privacy analysis of RD ,D ′ ,β , we introduce a mechanism called the joint binary input mechanism: Definition 8 (Joint binary input mechanism). Let β ∈ [0, 1]. The joint binary input mechanism MD∗ ,D ′ ,β = (MD ,β , MD−′ ,β ) is a pair of two mechanisms (MD ,β , MD−′ ,β ) that takes binary data x ∈ {0, 1} as input and outputs (MD ,β (x), MD−′ ,β (x)) = (αx + z, −αx + ω),
(7)
where α ∼ Ber(β), z ∼ D , and ω ∼ D ′ . Note that outputting (7) is equivalent to outputting (MD ,β (x), MD ,β (x) + MD−′ ,β (x)) = (αx + z, z + ω) and that z + ω follows the same distribution as κi (= zi + ωi ). Thus, this joint mechanism can be regarded as a binary input version ∗ of RDFOLNF ,D ′ ,β (see Appendix E.7 for details). Based on this, we ∗
reduce FODP of RDFOLNF ,D ′ ,β to DP of this joint mechanism: Theorem 5. Let MD∗ ,D ′ ,β = (MD ,β , MD−′ ,β ) be a joint binary input mechanism. If MD ,β provides ( 2ε , 2δ )-DP and MD∗ ,D ′ ,β ε∗
δ∗
FOLNF∗
provides ( 2 , 2 )-DP, then RD ,D ′ ,β provides (ε, δ)-DP and (ε∗ , δ∗ )-FODP and is robust against collusion with users.
e−ε/2 −1+β β , and R(ε) = eε/2 −1+β . The joint asymmetric geoβ
We use AGeo(ν, ql , qr ) as D and AGeo(ν′ , q′ l , q′ r ) as D ′ . Figure 4 shows their examples. In this case, D is identical to the asymmetric geometric distribution in [60], whose left tail shrinks as β decreases. An interesting feature of D ′ is that the right tail shrinks as β decreases. In other words, D is positively skewed, whereas D ′ is negatively skewed. This corresponds to the fact that (7) adds samples from D and D ′ to a positive value αx and a negative value −αx, respectively. We now prove that the joint binary input mechanism MD∗ ,D ′ ,β with this joint distribution provides DP: Theorem 6. Let MD∗ ,D ′ ,β = (MD ,β , MD−′ ,β ) be a joint binary input mechanism, where (D , D ′ ) is given by (AGeo(ν, ql , qr ), AGeo(ν′ , q′ l , q′ r )) in Definition 9. Then, MD ,β provides ∗ ∗ ( 2ε , 2δ )-DP and MD∗ ,D ′ ,β provides ( ε2 , δ2 )-DP, where δ is given ′
′
by (6), δ∗ = max{δ, 2βq′ νl /η′ }, and η′ = q′l (1 − q′ νl )/(1 − q′l ) + 1/(1 − q′r ). By Theorems 5 and 6, FOLNF∗ with the joint asymmetric geometric distribution provides (ε, δ)-DP and (ε∗ , δ∗ )-FODP, where ε ≤ ε∗ and δ ≤ δ∗ . We can control the privacy parameters (ε∗ , δ∗ ) in FODP by changing the parameters in D ′ . The parameters ν and ν′ are uniquely determined as minimum values such that δ∗ does not exceed a required value. Comparison with [34]. The asymmetric geometric distribution D = AGeo(ν, ql , qr ) becomes a symmetric geometric distribution when β = 1, which is near-optimal in the central model [35]. Ghazi et al. [34] propose a multi-message shuffle
protocol that achieves accuracy close to the symmetric geometric mechanism. However, the protocol in [34] requires many dummies generated from the negative binomial distribution to achieve almost the same accuracy as the geometric mechanism; the number of dummies even diverges to infinity. Thus, our FOLNF/FOLNF∗ with D = AGeo(ν, ql , qr ) significantly outperforms [34] in terms of accuracy and efficiency.
5.6
Comparisons of Our Three Algorithms
FOUD vs. FOLNF. We first compare our FOUD with FOLNF. The advantage of FOUD is that it uses only ORAND_NATS and OSHUFFLE as primitives and is easy to implement. However, FOLNF is more flexible in that it can use any distribution providing DP as D . In particular, FOLNF with the asymmetric geometric distribution D = AGeo(ν, ql , qr ) provides higher accuracy and efficiency than FOUD, as shown in Section 7. FOLNF vs. FOLNF∗ . Next, we compare our FOLNF with FOLNF∗ . FOLNF achieves DP and FODP with (εE , δE ) = (εI , δI ) = (ε, δ + δ0 ). In contrast, FOLNF∗ with the same dummy-count distribution D provides DP and FODP with (εE , δE ) = (ε, δ), (εI , δI ) = (ε∗ , δ∗ ), ε ≤ ε∗ , and δ ≤ δ∗ . Thus, these algorithms differ in the following two aspects. First, FOLNF∗ achieves FODP with a larger privacy budget εI than FOLNF. The resulting benefit is higher efficiency. Specifically, FOLNF∗ can reduce the number of bots ⊥ (thereby improving efficiency) by increasing εI in FODP. Second, FOLNF introduces an additional term δ0 in DP, whereas FOLNF∗ does not introduce δ0 . In particular, when β = 1 − e−εE /2 , FOLNF∗ provides pure DP (i.e., δE = 0).
6
Efficiency of Our FODP Algorithms
In this section, we analyze the runtime of our algorithms (Section 6.1) and improve it using the count-min (Section 6.2).
6.1
Efficiency Analysis
We first show the runtime of our general algorithm RD ,D ′ ,β,λ : Theorem 7. The runtime of random sampling and dummy data addition in RD ,D ′ ,β,λ (Algorithm 1) is O(n log d) and O((λ + ∑di=1 κi ) log d), respectively. The total runtime of RD ,D ′ ,β,λ is O(n̄ log d + ρ), where n̄ = n + λ + ∑di=1 κi is the number of shuffled values and ρ is the runtime of OSHUFFLE. If we use ORShuffle [68] (resp. WaksShuffle [69]) as OSHUFFLE, then ρ = O((n̄ log2 n̄) log d) (resp. O(n̄ log3 n̄ + n̄ log n̄ log d)). Since λ = O(d), the runtime of RD ,D ′ ,β,λ can be expressed as Õ(n + d) by ignoring the logarithmic factor. It is also possible to run a central DP algorithm [20, 27, 47] within the TEE. However, it requires prohibitively large runtime Õ(nd), as it must access the entire memory to provide obliviousness when adding each input value to the histogram [6]. See Appendix B.2 for details.
Input: Database x = (x1 , . . . , xn ), #items d ∈ N, hash functions h1 , . . . , hτ : [d] → [b]. Output: Tuple (x̃1 , . . . , x̃τ ) of shuffled values. 1 foreach t ∈ [τ] do 2 xt ← (ht (x1 ), . . . , ht (xn )); 3 x̃t ← RD ,D ′ ,β,λ (xt , b); 4 end 5 return (x̃1 , . . . , x̃τ ) Algorithm 2: Our general algorithm RDLarge ,D ′ ,β,λ for large-domain data.
6.2
Improving the Efficiency
Overview. Our algorithms achieve a runtime of Õ(n + d). Note that we can reduce n by sampling users in advance. However, we cannot reduce d by sampling items, as we need to estimate the frequency for each item. Thus, our algorithms are still inefficient for large-domain data with large d. To address this issue, we improve the efficiency of our general algorithm using the count-min sketch [25]. The countmin sketch compresses each input or dummy value using τ ∈ N hash functions. Then, it estimates the frequency of each item by taking the minimum of τ counts to mitigate the impact of hash collisions. We show a bound on the accuracy much tighter than [24, 33] and optimize τ based on our bound. Algorithm. Algorithm 2 shows our general framework for large-domain data, denoted by RDLarge ,D ′ ,β,λ . This algorithm uses τ hash functions h1 , . . . , hτ : [d] → [b], where b < d. For each t ∈ [τ], we transform input values (x1 , . . . , xn ) into their hash values xt = (ht (x1 ), . . . , ht (xn )) (line 2). Then, we run our general algorithm RD ,D ′ ,β,λ (Algorithm 1) with inputs xt and b to obtain shuffled values x̃t (line 3). The output of RDLarge ,D ′ ,β,λ is the tuple (x̃1 , . . . , x̃τ ) of shuffled values. Calculation of f̂. After RDLarge ,D ′ ,β,λ outputs (x̃1 , . . . , x̃τ ), the server (outside the TEE) discards ⊥ from the shuffled data. Then, for each i ∈ [d] and each t ∈ [τ], the server counts the number ct,ht (i) ∈ Z≥0 of hash value ht (i) in x̃t . Based on the count ct,ht (i) , the server calculates an estimate f̂ as follows: 1 fˆi = nβ (mint∈[τ] ct,ht (i) − λb − µ) (i ∈ [d]).
(8)
where µ is the mean of the dummy-count distribution D . Theoretical Properties. It is easy to show that RDLarge ,D ′ ,β,λ provides DP, FODP, and robustness based on the composition theorem [42]; see Appendix C.3. The runtime of RDLarge ,D ′ ,β,λ is Õ(n + b). For example, when n ≪ d, we can reduce the runtime from Õ(n + d) to Õ(n) by setting b = O(n). Below, we analyze the accuracy of RDLarge ,D ′ ,β,λ . Following [33], we use additive error as a metric:
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0 1
2
3
4
5
Our bound ( Our bound ( GGK+21 ( GGK+21 ( 1
2
3
4
) ) )
5
Figure 5: Our bound (Theorem 8) and the bound in [33] (GGK+21) for FOLNF with D = Bin(n, ϕ) (ϕ ∈ [0, 1]) and β = 1. We set (n, ϕ) = (104 , 0.26), in which case (εI , δI ) = (εE , δE ) = (1, 10−12 ) for a single hash function (τ = 1). Theorem 8. Let γ ∈ (0, ∞), ξ ∼ Bin(n fi , β) + Bin(λ, 1b ) + D , and ξavg = n fi β + λb + µ. Then, for each item i ∈ [d], RDLarge ,D ′ ,β,λ provides the following accuracy guarantee: τ 2 Pr[| fˆi − fi | ≤ γ] ≥ 1 − bγ + Pr[ξ > ξavg + nβγ ] 2 −τ · Pr[ξ < ξavg − nβγ].
7
Experimental Evaluation
7.1
Experimental Set-up
)
(9)
Theorem 8 decomposes the increase in the additive error 2 | fˆi − fi | into two factors: hash collision ( bγ in (9)) and DP noise (Pr[ξ > ξavg + nβγ 2 ] and Pr[ξ < ξavg − nβγ] in (9)). The values of Pr[ξ > ξavg + nβγ 2 ] and Pr[ξ < ξavg − nβγ] depend on the concrete algorithm of RD ,D ′ ,β,λ . In Appendix C.3, we analyze these values in FOUD, FOLNF, and FOLNF∗ . Figure 5 shows our bound in Theorem 8 and the bound in [33] (denoted by GGK+21) when applied to FOLNF with the binomial distribution D = Bin(n, ϕ) (ϕ ∈ [0, 1]) and β = 1. We do not show the bound in [24], as it yields the same results as GGK+21; see Appendix C.3 for details of these bounds. We observe that GGK+21 cannot lower bound Pr[| fˆi − fi | ≤ γ]. This is because GGK+21 calculates the lower bound based on the probability that no hash collision occurs among n input values, which is almost zero when b ≤ n. In contrast, our bound gives a non-trivial lower bound on Pr[| fˆi − fi | ≤ γ], as it directly evaluates the increase in the additive error caused by the hash collision. For example, our bound shows that when τ = 2 and b = n, the additive error is smaller than 100 n (resp. 200 n ) with probability at least 0.56 (resp. 0.99). Optimization of τ. The probability Pr[| fˆi − fi | ≤ γ] increases with an increase in τ because the impact of hash collisions can be mitigated by taking the minimum of τ counts. However, the increase in τ results in larger privacy parameters (εI , δI ) and (εE , δE ) due to the composition. Therefore, we calculate an optimal value of τ that maximizes the accuracy at the same privacy parameters based on our bound in Theorem 8. Specifically, given τ and the required values for (εI , δI ) and (εE , δE ), we calculate the privacy parameters for each hash function based on the composition theorem [42]. Then, we calculate the value of γ such that the right side of (9) is larger than a predetermined threshold pthr ∈ [0, 1]. We perform this process for various values of τ and select τ that minimizes γ. We show that this approach works well in our experiments.
In this section, we evaluate the accuracy and runtime of our algorithms. Following [56, 60, 61, 76], we use the following datasets with various n, d, and data types: IPUMS [67]. U.S. Census data with n = 602156 users and d = 915 cities (we sampled 1% of users, as in [76]). Localization [43]. Person activity data with n = 164860 instances and d = 11 activity types (e.g., walking, lying). Foursquare [77]. Location data containing n = 18201 checkins in New York divided into d = 106 (= 103 × 103 ) regions. AOL [66]. Website access data. We used n = 10000 accesses and d = 16777216 (= 224 ) domain names comprising the first three characters of the URL, as in [56]. IPUMS and Localization are small-domain datasets, whereas Foursquare and AOL are large-domain datasets. Algorithms. We first evaluated our three algorithms (FOUD, FOLNF, and FOLNF∗ ) using two small-domain datasets. As (D , D ′ ), we used the joint asymmetric geometric distribution with β = 1 (denoted by AGeo) or 1 − eεE /2 (denoted by 1Geo, as D and D ′ are one-sided geometric distributions in this case). Note that we used the same distribution D for FOLNF and FOLNF∗ . In FOLNF, we set δ = δ0 (= δ2E = δ2I ). We compared the accuracy of our algorithms with that of six existing pure shuffle algorithms. Specifically, as competitors, we evaluated three shuffle algorithms based on the GRR [41, 76], OUE [75], and OLH [75] and three multi-message shuffle algorithms in [11,24,56] (denoted by GRR, OUE, OLH, BC20, CM22, and LWY22, respectively). Then, we evaluated our three algorithms with the countmin sketch (denoted by FOUD-L, FOLNF-L, and FOLNF∗ -L) using two large-domain datasets. We set pthr = 0.5 and compared the accuracy of our algorithms with that of two existing algorithms: the FME algorithm [61] (denoted by FME) and LWY22 for a large domain [56] (denoted by LWY22-L). For FME, we evaluated an accurate version (“large l” in [61]). For the other existing algorithms, we used the same parameters and privacy amplification bounds as [60] (see [60]). Note that none of the existing algorithms provides FODP. Thus, we compared our algorithms with the existing ones at the same value of εE in DP. We evaluated εI in FODP only for our algorithms. For the delta values, we set δE , δI ≤ 10−12 . Accuracy Metrics. We used the MSE (Mean Squared Error) d1 ∑di=1 ( fˆi − fi )2 as a metric for small-domain datasets. For large-domain datasets, we used the MSE over the top-50 items with the highest frequencies, as most items have zero frequencies. We evaluated the average MSE over 100 runs. Runtime on Intel SGX. We also measured the runtime of our algorithms on a Microsoft Azure Virtual Machine (Standard DC2s v3) [5], a public cloud platform that supports Intel SGX. It includes 2 vCPUs and 16 GiB of memory and runs
10 10−6 10−7 10−8 10−9 10−10 10−11 10−12
*
FOLNF/FOLNF -L (AGeo) LWY22-L
Foursquare
10−4
1
0.1
10
10
FOLNF/FOLNF -L (1Geo)
b=0.1n
AOL
b=0.1n
b=0.1n
10−6 10−7
10−4
Figure 0.1 6: MSE vs. ε 60
800
40
400
20
FOLNF (AGeo) FOLNF* (AGeo) 0.2
0.4
0.6
0.8
1
1
0.1
10−5 10−4
10
10
0.1
1
10
10−5
10−8 10
−7
−9 10
−8
10
b=10n
0.1
1
0.4
0.6
0.8
1
0.2
0.4
0.6
0.8
b=n
b=10n
0.1 1 b=0.1n b=n
b=10n
FOLNF/FOLNF* (1Geo)
−5 −6 10 10−5 10
10−7 10−5 10−6 10−8
10
10−6 10−7
1
10
10
Figure 9: MSE for various values of b (τ: optimized, AOL).
FOLNF (AGeo) FOLNF (1Geo) FOLNF* (AGeo) FOLNF* (1Geo)
10−4
∗ Appendix D.2, we also show that FOLNF-L 10 and FOLNF -L are much more communication-efficient than FME.
0 0.2
b=10n
b=0.1n
−4
10 FOLNF/FOLNF* (AGeo) 10−5
−5
10−7 −6 10−5 10
10−6 10−5
10 1 E in DP (τ: optimized, b = n).
FOLNF (1Geo) FOLNF* (1Geo)
b=n
b=10n
b=n
MSE
1200
0
10
10
MSE
1
0.1
−9
b=10n
−4 10−6 0.110
MSE
10−8
10−9
b=n
FOUD
b=n
b=0.1n
MSEMSE MSE
10−8
10
Figure 8: MSE for various values of τ (b = n,b=nAGeo ). b=0.1n b=10n
10−5
−6
1
0.1
*
10−4
10−7
1
0.1 1 expected number 10 E[κi ] of Figure 7: Relationship between the bots, δE in DP, and εI in FODP (εE = 0.1, δI = 10−12 ).
on Ubuntu 20.04.6 LTS (Linux kernel 5.15.0-1089-azure). Since the codes of ORShuffle and WaksShuffle in [1] could not handle over ten million data points due to stack overflow, we implemented ORShuffle without a stack. In Appendix D.1, we also evaluate the runtime of our algorithms using the codes of ORShuffle and WaksShuffle in [1]. Note that the runtime depends on n and d, but not on input values (x1 , . . . , xn ). Thus, we randomly generated each input value xi (i ∈ [n]) from [d] when measuring the runtime. We also confirmed that the runtime is almost the same when we used real datasets with the same n and d.
7.2
10−8
−9
MSE
MSE
1
10−3
10−5 10
10−7
10−8
MSE
FOUD-L FME
10−6
10−7
0.1
10
AOL
10−5
10−6
10
Optimized
10−4
MSE
MSE
1
0.1
Foursquare
10−5
MSE
10−7 10−8 10−9 10−10 10−11 10−12 10−13
Localization
−5
MSE MSE MSE
IPUMS
FOLNF/FOLNF* (1Geo) BC20 CM22 LWY22
MSE
FOLNF/FOLNF* (AGeo) OUE/OLH
FOUD GRR
Experimental Results
Accuracy. Figure 6 shows the MSE over a wide range of εE from 0.1 to 10. In FOUD-L, FOLNF-L, and FOLNF∗ -L, we set b = n and optimized τ using our method. FOLNF and FOLNF∗ provide the same accuracy, as they use the same D . Figure 6 shows that our FOLNF/FOLNF∗ (AGeo) and FOUD achieve the best and second-best accuracy, respectively, which indicates that accuracy can be improved by introducing the augmented shuffle model. Although 1Geo is less accurate than AGeo, it achieves pure DP and higher efficiency, as shown later. For large-domain data, our FOLNF-L and FOLNF∗ -L provide the best (or almost the best) accuracy when ε ≤ 5. In
−5
FOLNF vs. FOLNF∗ . Next, we compared FOLNF with FOLNF∗ . Figure 7 shows the expected number E[κi ] of bots
for each item i ∈ [d] and the value of δE in DP. Here, we set εE = 0.1, which is the most stringent in terms of efficiency; i.e., both E[κi ] and the runtime are smaller when εE > 0.1. Figure 7 shows that E[κi ] in FOLNF∗ decreases with an increase in εI in FODP, as the variance of the bot-count distribution D ′ decreases in this case. For example, when εI = 1, FOLNF∗ with AGeo (resp. 1Geo) reduces E[κi ] of FOLNF by about half (resp. one-third). Figure 7 also shows that FOLNF∗ reduces δE in DP. Specifically, FOLNF∗ (AGeo) reduces δE of FOLNF by half, and FOLNF∗ (1Geo) achieves pure DP (δE = 0). Changing τ and b. We also evaluated our algorithms for large-domain data while changing the number τ of hashes and the hash range b. Figures 8 and 9 show the results. In Appendix D.3, we also show that similar results are obtained when varying τ in 1Geo and varying b in Foursquare. Figure 8 shows that setting τ = 1 results in the smallest MSE for small εE , as it avoids an increase in εE due to composition. However, setting τ ≥ 2 results in a smaller MSE for large εE , as it mitigates the impact of hash collisions. Our optimization method successfully takes the best of both worlds and finds the optimal τ in most cases. Figure 9 shows that the MSE is reduced by increasing b. However, it comes at the cost of efficiency, as the runtime of our algorithms is Õ(n + b). Figure 9 also shows that the accuracy is close between b = n and b = 10n. Runtime. Then, we measured the runtime of our algorithms. Figure 10 shows the time for random sampling, dummy data addition, and shuffling when (n, d) = (106 , 103 ) or (103 , 106 ).
(a)
(b)
Random Adding Shuffling sampling dummies
Random Adding Shuffling sampling dummies
Figure 10: Time for random sampling, dummy data addition, and shuffling in our algorithms (εE = 0.1, εI = 1). In (b), we used the count-min sketch (b = n).
Runtime (s)
FOUD
FOLNF (AGeo)
(a)
FOLNF (AGeo) FOLNF (1Geo) FOLNF* (AGeo) FOLNF* (1Geo) Basic DP histogram
Runtime (s)
Runtime (s)
FOUD FOLNF (AGeo) FOLNF* (AGeo) FOLNF (1Geo) FOLNF* (1Geo)
FOLNF* (AGeo)
(b)
FOLNF (1Geo)
FOLNF* (1Geo)
(c)
Figure 11: Total runtime of our algorithms (εE = 0.1, εI = 1). In (b), we used the count-min sketch (b = n) when n < d.
Figure 12: Total runtime of our algorithms and the basic DP histogram (εE = 1, εI = 5). the central DP algorithm when n ≥ 104 . Note that this also holds when d ≫ n ≥ 104 and all algorithms (including the basic DP histogram) use the count-min with b = n. Figure 11(c) and Figure 12 show that our algorithms have a lower runtime when εE = 1, as the number of bots is smaller. For example, when n = d = 108 , the central DP algorithm requires about 270 days (= 2.3 × 107 seconds). In contrast, our algorithms take less than one day when n and d are at most 109 (e.g., n = 3 × 108 and d = 6 × 108 in Amazon [2]), demonstrating their efficiency. We also note that when n = d ≤ 103 , the basic DP histogram is comparable to or more efficient than our algorithms. Thus, the former would be preferable in such small n and d.
Figure 11 shows the total runtime when n and d are varied to various values. In Figure 11(c), we confirmed that the runtime of FOLNF and FOLNF∗ was almost linear in n̄ log2 n̄, where n̄ is the number of shuffled values. Based on this property, we estimated the runtime of these algorithms for n ≥ 106 . Figure 10 shows that the time for shuffling is dominant. This is consistent with our theoretical results that the runtime of random sampling, dummy data addition, and shuffling is O(n log d), O((λ + ∑di=1 κi ) log d), and O((n̄ log2 n̄) log d), respectively, where n̄ = n + λ + ∑di=1 κi (Theorem 7). Figure 11(a) shows that FOLNF is more efficient than FOUD, as FOLNF adds fewer dummies than FOUD. In addition, FOLNF∗ and 1Geo are more efficient than FOLNF and AGeo, respectively, because they add fewer bots, as shown in Figure 7. Figure 11(b) shows that the runtime for largedomain data can be significantly reduced from Õ(n + d) to Õ(n) by using the count-min sketch. Furthermore, Figure 11(c) shows that our algorithms handle very large data. For example, the runtime of our FOLNF (AGeo), FOLNF∗ (AGeo), FOLNF (1Geo), and FOLNF∗ (1Geo) is 16 hours, 8 hours, 29 minutes, and 13 minutes, respectively.
We proposed a new privacy notion, FODP, and its algorithms for the augmented shuffle model with TEEs. Through theoretical analysis and extensive experiments, we showed that our algorithms achieve high accuracy, robustness, and efficiency (e.g., 16 hours or less when n = d = 108 ) under FODP. For future work, we would like to study FODP for other tasks, such as the report noisy max [28], graph analysis [30,39], and federated learning [36, 55].
Comparison with a Central DP Algorithm. Finally, we compared the runtime of our algorithms with that of a central DP algorithm within the TEE. Specifically, we evaluated the basic DP histogram [12, 27] because it has the same time complexity as the stability histogram [20, 47] when they are fully oblivious; see Appendix B.2 for details. Figure 12 shows the results. Here, we confirmed that the total runtime of the basic DP histogram (resp. our algorithms) was almost linear in nd (resp. n̄ log2 n̄, where n̄ is #shuffled values). Based on this, we estimated the total runtime when n = d = 103 to 109 . Figure 12 shows that our algorithms are more efficient than
Ethical Considerations
8
Conclusion
Acknowledgments We thank Shun Takagi, Satoshi Hasegawa, and anonymous reviewers for their helpful comments. This paper was edited for grammar using ChatGPT and Grammarly. This study was supported in part by JSPS KAKENHI 22H00521, 24H00714, 24K20775, JST K Program Grant Number JPMJKP24U5, JST NEXUS JPMJNX25C2, JST AIP Acceleration Research JPMJCR22U5, and JST CREST JPMJCR22M1.
Our work develops a new privacy notion, FODP, and algorithms for FODP in the augmented shuffle model with TEEs. Our algorithms can be used to calculate a frequency distribution on a single server while strongly preventing the leakage
of personal data from the algorithms’ outputs and their sidechannel information, such as memory access patterns and control flows. Following the ethics guidelines, we conduct a stakeholder-based analysis. Stakeholder Analysis. Our stakeholders include (1) users who join the protocol, (2) a service provider who manages the server and collects their personal data, and (3) a data analyst (or anyone) who obtains the published frequency distribution. Impacts. Our algorithms provide high accuracy, privacy, robustness, and efficiency, thereby having a positive ethical impact on all of the stakeholders. In addition, we do not encounter privacy issues that may arise from the use of private datasets, as we used only public datasets. However, there are some potential negative impacts. Specifically: • Users. Robustness means that privacy is not violated, even if the service provider (or data analyst) colludes with some users. Thus, high privacy and robustness reduce the risks of compromising user privacy. One potential negative impact is that privacy information might be leaked by timing attacks, as described in Section 4.1. • Service Provider. The high privacy and robustness reduce the risks of damaging his/her reputation. One potential negative impact is that using our algorithms may increase the service provider’s effort and overhead. • Data Analyst. The data analyst benefits from high accuracy and efficiency, as he/she wants to calculate an accurate frequency distribution in a timely manner. Mitigation. As discussed in Section 4.1, a mitigation strategy for timing attacks is to make the runtime constant [37, 40]. In addition, we have published our code to decrease the effort and overhead for the service provider. Improving efficiency is an important future direction to further decrease overhead. Decision. We decided to proceed with the research and publish it because the high accuracy, privacy, robustness, and efficiency of our algorithms have a positive impact on all stakeholders, as explained above. The potential negative impacts can also be mitigated by, e.g., making the runtime constant and improving efficiency. We also believe that our work will serve as a basis for further research on more accurate, private, and efficient algorithms that have more positive ethical impacts on all stakeholders.
Open Science Following the open science policy, we have published our artifacts on the following website: https://doi.org/10.5 281/zenodo.20287113. Our artifacts include: • Source code of an implementation of our algorithms. • Instructions on how to run our code to obtain our experimental results (README).
We have explained how to run our code for all experimental results. See README for more details.
References [1] Fully oblivious algorithms. https://crysp.uwater loo.ca/software/obliv/, 2023. [2] Amazon statistics: Key numbers and fun facts. http s://amzscout.net/blog/amazon-statistics/, 2024. [3] Community standards enforcement report: Fake accounts. https://transparency.meta.com/repo rts/community-standards-enforcement/fake-a ccounts/, 2025. [4] Twitter spam bots: How they hurt users, brands, and advertisers. https://www.clickguard.com/blog/ twitter-spam-bots/, 2025. [5] Virtual machines in azure. https://learn.microsof t.com/en-us/azure/virtual-machines/, 2026. [6] J. Allen, B. Ding, J. Kulkarni, H. Nori, O. Ohrimenko, and S. Yekhanin. An algorithmic framework for differentially private data analysis on trusted processors. In Proc. NeurIPS’19, pages 13657–13664, 2019. [7] I. Anati, S. Gueron, S. Johnson, and V. Scarlata. Innovative technology for CPU based attestation and sealing. In Proc. HASP’13, pages 1–7, 2013. [8] R. Arratia and L. Gordon. Tutorial on large deviations for the binomial distribution. Bulletin of Mathematical Biology, 51(1):125–131, 1989. [9] G. Asharov, I. Komargodski, W.-K. Lin, K. Nayak, E. Peserico, and E. Shi. OptORAMa: Optimal oblivious RAM. Journal of the ACM, 70(1):1–70, 2022. [10] A. Athanasiou, K. Chatzikokolakis, and C. Palamidessi. Enhancing metric privacy with a shuffler. PoPETs, 2025(2):650–679, 2025. [11] V. Balcer and A. Cheu. Separating local & shuffled differential privacy via histograms. In Proc. ITC’20, pages 1–14, 2020. [12] V. Balcer and S. Vadhan. Differential privacy on finite computers. Journal of Privacy and Confidentiality, 9(2):1–46, 2019. [13] B. Balle, G. Barthe, and M. Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Proc. NeurIPS’18, pages 6280–6290, 2018.
[14] B. Balle, J. Bell, A. Gascon, and K. Nissim. The privacy blanket of the shuffle model. In Proc. CRYPTO’19, pages 638–667, 2019.
[27] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proc. TCC’06, pages 265–284, 2006.
[15] R. Baruchin. Musk v. Twitter: Read CNN’s article on Cyabra’s analysis. https://cyabra.com/press-r elease/in-the-news/musk-v-twitter-read-cnn s-article-on-cyabras-analysis/, 2022.
[28] C. Dwork and A. Roth. The Algorithmic Foundations of Differential Privacy. Now Publishers, 2014.
[16] A. Beimel, K. Nissim, and E. Omri. Distributed private data analysis: Simultaneously solving how and what. In Proc. CRYPTO’08, pages 451–468, 2008. [17] J. Bell, A. Gascon, B. Ghazi, R. Kumar, P. Manurangsi, M. Raykova, and P. Schoppmann. Distributed, private, sparse histograms in the two-server model. In Proc. CCS’22, pages 307–321, 2022. [18] A. Bittau, U. Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer, U. Kode, J. Tinnes, and B. Seefeld. PROCHLO: Strong privacy for analytics in the crowd. In Proc. SOSP’17, pages 441–459, 2017. [19] J. V. Bulck, N. Weichbrodt, R. Kapitza, F. Piessens, and R. Strackx. Telling your secrets without page faults: Stealthy page table-based attacks on enclaved execution. In Proc. USENIX Security’17, pages 1041–1056, 2017. [20] M. Bun, K. Nissim, and U. Stemmer. Simultaneous private learning of multiple concepts. Journal of Machine Learning Research, 20(94):1–34, 2019. [21] X. Cao, J. Jia, and N. Z. Gong. Data poisoning attacks to local differential privacy protocols. In Proc. USENIX Security’21, pages 947–964, 2021. [22] T.-H. H. Chan, K.-M. Chung, B. M. Maggs, and E. Shi. Foundations of differentially oblivious algorithms. In Proc. SODA’19, pages 2448–2467, 2019.
[29] U. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, and K. Talwar. Amplification by shuffling: from local to central differential privacy via anonymity. In Proc. SODA’19, pages 2468–2479, 2019. [30] J. Fang and K. Yi. Counting subgraphs under shuffle differential privacy. In Proc. CCS’25, pages 2369–2383, 2025. [31] V. Feldman, A. McMillan, and K. Talwar. Stronger privacy amplification by shuffling for rényi and approximate differential privacy. In Proc. SODA’23, pages 4966–4981, 2023. [32] M. Fredman and D. Willard. Blasting through the information theoretic barrier with fusion trees. In Proc. STOC’90, pages 1–7, 1990. [33] B. Ghazi, N. Golowich, R. Kumar, R. Pagh, and A. Velingker. On the power of multiple anonymous messages: Frequency estimation and selection in the shuffle model of differential privacy. In Proc. EUROCRYPT’21, pages 463–488, 2021. [34] B. Ghazi, R. Kumar, P. Manurangsi, and R. Pagh. Private counting from anonymous messages: Near-optimal accuracy with vanishing communication overhead. In Proc. ICML’20, pages 3505–3514, 2020. [35] A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility-maximizing privacy mechanisms. SIAM Journal on Computing, 41(6):1673–1693, 2012.
[23] A. Cheu, A. Smith, and J. Ullman. Manipulation attacks in local differential privacy. In Proc. S&P’21, pages 883–900, 2021.
[36] A. Girgis, D. Data, S. Diggavi, P. Kairouz, and A. T. Suresh. Shuffled model of differential privacy in federated learning. In Proc. AISTATS’21, pages 2521–2529, 2021.
[24] A. Cheu and M. Zhilyaev. Differentially private histograms in the shuffle model from fake users. In Proc. S&P’22, pages 440–457, 2022.
[37] A. Haeberlen, B. C. Pierce, and A. Narayan. Differential privacy under fire. In Proc. USENIX Security’11, pages 1–15, 2011.
[25] G. Cormode and S. Muthukrishnan. An improved data stream summary: The count-min sketch and its applications. Journal of Algorithms, 55(1):58–75, 2005.
[38] C. Harrison and P. Manurangsi. Infinitely divisible noise for differential privacy: Nearly optimal error in the high ε regime. In Proc. FORC’25, pages 12:1–12:24, 2025.
[26] J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates. In Proc. FOCS’13, pages 429–438, 2013.
[39] J. Imola, T. Murakami, and K. Chaudhuri. Differentially private triangle and 4-cycle counting in the shuffle model. In Proc. CCS’22, pages 1505–1518, 2022.
[40] J. Jin, E. McMurtry, B. I. P. Rubinstein, and O. Ohrimenko. Are we there yet? Timing and floating-point attacks on differential privacy systems. In Proc. S&P’22, pages 473–488, 2022.
[53] N. Li, W. Qardaji, and D. Su. On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy. In Proc. ASIACCS’12, pages 1–11, 2012.
[41] P. Kairouz, K. Bonawitz, and D. Ramage. Discrete distribution estimation under local privacy. In Proc. ICML’16, pages 2436–2444, 2016.
[54] X. Li, N. Li, W. Sun, N. Z. Gong, and H. Li. Fine-grained poisoning attack to local differential privacy protocols for mean and variance estimation. In Proc. USENIX Security’23, pages 1739–1756, 2023.
[42] P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for differential privacy. In Proc. ICML’15, pages 1376–1385, 2015. [43] B. Kaluža, V. Mirchevska, E. Dovgan, M. Luštrek, and M. Gams. An agent-based approach to care in independent living. In Proc. AmI’10, pages 177–186, 2010. [44] A. Karmakar, S. S. Roy, O. Reparaz, F. Vercauteren, and I. Verbauwhede. Constant-time discrete gaussian sampling. IEEE Trans. Computers, 67(11):1561–1571, 2018. [45] S. P. Kasivisiwanathan and A. Smith. On the ‘semantics’ of differential privacy: A bayesian formulation. Journal of Privacy and Confidentiality, 6(1):1–16, 2014. [46] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, and S. Raskhodnikova. What can we learn privately? In Proc. FOCS’08, pages 531–540, 2008. [47] C. J. Lebeda and L. Retschmeier. The correlated Gaussian sparse histogram mechanism. In Proc. FORC’25, pages 23:1–23:20, 2025. [48] D. Lee. Building trusted execution environments. Technical Report EECS-2022-96, EECS Department, University of California, Berkeley, 2022. [49] D. Lee, D. Jung, I. T. Fang, C.-C. Tsai, and R. A. Popa. An off-chip attack on hardware enclaves via the memory bus. In Proc. USENIX Security’20, pages 487–504, 2020. [50] S. Lee, M.-W. Shih, P. Gera, T. Kim, and H. Kim. Inferring fine-grained control flow inside SGX enclaves with branch shadowing. In Proceedings of the 26th USENIX Security Symposium (USENIX Security’17), pages 557–574, 2017. [51] S. V. Lekshmi and S. Sebastian. A skewed generalized discrete laplace distribution. International Journal of Mathematics and Statistics Invention, 2(3):95–102, 2014. [52] N. Li, M. Lyu, and D. Su. Differential Privacy: From Theory to Practice. Morgan & Claypool Publishers, 2016.
[55] R. Liu, Y. Cao, H. Chen, R. Guo, and M. Yoshikawa. FLAME: Differentially private federated learning in the shuffle model. In Proc. AAAI’21, pages 8688–8696, 2021. [56] Q. Luo, Y. Wang, and K. Yi. Frequency estimation in the shuffle model with almost a single message. In Proc. CCS’22, pages 2219–2232, 2022. [57] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, 2017. [58] D. Moghimi, J. V. Bulck, N. Heninger, F. Piessens, and B. Sunar. Copycat: Controlled instruction-level attacks on enclaves. In Proc. USENIX Security’20, pages 469– 486, 2020. [59] S. Morgan. 2025 cybersecurity almanac: 100 facts, figures, predictions and statistics. https://cybersec urityventures.com/cybersecurity-almanac-2 025/, 2025. [60] T. Murakami, Y. Sei, and R. Eriguchi. Augmented shuffle protocols for accurate and robust frequency estimation under differential privacy. In Proc. S&P’25, pages 3892–3911, 2025. [61] T. Murakami, Y. Sei, and R. Eriguchi. Augmented shuffle differential privacy protocols for large-domain categorical and key-value data. In Proc. NDSS’26, pages 1–20, 2026. [62] K. P. Murphy. Machine Learning: A Probabilistic Perspective. The MIT Press, 2012. [63] L. H. X. Ng and K. M. Carley. A global comparison of social media bot and human characteristics. Scientific Reports, 15(10973):1–18, 2025. [64] N. Ngai, I. Demertzis, J. G. Chamani, and D. Papadopoulos. Distributed & scalable oblivious sorting and shuffling. In Proc. S&P’24, pages 4277–4295, 2024. [65] O. Ohrimenko, M. T. Goodrich, R. Tamassia, and E. Upfal. The Melbourne shuffle: Improving oblivious storage in the cloud. In Proc. ICALP’14, pages 556–567, 2014.
[66] G. Pass, A. Chowdhury, and C. Torgeson. A picture of search. In Proc. InfoScale’06, pages 1–7, 2006.
A
[67] S. Ruggles, S. Flood, M. Sobek, D. Backman, A. Chen, G. Cooper, S. Richards, R. Rogers, and M. Schouweiler. IPUMS USA: Version 14.0 [dataset]. https://doi.or g/10.18128/D010.V14.0, 2023.
A.1
[68] S. Sasy, A. Johnson, and I. Goldberg. Fast fully oblivious compaction and shuffling. In Proc. CCS’22, pages 2565– 2579, 2022. [69] S. Sasy, A. Johnson, and I. Goldberg. Waks-on/waks-off: Fast oblivious offline/online shuffling and sorting with waksman networks. In Proc. CCS’23, pages 3328–3342, 2023. [70] C. Shepherd and K. Markantonakis. Trusted Execution Environments. Springer, 2024. [71] E. Stefanov, M. van Dijk, E. Shi, C. Fletcher, L. Ren, X. Yu, and S. Devadas. Path ORAM: An extremely simple oblivious RAM protocol. Journal of the ACM, 65(4):1–26, 2018. [72] K. Thomas, D. McCoy, C. Grier, A. Kolcz, and V. Paxson. Trafficking fraudulent accounts: The role of the underground market in twitter spam and abuse. In Proc. USENIX Security’13, pages 195–210, 2013. [73] S. Wagh, X. He, A. Machanavajjhala, and P. Mittal. DPcryptography: Marrying differential privacy and cryptography in emerging applications. Communications of the ACM, 64(2):84–93, 2021. [74] S. Wang, J. Li, C. Dong, J. Li, Z. Zhou, and D. Wang. Side-channel attacks and new principles in the shuffle model of differential privacy. IEEE Trans. Information Forensics and Security, 20:6515–6528, 2025. [75] T. Wang, J. Blocki, N. Li, and S. Jha. Locally differentially private protocols for frequency estimation. In Proc. USENIX Security’17, pages 729–745, 2017. [76] T. Wang, B. Ding, M. Xu, Z. Huang, C. Hong, J. Zhou, N. Li, and S. Jha. Improving utility and security of the shuffler-based differential privacy. Proceedings of the VLDB Endowment, 13(13):3545–3558, 2020. [77] D. Yang, D. Zhang, and B. Qu. Participatory cultural mapping based on collective behavior data in location based social network. ACM Trans. Intelligent Systems and Technology, 7(3):30:1–30:23, 2016.
Details of Existing Shuffle Protocols and Robustness against Collusion with Users Privacy Amplification Results
Below, we present state-of-the-art privacy amplification results for pure shuffle protocols: Theorem 9 (Amplification-by-shuffling result [31]). Let εL ∈ R≥0 and δ ∈ [0, 1]. Let RL be a local randomizer. Let RS be a pure shuffle algorithm that takes x = (x1 , . . . , xn ) as input and outputs RS (x) = (RL (xπ(1) ), . . . , RL (xπ(n) )), where π is a random permutation over [n]. If RL provides εL -LDP, then RS provides (ε, δ)-DP with ε =g(n, εL , δ), where g(n, εL , δ) = √ 4(eεL −1) 2 ln(4/δ) n √ ε ln 1 + + n4 if εL ≤ ln( 8 ln(2/δ) − 1) and L (e +1)n
g(n, εL , δ) = εL otherwise. Theorem 9 is typically used for single-message protocols in the pure shuffle model. [11, 24, 56] show different values of g(n, εL , δ) for their multi-message protocols.
A.2 Formal Definition of the Robustness against Collusion with Users Below, we formally define the robustness against collusion with users by using Ω-neighboring databases [16]: Definition 10 (Ω-neighboring databases [16]). Let Ω ⊂ [n]. Two databases x = (x1 , . . . , xn ) ∈ [d]n and x′ = (x1′ , . . . , xn′ ) ∈ [d]n are Ω-neighboring if they differ on a single entry whose index i is not in Ω, i.e., ∃i ∈ / Ω: xi ̸= xi′ and ∀ j ̸= i: x j = x′j . In Definition 10, we consider an adversary who colludes with users {ui |i ∈ Ω} and tries to infer input values of the remaining users (i.e., victims) {ui |i ∈ / Ω}. Consider a shuffle DP algorithm R that achieves (εE , δE )DP and (εI , δI )-FODP, as shown in Figure 1. Then, we can define the robustness against collusion with users as follows: Definition 11 (Robustness against collusion with users). Let εE , εI ∈ R≥0 and δE , δI ∈ [0, 1]. Let R be a shuffle algorithm with domain [d]n that provides (εE , δE )-DP and (εI , δI )-FODP. For i ∈ [n], let ψi be data sent from user ui to the shuffler in R . For Ω ⊂ [n], let RΩ be an algorithm that takes a database x ∈ [d]n as input and outputs RΩ (x) = (R (x), (ψi )i∈Ω ). Then, R is robust against collusion with users if it satisfies the following two conditions for any Ω ⊂ [n] and any Ω-neighboring databases x, x′ ∈ [d]n : • For any O ⊆ Range(RΩ ), RΩ satisfies (1) with (ε, δ) = (εE , δE ). • For any (O, OM , OI ) ⊆ Range((RΩ , R M , R I )), (RΩ , R M , R I ) satisfies (3) with (ε, δ) = (εI , δI ). ψi in Definition 11 depends on the protocol, e.g., ψi = xi in our protocols. Definition 11 states that the values of (εE , δE ) and (εI , δI ) in R are not increased by collusion with users.
Input: Asymmetric geometric distribution AGeo(ν, ql , qr ). Output: Random sample zi from AGeo(ν, ql , qr ). 1 r ← ORAND_REAL(); q (1−qν )
1 ; η = l 1−ql l + 1−q r qr 3 B ← [r ≥ 1 − η(1−qr ) ];
2
zli ← ν − ⌈logql (η(1 − ql )r + qν+1 )⌉ + 1; l r 5 zi ← ⌊logq η(1 − qr )(1 − r)⌋ + ν; r l r 6 zi ← (1 − B)zi + Bzi ; 7 return zi Algorithm 3: DummyCountGeneration via arithmetic operations when D = AGeo(ν, ql , qr ). 4
B B.1
Details of Algorithms Fully Oblivious Sampling from a DummyCount Distribution
The function DummyCountGeneration can be implemented using the CDF F for a dummy-count distribution D as follows. First, we compare F(0), . . . , F(zmax − 1) to a random value r ∈ [0, 1), where zmax is the maximum value of zi , i.e., zmax = κ in FOLNF. Then, it outputs the first value whose CDF exceeds r as zi (zi = zmax if no CDF exceeds r). This algorithm is fully oblivious to zi , as memory and instruction traces are independent of zi . Its time complexity is O(zmax ). It is also possible to directly calculate zi from r by arithmetic operations. Algorithm 3 shows such an algorithm in the asymmetric geometric distribution AGeo(ν, ql , qr ). Note that when ν = ql = 0 (i.e., one-sided geometric distribution), zi can be easily calculated from r as: zi ← ⌊logqr (1 − r)⌋. Algorithm 3 is also fully oblivious, as it consists of arithmetic operations. The time complexity of this algorithm is O(1). We used Algorithm 3 in our experiments.
B.2
Input: Input values x = (x1 , . . . , xn ), #items d ∈ N. Output: Estimate f̂ = ( fˆi , . . . , fˆd ). /* Histogram calculation */ 1 h ≜ (h1 , . . . , hd ) ← (0, . . . , 0); 2 foreach i ∈ [n] do 3 foreach j ∈ [d] do 4 h j ← h j + [xi = j]; 5 end 6 end /* Adding the two-sided Geometric noise (s ∈ {−1, 1}, z ∼ 1Geo(2/ε)) */ 7 foreach i ∈ [d] do 8 r ← ORAND_REAL(); 9 z ← ⌊log2/ε (1 − r)⌋; 10 s ← 2 · ORAND_NATS(2) − 3; 11 fˆi ← 1n (hi + sz); 12 end 13 return f̂ = ( fˆi , . . . , fˆd ) Algorithm 4: Basic DP histogram.
each element in h is |h j | = log2 d. Thus, the runtime is upper bounded by O(nd log d)2 and is simplified as Õ(nd). Stability Histogram. The runtime Õ(nd) also applies to the stability histogram [20, 47], which adds DP noise to only items whose frequencies exceed a threshold in a sparse histogram. Specifically, the stability histogram has the same issue as Algorithm 4; i.e., it must access the entire memory to provide full obliviousness when adding each input value to the histogram h (lines 2-6 in Algorithm 4). In other words, it requires the runtime Õ(nd) to calculate a clean histogram before adding DP noise. We also confirmed that the runtime for the histogram calculation (lines 2-6) is dominant in Algorithm 4. Since the stability histogram needs h, it also requires Õ(nd) when running within the TEE; e.g., it requires about 270 days when n = d = 108 , as shown in Figure 12.
Central DP Algorithms within the TEE
Basic DP Histogram. Algorithm 4 shows a fully oblivious version of the basic DP histogram [12, 27], which calculates a histogram and adds DP noise to each histogram bin within the TEE. We first calculate a histogram h ≜ (h1 , . . . , hd ) ∈ (Z≥0 )d of input values x (lines 1-6). Then, we add the two-sided Geometric noise sz to each bin of h and divide the result by n, where s is a random value in {−1, 1} and z is a sample from the one-sided Geometric distribution 1Geo(2/ε) (lines 7-12). Algorithm 4 provides ε-DP [12]. It is also fully oblivious to a single secret, as memory and instruction traces are independent of x. Thus, by Theorem 1, it provides ε-FODP. Runtime. Algorithm 4 accesses the entire memory (i.e., each element in h) to provide full obliviousness when adding each input value to the histogram. In addition, the size of
C
Details of Theoretical Properties
C.1 Robustness of Our General Algorithm against Poisoning Attacks Following [21], we consider a targeted attack that attempts to increase the estimates of some target items T ⊆ [d]. Without loss of generality, assume that users u1 , . . . , un are genuine and that the attacker injects n′ ∈ N fake users un+1 , . . . , un+n′ . The fake users can send arbitrary messages to the shuffler. For example, when honest users apply a local randomizer RL and send the noisy values RL (x1 ), . . . , RL (xn ) to the shuffler, the 2 Note that when log d is smaller than the word length in the word RAM 2
model [32], the runtime is O(nd).
(a)
(b) Our bound WDX+20
(c) Our bound WDX+20
Our bound WDX+20
Theorem 12. Let εE , εI ∈ R≥0 and δE , δI ∈ [0, 1]. If RD ,D ′ ,β,λ (Algorithm 1) provides (εE , δE )-DP and (εI , δI )FODP, then RDLarge ,D ′ ,β,λ (Algorithm 2) provides ((τ − 2i)εE , 1 − (1 − δE )(1 − δi ))-DP and ((τ − 2i)εI , 1 − (1 − δI )(1 −δi ))-FODP for any i = {0, 1,. . . , ⌊ 2τ ⌋}, where δi = (τ− j)ε i−1 τ 1 − e(τ−2i+ j)ε ) , and is robust against (1+eε )τ ∑ j=0 j (e collusion with users.
Figure 13: Two bounds on ε for FOUD.
Accuracy. We denote our general algorithm RDLarge ,D ′ ,β,λ applied FOUD-L ∗ to FOUD, FOLNF, and FOLNF by Rλ , RDFOLNF-L , and ,β
fake users can change their noisy values to arbitrary values. This is called the output poisoning attack [54]. Let fˆi′ ∈ R be an estimate of fi after poisoning. Let ∆ fi = fˆi′ − fˆi be the frequency gain for the i-th item. Let y′ = (y′1 , . . . , y′n′ ) be messages sent from n′ fake users. Let G(y′ ) be the attacker’s overall gain defined as follows: G(y′ ) = ∑i∈T E[∆ fi ]. Cao et al. [21] propose an optimal attack called the MGA (Maximal Gain Attack) that maximizes G(y′ ). Let GMGA be the MGA’s overall gain, i.e., GMGA = maxy′ G(y′ ). Then, we can show the robustness of our general algorithm:
-L RDFOLNF ,D ′ ,β , respectively. Then, the following corollaries are
Theorem 10. Our general algorithm RD ,D ′ ,β,λ (Algorithm 1) provides the following robustness guarantee: ′
n GMGA = n+n ′ (1 − ∑i∈T f i ).
Privacy Parameters in FOUD
Below, we compare our bound on (ε, δ)-DP for FOUD (Theorem 3) with the bound directly derived from [76]: Theorem 11 ((ε, δ)-DP of FOUD derived from q [76]). For ε ≤ 1, RλFOUD provides (ε, δ)-DP, where ε =
derived from Theorem 8: Corollary 1. RλFOUD-L achieves 2 Pr[| fˆi − fi | ≤ γ] ≥ 1 − ( bγ + d1 )τ − τd2 ,
14 ln(2/δ)d . λ
Figure 13 shows ε in Theorem 3 (our bound) and Theorem 11 (denoted by WDX+20). Our bound provides a tighter bound on ε than WDX+20 for various values of λ, d, and δ.
nγ
1
(11)
1
for each i ∈ [d], where d1 = e−λ·D( b + 2λ ∥ b ) if γ < 2λ(b−1) and nb 1 −λ·D( 1b − nγ ∥ λ ) λ b if γ < d = 0 otherwise, d = e and d = 0 1
2
2
nb
otherwise, and D(x ∥ y) = x ln xy + (1 − x) ln 1−x 1−y . ∗
-L Corollary 2. RDFOLNF-L and RDFOLNF with D = AGeo(ν, ql , ,β ,D ′ ,β qr ) in Definition 9 and β = 1 achieve
(10)
GMGA in (10) is exactly the same as the overall gain of the input poisoning attack [21], in which fake users change their input values and then follow the protocol (e.g., apply RL ). This is quite obvious because users do not add noise in our algorithm; i.e., output values are identical to input values. It is shown that pure shuffle protocols are vulnerable to the output poisoning attack, especially when ε is small [21, 60]. Our algorithm prevents the output poisoning attack, as the attacker can perform only the input poisoning attack.
C.2
∗
2 + d3 )τ − τd4 , Pr[| fˆi − fi | ≤ γ] ≥ 1 − ( bγ
(12)
1 1 · qar r −ν , d4 = η(1−q for each i ∈ [d], where d3 = η(1−q ) · (1 − r) l
a +1
)ql l if γ < nµ and d4 = 0 otherwise, η = nγ 1 1−qr , ar = ⌈µ + 2 ⌉, and al = ⌊µ − nγ⌋.
ql l
ν−a
ql (1−qνl ) 1−ql +
Corollary 2 assumes β = 1. When β < 1, the factors of random sampling (i.e., Bin(n fi , β) and n fi β in Theorem 8) are independent of τ. Thus, in our experiments, we used the same optimization method for β < 1 (1Geo) as for β = 1. We show that it works well in Appendix D.3. Comparison with the Bounds in [24, 33]. Ghazi et al. [33] analyze the additive error of a pure shuffle protocol, where each user adds a dummy value with probability ϕ ∈ [0, 1] for each entry of the count-min sketch (i.e., each of τb hash values) and sends the dummy values along with her hash values. Shuffled values of this protocol are the same as those of RDFOLNF-L with D = Bin(n, ϕ) and β = 1. Therefore, we ,β show our bound in this case and compare it with the bound in [33] (we discuss the bound in [24] at the end of this section): Corollary 3. RDFOLNF-L with D = Bin(n, ϕ) and β = 1 ,β achieves
C.3 Privacy, Robustness, and Accuracy of Our Algorithms for Large-Domain Data
2 Pr[| fˆi − fi | ≤ γ] ≥ 1 − ( bγ + d5 )τ − τd6 ,
Privacy and Robustness. We use the optimal composition theorem in [42] to show that our general algorithm RDLarge ,D ′ ,β,λ for large-domain data provides the following guarantees:
γ for each i ∈ [d], where d5 = e−n·D(ϕ+ 2 ∥ϕ) if γ < 2(1 − ϕ) and d5 = 0 otherwise, d6 = e−n·D(ϕ−γ∥ϕ) if γ < ϕ and d6 = 0 otherwise, and D(x ∥ y) = x ln xy + (1 − x) ln 1−x 1−y .
(13)
Runtime (s)
FOLNF* (AGeo)
FOLNF* (1Geo)
FOLNF (1Geo)
(a) Foursquare
(b) AOL FOUD-L FOLNF-L (AGeo) FOLNF*-L (AGeo) FOLNF-L (1Geo) FOLNF*-L (1Geo) FME LYW22-L
(bits)
Runtime (s)
FOLNF (AGeo)
(a) ORShuffle,
(b) ORShuffle,
Figure 15: Total communication cost Ctot (εE = 0.1, εI = 1). (c) WaksShuffle,
(d) WaksShuffle,
AGeo, respectively, and the count-min sketch significantly re-
Figure 14: Total runtime of our algorithms with the codes of ORShuffle and WaksShuffle in [1] (εE = 0.1). In (b) and (d), we used the count-min sketch (b = n) when n < d. Theorem 13 (Additive error derived from [33]). RDFOLNF-L ,β with D = Bin(λ, 1b ) and β = 1 achieves 2
Pr[| fˆi − fi | ≤ γ] ≥ 1 − ( bn )τ − 2log2 (2bτ)−γ n/(3ϕ) .
(14)
The privacy parameters in DP can also be derived from [33]. Specifically, it follows from Lemma 4.10 in [33] that RDFOLNF-L with D = Bin(n, ϕ) and β = 1 provides (εE , δE )-DP ,β q E) for a single hash function (τ = 1), where εE = 90 ln(2/δ . ϕn By Theorem 4, RDFOLNF-L also provides (εI , δI )-FODP, where ,β (εI , δI ) = (εE , δE ). Based on these results, we set (n, ϕ) = (104 , 0.26) in Figure 5 so that (εI , δI ) = (εE , δE ) = (1, 10−12 ). The first and second terms (= 1 − ( bn )τ ) in the right side of (14) represent the probability that no hash collision occurs among n input values. Note that these terms are zero or less when b ≤ n. In other words, the bound in [33] cannot lower bound Pr[| fˆi − fi | ≤ γ] in this case, as shown in Figure 5. Finally, we note that the bound in [24] is also based on the probability that no hash collision occurs and therefore cannot lower bound Pr[| fˆi − fi | ≤ γ]. Specifically, Pr[| fˆi − fi | ≤ γ] in their bound is less than or equal to 1 − d( nb )τ . Since d ≥ 2, Pr[| fˆi − fi | ≤ γ] becomes negative when b ≤ n.
D
Additional Experiments
D.1 Runtime of Our Algorithms with the Codes in [1] Figure 14 shows the total runtime of our algorithms when we used the codes of ORShuffle and WaksShuffle in [1]. In Figure 14(b) and (d), we did not show the runtime of FOUD, because the number of shuffled values exceeded ten million and caused a stack overflow in their codes. Figure 14 shows a similar tendency to Figure 11. For example, FOLNF∗ and 1Geo are more efficient than FOLNF and
duces the runtime for large-domain data. Figure 14 also shows that ORShuffle is more efficient than WaksShuffle, which is consistent with their upper bounds on the runtime [68, 69]. Note that the online runtime (i.e., the runtime after obtaining n input values) of WaksShuffle is smaller than that of ORShuffle [69]. However, we evaluate the total runtime, in which case ORShuffle is more efficient. Figures 11 and 14 also show that the ORShuffle code in [1] requires more time than our ORShuffle code. One possible reason for this is that ORShuffle in [1] stores a lot of data within the enclave and causes EPC (Enclave Page Cache) miss.
D.2
Communication Efficiency
We also compared our algorithms with FME in terms of communication costs. Note that FME uses multiple encryption using a public key encryption scheme. To conduct a fair comparison with FME, we followed [61] and used the ECIES to encrypt a message. Then, we evaluated the expected total number Ctot ∈ R≥0 of bits sent from one party (i.e., a user, shuffler, or data collector) to another. Figure 15 shows Ctot of each algorithm in Foursquare and AOL when εE = 0.1 and εI = 1. We observe that FME is the least efficient. This stems from the fact that FME uses multiple encryption and introduces two rounds of communication between the shuffler and the data collector. Our algorithms significantly reduce Ctot of FME; e.g., FOLNF-L and FOLNF∗ L reduce Ctot of FME by two to four orders of magnitude. We also confirmed that our algorithms are much more efficient than FME in other values of εE and εI .
D.3
Changing τ and b
Figures 16 and 17 show the MSE when varying τ in 1Geo and varying b in Foursquare. These figures show similar tendencies to Figures 8 and 9; e.g., our optimization method works well, and the accuracy is close between b = n and b = 10n.
Foursquare
10−4
10−5
Pr[R (x′ ) ∈ O] ̸= 0, we have
Optimized
AOL
Pr[(R (x), R M (x), R I (x)) ∈ (O, OM , OI )] = Pr[R (x) ∈ O]
MSE
MSE
10−5
10−6
10−6
10−7
· Pr[(R M (x), R I (x)) ∈ (OM , OI )|R (x) ∈ O]
10−7
1
0.1
10
1
0.1
10
= Pr[R (x) ∈ O] Pr[S (x−i , |xi |) ∈ (OM , OI )|R (x) ∈ O] (by (15) with Λ = {i})
b=10n ). Figure 16: MSE for various values ofb=0.1n τ (b =b=nn, 1Geo
b=0.1n
0.110
−5
MSEMSE
MSE
10−5 10−7 0.1
1
10
MSE
10−7−5 10−6 10 10−8 10−7
10−4 10−6
b=n
b=10n
1
−5 10−6 10−5 10
−4
10 FOLNF/FOLNF* (AGeo) 10−5
10−6−4 −5 10 10
10−5
MSE
b=0.1n
b=10n
MSE
10−4
b=n
FOUD
b=0.1n
b=10n
10−9 10−8 0.1
b=n
b=0.1n
(as x−i = x′−i )
b=10n
b=n
b=10n
FOLNF/FOLNF* (1Geo)
0.1
10
· Pr[(R M (x′ ), R I (x′ )) ∈ (OM , OI )|R (x′ ) ∈ O] + δ (by (1) and (15) with Λ = {i})
10−7 10−5 10−6 10−8
= eε Pr[(R (x′ ), R M (x′ ), R I (x′ )) ∈ (O, OM , OI )] + δ.
10−6 10−7
1
≤ eε Pr[R (x′ ) ∈ O]
10
MSE MSE MSE
b=0.1n
b=n
= Pr[R (x) ∈ O] Pr[S (x′−i , |xi |) ∈ (OM , OI )|R (x′ ) ∈ O]
1 b=n
b=0.1n
10
b=10n
Figure 17: MSE vs. hash range b (τ: optimized, Foursquare).
Thus, (3) always holds for any two neighboring databases x and x′ and any (O, OM , OI ) ⊆ Range((R , R M , R I )), which means that R provides (ε, δ)-FODP.
10−4
E
Proofs of Statements
E.1
Proof of Theorem 1
MSE
10−5
Consider two neighboring databases x and x′ such that xi ̸= xi′ and x j = x′j for any j ∈ [n] \ {i}. Let x−i = (x1 , . . . , xi−1 , xi+1 , . . . , xn ). Then, x−i = x′−i . The equation (2) states that the distribution of (R M (x), I R (x)) conditioned on R (x) = o can be simulated using the simulator S , i.e., for any (o, (oM , oI )) ∈ Range(R × (R M , R I )), Pr[(R M (x), R I (x)) = (oM , oI )|R (x) = o] = Pr[S ((xi )i∈[n]\Λ , (|xi |)i∈Λ ) = (oM , oI )|R (x) = o]. This implies the following equation for any (O, OM , OI ) ⊆ Range((R , R M , R I )): Pr[(R M (x), R I (x)) ∈ (OM , OI )|R (x) ∈ O] = Pr[S ((xi )i∈[n]\Λ , (|xi |)i∈Λ ) ∈ (OM , OI )|R (x) ∈ O]. (15)
Assume that R provides (ε, δ)-DP and is fully oblivious to a single secret. If Pr[R (x) ∈ O] = 0, (3) clearly holds. If Pr[R (x′ ) ∈ O] = 0, (3) holds (as the left-hand side of (3) ≤ Pr[R (x) ∈ O] ≤ δ by (1)). If Pr[R (x) ∈ O] ̸= 0 and
E.2
Proof of Lemma 1
Random sampling (lines 1-6) and adding uniform dummies (lines 7-10) in RD ,D ′ ,β,λ are fully oblivious to x and r (i.e., memory and instruction traces do not depend on x and r), as ORAND_REAL, OSWAP, and ORAND_NATS are fully oblivious (as described in Section 3.5) and the numbers n and λ of iterations do not depend on x and r. DummyCountGeneration (line 12) can be implemented via a CDF for D or arithmetic operations and is fully oblivious to zi (see Appendix B.1 for details). BotCountGeneration (line 13) consists of sampling a random value from D ′ and arithmetic operations; e.g., the output is κi = κ (resp. κi = zi +ωi , ωi ∼ D ′ ) in FOLNF (resp. FOLNF∗ ). As with sampling from D , sampling from D ′ can be implemented via a CDF or arithmetic operations. Thus, BotCountGeneration is also fully oblivious to zi . The output κi is also encrypted. It should be noted, however, that RD ,D ′ ,β,λ allocates memory of size κi for (a1 , . . . , aκi ) = (⊥, . . . , ⊥) (line 14). Thus, κi is leaked from the size of the allocated memory. The subsequent OSWAP (line 15-17) is fully oblivious to the dummy value i and zi . However, κi is leaked from the instruction trace, as the process is repeated κi times in this “foreach” loop. OSHUFFLE (line 20) is fully oblivious to the shuffled values, as described in Section 3.5. In summary, memory and instruction traces of RD ,D ′ ,β,λ depend on x only through (κ1 , . . . , κd ), which means that there exists a randomized post-processing algorithm φ such that (5) holds for any x ∈ [d]n .
E.3
Proof of Lemma 2
Intuitively, Lemma 2 can be explained from the following two facts: (i) users do not add noise to their input values in
RD ,D ′ ,β,λ , (ii) DP and FODP guarantee privacy even if the adversary obtains the input values of others. Formally, we can prove Lemma 2 as follows. Let x = (x1 , . . . , xn ) and x′ = (x1′ , . . . , xn′ ) be neighboring databases such that xi ̸= xi′ and x j = x′j for j ∈ [n] \ {i}. Let Ω ⊆ [n] \ {i}, and RΩ (x) = (R (x), (xk )k∈Ω ). Then, it suffices to show the following inequalities for any O ⊆ Range(RΩ ) and any (O, OM , OI ) ⊆ Range((RΩ , R M , R I )): ′
Pr[RΩ (x) ∈ O] ≤ e Pr[RΩ (x ) ∈ O] + δE εE
Pr[(RΩ
(x), R M (x), R I (x)) ∈ (O, O
≤ e Pr[(RΩ εI
hk = h′k + 1, and h′l = hl + 1. Let c = (c1 , . . . , cd ). Let R̄λFOUD be a randomized algorithm with domain [d]n that outputs the histogram of the shuffled values output by RλFOUD . Then,
(16)
M , OI )] + δI .
(17) Since x and x′ are fixed, the randomness in RΩ arises solely from R . Thus, if (1) and (3) hold, then (16) and (17) also hold with the same privacy parameters (εE , δE ) and (εI , δI ).
λ! 1 ∏di=1 (ci −hi )! d λ
Pr[R̄λFOUD (x′ ) = c] =
λ! 1 , ∏di=1 (ci −h′i )! d λ
and therefore, Pr[R̄λFOUD (x)=c] c −h′ k +1 = ckl −hlk = ckc−h . Pr[R̄λFOUD (x′ )=c] l −hl
M , OI )]
(x ), R M (x′ ), R I (x′ )) ∈ (O, O ′
Pr[R̄λFOUD (x) = c] =
Assume that c is generated from R̄λFOUD (x). Then, both ck −hk and cl − hl follow the binomial distribution Bin(λ, d1 ). Thus, we consider random variables X1 and X2 such that X1 , X2 ∼ Bin(λ, d1 ). By the multiplicative Chernoff bound [57], it holds that for θ1 ∈ R≥0 and θ2 ∈ [0, 1), θ2 λ
E.4
2
θ2 λ − 1 Pr[X1 ≥ (1+θd 1 )λ ] ≤ e (2+θ1 )d , Pr[X2 ≤ (1−θd 2 )λ ] ≤ e− 2d .
Proof of Theorem 2
In addition, when X1 < (1+θd 1 )λ and X2 > (1−θd 2 )λ , we have
For any i ∈ [d], the expectation of fˆi can be written as 1 1 E[ fˆi ] = βn (E[ci ] − dλ − µ) = βn (βn fi + dλ + µ − dλ − µ) = fi .
d+(1+θ1 )λ X1 +1 ε X2 < (1−θ2 )λ = e .
Thus, the estimate f̂ is unbiased, in which case the expected l2 loss E[∑di=1 ( fˆi − fi )2 ] is equal to the variance ∑di=1 V[ fˆi ] [62]. For i ∈ [d], let yi ∈ Z≥0 be the number of uniform dummies added to item i. Note that ∑di=1 yi = λ. Then, by the law of total variance, and noting that yi and zi are independent,
Thus, by taking the union bound, h i ε ≤ Pr[X ≥ (1+θ1 )λ ] + Pr[X ≤ (1−θ2 )λ ] ≤ δ. Pr X1X+1 ≥ e 2 1 d d 2 Therefore, we have
V[ci ] = E[V[ci |yi , zi ]] + V[E[ci |yi , zi ]]
Prc∼R̄ FOUD (x) λ
= E[n fi β(1 − β)] + V[βn fi + yi + zi ] = n fi β(1 − β) + V[yi ] + V[zi ]
Thus, the expected l2 loss can be written as follows: E[∑di=1 ( fˆi − fi )2 ] d
∑ V[ci ] λ(d−1) σ2 d = ∑di=1 V[ fˆi ] = i=1 = 1−β βn + β2 n2 d + β2 n2 . β2 n2
≤ δ,
(18)
Robustness. The robustness of RλFOUD against collusion with users is immediately derived from Lemma 2.
E.6 Proof of Theorem 3 FOUD
which implies (ε, δ)-DP [14, 33]. FODP. RλFOUD sets κi = 0 for each item i ∈ [d]. Thus, the bot counts (κ1 , . . . , κd ) = (0, . . . , 0) do not depend on x. Then, by Lemma 1, memory and instruction traces do not depend on x, which means that RλFOUD is fully oblivious to a single secret. By Theorem 1, RλFOUD also provides (ε, δ)-FODP.
= n fi β(1 − β) + λ d1 (1 − d1 ) + σ2 .
E.5
Pr[R̄λFOUD (x)=c] ≥ eε Pr[R̄λFOUD (x′ )=c]
FOUD
DP. We prove DP of Rλ based on the insight that Rλ with n = 1 is equivalent to the balls-into-bins mechanism in [56] (with parameter s = 1 and p = 0 in their notations). Specifically, let x = (x1 , . . . , xn ) and x′ = (x1′ , . . . , xn′ ) be neighboring databases such that xi = k, xi′ = l, k ̸= l, and x j = x′j for j ∈ [n] \ {i}. For i ∈ [d], let hi (resp. h′i ) ∈ Z≥0 be the absolute frequency of item i in x (resp. x′ ). Let ci ∈ Z≥0 be the absolute frequency of item i in the shuffled values output by RλFOUD . Note that ∑di=1 hi = ∑di=1 h′i = n, ∑di=1 ci = n + λ,
Proof of Theorem 4
DP. After discarding ⊥, the output of RDFOLNF is the same as ,β FOLNF that of the LNF protocol [60], except that RD ,β truncates D at κ; i.e., the number zi of dummies is zi = κ if F(κ) ≤ r, where r ∈ [0, 1) is a random value. Let D ∗ be the dummycount distribution over {0, 1, . . . , κ} obtained by truncating D at κ. The probability of κ in D ∗ is 1 − F(κ − 1) = δ20 . Therefore, if the binary input mechanism MD ,β provides ( 2ε , 2δ )-DP, then MD ∗ ,β obtained by replacing D in MD ,β with D ∗ pro0 vides ( 2ε , δ+δ 2 )-DP (as the probability that DP is violated can
be transformed into δ in DP [45]). The LNF protocol provides (ε, δ)-DP if the corresponding binary input mechanism with the same dummy-count distribution provides ( 2ε , 2δ )-DP 0 (Theorem 2 in [60]). Thus, if MD ∗ ,β provides ( 2ε , δ+δ 2 )-DP, FOLNF then RD ,β provides (ε, δ + δ0 )-DP (as the dummy-count distribution is the same between the two).
holds, where Φ j = (αi xi [ j] + z j , z j + ω j ), Φ′j = (αi x′i [ j] + z j , z j + ω j ), and xi [ j] (resp. x′i [ j]) is the j-th element of xi (resp. x′i ). Recall that α, αi ∼ Ber(β), z, z j ∼ D , and ω, ω j ∼ D ′ . Therefore, Φ is a binary input version of (Φ1 , . . . , Φd ). Based on this, we show that (20) holds if MD∗ ,D ′ ,β pro∗
∗
FODP. In RDFOLNF , the bot counts (κ1 , . . . , κd ) = (κ, . . . , κ) ,β do not depend on x. Thus, RDFOLNF is fully oblivious to a ,β single secret (by Lemma 1) and provides (ε, δ + δ0 )-FODP (by Theorem 1).
vides ( ε2 , δ2 )-DP. If j ∈ / {xi , xi′ }, then Φ j follows the same ′ distribution as Φ j . If j = xi , then Φ j (resp. Φ′j ) follows the same distribution as MD∗ ,D ′ ,β (1) (resp. MD∗ ,D ′ ,β (0)). If j = xi′ , then Φ j (resp. Φ′j ) follows the same distribution as MD∗ ,D ′ ,β (0) (resp. MD∗ ,D ′ ,β (1)). Thus, by group privacy [28],
Robustness. The robustness is derived from Lemma 2.
if MD∗ ,D ′ ,β provides ( ε2 , δ2 )-DP, then (20) holds for any set
E.7
OΦ ⊆ (Z≥0 × Z≥0 )d , which means that RDFOLNF ,D ′ ,β provides (ε∗ , δ∗ )-FODP.
Proof of Theorem 5 ∗
DP. By Theorem 2 in [60], RDFOLNF ,D ′ ,β provides (ε, δ)-DP if
MD ,β provides ( 2ε , 2δ )-DP. ∗
FODP. Below, we show FODP of RDFOLNF ,D ′ ,β by directly showing the inequality (3). We denote the bot-count algo∗ FOLNF∗ ⊥ rithm of RDFOLNF ,D ′ ,β by RD ,D ′ ,β . Let x = (x1 , . . . , xn ) and x′ = (x1′ , . . . , xn′ ) be neighboring databases such that xi ̸= xi′ and x j = x′j for j ∈ [n] \ {i}. By Lemma 1, showing (3) with (ε, δ) = (ε∗ , δ∗ ) is reduced to showing the following inequal∗ FOLNF∗ ⊥ ity for any (O, O⊥ ) ⊆ Range((RDFOLNF ,D ′ ,β , RD ,D ′ ,β )): ∗
∗
FOLNF ⊥ Pr[(RDFOLNF ,D ′ ,β (x), RD ,D ′ ,β (x)) ∈ (O, O⊥ )] ∗
∗
∗
′ FOLNF ⊥ ′ ∗ ≤ eε Pr[(RDFOLNF ,D ′ ,β (x ), RD ,D ′ ,β (x )) ∈ (O, O⊥ )] + δ . (19)
Meanwhile, outputting MD∗ ,D ′ ,β (x) = (MD ,β (x), MD−′ ,β (x)) is equivalent to outputting (MD ,β (x), MD ′ ,β (x) + MD−′ ,β (x)) = (αx + z, z + ω) ≜ Φ. Notice that Φ is a binary input version of the output ∗ FOLNF∗ ⊥ of (RDFOLNF ,D ′ ,β , RD ,D ′ ,β ). This can be explained as follows. Given the database x, let (c1 , . . . , cd ) ∈ (Z≥0 )d be a histogram ∗ FOLNF∗ of shuffled values output by RDFOLNF ,D ′ ,β . The output of RD ,D ′ ,β leaks no information other than (c1 , . . . , cd ), as it is randomly shuffled. Let xi (resp. x′i ) ∈ {0, 1}d be a vector whose xi -th (resp. xi′ -th) element is 1 and other elements are 0. Then, (c1 , . . . , cd ) = (∑nj=1 α j x j ) + z, where α j ∼ Ber(β) and z = (z1 , . . . , zd ). Since x j = x′j for j ∈ [n] \ {i}, ∑ j̸=i α j x j follows the same distribution as ∑ j̸=i α j x′j . ∗⊥ In addition, the output of RDFOLNF is (z1 + ω1 , . . . , zd + ωd ). ,D ′ ,β Thus, showing (19) is reduced to showing that for any set OΦ ⊆ (Z≥0 × Z≥0 )d , ∗
Pr[(Φ1 , . . . , Φd ) ∈ OΦ ] ≤ eε Pr[(Φ′1 , . . . , Φ′d ) ∈ OΦ ] + δ∗ (20)
∗
∗
∗
Robustness. Immediately derived from Lemma 2.
E.8
Proof of Theorem 6
Let x = 0 and x′ = 1. Then, by (7) with α ∼ Ber(β), z ∼ AGeo(ν, ql , qr ), and ω ∼ AGeo(ν′ , q′l , q′r ), we have ( 1 ν−k q (if k = 0, 1, . . . , ν) A Pr[MD ,β (x) = k] = η1 lk−ν (if k = ν, ν + 1, . . .) η qr Pr[MDA,β (x′ ) = k] 1−β ν η ql ν−k = 1−β + ηβ qν−k+1 l η ql 1−β k−ν β k−ν−1 + q q η r η r (
(if k = 0) (if k = 1, . . . , ν) (if k = ν + 1, ν + 2, . . .)
1 ′ ν′ −k′ η′ q l 1 ′ k′ −ν′ η′ q r
′ Pr[MDA− ′ ,β (x) = k ] =
′ ′ Pr[MDA− ′ ,β (x ) = k ] β ν′ η′ q′ l ′ ′ ′ ′ ′ ν −k + β q′ ν −k −1 = 1−β η′ q l η′ l ′ ′ ′ 1−β q′ k −ν + β q′ k −ν′ +1 η′
r
η′
r
(if k′ = 0, 1, . . . , ν′ ) (if k′ = ν′ , ν′ + 1, . . .)
(if k′ = −1) (if k′ = 0, . . . , ν′ − 1) (if k′ = ν′ , ν′ + 1, . . .).
′ Let P1 = Pr[(MDA,β (x), MDA− ′ ,β (x)) = (k, k )] and P2 = ′ ′ Pr[(MDA,β (x′ ), MDA− ′ ,β (x )) = (k, k )]. Below, we calculate P1 and P2 in three cases: (i) when k ≥ 1 and k′ ≥ 0, (ii) when k = 0 and k′ ≥ 0, and (iii) when k′ = −1.
Case 1: k ≥ 1 and k′ ≥ 0. Noting that MDA,β and MDA− ,β share α generated from Ber(β) in (7), we have 1 ν−k ′ ν′ −k′ ql ηη′ ql 1 qν−k q′ k′ −ν′ ′ l r P1 = ηη 1 k−ν ′ ν′ −k′ q q ηη′ r l 1 k−ν ′ k′ −ν′ q q r ηη′ r
(if 1 ≤ k ≤ ν and 1 ≤ k′ < ν′ ) (if 1 ≤ k ≤ ν and k′ ≥ ν′ ) (if k > ν and 1 ≤ k′ < ν′ ) (if k > ν and k′ ≥ ν′ )
P2 =
′ ′ ν−k ′ ν′ −k′ 1 + βqν−k+1 ql q′ νl −k −1 } l ηη′ {(1 − β)ql (if 1 ≤ k ≤ ν and 1 ≤ k′ < ν′ ) ′ ′ ′ ν−k ′ k −ν′ 1 qr + βqν−k+1 q′ rk −ν +1 } l ηη′ {(1 − β)ql (if 1 ≤ k ≤ ν and k′ ≥ ν′ ) ′ ′ ′ ′ 1 k−ν q′ ν −k + βqk−ν−1 q′ ν −k −1 } ′ {(1 − β)qr r l l ηη (if k > ν and 1 ≤ k′ < ν′ )
′
′
′
∗
′
′
∗
′
′
∗
∗
ε δ Therefore, MDA∗,D ′ ,β = (MDA,β , MDA− ′ ,β ) provides ( 2 , 2 )-DP,
(if k > ν and k′ ≥ ν′ ).
r
′
where δ∗ = max{δ, η2′ βq′ νl }. In addition, MDA,β provides ( 2ε , 2δ )-DP, as explained in Section 5.4.
ql qr = L(ε)R(ε).
E.9
∗
Since
ε∗ ≥ ε, we
have
−ε/2 −1+β −ε /2 −1+β L(ε)R(ε) = eeε/2 −1+β = L(ε∗ )R(ε∗ ). Thus, ql qr ≥ eeε∗ /2 −1+β ∈ [L(ε∗ )R(ε∗ ), 1], which means that ql q1′ ∈ [L(ε∗ ), R(ε1∗ ) ] and l 1 1 1 ′ ∗ qr q r ∈ [L(ε ), R(ε∗ ) ]. Therefore, we have (1 − β) + βql q′ l ∈ ∗ ∗ ∗ ∗ [e−ε /2 , eε /2 ] and (1 − β) + β q1r q′ r ∈ [e−ε /2 , eε /2 ]. In addi∗ ∗ tion, (1 − β) + βql q′ r = e−ε /2 and (1 − β) + β q1r q1′ = eε /2 . l ∗ ∗ Thus, by (21), we have PP21 ∈ [e−ε /2 , eε /2 ]. Case 2: k = 0 and k′ ≥ 0. In this case, P1 and P2 are written as ′ ′ 1 ν ′ ν′ −k′ ν ′ ν −k , respectively, where P1 = ηη and P2 = 1−β ′ ql r ηη′ ql r
=
′
≤ ∑k≥0 δ2,k = η1′ βq′ νl . δK,K 2
(if 1 ≤ k ≤ ν and k′ ≥ ν′ ) (if k > ν and 1 ≤ k′ < ν′ )
l
r
∗
′
ql q1′ = ql qr R(ε1∗ ) , q1r q′ r = ql1qr L(ε∗ ),
′
Let
δK,K ≤ ∑k′ ≥0 δ1,k′ = η1 qνl (1 − eε /2 (1 − β)) ≤ 2δ 1
(if 1 ≤ k ≤ ν and 1 ≤ k′ < ν′ )
By Definition 9,
′
′
′ ′ and P2K,K = Pr[(MDA,β (x′ ), MDA− ′ ,β (x )) ∈ (K, K )].
P1K,K ≤ eε /2 P2K,K + δK,K , P2K,K ≤ eε /2 P1K,K + δK,K . 1 2
(21)
′ ν −k
′
K,K ′ (MDA− = Pr[(MDA,β (x), MDA− ′ ,β (x)) ∈ (K, K )] ,β ), let P1
Then, by (22), (23), and ε ≤ ε∗ ,
Therefore, (1 − β) + βql q1′ l P2 (1 − β) + βql q′ r = (1 − β) + β q1 q1′ P1 r l (1 − β) + β 1 q′
and
Putting Together. For K ⊆ Range(MDA,β ) and K ′ ⊆ Range
′ ′ δK,K , δK,K ∈ [0, 1] be the minimum values satisfying 1 2
′ ′ ′ ′ 1 k−ν q′ k −ν + βqk−ν−1 q′ ν −k +1 } ′ {(1 − β)qr r r r ηη (if k > ν and k′ ≥ ν′ ).
qr
′
1 ν−k q′ ν . where δ2,k = ηη ′ βr l
( ′ ′ q′ νl −k
(if k′ = 0, 1, . . . , ν′ − 1)
q′ r
(if k′ = ν′ , ν′ + 1, . . .).
k′ −ν′
P1 ≤ e
ε∗ /2 ′
′
P2 + δ1,k′ , P2 ≤ P1 ,
(22)
∗
1 ν ′ ν −k (1 − eε /2 (1 − β)). where δ1,k′ = ηη ′ ql r
Case 3: k′ = −1. In this case, α = 1. Thus, P1 = 0 and β ν−k ′ ν′ P2 = ηη q l , where ′r 0 rν−k = qν−k+1 l k−ν−1 qr
Since the size of each input value xi (i ∈ [n]) is O(log d), the runtime of ORAND_REAL and OSWAP can be expressed as O(1) and O(log d), respectively. The runtime of ORAND_NATS(d) is O(log d), as it generates a ⌈log2 d⌉-bit binary integer. The runtime of DummyCountGeneration (line 12 in Algorithm 1) is O(1) when it is implemented via arithmetic operations (see Appendix B.1). Similarly, the runtime of BotCountGeneration (line 13) is O(1). Therefore, the runtime of random sampling (lines 1-6) and dummy data addition (lines 7-19) in RD ,D ′ ,β,λ can be expressed as O(n log d) and O((λ + ∑di=1 κi ) log d), respectively. Then, the runtime of RD ,D ′ ,β,λ is O(n̄ log d + ρ), where n̄ = n + λ + ∑di=1 κi , and ρ is the runtime of OSHUFFLE.
E.10
Thus, we have
(if k = 0) (if k = 1, . . . , ν) (if k = ν + 1, ν + 2, . . .).
Proof of Theorem 7
Proof of Theorem 8
′ ) be a random variable that represents the Let Xt,i (resp. Xt,i number of users who have (resp. do not have) item i and ′ is the increase in increase the count ct,ht (i) . Note that Xt,i ct,ht (i) due to hash collisions. Each input value is sampled with probability β, and the hash collision occurs with probability β 1 ′ b . Thus, Xt,i ∼ Bin(n f i , β) and Xt,i ∼ Bin(n(1 − f i ), b ). For t ∈ [τ] and j ∈ [b], let λt, j (resp. zt, j ) ∈ Z≥0 be the number of uniform dummies (resp. dummies based on D ) for the j-th hash value in the t-th hash function. Then, ′ +λ ct,ht (i) = Xt,i + Xt,i t,ht (i) + zt,ht (i) .
(24)
For γ > 0,
Thus, we have ∗
P1 ≤ P2 , P2 ≤ eε /2 P1 + δ2,k ,
(23)
Pr[| fˆi − fi | > γ] = Pr[ fˆi > fi + γ] + Pr[ fˆi < fi − γ].
(25)
By (8), (24), λt,ht (i) ∼ Bin(λ, 1b ), and zt,ht (i) ∼ D , we have Pr[ fˆi > fi + γ] = Pr[∀t ∈ [τ] : ct,ht (i) − λb − µ > nβ( fi + γ)] ′ +ξ > ξ τ = (Pr[Xt,i avg + nβγ]) ,
(26)
E.14
RλFOUD-L sets β = 1 and zi = κi = 0 for i ∈ [d]. Thus, ξ ∼
n fi + Bin(λ, 1b ) and ξavg = n fi + λb . Let ξ0 ∼ Bin(λ, 1b ). Then, by the additive Chernoff bound [8], ξ0 nγ 1 Pr[ξ > ξavg + nγ 2 ] = Pr[ λ > b + 2λ ] ≤ d1
where ξ ∼ Bin(n fi , β) + Bin(λ, 1b ) + D and ξavg = n fi β + λb + nβγ ′ + ξ exceeds ξ ′ µ. Note that Xt,i avg + nβγ only if Xt,i > 2 or ξ > ξavg + nβγ 2 . Thus, by the union bound, ′ Pr[Xt,i + ξ > ξavg + nβγ] nβγ ′ > nβγ ] + Pr[ξ > ξ ≤ Pr[Xt,i avg + 2 ]. 2
Pr[ξ < ξavg − nγ] = Pr[ ξλ0 < 1b − nγ λ ] ≤ d2 . (11) is derived from these inequalities and (9).
(27)
Intuitively, (26) and (27) decompose Pr[ fˆi > fi + γ] in (25) into two factors: hash collision (the first term in (27)) and DP noise (the second term in (27)). We bound the first term in (27) using Markov’s inequality [57]: ′ > nβγ ] ≤ E[X ′ ]/( nβγ ) (by Markov’s inequality) Pr[Xt,i t,i 2 2 2 = ( n(1−b fi )β )/( nβγ 2 ) ≤ bγ .
Proof of Corollary 1
(28)
E.15
Proof of Corollary 2
In this case, β = 1, λ = 0, and D = AGeo(ν, ql , qr ). Thus, ξ ∼ n fi + AGeo(ν, ql , qr ) and ξavg = n fi + µ. Let ξ0 ∼ AGeo(ν, ql , qr ). Then, we can calculate the exact values of Pr[ξ > ξavg + nγ 2 ] and Pr[ξ < ξavg − nγ]: nγ 1 ∞ k−ν = d Pr[ξ > ξavg + nγ 3 2 ] = Pr[ξ0 > µ + 2 ] = η ∑k=ar qr a
l Pr[ξ < ξavg − nγ] = Pr[ξ0 < µ − nγ] = η1 ∑k=0 qν−k = d4 , l
from which (12) is derived.
Pr[ fˆi < fi −γ] in (25) is caused by DP noise and can be written as follows:
E.16
Pr[ fˆi < fi − γ] = Pr[∃t ∈ [τ] : ct,ht (i) − λb − µ < nβ( fi − γ)]
In this case, ξ ∼ n fi + Bin(n, ϕ) and ξavg = n fi + nϕ. Let ξ0 ∼ Bin(n, ϕ). By the Chernoff bound,
≤ τ · Pr[ξ < ξavg − nβγ] ′ (by the union bound and Xt,i ≥ 0).
Proof of Corollary 3
ξ0 γ Pr[ξ > ξavg + nγ 2 ] = Pr[ n > ϕ + 2 ] ≤ d5
(29)
Pr[ξ < ξavg − nγ] = Pr[ ξn0 < ϕ − γ] ≤ d6 .
By (25), (26), (27), (28), and (29), we have (9).
(13) follows from these inequalities and (9).
E.11
Proof of Theorem 10
Since the proof of Theorem 10 is exactly the same as the proof of Theorem 3 in [60], we omit the proof; see [60].
E.12
Proof of Theorem 11
RλFOUD outputs the same data as the UD protocol without LDP noise. Thus, (ε, δ)-DP of RλFOUD can be immediately
derived from [76] (Theorem 1 in [76] with Bin(n, p) replaced with Bin(λ, d1 )). Note that ε ≤ 1 is necessary, as [76] is based on [14], which assumes ε ≤ 1.
E.13
Proof of Theorem 12
′ RDLarge ,D ′ ,β,λ uses RD ,D ,β,λ for τ times. Thus, DP and FODP of Large RD ,D ′ ,β,λ follow immediately from the optimal composition theorem (Theorem 3.3 in [42]). The robustness of RDLarge ,D ′ ,β,λ
is derived from Lemma 2.
E.17
Proof of Theorem 13
Immediately derived from Lemma 4.8 (with k = 1) in [33].