Differential privacy with adjustable preservation of multivariate relationships

Differential privacy with adjustable preservation of multivariate relationships Nicolas Ruiz Universitat Rovira i Virgili Departament d'Enginyeria Informàtica i Matemàtiques Av. Països Catalans 26, 43007 Tarragona, Catalonia nicolas.ruiz@urv.cat

Abstract. This paper derives an exact attenuation formula for multivariate crossmoments under differential privacy achieved through randomized response. From a proposed alternative formulation of randomization matrices compliant with differential privacy guarantees we show that, under attribute-level randomization and where the randomization of the whole distribution is characterized by Kronecker products, any cross-moment of the anonymized dataset involving distinct attributes is equal to the original cross-moment multiplied by attenuation parameters, themselves determined by the part of the overall privacy budget allocated to each attribute. This characterization enables explicit and transparent controls of multivariate relationships preservations in differential privacy through privacy budget allocation. A simple numerical illustration demonstrates that identical total budgets can yield substantially different covariance-preservation profiles. The results also make the multiplicative loss of higher-order interactions explicit and thus can support mechanism design guided by analytical priorities. Keywords. Privacy, anonymization, differential privacy, randomized response

1

Introduction

Data on individual subjects are increasingly collected and exchanged. By their nature, they provide a rich amount of information that can inform statistical and policy analysis in a meaningful way. However, the richness of data is also a curse. Due to legal obligations and privacy concerns in societies, information is often not fully exploited to protect the confidentiality of respondents. In fact, such requirements shape the dissemination policy of micro data at national and international levels. The issue is how to ensure a sufficient level of data protection to meet releasers’ concerns in terms of legal and ethical requirements, while offering users a reasonable richness of information. To manage this tension, anonymization stands out to reconcile both sides, by providing effective privacy protection while offering suitable data utility. A traditional approach to anonymization essentially consists of leveraging a repertoire of masking

1

methods collectively known as statistical disclosure control (SDC, [1]). An SDC method with a heuristic parameter is run to anonymize the original data. Another, and relatively more recent approach, is based on privacy models. A privacy model is an ex-ante privacy condition dependent on a parameter that guarantees a prespecified upper-bound on disclosure risk, regardless of the impact on utility. Each privacy model can be enforced using one or several SDC methods whose parameters then depend on the privacy model parameter. There are currently two main families of privacy models, one based on k-anonymity [2] and the other on ε-differential privacy (DP) [3]. This paper will focus on the latter. For all its current popularity, deploying DP in practice is not without difficulties. For example, the interpretation of the ε parameter or the complexity of implementation remain challenging [4]. But probably the most stringent issue is the resulting data utility that can be exploited from differentially private data. Indeed, if properly applied, DP can result in a severe degradation of data usefulness for analytical tasks [5]. Contribution and plan of this paper There exists in the DP literature a very large set of contributions aiming at assessing, formalizing, estimating etc., which quantities of interest, after application of DP, can be retrieved up to a reasonable degree [6]. In fact, the same applies to the literature on k-anonymity or even for SDC methods leaning or not against privacy conditions [1]. Note that we remain voluntarily vague on the terms “quantities of interest” and “utility guarantees”, as further qualification is intimately linked to what a data user is in practice looking for in terms of data utility: means, variances, correlations, regression coefficients etc. To be precise, in much of the literature privacy is formulated as an ex-ante constraint on the data-release mechanism, while utility is typically specified separately, and often evaluated ex-post, through application-dependent measures such as information loss, distortion, or statistical accuracy [7]. Although utility-aware mechanism design can incorporate such objectives ex-ante (using for example optimal mechanism design [8]), the privacy definition itself generally does not prescribe which aspects of the data's statistical structure should be preserved. In this paper, we focus on one, albeit quite central, aspect of data's statistical structure, that is multivariate relationships, of any order. Starting from a fairly general and popular application mechanism of DP guarantees, i.e. randomized response plus the use of Kronecker products for our multivariate setting, we first characterize in Section 2 a new and simple alternative formulation of differentially private randomized response mechanisms. From this formulation, Section 3 establishes the central result of this paper, by showing that any cross-order moments of a data set can be ex-ante preserved to a selectable extent. In practice, that means that a data curator can decide, before deploying DP, which relationships between attributes she wants to preserve, or lose, depending on the overall privacy budget that has been decided for the protection of the data set. To the best of our knowledge, this is the first time that such result is produced in the DP literature, and more generally in the privacy literature; after a thorough review we have not been able to identify contributions enabling a precise control of multivariate relationships pre-anonymization, for any approach. Finally, leveraging this new

2

feature, Section 5 presents a small empirical illustration, while conclusions and future research directions are gathered in Section 6.

2

Background elements

2.1

Randomized response

Let X denotes an original categorical attribute with 1, … , 𝑟 categories, and Y its anonymized version. Given a value X = u, RR [9] computes a value Y = v by using an r × r Markov transition matrix: 𝑝11 ⋯ 𝑝1𝑟 ⋱ ⋮ ) 𝑃=( ⋮ 𝑝𝑟1 ⋯ 𝑝𝑟𝑟 where 𝑝𝑢𝑣 = Pr(𝑌 = 𝑣|𝑋 = 𝑢) denotes the probability that the original response u in X is reported as v in Y, for 𝑢, 𝑣 ∈ {1, … , 𝑟}. To be a proper Markov transition matrix, it must hold that ∑𝑟𝑣=1 𝑝𝑢𝑣 = 1 ∀𝑢 = 1, … , 𝑟. P is thus right stochastic, meaning that any original category must be spread along the anonymized categories. Moreover, if P is nonsingular, it is proven in [9] that an unbiased estimator of the proportions of respondents whose true values fall in each of the r categories of X can be obtained. The usual setting in RR is that each subject computes her randomized response Y to be reported instead of her true response X. This is called the ex-ante or local anonymization mode. Nevertheless, it is also possible for a (trusted) data curator to gather the original responses from the subjects and randomize them in a centralized way. This expost mode corresponds to PRAM [10]. Apart from who performs the anonymization, RR and PRAM operate the same way and make use of the same matrix P. RR is based on an implicit privacy guarantee called plausible deniability [11]. It equips the individuals with the ability to deny, with variable strength according to the parameterization of P, that they have reported a specific value. In fact, the more similar the probabilities in P, the higher the deniability. In the case where the probabilities within each column of P are identical, it can be proved that perfect secrecy, or perfect privacy, in the Shannon sense is reached [12]: observing the anonymized attribute Y gives no information at all on the real value X. Under such parameterization of P, that will denote hereafter 𝑃 ∗ , a privacy breach cannot originate from the release of an anonymized data set, as the release does not bring any information that could be used for an attack. However, the price to pay in terms of data utility is high [11]. 2.2

Differentially private randomized response

DP being a privacy condition but not a method in itself, it can be achieved through a variety of mechanisms. At a broad level, three foundational approaches are additivenoise mechanisms, including the Laplace and Gaussian mechanisms; randomized-response mechanisms, which directly perturb individual values; and probabilityweighting mechanisms, such as the exponential mechanism, which privately select among discrete or non-numerical outputs. This taxonomy is not exhaustive, but it covers the principal building blocks used in many differentially private algorithms [6, 13]. 3

Moreover, and as for RR, DP can be implemented under either a central or a local model. In central DP, individuals provide their original data to a trusted curator, who applies a privacy-preserving mechanism before releasing statistics or analytical outputs. In local DP, each individual randomizes their data before transmission, so the collector never observes the original values. Although the local model requires less trust in the collector, it generally introduces more noise and therefore yields lower statistical utility for a given privacy guarantee. As such many local DP-mechanisms became over the years designed based on RR [13]. It can also be noted that, during the inception of DP, randomized response was already considered as a method to produce differentially private data sets [3]. This is the choice that we will retain in this paper, remarking also that the results derived in what follows apply to both the central and local scenario. For a categorical attribute with 1,…,r categories, an DP-mechanism based on RR must have the following form: Proposition 1 (DP-RR, [14]): The r×r matrix P of an 𝜀-differentially private randomized response scheme is of the form: 𝑒𝜀 𝜀 𝑝𝑢𝑣 = {𝑟−1+𝑒 1

𝑟−1+𝑒

𝑖𝑓 𝑢 = 𝑣

𝜀 𝑖𝑓 𝑢 ≠ 𝑣

with 𝜀 ≥ ln max𝑢=1,…,𝑟

max𝑢=1,…,𝐾 𝑝𝑢𝑣 max𝑢=1,…,𝐾 𝑝𝑢𝑣

Proposition 1 describes the constraints that DP happens to enforce on a randomization matrix, which incidentally must be symmetric and bistochastic. Finally, and as the setting of this paper is inherently multi-dimensional, we need to endorse a multivariate approach to DP. Various ways are available in the literature, e.g. encoding-based mechanisms such as RAPPOR [15], pre-clustering of attributes [16], or using Kronecker products [17]. Here, we will adopt the latter. Multivariate randomized-response work going back decades observes that when independent RR is performed on each categorical variable of a data set, the resulting multivariate randomization matrix is the Kronecker product of the individual design matrices, and several recent contributions made use of it e.g. [18, 19]. Arguably, this is also an intuitive approach. Moreover, and coupled with the re-formulation of DP proposed below, it appears that this approach allows to control exactly the retention of dependencies in a protected data set.

3

An alternative formulation of randomization matrices for differential privacy

In this section we propose a simple, alternative formulation of randomization matrices for DP mechanisms. To do so, we consider a new class of randomization matrices recently introduced in the privacy literature, the 𝑃(𝜆) class [20]. Considering again the case of a categorical attribute with 1,…,r categories, this class is described by: 𝑃(𝜆) = 𝜆𝐼 + (1 − 𝜆)𝑃 ∗ 𝑤𝑖𝑡ℎ 0 ≤ 𝜆 ≤ 1 (1) 1 ∗ 𝑇 where 𝐼 denotes the identity matrix, and 𝑃 = 𝟏𝟏 with 𝟏 the all-ones vector. 𝑟 Therefore, we have: 4

1−𝜆 𝜆+ 𝑖𝑓 𝑢 = 𝑣 𝑟 𝑝𝑢𝑣 (𝜆) = { (2) 1−𝜆 𝑖𝑓 𝑢 ≠ 𝑣 𝑟 Under Equation (1), a randomization matrix is built by considering two polar situations, no randomization at all (the identity matrix) or maximum randomization (the perfect privacy matrix 𝑃∗ ), while a single parameter 𝜆 is weighing the two situations. The randomization matrix then follows. Arguably, it is a simple and intuitive way of deciding how randomization should be conducted, and also a straightforward procedure to generate randomization matrices. Such randomization matrix reports the true category with a probability exceeding that assigned to each alternative category. Thus, the largest probability is given by the on-diagonal terms, while the smallest by the off-diagonal. Remark also that 𝑃(𝜆) is a symmetric, bistochastic matrix, as Proposition (1). Based on these elements, the following proposition holds: Proposition 2 (formulation of DP-RR as 𝑷(𝝀)): Let 𝑀𝜆 be the randomization mechanism defined by Equations (1) and (2). Then 𝑀𝜆 satisfies 𝜀-differentially privacy for: 1 + (𝑟 − 1)𝜆 𝜀(𝜆) = 𝑙𝑜𝑔 ( ) (3) 1−𝜆 𝑃𝑟(𝑀𝜆 (𝑢)=𝑣) Proof: For arbitrary categories 𝑢, 𝑢′ , 𝑣 ∈ {1, … , 𝑟}, the likelihood ratio (𝑢′ )=𝑣) 1−𝜆

can take the values 1, one:

𝜆+ 𝑟 1−𝜆 𝑟

or

1−𝜆 𝑟 1−𝜆 𝜆+ 𝑟

𝑃𝑟(𝑀𝜆

. The maximum likelihood ratio is thus the second

1−𝜆 𝜆+ 𝑃𝑟(𝑀𝜆 (𝑢) = 𝑣) 𝑟 = 1 + (𝑟 − 1)𝜆 𝑀𝑎𝑥𝑢,𝑢′,𝑣 = 1−𝜆 𝑃𝑟(𝑀𝜆 (𝑢′ ) = 𝑣) 1−𝜆 𝑟 𝑃𝑟(𝑀𝜆 (𝑢)=𝑣) Setting 𝜀 equal to the logarithm of this quantity gives ≤ 𝑒 𝜀 for all 𝑢, 𝑢′ , 𝑣 ∈ (𝑢′ )=𝑣) 𝑃𝑟(𝑀𝜆

{1, … , 𝑟}, which proves 𝜀-differentially privacy. The bound is attained by choosing v=u and any 𝑢′ ≠ 𝑢. It is therefore tight. Any randomization mechanism based on the 𝑃(𝜆) class of randomization matrices appears to provide a direct characterization in terms of DP. Moreover, Equation (3) can be reversed, which gives: 𝑒𝜀 − 1 𝜆(𝜀) = 𝜀 (4) 𝑒 +𝑟−1 Reinjecting this expression into Equations (1) and (2) characterizes an alternative formulation of randomization matrices for DP: 𝑒𝜀 − 1 𝑒𝜀 − 1 𝑃(𝜀) = ( 𝜀 ) 𝐼 + (1 − 𝜀 ) 𝑃∗ 𝑒 +𝑟−1 𝑒 +𝑟−1 with

5

𝑒𝜀 𝑝𝑢𝑣 (𝜀) = {

𝑒𝜀 + 𝑟 − 1

𝑖𝑓 𝑢 = 𝑣

(5) 1 𝑖𝑓 𝑢 ≠ 𝑣 𝑒𝜀 + 𝑟 − 1 Equation (5) is in fact Proposition 1. Thus, DP can be formulated using randomization matrices that also consider explicitly the two polar situations mentioned above, no randomization at all vs. maximum randomization, with the weighting operating through 𝑒 𝜀 −1

the parameter 𝜀 . 𝑒 +𝑟−1 This result simply spells out an underlying matrix structure that happened to be implicitly present in Proposition 1, but which to the best of our knowledge has never been made explicit in the DP literature. However, one can note that it sheds an alternative light on the functioning of DP, specifically the interpretation of 𝜀. Figure 1 displays Equation (4) for various sizes of categorical attributes, showing the implicit weight given to the identity matrix when selecting 𝜀. Figure 1. Implicit weighting of the identity matrix for various levels of 𝜀 in DP.

1 0.9 0.8

0.7 0.6

λ 0.5 0.4

0.3 0.2 0.1 0 0

1

2

3

4

5

6

7

8

9

10

ε λ for r=2

λ for r=3

λ for r=5

λ for r=10

No formal rules exist for selecting 𝜀. Some contributions in the literature recommend setting 𝜀 to small values between 0.01 and 1 to enact protection, but it is known that practical deployments have required much larger values [5]. With the new formulation proposed, setting 𝜀 below or in the vicinity of one is equivalent to performing no randomization at all at most 20% of the time, which is coherent with recommendations. However, when setting 𝜀 above 3 it is equivalent to performing randomization with a weight attached to the identity matrix of 80% or more (except when the number of categories is large), which provides in practice very little protection, while above 4 it is as if no randomization is taking place. 6

4

Structural characterization of multivariate relationships attenuations in differential privacy

Consider a data set D with 1,…,M attributes, each with r1,…,rM categories, respectively, a record 𝑥 = (𝑥1 , … , 𝑥𝑀 ), and let the corresponding attribute-level randomization matrix be as in Equation (1): 𝑃𝑚 (𝜆𝑚 ) = 𝜆𝑚 𝐼𝑟𝑚 + (1 − 𝜆𝑚 )𝑃𝑟∗𝑚 𝑤𝑖𝑡ℎ 0 ≤ 𝜆𝑚 ≤ 1 ∀𝑚 = 1, … , 𝑀 (6) By Proposition 2, for attribute m the following holds: 1 + (𝑟𝑚 − 1)𝜆𝑚 𝜀𝑚 (𝜆𝑚 ) = 𝑙𝑜𝑔 ( ) (7) 1 − 𝜆𝑚 Then, the randomization of the joint distribution of D can be represented by the Kronecker product of the matrices used for each attribute: 𝑃𝐷 (𝜆1 , … , 𝜆𝑀 ) = 𝑃1 (𝜆1 ) ⊗ … ⊗ 𝑃𝑀 (𝜆𝑀 ) (8) The choice made in this paper to use the Kronecker product implies that the randomizations of each attribute are conditionally independent given x. Stated otherwise the randomization of one attribute does not depend on the randomizations of the others. To be clear, this assumption does not imply that the original attributes in D are assumed independent, nor that their randomized versions are independent. For example, 𝑥1 and 𝑥2 could be highly dependent and the Kronecker product will randomize them independently conditional on their original values, but the dependence is transmitted to 𝑦1 and 𝑦2 , albeit in a way altered by DP. We mentioned above that there are many ways to enact DP in a multivariate scenario. But as will be clear with the theorem that follows, and beyond the computational simplicity of this choice, using Kronecker products for DP carries unintended benefits. Now, for each attribute m define an arbitrary real-valued function 𝑓𝑚 of 𝑥𝑚 and of 𝑦𝑚 (the latter obtained from 𝑥𝑚 through application of DP), and define: 𝑍𝑚 = 𝑓𝑚 (𝑥𝑚 ) 𝑎𝑛𝑑 𝑊𝑚 = 𝑓𝑚 (𝑦𝑚 ) and ̃𝑚 = 𝑊𝑚 − 𝐸(𝑊𝑚 ) 𝑍̃𝑚 = 𝑍𝑚 − 𝐸(𝑍𝑚 ) 𝑎𝑛𝑑 𝑊 From these elements, we have the following theorem: Theorem 1 (exact attenuation of multivariate relationships in DP): For every subset of distinct attributes 𝑆 ⊆ {1, … , 𝑀}, it holds that: 𝑒 𝜀𝑚 − 1 ̃𝑚 ) = (∏ 𝐸 (∏ 𝑊 ) 𝐸 (∏ 𝑍̃𝑚 ) (9) 𝑒 𝜀𝑚 + 𝑟𝑚 − 1 𝑚∈𝑆

𝑚∈𝑆

𝑚∈𝑆

Proof: For an attribute m, and conditional on the true value of the individual 𝑥𝑚 , under the 𝑃(𝜆) formulation DP retains 𝑥𝑚 with probability 𝜆𝑚 and replaces it with a uniformly selected category with probability 1 − 𝜆𝑚 , which implies: 𝑟𝑚

1 𝐸[𝑓𝑚 (𝑦𝑚 )|𝑥𝑚 ] = 𝜆𝑚 𝑓𝑚 (𝑥𝑚 ) + (1 − 𝜆𝑚 ) ∑ 𝑓𝑚 (𝑎) 𝑟𝑚 Taking the expectation of this last expression gives:

7

𝑎=1

𝑟𝑚

1 𝐸(𝑊𝑚 ) = 𝜆𝑚 𝐸(𝑍𝑚 ) + (1 − 𝜆𝑚 ) ∑ 𝑓𝑚 (𝑎) 𝑟𝑚 𝑎=1

Next, we have:

̃𝑚 |𝑥𝑚 ) = 𝐸(𝑊𝑚 |𝑥𝑚 ) − 𝐸(𝑊𝑚 ) 𝐸(𝑊 1 1 𝑟𝑚 𝑟𝑚 = 𝜆𝑚 𝑓𝑚 (𝑥𝑚 )+(1 − 𝜆𝑚 ) ∑𝑎=1 𝑓𝑚 (𝑎) −𝜆𝑚 𝐸(𝑍𝑚 ) + (1 − 𝜆𝑚 ) ∑𝑎=1 𝑓𝑚 (𝑎) 𝑟𝑚

𝑟𝑚

Hence, we get: ̃𝑚 |𝑥𝑚 ) = 𝜆𝑚 [𝑓𝑚 (𝑥𝑚 ) − 𝐸(𝑍𝑚 )] = 𝜆𝑚 𝑍̃𝑚 𝐸(𝑊 (10) Now, consider any subset of distinct attributes S. By the assumed conditional assumption of the randomized variables 𝑦𝑚 given x, due to the use of the Kronecker product as the multidimensional setting retained, we have: ̃𝑚 |𝑥) = ∏ 𝐸(𝑊 ̃𝑚 |𝑥) 𝐸 (∏ 𝑊 Using Equation (10), we get:

𝑚∈𝑆

𝑚∈𝑆

̃𝑚 |𝑥) = ∏ 𝜆𝑚 𝑍̃𝑚 = (∏ 𝜆𝑚 ) ∏ 𝑍̃𝑚 𝐸 (∏ 𝑊 𝑚∈𝑆

𝑚∈𝑆

𝑚∈𝑆

𝑚∈𝑆

Finally, taking expectations with respect to x and using Equation (4), we have:

̃𝑚 ) = 𝐸 [𝐸 [∏ 𝑊 ̃𝑚 |𝑥]] = (∏ 𝜆𝑚 ) 𝐸 (∏ 𝑍̃𝑚 ) 𝐸 (∏ 𝑊 𝑚∈𝑆

𝑚∈𝑆

= (∏ 𝑚∈𝑆

𝑒

𝜀𝑚

𝑚∈𝑆

−1

𝑒 𝜀𝑚 + 𝑟𝑚 − 1

𝑚∈𝑆

) 𝐸 (∏ 𝑍̃𝑚 ) 𝑚∈𝑆

To illustrate the functioning of Theorem 1, consider the case of the covariance between two attributes 𝑥1 and 𝑥2 (with 𝑥̃1 and 𝑥̃2 their centered versions, respectively) both with the same number of categories r, and each randomized with 𝑃1 (𝜆1 ) and 𝑃2 (𝜆2 ), as defined in Equation (6), to produce their randomized versions 𝑦1 and 𝑦2 . We have: 1 1 cov(𝑦1 , 𝑦2 ) = (𝑃1 (𝜆1 )𝑥̃1 )⊤ (𝑃2 (𝜆2 )𝑥̃2 ) = 𝑥̃1𝑇 𝑃1𝑇 (𝜆1 )𝑃2 (𝜆2 )𝑥̃2 𝑟 𝑟 1 𝑇 ∗ = 𝑥̃1 [𝜆1 𝜆2 𝐼𝑟 + (1 − 𝜆1 𝜆2 )𝑃𝑟 ]𝑥̃2 (11) 𝑟 Then, because 𝑥̃1 and 𝑥̃2 are centered, it holds that: 𝟏𝑻 𝑥̃1 = 𝟏𝑻 𝑥̃2 = 0 and thus: 1 𝑃𝑟∗ 𝑥̃2 = 𝟏𝟏𝑇 𝑥̃2 = 0 𝑟 𝑥̃1𝑇 𝑃𝑟∗ = 0 Simplifying Equation (11) and using Equation (4), we have: 𝑒 𝜀1 − 1 𝑒 𝜀2 − 1 cov(𝑦1 , 𝑦2 ) = 𝜆1 𝜆2 cov(𝑥1 , 𝑥2 ) = ( 𝜀 )( 𝜀 ) cov(𝑥1 , 𝑥2 ) 𝑒 1 + 𝑟1 − 1 𝑒 2 + 𝑟2 − 1 8

𝑒 𝜀1 −1

Remark that, rather counter-intuitively, 𝑉𝑎𝑟(𝑦1 ) ≠ ( 𝜀1 𝑒

+𝑟1 −1

2

) 𝑉𝑎𝑟(𝑥1 ). Theorem

1, formulated for a subset 𝑆 of distinct attributes, does not extend to the moments of any order of a single attribute. To see why, from the proof of Theorem 1 consider that: 𝑟𝑚

1 𝐸[𝑊𝑚 |𝑥𝑚 ] = 𝜆𝑚 𝑍𝑚 + (1 − 𝜆𝑚 ) ∑ 𝑓𝑚 (𝑎) 𝑟𝑚 𝑎=1

which implies, for the variance: 𝑉𝑎𝑟(𝐸[𝑊𝑚 |𝑥𝑚 ]) = 𝜆2𝑚 𝑉𝑎𝑟(𝑍𝑚 ) But, by the law of total variance, we have: 𝑉𝑎𝑟(𝑊𝑚 ) = 𝑉𝑎𝑟(𝐸[𝑊𝑚 |𝑥𝑚 ]) + 𝐸(𝑉𝑎𝑟[𝑊𝑚 |𝑥𝑚 ]) The second term on the right of the last expression represents the additional variability generated by randomization. It is a feature well-known in the RR literature [21], which cannot be omitted. This feature is however disappearing for cross-moments because the randomizations of two (or more) distinct attributes are conditionally independent, a consequence of the use of Kronecker products. Thus, Theorem 1 characterizes the attenuation of multivariate relationships, while univariate moments behave differently because randomization adds its own variability. More generally, Theorem 1 establishes that, under the alternative parameterization of DP proposed in this paper, any cross-moment of a randomized distribution is linked to its original moment through an exact attenuation relationship, where the attenuation terms are the weights (themselves functions of the privacy parameters 𝜀’s) allocated to the identity matrices. Probably the most direct consequence of Theorem 1 is that it is possible to steer anonymization to precisely control for which multivariate relationship should be preserved to a lesser or greater extent. Indeed, through the choice of 𝜀 for each attribute, one can control for the preservation of say certain covariances that are deemed more valuable (in terms of information value for data users) when close to the original ones in the randomized version of the dataset, while others less relevant could be more degraded. But in doing so, one is confronted with the classic information/privacy trade off. Again, considering the covariance, large epsilons for two attributes will preserve it, while a small epsilon for at least one attribute will degrade the relationship, a rather intuitive consequence. Moreover, by choosing to largely preserve a covariance, this will directly weigh on an overall given privacy budget for the whole database, and thus other relationships will have automatically to be degraded. However, as unavoidable as the information/privacy tradeoff is, we believe Theorem 1 allows to get a better appraisal of it. In fact, those considerations are linked to the curse of dimensionality in privacy. This well-documented curse is the phenomenon that protecting a dataset becomes substantially harder as the number of attributes increases. Difficulties arise computationally, as the numerical operations required to protect a large dataset become costly if not intractable, but they also arise because statistical utility can deteriorate very quickly [16]. Theorem 1 captures this curse on the statistical side, as the higher the order of a moment one wants to preserve, the more attenuation there is to deal with. For instance, and for a fourth-order cross-moment, 4 attenuation terms are involved. Thus, and as far as DP 9

is concerned, high-order interactions disappear much faster, in fact multiplicatively so, than low-order effects. Consequently, for a data set with many attributes multivariate relationships are mechanically almost lost, even for medium or high 𝜀’s. Thus, the results in this paper establish an analytical hierarchy in the information/privacy trade off: for a given overall privacy budget, low-order relationships can be preserved more strongly, but high-order ones are attenuated more strongly, almost to the point of irretrievability. It must be noted that the ambition of this paper was not pretending to “solve” the curse of dimensionality. However, it provides a statistical manifestation of it, and potentially offers a solution to manage it by characterizing a particular structure in the preservation of multivariate relationships. Finally, as mentioned above this paper considered the local and central scenario indifferently. However, for the latter those results can offer specific insights as to how an overall privacy budget should be allocated. Obviously, in the local scenario the data curator cannot know ex-ante what the strengths of the various relationships are in the original data. Thus, the curator must act blindly regarding how to allocate the privacy budget across the various attributes (a standard difficulty of the local scenario in privacy) or possibly act based on prior beliefs. However, in the central scenario the curator can witness the original strengths and thus decide how to dispatch the privacy budget. Indeed, using Theorem 1 the curator can choose to strongly protect attributes which originally have poor relationships, as in that case attenuation will be harmless in terms of data utility, while relaxing protection on attributes with strong relationships, under the constraint of a given, overall privacy budget. Thus, for the central scenario the results developed in this paper offer room for improved management of the information/privacy trade off and the curse of dimensionality.

5

Numerical illustrations

In the example below, we act as a data curator who must protect a data set composed of five attributes 𝑋1 , … , 𝑋5 , each with four categories, so 𝑟𝑚 = 4 (using the writings above). The curator sets a total privacy budget, under DP, of: 5

𝜀𝑇𝑜𝑡 = ∑ 5 𝑚=1

Thus, for 𝑟𝑚 = 4 we have the following attenuation coefficients: 𝑒 𝜀𝑚 − 1 𝜆𝑚 = 𝜀 𝑒 𝑚+3 From the assigned total privacy budget, using basic sequential composition the curator designs three configurations: • A balanced configuration where the budget is allocated equally: {1, 1, 1, 1, 1} • A second where the preservation of the relationship between 𝑋1 and 𝑋2 is favored: {2, 2, 1/3, 1/3, 1/3} • A third where priorities are graduated: {2, 1.5, 0.75, 0.5, 0.25} 10

Table 1 illustrates how the allocation of a fixed privacy budget determines the preservation of pairwise relationships. It reports percentages of the original covariances retained. Table 1. Covariances preservations under different privacy budget allocation. Covariance between X_1 and X_2 X_1 and X_3 X_1 and X_4 X_1 and X_5 X_2 and X_3 X_2 and X_4 X_2 and X_5 X_3 and X_4 X_3 and X_5 X_4 and X_5

Balanced

X_1 and X_2 favored

9% 9% 9% 9% 9% 9% 9% 9% 9% 9%

37.8% 5.5% 5.5% 5.5% 5.5% 5.5% 5.5% 0.8% 0.8% 0.8%

Graduated 28.6% 13.4% 8.6% 4.1% 10.2% 6.5% 3.1% 3.0% 1.4% 0.9%

For the balanced configuration, all covariances retain the same proportion of their original values, as expected: the total budget is distributed evenly, so all pairwise relationships experience the same degradation. Still, with an 𝜀 value of 1 for each attribute, i.e. when substantial protection is applied, only 9% of the original covariances is retained. Then, concentrating the budget on 𝑋1 and 𝑋2 substantially improves the preservation of their covariances (37.8%) compared to the balanced scenario, but almost cancels out relationships among the other attributes, a striking illustration of the trade-off involved. Finally, the graduated configuration produces an intermediate hierarchy of covariance preservation. Overall, an identical total privacy budget can induce very marked differences in data utility profiles, depending on how it is allocated across attributes.

6

Conclusions and future work

This paper considered the preservation of multivariate relationships under DP. Under a fairly general choice of application mechanism to enforce DP privacy guarantees, it first identified an alternative formulation for a differentially private randomized response scheme, as a combination of the identity matrix and the maximum, uniform randomization matrix. From this formulation, it then proceeded to an exact characterization of the attenuation of cross-moments involving distinct attributes, where attenuation is driven by the weights set to the identity matrix in the combination, and where those weights are determined by the attribute-level privacy budgets allocated from the overall budget.

11

Those results entail two main consequences. On the one hand, within the application mechanism for DP retained, the exact preservation of selected relationships can be specified before randomization, rather than assessed only after data release, a feature which to the best of our knowledge is new in the literature. The numerical illustration demonstrates that an identical total privacy budget can produce markedly different covariance-preservation profiles, depending on whether resources are distributed evenly or concentrated on selected attributes. Results of this paper therefore support the prioritization of analytical objectives by offering a better, more granular grasp of the information/privacy trade-off. On the other hand, from those results it is clear that higher-order cross-moments accumulate more attenuation factors, making their preservation an arduous task. Thus, this paper exposes and analytically clarifies an unavoidable, structural source of utility loss in high-dimensional settings, by characterizing an exact mathematical relationship to appraise and manage what is otherwise known as the curse of dimensionality in privacy. Several avenues for future research follow from these findings. A potential direction is to formulate the privacy budget allocation as an explicit optimization problem. Given a fixed total budget and a set of analytical priorities, one could seek allocations that maximize a weighted measure of cross-moment preservation or satisfy minimum retention requirements for selected relationships. Another direction concerns statistical estimation. The present results describe population-level attenuation, whereas practical applications rely on finite samples. Future work could then investigate estimators that correct for known attenuation, their sampling variability, and the conditions under which correction remains statistically useful. This would help distinguish the algebraic recoverability of a relationship from the precision with which it can be estimated, particularly when interaction orders are high.

References 1. Hundepool A., J. Domingo-Ferrer, L. Franconi, S. Giessing, E. Schulte Nordholt, K. Spicer and P.-P. de Wolf, Statistical Disclosure Control, Wiley, 2012. 2. Samarati, P., and Sweeney, L. “Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression”, SRI International Report, 1998. 3. Dwork, C, “Differential privacy”, Proceedings of the 33rd International Colloquium on Automata, Languages and Programming - ICALP 2006, Springer, pp. 1–12, 2006. 4. Garrido G., X. Liu, F. Matthes, and D. Song, “Lessons learned: Surveying the practicality of differential privacy in the industry,” Proceedings on Privacy Enhancing Technologies Symposium, vol. 2023, no. 2, pp. 151–170, 2023. 5. Del Vasto-Terrientes L., D. Sanchez, and J. Domingo-Ferrer, “Differential privacy in practice: lessons learned from 10 years of real-world applications”, IEEE Security & Privacy, vol. 24, Issue 1, Jan.-Feb, 2026. 6. Guo L., P. Lyu, H. Li, and D. Liu, “A comprehensive survey of differential privacy: Taxonomy and analysis based on symmetry”, Neurocomputing, vol. 701, 134556, 2026. 7. Slavkovic A., and J. Seeman, “Statistical data privacy: A song of privacy and utility”, Annual Review of Statistics and Its Application, vol. 10, Issue 1, pp. 189-218, 2023.

12

8. Ghosh A., T. Roughgarden, and M. Sundararajan, “Universally utility-maximizing privacy mechanisms”, SIAM Journal on Computing, vol. 41, Issue 6, 2012. 9. Chaudhuri, A., and Mukerjee, R. Randomized Response: Theory and Techniques. Marcel Dekker, 1988. 10. Kooiman P.L., L. Willenborg, and J. Gouweleeuw, “PRAM: a method for disclosure limitation of microdata”, Research Report 9705, Statistics Netherlands, Voorburg, NL, 1998. 11. Domingo-Ferrer J., and J. Soria-Comas, “Connecting randomized response, post-randomization, differential privacy and t-closeness via deniability and permutation”, https://arxiv.org/abs/1803.02139, 2018. 12. Shannon, C.E., “Communication theory of secrecy systems”, Bell System Technical Journal, 28, 4, 656–715, 1949. 13. Mengmeng Y., T. Guo, T. Zhu, I. Tjuawinata, J. Zhao, and K. Lam, “Local differential privacy and its applications: A comprehensive survey, Computer Standards & Interfaces, vol. 89, 103827, 2024. 14. Wang Y., X. Wu, and D. Hu, “Using randomized response for differential privacy preserving data collection”. Proceedings of the EDBT/ICDT 2016 Joint Conference, vol. 1558, 0090– 6778, 2016. 15. Erlingsson U., V. Pihur, and A. Korolova, “RAPPOR: Randomized aggregatable privacypreserving ordinal response”, Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS ‘14, p. 1054–1067, 2014. 16. Domingo-Ferrer J., and J. Soria-Comas, "Multi-dimensional randomized response", IEEE Transactions on Knowledge and Data Engineering, Vol. 34, no. 10, pp. 4933-4946, Oct 2022. 17. Bourke P.D, “On the analysis of some multivariate randomized response designs for categorical data”, Journal of Statistical Planning and Inference, Volume 5, Issue 2, 1981, Pages 165-170. 18. Chaobin L, C. Shixi, Z. Shuigeng, G. Jihong, and M. Yao, “A general framework for privacy-preserving of data publication based on randomized response techniques”, Information Systems, vol. 96, 101648, 2021. 19. Yamamoto A., and T. Shibuya, “Privacy-optimized randomized response for sharing multiattribute data”, 2024 IEEE Symposium on Computers and Communications (ISCC), Pages 1-8, 2024. 20. Ruiz, N., “λ-randomization: multi-dimensional randomized response made easy”, Lecture Notes in Computer Science, Privacy in Statistical Databases (PSD 2026), vol. 16925, pages 82-97, 2026. 21. Le, T.-N., S. Lee, P. Tran, and C. Li, “Randomized response techniques: a systematic review from the pioneering work of Warner (1965) to the present”, Mathematics, vol. 11, 1718, 2023.

13

Related documents

• Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning#609724
• High-Dimensional Asymptotics of Differentially Private PCA#1187270
• Differentially Private Sampling from Distributions via Wasserstein Projection#175142
• Unifying Privacy Accounting: Information Equivalence and Information Loss#1186728
• Unifying Privacy Accounting: Information Equivalence and Information Loss#1181584