Adaptive Data Analysis in a Balanced Adversarial Model
Authors: Kobbi Nissim
Uri Stemmer
Eliad Tsfadia
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Adaptive Data Analysis
Differential Privacy
Statistical Queries

Abstract: In adaptive data analysis, a mechanism gets $n$ i.i.d. samples from an unknown distribution $\cal{D}$, and
is required to provide accurate estimations to a sequence of adaptively chosen statistical queries with respect to $\cal{D}$.
Hardt and Ullman (FOCS 2014) and Steinke and Ullman (COLT 2015) showed that in general, it is computationally hard to answer more than $\Theta(n^2)$ adaptive queries, assuming the existence of one-way functions. 

However, these negative results strongly rely on an adversarial model that significantly advantages the adversarial analyst over the mechanism, as the analyst, who chooses the adaptive queries, also chooses the underlying distribution $\cal{D}$. 
This imbalance raises questions with respect to the applicability of the obtained hardness results -- an analyst who has complete knowledge of the underlying distribution $\cal{D}$ would have little need, if at all, to issue statistical queries to a mechanism which only holds a finite number of samples from $\cal{D}$.

We consider more restricted adversaries, called \emph{balanced}, where each such adversary consists of two separated algorithms: The \emph{sampler} who is the entity that chooses the distribution and provides the samples to the mechanism, and the \emph{analyst} who chooses the adaptive queries, but has no prior knowledge of the underlying distribution (and hence has no a priori advantage with respect to the mechanism). 
We improve the quality of previous lower bounds by revisiting them using an efficient \emph{balanced} adversary, under standard public-key cryptography assumptions. We show that these stronger hardness assumptions are unavoidable in the sense that any computationally bounded \emph{balanced} adversary that has the structure of all known attacks, implies the existence of public-key cryptography.

Adaptive Data Analysis in a Balanced Adversarial Model
Kobbi Nissim Department of Computer Science
Uri Stemmer Blavatnik School of Computer Science Tel Aviv University Google Research
Georgetown University kobbi www.siiigggorgetton.nnnmmm .du
u@uri.co.
Eliad Tsfadia Department of Computer Science Georgetown University el @liadtsfadia@gmail. com
Abstract
In adaptive data analysis, mechanism gets i.i.d. samples from unknown distribution D, and is required to provide accurate estimations to sequence of adaptively chosen statistical queries with respect D. Hardt and Ullman [2014] and Steinke and Ullman [2015a] showed that, in general, it is computationally hard to answer more than ((n) adaptive queries, assuming the existence of one-way functions.
However, these negative results strongly rely on adversarial model that signifi- cantly advantages the adversarial analyst over the mechanism, as the analyst, who chooses the adaptive queries, also chooses the underlying distribution D. This imbalance raises questions with respect to the applicability of the obtained hardness results an analyst who has complete knowledge of the underlying distribution would have little need, if at all, to issue statistical queries to mechanism which only holds a finite number of samples from D.
We consider more restricted adversaries, called balanced, where each such ad- versary consists of two separate algorithms: The sampler who is the entity that chooses the distribution and provides the samples to the mechanism, and the analyst who chooses the adaptive queries, but has prior knowledge of the underlying distribution (and hence has no a priori ad advantage with respect to the mechanism).
We improve the quality of previous lower bounds by revisiting them using efficient balanced adversary, under standard public-key cryptography assumptions. unavoidable in the sense
We show that these stronger hardness assumptions that any computationally bounded balanced adversary that has the structure all known attacks, implies the existence of public-key cryptography.
Introduction
Statistical validity is widely recognized crucial feature of modern science. Lack of validity popularly known as the replication crisis in science poses a serious threat to the scientific process and also to the public's trust in scientific findings.
One the factors leading to the replication crisis is the inherent adaptivity in the data analysis process. To illustrate adaptivity and its effect, consider data analyst who testing specific research
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

hypothesis. The analyst gathers data, evaluates the hypothesis empirically, and often finds that their hypothesis is not supported by the data, leading to the formulation and testing of more hypotheses. If these hypotheses are tested and formed based on the same data (as acquiring fresh data is often expensive or even impossible), then the process is of adaptive data analysis (ADA) because the choice of hypotheses depends on the data. However, ADA no longer aligns with classical statistical theory, which assumes that hypotheses are selected independently of the data (and preferably before gathering data). ADA may lead to overfitting and hence false discoveries.
Statistical validity under ADA is fundamental problem in statistics, that has received only partial answers. A recent line of work. initiated by Dwork et al.
[2015c] and includes (Hardt and Ullman
Dwork al., [2015a b] [Steinke and Ullman| 2015a b Bassily et al. [016 Rogers et 2016
Russo and Zou, 2016 |mith|20171 Feldman and Steinke
2017]
et al., 2018 Feldmann and
Fish et al. 2020, Dagan and Kur 2022 Kontorovich et al. [022 Dinur et al. 2023] Blanc 2023] has resulted in new insights into ADA
Steinke||0013 2018 Shenfeld and Ligett 2019 Jung et al. 2020
and robust paradigms for guaranteeing statistical validity in ADA, A major objective of this line of work is to design optimal mechanisms M that initially obtain a dataset S containing i.i.d. samples from an unknown distribution D, and then answers adaptively chosen queries with respect to D. Importantly, all of M's s answers must be accurate with respect to the underlying distribution D, not just w.r.t the empirical dataset S. The main question is how to design an efficient mechanism that provides accurate estimations to adaptively chosen statistical queries, where the goal is to maximize the number of queries M can answer. This objective is achieved by providing both upper- and power-bound constructions, where the lower-bound constructions demonstrate how adversarial analyst making a small number of queries to an arbitrary M can invariably force M to err. The setting for these lower-bound proofs is formalized as two-player game between mechanism M and an adversary A as in Game 1.1
Game 1.1 (ADA game between a mechanism M and an adversarial analyst A).
M gets a dataset S of n i.i.d. samples from an unknown distribution 'D over X.
* For i = l..
A sends query q: X' ++ [-1, M.
. sends an answer y: E [-11,1] to A
(As A and M are stateful, qs and y/ may depend on the previous messages.)
M fails 3i [6] s.t. 1y: E (x)]] 1/10.
A question that immediately arises from the description of Game 1.I is to whom should the distribution DD be unknown, and how to formalize this lack of knowledge. Ideally, the mechanism M should succeed with high probability for every unknown distribution DD and against any adversary A.
In prior work, this property was captured by letting the adversary choose the distribution D at the outset of Game 1.1 Namely, the adversary A can be seen pair of algorithms (A1, A2), where Ai chooses the distribution DD and sends a state st to A (which may contain the entire view of A1), and after that, M and (st) interacts in Game 1.1. In this adversarial model, Hardt and Ullman [2014) and Steiikee and Ullman| [2015a] showed that, assuming the existence of one way functions, it is computationally hard to answer more than (n²²) adaptive queries. These results match the state-of-the-ard constructions (Dwork et al. 2015c b Steinke and Ullman 2015b Bassily et al.
2016 Feldman and Steinke, 2017 2018 Dagan and Kur 2022 Blane 2023 In fact, each such negative result was obtained by constructing a single adversary A that fails all effciint mechanisms. This means that, in general, it is computationally hard to answer more than (n?) adaptive queries even when the analyst's algorithm is known to the mechanism. On the other hand, in each of these negative results, the adversarial analyst has significant advantage over the mechanism their ability to select the distribution D. This allows the analyst to inject random trapdoors in D (e.g.. keys of an encryption scheme) which are then used in forcing computationally limited mechanism to fail, as the mechanism does not get a hold of the trapdoor information.
'erre is an example of mechanism that handles @(n²) adaptive queries using differential privacy: Given query qi the mechanism returns an answer y; =1 noises, each with standard deviation of Ö(Vē/n). The noises guarantee that the entire process is "private enough" for avoiding overfitting in the ADA game, and accuracy is obtained whenever é Ö(n?).
R. >xes x 14 where the v, are independent Gaussian

---

For most applications, the above adversarial model seems to be too strong, For instance, a data analyst who is testing research hypotheses usually has no knowledge advantage about the distribution that the mechanism does not have. In this typical setting, even if the underlying distribution DD happens to have trapdoor, if the analyst recovers the trapdoor then the mechanism should also be able to recover it and hence disable its adversarial usage.
In light of this observation, we could hope that in balanced setting, where the underlying distribution is unknown to both the mechanism and the analyst, it would always be possible for M to answer more than (n²)) adaptive queries. To explore this possibility, we introduce what we call balanced adversarial model.
Definition 1.2 (Balanced Adversary). A balanced adversary A consists of two isolated algorithms: The sampler A1, which chooses distribution 'D and provides i..d. samples to the mechanism M, and the analyst Ag. which asks the adaptive queries. No information is transferred from A1 to Ag. See
Game 1.3
Game 1.3 (The ADA game between a mechanism M and a balanced adversary A = (A1, A2)).
A₁ chooses a distribution 'D over X (specified by a sampling algorithm) and provides n. i..dd samples S to M (by applying the sampling algorithm times).
/ Ai does not provide A2 with any information $/
M and A2 play Game 1.1 (with respect to DD and S).
M fails if and only if it fails in Game 7.1
Note that the difference between the balanced model and the previous (imbalanced) one is whether Aı can send state to A2 after choosing the distribution 'D (in the imbalanced model it is allowed, in contrast to the balanced I
We remark that the main advantage of the balanced model comes when considering publicly known sampler A (as we do throughout this work). This way, A captures the common knowledge that both the mechanism M and the analyst Ag have about the underlying distribution D.
Question 1.4. Do the lower-bounds proved in prior work hold also for balanced adversaries?
In this work we answer Question 1.4 in the positive. We do that using a publicly known analyst Ae (which even makes it stronger than what required for a lower bound). L.e., even though the sampler A and the analyst A are publicly known and cannot communicate with each other, they fail any computationally bounded mechanism. However, our lower-bound is based on stronger hardness assumptions than in prior work, namely, we use public-key cryptography.
1.1 Our Results
Our first result is construction of balanced adversary forcing any computationally bounded mechanim to fail in Game L.3
Theorem 1.5 (Computational lower bound, informal). There exists efficient balanced adversary = (A1, Aa) that fails any computationally bounded mechanism M using ((n²) adaptive queries. Moreover, it does so by choosing a distribution over small domain.
Our construction Theorem 1.5 uses the structure of previous attacks of Hardt and Ullman (014) and Steinke and Ullman| [2015a]. but relies on stronger hardness assumption of public-key cryptography. We prove that this unavoidable.
Theorem 1.6 (The necessity of public-key cryptography for proving Theorem 1.5 informal). Any computationally bounded balanced adversary that follows the structure of all currently known attucks, implies the existence of public-key cryptography (in particular, a key-agreement protocol).
In Section 1.3
we provide proof sketches of Theorems 1.5 and 1.6 where the formal statements appear in Sections and (respectively) and the formal proof' appear in the supplementary material.
AAn additional (minor) difference is that we chose in our model to let A₁ also provide the i.idd samples to M. This is only useful for Theorem [66 as we need there that choosing D and sampling from 2 are both computationally efficient (which simply captured by saying that A1 is computationally bounded).
3

---

Potential Consequences for the Information Theoretic Setting, Theorem 1.6 has immediate implication to the information theoretic setting, and allow for some optimism regarding the possibility of constructing an inefficient mechanism that answers many adaptive queries.
It is known that inefficient mechanism can answer exponentially many adaptive queries, but such results have a strong dependency on the domain size. For instance, the Private Multiplicative Weights
algorithm of Hardt and Rothblum (2010) can answer 2 (1/V//iglla /log//)) adaptive queries accurately. However, this result is not useful whenever S O( /log X1)- Indeed, Steinke and Ullman [2015a] showed that this dependency is unavoidable in general, by showing that large domain can be used for constructing similar, unconditional, adversary that fails any computationally unbounded mechanism after ((n²) queries. Our Theorem 1.6 implies that such an attack cannot be implemented in the balanced setting, which gives the first evidence that there might be separation between the computational and information theoretic setting under the balanced adversarial model (in contrast with the imbalanced model).
Corollary 1.7. There is no balanced adversary that follows the structure of all currently known attacks, and fails any (computationally unbounded) mechanism.
In order to see why Corollary 1.7 holds, suppose that we could implement such kind of attack using a balanced adversary. Then by Theorem [.6]] this would imply that we could construct an information-theoreti key agreement protocol (i.e., a protocol between two parties that agree on key that is secret from the eyes of a computationally unbounded adversary that only sees the transcript of the execution). But since the latter does not exist, we conclude that such a balanced adversary does not exists either. In other words, we do not have negative result that rules out the possibility of constructing an inefficient mechanism that can answer many adaptive queries of a balanced adversary. and we know that if a negative result exists, then by Theorem I.6 it cannot follow the structure of Hardt and Ullman 2014). Steinke and Ullman 2015a]
1.2 Comparison with Elder 2016
The criticism about the lower bounds of Hardt and Ullman (014)) Steinke and Ullman [015a is not new and prior work has attempted at addressing them with only partial success.
For example, Elder 2016) presented a similar "balanced" model (called "Bayesian ADA"), where both the analyst and the mechanism receive a prior P which is family of distributions, and then the distribution D is drawn according to P (unknown to both the mechanism and the analyst).
From an information theoretic point of view, this model is equivalent to ours when the sampler A₁ is publicly known, since A₃ simply defines a prior. But from a computational point of view, defining the sampling process (i.e., sampling D and the i.i.d. samples from it) in an algorithmic way is better when we would like to focus on computationally bounded samplers.
Elder 2016 only focused on the information-theoredl setting. His main result is that a certain family of mechanisms (ones that only use the posterior means) cannot answer more than Ö(n*) adaptive queries. This, however, does not hold for any mechanism's 's strategy. In particular, it does not apply to general computationally efficient mechanisms. Our negative result is quantitatively stronger (n²² vs n²) and it applies for all computationally efficient mechanisms
Table T summarizes the comparison between Theorem I.5 and the prior lower bounds (ignoring computational hardness assumptions).
1.3 Techniques
We follow a similar technique to that used in Hardt and Ullman| (014 and Steinke and Ullman 2015a i.e., reduction to a restricted set of mechanisms, called natural.
Definition 1.8 (Natural mechanism (Hardt and Ullman| 2014). A mechanism M is natural if. when given a sample S = (I1,.... . Inn E Xn and a query q: X X- 1-1,11 11. M returns an answer that is function solely of
(z),)). In particular, M does not evaluate q on other data points of its
choice.
*Our result is not directly comparable to that of Elder 2016). because our negative result does not say anything for non- con-efficient mechanisms, while his result does rule out certain family of non-efficient mechanisms.

---

Balanced?
Class of Mechanisms
# #o Queries
Dimension (log X
Steinke and Ullman
2015a
No
PPT Algorithms
O
n²)))
Steinke and Ullman
2015a
No
All
O
O(n²)
Elder [2016]
Yes
Certain Family
O(n²)
((n²)
Theorem 1.5
Yes
PPT Algorithms
O(n²)
n2(1)
Table I: Comparison between the lower bounds for adaptive data analysis.
Hardt and Ullman [2014] and Steinke and U1lman| [0015a] showed that there exists an adversarial analyst A that fails any natural mechanism M. even when M computationally unbounded, and even 2000n} (I.c., D is known to everyone). While general mechanisms could simply use the knowledge of the distribution to answer any query, natural mechanisms are more restricted, and can only provide answers based on the n-size dataset S that they get. The restriction to natural mechanisms allowed Steinke and Ullman [2015a] to use interactive fingerprinting codes, which enable to reveal S using ((n") adaptive queries when the answers are accurate and correlated with S.
when D is chosen to be the uniform distribution over {1, ...,...., m
To construct an attacker A that fails any computationally bounded mechanism (and not just natural mechanisms), prior work forced the mechanism to behave naturally by using private-key encryption scheme. More specifically, the ad adversary first samples m secret keys skı.... skm, and then defines D to be the uniform distribution over the pairs { sk,) }) The adversary then simulates an adversary
A which fails natural mechanisms follows: query q: [ma] + [-1, 1] issued by À is translated by A to a set of m encryptions {ctz)]== where each ct, is an encryption of T() under the key sky. These encryptions define a new query that on input (j. sk), outputs the decryption of ct₃ under the key sk. However, since M is computationally bounded and has only the secret keys that are part of its dataset S, it can only decrypt the values of i on points in S, yielding that it effectively behaves naturally.
Note that the above attack A imbalanced as injects the secret keys sk skm into 'D and then uses these keys when it forms queries. In other words, even though the attacker A is known to the mechanism, A is able to fail M by creating a secret correlation between its random coins and the distribution D.
1.3.1 Balanced Adversary via Identity Based Encryption Scheme
For proving Theorem 1.5) we replace the private-key encryption scheme with a public-key primitive
called identity-based encryption (IBE) scheme (Shamir 1984 Cocks, 2001 Bonch and Franklin 2001]. Such scheme enables to produce m secret keys skj.... skm along with a master public key mpk. Encrypting a message to a speific identity j E [m] only requires mpk, but decrypting a message for identity j must be done using its secret key sky. Using an IBE scheme we can achieve a reduction to natural mechanisms via a balanced adversary A = (A1, A2) as follows: A samples keys mpk, sk!....,sk, according to the IBE scheme, and defines D to be the uniform distribution over the triplets ((j. mpk, )k,)) The analyst A2, which does not know the keys, first asks queries of the form q(j, mpk, sk) = mpk; for every bit & of mpk in order to reveal it. Then, it follows a strategy as in the previous section, i.e., it simulates an adversary À which foils natural mechanisms by translating each query query q: [m] [-1, issued by À by encrypting each q(j) for identity using mpk. Namely, the IBE scheme allowed the analyst to implement the attack of Hardt and Ullman (2014] and Steinke and Ullman 2015a), but without having to know the secret keys skı,... skm.
We can implement the IBE scheme using a standard kub encryption scheme: in the sampling process, we sample m independent pairs of public and secret keys [[pk,, Jyy of the original scheme, and define mpk = (pkj.... pk..). When encrypting message for identity j E [m]. we could simply encrypt it using pk, (part of mpk), which can only be decrypted using sky. The disadvantage of this approach is the large master public key mpk that it induces. Applying the encryption scheme with security parameter of X, the master key mpk will be of size - and not just A as the sizes of the secret keys. This means that implementing our balanced adversary with such an encryption scheme would result with a distribution over a large domain X,, which would not rule out the possibility to construct mechanism for distributions over smaller domains. Yet. Döttling and

---

showed that it is possible to construct a fully secure IBE scheme using small mpk of size only O(x log m) under standard hardness assumptions (e.g.. the Computational Diffie Helman problem Diffie and Hellman 1976 the hardness of factoring).
Garg 2021
1.3.2 Key-Agreement Protocol via Balanced Adversary
In order prove Theorem 1.6 we first explain what type of adversaries the theorem applies to. Recall that all known attacks (including ours), the adversary wraps a simpler adversary A that fails natural mechanisms. In particular, the wrapper A has two key properties:
A knows Eg~plar [x]] for the last query qe that it asks (becuase it equals to +. E Te(s). where éf is the wrapped query which part of A's view), and
2. If the mechanism attempts behave accurately in the first - rounds (e.g., it answers the empirical mean n Eres ((x) for every query q), then A, as a wrapper of A, will be able to ask a last query ge that would fail any computationally bounded last-round strategy for the mechanism.
We next show that any computationally bounded balanced adversary A that has the above two properties, can be used for constructing a key-agreement protocol. That is, a protocol between two computationally bounded parties P1 and P2 that enable them agree on value which cannot be revealed by a computationally bounded adversary who only sees the transcript of the execution. See Protocol 1.9
Protocol 1.9 (Key-Agreement Protocol P2) via a balanced adversary A (A1, A2)).
Input: 1 Let f = {(n) and X' X(n) be the number queries and the domain that used by the adversary A.
Operation:
P1 emulates A on imput for obtaining distribution DD over X (specified by sampling procedure), and samples i.i.d. samples S.
P2 initializes an emulation of A2 on input n.
For to
1. P2 receives the ith query qs from the emulated A and sends it to P1.
2. Pi computes yi Exes qi (i(x), and sends it to P2.
3. P2 sends yi as the ith answer to the emulated Ag-
Pi and P2 agree on Ez-D(u((x)).
The agreement of Protocol 1.9 relies on the ability of P1 and P.z to compute ExwDlge(x)) Indeed, P1 accurately estimate using the access to the sampling procedure, and P compute it based on the view of the analyst A (follows by Property [].
To prove the secrecy guarantee of Protocol 1.9 assume towards contradiction that there exists a com- putationally bounded adversary that given the transcript of the execution, can reveal E [4)())) Now consider the following mechanism for the ADA game: In the first & queries, answer the em- pirical mean, but in the last query, apply G on the transcript and answer its output. By the assumption on G, the mechanism will be able accurately answer the last query, in contradiction to Property 2
We note that Property D can be relaxed by only requiring that is able to provide a "good enough" estimation of Ez~zí ge (z)]. Namely, as long as the estimation provided in Property [ is better than the estimation that an adversary can obtain in Property (we prove that an n (1) multiplicative gap suffices), this would imply that Protocol 1.9 is weak key-agreement protocol, which can be amplified to fully secure one using standard techniques.
We also note that by requiring Game 1.3 that A₁ samples from D according to the sampling procedure, we implicitly assume here that sampling from D can be done efficiently (because A is
'CDH is hard with respect to group G of order if given random generator along with g" and g². for uniformly random b jp). as inputs, the probability that PPT algorithm compute 9b negligible.

---

assumed to be computationally bounded). Our reduction to key- agreemeet relies on this property. since if sampling from D could not be done efficiently, then P would not have been computationally bounded algorithm.
1.4 Perspective of Public Key Cryptography
Over the years, cryptographic research has proposed solutions to many different cryptographic tasks under a growing number of (unproven) computational hardness assumptions. To some extent, this state of affairs unavoidable, since the security of almost any cryptographic primitive implies the existence of oee functions [Impagliazzo and Luby, [989] (which in particular implies that P * P). Yet, all various assumptions can essentially be divided into two main types: private key cryptography and public key cryptography (Impagliazzo] [1955. The former type is better understood: A series of works have shown that the unstructured form of hardness guaranteed by one-way functions is sufficient to construct many complex and structured primitives such pseudorandom generators (Hástad
et al. 1999]. pseudorandom functions [Goldreich et al. 1986) and permutations [Luby and Rackoff 1988 commitment schemes [aor 1991] Haitner al. 2009), , universal one-way hash functions
Rompel 1990], zero- kroweleweeedee proofs Goldreich et al., 1987 and more. However, reductions are
much less common outside the one-way functions regime, particularly when constructing public-key primitives. In the famous work of Impagliazzo and Rudich 1989] they gave the first evidence that strictly stronger than one-way functions, by showing that key-agreement, which enables two parties to exchange secret messages over open channels, cannot be constructed from one-way functions in black-box way.
public key cryptography assumptions
Our work shows that a balanced adversary for the ADA game that has the structure of all known attacks, is primitive that belongs to the public-key cryptography type. In particular, if public-key cryptography does not exist, it could be possible to construct a computationally bounded mechanism that can handle more than (nn?) adaptive queries of balanced adversary (i.e., currently do not have a negative result that rules out this possibility).
1.5 Other Related Work
Nissim et al.
2018 presented variant of the lower bound of Steinke and Ullman| [2015a] that aims to reduce the number of queries used by the attacker. However, their resulting lower bound only holds for certain family of mechanisms, and it does not rule out all computationally efficient mechanisms.
Dinur et al. 2023 revisited and generalized the lower bounds of HHrdt and Ullman [2014) and
Steinke and Ullman [015a] by showing that they are a consequence of space bottleneck rather than a sampling bottleneck. Yet, as in the works by Hardt, Steinke, and Ullman, the attack by Dinur et al. relies on the ability to choose the underlying distribution D and inject secret trapdoors in it, and hence it utilizes an imbalanced adversary.
Recently, lower bounds constructions for the ADA problem were used as a tool for constructing (conditional) lower bounds for other problems, such as the space complexity of adaptive streaming algorithums [Kaplan et al., [021]] and the time complexity of dynamic algorithms SeroorthsssBimmelll et al. [2022]. Our lower bound for the ADA problem is qualitatively stronger than previous lower bounds (as the adversary we construct has less power). Thus, our lower bound could potentially yield new connections and constructions in additional settings.
1.6 Conclusion and Open Problems
In this work we present the balanced adversarial model for the ADA problem, and show that the existence of balanced adversary that has the structure of all previously known attacks is equivalent to the existence of public-key cryptography. Yet, we do not know what is the truth outside of the public-key cryptography world. Can we present different type of efficient attack that is based on weaker hardness assumptions (like one-way functions)? Or is it possible to construct an efficient mechanism that answer more than O(1²) adaptive queries assuming that public-key cryptography does not exist? We also leave open similar questions regarding the information theoretic case. We currently do not know whether is possible to construct an unbounded mechanism that answers exponential number of queries for any distribution D (regardless of its domain size).
7

---

In broader perspective, lower bounds such ours show that no general solution exists for a problem. They often use unnatural inputs or distributions and rely on cryptographic assumptions. They are important as guidance for how to proceed with problem, e.g., search for mechanisms that would succeed the underlying distribution from a "nice" family of distributions.
2 Preliminaries
2.1 Notations
We use calligraphic letters to denote sets and distributions, uppercase for random variables, and lowercase for values and functions. For E N, let [n] (1,2.... n). Let neg(n) stand for negligible function in n, i.e., a function (nn such that for every constant e > 0 and large enough n holds that v(n) < n ". For N we denote by 1" the n-size string 1 1 (n times). Let PPT stand for probabilistic polynomial time. We say that pair of algorithms = (A1, A2) is PPT both A and A2 PPT algorithms.
2.2 Distributions and Random Variables
Given a distribution D, we write D, meaning that is sampled according to For multiset S, we denote by Us the uniform distribution over S, and let I + S denote that æ ~ Us. For distribution and value
N, we denote by D the distribution of i.i.d samples from D. For distribution D over A' and query X + [-1,1], we abuse notation and denote (()) Ea>Dig [g()), and similarly for (I1,..., E X abuse notation and denote
((S) = Ez-sl9(z)) = - Zz.
2.3
Cryptographic Primitives
2.3.1 Key Agreement Protocols
The most basic public-key cryptographic primitive is a (1-bit) key-agreement protocol, defined below. Definition 2.1 (key-agreement protocol). Let be two party protocol between two interactive PPT algorithms Pi and P2, each outputs 1-bit. Let π (1a) denote random execution of the protocol on joint input 1 (the security parameter), and let O O and Tn denote the random variables of P1 output, P2 's output, and the transcript (respectively) in this execution. We say that π is an (a, B)- aeey-agreement protocol if the following holds for any PPT ("eavesdropper") A and any N:
Agreement: Pr[O), 0% 2 an)) and
Secrecy: Pr(A(T.) = 0 < (n).
We say that a is fully-secure key-agreement protocol if is an -neg(n), 1/2 nng(n))) agreement protocol.
2.3.2 Identity-Based Encryption
An Identity-Basse Based Encryption (IBE) scheme [Shamir 1984 Cocks 2001 Boneh and Franklin 2001
consists of four PPT algorithms (Setup, KeyGen, Encrypt, Decrypt) defined as follows:
Setup(1>): given the security parameter X, it outputs master public key mpk and master secret key msk.
KeyGen id): given the master secret key msk and an identity id [ni], it outputs decryption key skia-
Encrypt(mpk, id, m): given the master public key mpk, and identity id [m]] and message m, it outputs ciphertext ct.
Decrypt (skia, ct): given a secret key skia for identity id and a ciphertext ct, outputs a string m.
The following the properties of such encryption scheme:

---

Completeness: For all security parameter X, identity id E [n] and message m, with probability 1 over (mpk, msk) ~ Setup(1^) >) and skid ~ KeyGen(mske id) it holds that Decrypt(skit Encrypt(mpk, id, m)) =
Security: For any PPT adversary A = (A1, A2) it holds that:
Pr[INDA BR
1/2 2 neg(A)
where IND is shown in Experiment 2.2
Experiment 2.2 (IND
1. (mpk, msk) ~ Setup(1^).
2. (id", (mf...., mb), (ml:..., mt),,t) ~ A KeyGen(mak, (mpk) where |m - m for
every E [k] and for each query by A to KeyGen( msk, :) we have that id + id
3. Sample b + {0, 1).
4. Sample ct; Emcrypt(mpk, id" mor every [k].
A KeyGGn((msk.) (mpk,
5. V' DeyGen(msk,"" we have that id & id".
st) where for each query id by A to
6. Output if b' and 0 otherwise.
Namely, the adversary chooses two sequences of messages (mf..... mg) and (ml...., m(). and gets encryptions of either the first sequence the second one, where the encryptions made for identity id" that the adversary does not hold key (not allowed to query KeyGen on input id"). The security requirement means that she cannot distinguish between the two cases (except with negligible probability).
Theorem 2.3 (Döttling and Garg 2021)). Assume that the Computational Diffie-Hellmane (CDH)) Problem hard. Then there exists an IBE scheme & (Setup, KeyGen, Encrypt, Decrypt) for n identities such that given security parameter A, the master keys and each decryption key are of size 0() log n
2.4 Balanced Adaptive Data Analysis
As described in the introduction, the mechanism plays a game with a balanced adversary that consists of (isolated) algorithms: sampler Ai, which chooses distribution D over domain X' and provides n i.i.d. samples to M, and an analyst A2, which asks the adaptive queries about the distribution. Let ADA,,, [M, A (2)) denote Game I.3 on public inputs n the number of samples, L the number of queries, and X' the domain. We denote by output 1 the case that M fails in the game, and 0 otherwise. Since this work mainly deals with computationally bounded algorithms that we would like to model as PPT algorithms, we provide and in unary representation. We also assume for simplicity that X' finite, which allows to represent each element as a binary vector of dimension [[], and we provide the dimension in unary representation as well.
All previous negative results (Hardt and Ullman 2014)] Steinke and Ullman (015a], and Dinur et al. 2023)) ) where achieved by reduction to restricted family of mechanisms, called natural mechanisms (Definition 1.8). These algorithms that only evaluate the query the sample points they given.
For natural mechanisms (even unbounded ones), the following proven. Theorem 2.4 (Hardt and Ullman (2014), [Steinke and Ullman (2015a]). There exists a pair of PPT algorithms = (Az, A2) such that for every natural mechanism and every large enough n and f = ((?)) it holds that
Pr ADA (2000m] [M. = 3/4.
(1)
2.2 with & (i.e., encrypting a single message). Yet, it can extended to any sequence of messages using simple reduction. 'The construction can also be based on the hardness of factoring.
'The IBE security experiment usually described Experiment 2.2

---

In particular. Ar always chooses the uniform distribution over [2000n], and Ag uses only queries over the range {-1.0,1}
Constructing a Balanced Adversary via IBE
We prove that if an IBE scheme exists, then there is an efficient reduction to natural mechanisms that holds against any PPT mechanism, yielding a general lower bound for the computational case.
Theorem 3.1 (Restatement of Theorem 1.5]. Assume the existence of an IBE scheme & that supports m 2000n identities with security parameter À = X(n) s.I. S poly(X) (e.g. À = n using keys of length k(n). Then there exists PPT balanced adversary such that for every PPT mechanism M it holds that
(A1, A2) and = O
Pr A.A, (,x (0.1)2x [M. A] A] =
> 3/4 neg(n).
The proof of the theorem given the supplementary material. Note that we use a domain with log| X 2 log x- O(1), and by applying Theorem 2.3 the lower bound holds for k = O(-llgnn)
under the CDH hardness assumption.
Reduction to Natural Mechanisms Implies Key Agreement
We prove that any PPT balanced adversary A (Ai, A2) that has the structure of all known lower bounds (Hardt and Ullman (2014), Steinke and Ullman (0115a), Dinur et al. 2023 and ours in Section 3). be used construct key-agreement protocol.
All known constructions use adversary A that wraps the adversary A for the natural mechanisms case (Theorem 2.4p by forcing every mechanism M to behave naturally using cryptography. In particular, they all satisfy Properties and from Section 1.3.2
The formal statement is given in the following theorem. The proof provided in the supplementary material.
Theorem 4.1 (Restatement of Theorem 1.6 Assume the existence of PPT adversary A = (Ai, and functions { f(n) S poly(n) and X X(n) with log| S poly such that the following holds: Let E N and consider random execution of ADA, n,ex' [M, A) where M is the mechanism that given sample S and query q. answers the empirical mean (SS). Let Dn and Qu be the (nw's of the) values Df and q = qe (the last query) in the execution (respectively), let Tn be the transcript of the execution between the analyst A and the mechanism M (i.e., the queries and answers), and let Vn the view of Az at the end of the execution (without loss of generality, its imput, random coins and the transcript). Assume that
1. 3 PPT algorithm F s.t. Vn E N: Pr[[F(V..) (D,)) S 1/10| 2 1- neg(n), and
2. A PPT algorithm G and Vn E:
S 1/10] s 1/4 + neg(n).
Then using and F is possible to construct a fully-secure key-agreement protocol.
Note that Assumption I in Theorem 4.1 formalizes the first property in which the analyst knows good estimation of the true answer, and the PPT algorithm is the assumed knowledge extractor. Assumption 2 in Theorem formalizes the second property which states that the mechanism, which answers the empirical mean along the way, will fail in the last query, no matter how it chooses to act (this behavior is captured with the PPT algorithm G), and moreover, it is enough to assume that this requirement only holds with respect to to transcript of the execution, and not with respect to the view of the mechanism.
We refer to the full version of the paper, given in the supplementary material, for all the missing proofs.
10

---

Acknowledgments and Disclosure of Funding
Kobbi Nissim is partially supported by NSF grant No. CNS-2001041 and gift to Georgetown University. Uri Stemmer is partially supported by the Israel Science Foundation (grant 187 1/19) and by Len Blavatnik and the Blavatník Family foundation. Eliad Tsfadia is partially supported by the Fulbright Program and gift to Georgetown University.
References
R. Bassily, K. Nissim, A. D. Smith, T. Steinke, U. Stemmer, and J. Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the 48th Annual ACM SIGACT Symposium Theory of Computing, STOC 2016, pages 1046-1059, 2016.
A. Beimel, H. Kaplan, Y. Mansour, K. Nissim, T. Saranurak, and U. Stemmer. Dynamic algorithms against adaptive adversary: generic constructions and lower bounds. In STOC, pages 1671-1684 ACM, 2022.
G. Blanc. Subsampling suffices for adaptive data analysis. CoRR, abs/2302.08661, 2023.
D. Boneh and M. K. Franklin. Identity- -based encryption from the weil pairing. In J. Kilian, editor, Advances Cryptology CRYPTO 2001, 21st Annual International Cryptology Conference, Proceedingg, volume 2139, pages 213-229, 2001.
C. C. Cocks, An identity based encryption scheme based on quadratic residues. In Cryptography and Coding, 8th IMA International Conference, Proceedings, volume 2260, pages 360-363, 2001.
Y. Dagan and G. Kur. A bounded-noise mechanism for differential privacy. In Conference Learning Theory, volume 178, pages 625-661. PMLR, 2022.
W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Trans. Inf. Theory, 22(6): 644-654 1976.
I. Dinur, U. Stemmer, D. Woodruff, and Zhou, On differential privacy and adaptive data analysis with bounded space. CoRR, abs/2302.05707, 2023.
N. Döttling and S. Garg. Identity-based encryption from the diffic-hellman assumption. J. ACM, 68 (3):4:11-14:6,, 2021.
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. Roth. Generalization in adaptive data analysis and holdout reuse. In Advances in Neural Information Processing Systems (NIPS), 2015a.
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and Roth. The reusable holdout: Preserving validity in adaptive data analysis. Science, 349(6248):636666) 666-66888666 2015b.
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. L. Roth. Preserving statistical validity in adaptive data analysis. In STOC, pages 117-126. ACM, 2015c.
Elder. Challenges bayesian adaptive data analysis. CoRR, abs/1604.02492, 2016. URL http///xivv.ogggbb////// 2ttp///aab/110004292222
V. Feldman and T. Steinke. Generalization for adaptively-chosen estimators via stable median, In Proceedings of the 30th Conference on Learning Theory, COLT 2017, volume 65, pages 728-757. PMLR, 2017.
V. Feldman and T. Steinke. Calibrating noise to variance in adaptive data analysis. In Conference On Learning Theory, COLT 2018, volume 75, pages 535-544. PMLR, 2018.
B. Fish, L. Reyzin, and B. Rubinstein. Sampling without compromising accuracy in adaptive data analysis. In Algorithmic Learning Theory, ALT 2020, volume 1 117, pages 297-318. PMLR, 2020.
O. Goldreich, Goldwasser, and Micali. How to construct random functions. Journal of the ACM, 33(4):792-807, 1986.

---

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC 1987, pages 218-229, 1987.
I. Haitner, M. Nguyen, S. Ong, O. Reingold, and S. Vadhan. Statistically hiding commitments and statistical eero-knowledge arguments from any one-way function. SIAM Journal on Computing. 39331:153-1218, 2009.
M. Hardt and G. Rothblum. A multiplicative weights mechanism for privacy-preservine data analysis. In Proc. 51st Foundations of Computer Science (FOCS), pages 61-70. IEEE, 2010.
M. Hardt and J. Ullman. Preventing false discovery in interactive data analysis is hard. FOCS, pages 454 3544463,42 2014.
Håstad, R. Impagliazzo, L. A. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364-133) 1999.
R. Impagliazzo. personal view of average-case complexity. Proceedings of the Tenth Annual Structure in Complexity Theory Conference, pages 134-147. IEEE Computer Society, 1995.
R. Impagliazzo and M. Luby. One-way functions are essential for complexity based cryptography (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, pages 230-235, 1989.
R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. In Annual ACM Symposium Theory of Computing (STOC), pages 44 44-61, 1989.
C. Jung, K. Ligett, Neel, A. Roth, Sharifi-Malvajerdi,, and M. Shenfeld. new analysis of differential privacy's generalization guarantees. In ITCS, volume 151 of L/PIcs, pages 31:1-31:17. Schloss Dagstuhl- cecibniz-Zentrum für Informatik, 2020.
H. Kaplan, Y. Mansour, K. Nissim, and U. Stemmer. Separating adaptive streaming from oblivious streaming using the bounded storage model. CRYPTO (3), volume 12827 of Lecture Notes in Computer Science, pages 94-121. Springer, 2021.
A. Kontorovich, M. Sadigurschi, and U. Stemmer. Adaptive data analysis with correlated observations. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 11483- 11498. PMLR, 2022.
M. Luby and C. Rackoff. How to construct pseudorandom permutations from pscudorandom functions. SIAM Journal on Computing, 17(2):33-3386, 1988.
M. Naor. Bit commitment using pseudorandomnes:. Journal of Cryptology, 4(2):151-158, 1991.
K. Nissim, A. D. Smith. T. Steinke, U. Stemmer, and J. R. Ullman. The limits of post-selection generalization. In NeurlPS, pages 6402-6411, 2018.
R. M. Rogers, A. Roth, A. D. Smith, and O. Thakkar. Max-information, differential privacy, and post-selection hypothesis testing. In IEEE 57th Annual Symposiun on Foundations of Computer Science, FOCS 2016, pages 487-494, 2016.
Rompel, One-way functions are necessary and sufficient for secure signatures. In Annual ACM Symposium on Theory of Computing (STOC), pages 387-394, 1990.
D. Russo and J. Zou. Controlling bias in adaptive data analysis using information theory. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016, volume 51, pages 1232-1240. JMLR.org, 2016.
A. Shamir. Identity- cryptosystems and signature schemes. In Advances in Cryptology. Proceedings of CRYPTO 1984, volume 196, pages 47-53, 1984.
M. Shenfeld and K. Ligett. A necessary and sufficient stability notion for adaptive generalization. In NeurIPS, pages 1488-11149,, 2019.
12

---

A. D. Smith. Information, privacy and stability in adaptive data analysis. CoRR, abs//a/s.sno. 176.000800 2017.
Steinke and J. Ullman. Interactive fingerprinting codes and the hardness of preventing false discovery. In COLT, pages 1588-1628, 2015a.
T. Steinke and J. Ullman. Between pure and approximate differential privacy. CoRR, 0os//1511.0099 2015b.
13


Reviews:
[{"review_id": "Ij8eRfSDM0", "reviewer": "Reviewer_vTGp", "summary": "The paper studies limitations of \"adaptive data analysis\" with a focus on \"computational assumptions\" that are used for proving such limitations (i.e., lower bounds).\n\nA mechanism $M$ answers $m=m(n)$ queries (almost) correctly, if it succeeds in the following game for every distribution $D$ and PPT adversary $A$. The mechanism is given n iid samples from D. Then the adversary $A$ asks $m$ adaptive statistical queries $q_1,\\dots,q_m$ from the mechanism $M$. The mechanism succeeds if all of its answers are within $\\pm 1/10$ of the true answers with respect to distribution $D$.\n\nPrevious work has shown that at most $m=\\Theta(n^2)$ queries can be answered adaptively by computationally bounded mechanisms, assuming one-way functions exist. Their proof uses private-key encryption schemes (whose existence is equivalent to one-way functions) and a reduction from a class of mechanisms, called \"natural\". The previous lower bound also implicitly assumes a rather powerful adversary who both chooses the distribution D as well as the queries $q_1,...q_m$.\n\nThis paper starts by making the (interesting) observation that if an adversary already knows the distribution $D$, then it won't have a meaningful interest in making the queries. So, in some sense, the previous lower bounds are not as meaningful as one wishes in real world scenarios; this raises the hope for getting positive results that go around the lower bounds by leveraging this observation.\n\nIn summary, the main result of the paper is bootstrap the previous lower bound to a model to a weaker adversarial model.\nIn more detail, the contributions of this paper are as follow:\n\n1. A new formal model of security called the \"balanced model\" is defined, in which the adversary is split into two entities that do not communicate. The first adversary $A_1$ picks the distribution $D$ and the iid samples. The second adversary $A_2$ picks the adaptive queries.\n2. It is shows that assuming the stronger primitive of secure public-key encryption (as opposed to just OWFs) one can still extend the previous lower to the balanced model.\n3. The assumption of public-key encryption is somehow justified, by showing any lower bound with minimal properties (that hold for current lower bound proofs) would lead to key agreement protocols (which is a close primitive/assumption to public key encryption).", "questions": "My main question is about the meaningfulness of the balanced attack model which is described above.", "limitations": "The limitations are also elaborated in the \"weakness\" section of the review above.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The main strengths of the paper:\n\n* excellent writing quality. my only criticism is that the definition used in *previous* work is not presented formally, and one cannot determine the exact details from the informal text. this is needed for making a fully detailed comparison between the new definition and the old one, because this is a major part of this paper.\n\n* revisiting a previous lower bound for an important problem from a natural practical perspective.", "weaknesses": "My criticisms of the paper are the following:\n\n1. About the model (Item 1 above): I am not sure if the new split (balanced) model is adding much value actually. suppose we fix a mechanism $M$ and look for a balanced 2-part polynomial-size adversary $(A_1,A_2)$ against $M$. In this setting, it seems meaningless to say that only $A_1$ knows the distribution D, because one can fix the distribution $D$ that $A_1$ picks to its \"best possible\" distribution (against $M$). This way, $A_2$ also would be aware of this distribution implicitly, as it can depend on it. In other words, one can see this argument as giving shared coin to $A_1,A_2$, and then fixing it to its best value (which leads to no communication between $A_1$ and $A_2$). \n\nI shall add that, from a game theoretic perspective, it would seems a preferred and stronger lower bound if we could use *one* fixed adversary strategy that bounds the power of every computationally limited mechanism. However, for the sake of proving lower bounds, it is fine if we'd pick the adversary $A_M$ based on the mechanism $M$. \n\n2. About the technical depth of the lower bound (Item 2 above). This proof seems like a rather straightforward adaptation of the previous proof. but using IBE (or a bunch of public key encryption schemes) instead of Secret Key Encryption schemes. This is a mild criticism, as I am in general in favor of simpler proofs. But this proof seems like a simple proof for a new question rather than a simple proof for a question that existed before, so I am a bit torn here.\n\n3. About necessity of Key Agreement (Item 3 above): I am not a fan of investing in weakening assumptions that are used for *lower bounds*. as I believe there is a fundamental difference between weakening assumptions behind positive results vs those of negative results. When we weaken the assumption behind, say, public key encryption from an assumption $P_1$ to a weaker assumption $P_2$, it means that the schemes that would be deployed *right now* would not break at an unknown time (with potential catastrophic consequences) even if $P_1$ turns to be false. However, when we weaken the (still widely believed) computational assumption behind a a *lower bound*, is is a completely different story, because even using an assumption as strong as IO to prove an impossibility has the same practical consequence as using OWFs. The two scenarios would diverge (and a weaker assumption would start to look interesting) after breaking every IO scheme, which is most likely never gonna happen, and the weakening assumption changes nothing right now. So, in summary, when it comes to lower bounds I am totally fine with using something as strong as any assumption that seems strong enough for the foreseeable future.\n\nupdate: the issues above were discussed and I am happy with author(s)' response.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the comments. In the following we would like to respond to specific points you make. \n\nW1: In our model, $A_1$ is publicly known. It defines a publicly known prior, similarly to the Bayesian ADA model of Elder [2016] (mentioned in Section 1.2). This way, $A_1$ captures the common knowledge that both the mechanism $M$ and the analyst $A_2$ have about the underlying distribution. We agree that showing that for every $M$ there exists a balanced adversary $A=(A_1,A_2)$ that fails it does not add much value. However, showing that there exists a publicly known balanced adversary $A=(A_1,A_2)$ that fails all mechanisms (as we do) is different and a significant improvement over the previous lower bounds. (In fact, our lower bound in Theorem 1.5 is stronger than what is required for a lower bound as it also uses a publicly known analyst $A_2$ - even though the sampler $A_1$ and the analyst $A_2$ are publicly known and cannot communicate with each other, they fail any computationally bounded mechanism). \nWe will add text to clarify the advantage of having $A_1$ publicly known.\n\nW2: The criticism about the lower bounds of Hardt and Ullman [2014] and Steinke and Ullman [2015a] is not new and prior work has attempted at addressing them with only partial success. For example, Elder [2016] (mentioned in section 1.2) considered a similar balanced setting. He proved a bound of $n^4$ for a limited family of mechanisms. Our Thm 1.5 gives a (stronger) bound of $n^2$ that holds for all computationally bounded mechanisms. \n\nW3: We believe that determining the minimal required hardness assumption for a lower bound (in general) is informative. Not necessarily because of immediate practical consequences, but because it can reveal the structure of the problem and help steer the research going forward.\n\nFor example, as mentioned in lines 113-119, our result implies that the existence of a certain kind of balanced adversaries that fail any *unbounded* mechanism yields an *information theoretic* key agreement protocol (i.e., where the secrecy holds even if the adversary that sees the transcript is computationally unbounded).  As information theoretic key agreement protocols do not exist, we conclude that such balanced adversaries do not exist either. This is in contrast with the imbalanced model for which we know that adversaries (of the same kind) that fail any unbounded mechanism do exist (Steinke and Ullman [2015a]). This gives the first evidence that there might be a separation between the computational and information theoretic setting under the balanced adversarial model (in contrast with the imbalanced model).\n\nRegarding the definition used in previous works:\nIn line 59 we explain that in previous works, the adversary (i.e., the analyst) is the one that chooses the distribution at the outset of Game 1.1. This is equivalent to playing against adversaries $A=(A_1,A_2)$ in the following game: (1) $A_1$ chooses a distribution $\\cal{D}$ and sends a state $st$ to $A_2$. (2) $M$ receives $n$ i.i.d. samples from $\\cal{D}$, and (3) $M$ and $A_2$ play Game 1.1. We will better explain it in our paper.\nThe difference from our model is that $A_1$ is allowed to send a state $st$ to $A_2$ after choosing the distribution. An additional (minor) difference is that we chose in our model to let $A_1$ also provide the i.i.d. samples to $M$. This is only useful for Thm 1.6 as we need there that choosing $\\cal{D}$ and sampling from $\\cal{D}$ are both computationally efficient (which are simply captured by saying that $A_1$ is computationally bounded). We mentioned this implicit assumption in lines 218-222. \n"}, {"review_id": "ro0ebASdsq", "reviewer": "Reviewer_Mqg2", "summary": "The paper proposes to consider balanced adversaries for ADA. Under the public-key assumptions, the paper proves that ", "questions": "1. Is there any real-world machine learning application of the results?\n\n\n\n", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper assumes a more practical threat model for ADA.\n\n2. The theoretical results in this paper seem to be well-supported. I am not an expert in this research direction, so I am not sure about my judgement.\n\n", "weaknesses": "1. There is no discussion about the real-world machine learning applications of the results.\n\n2. There is no conclusion section to summarize the paper. The paper ends after Section 4 and makes me feel that the paper is not complete.\n\n3. The theoretical results are based on the assumption that public-key cryptography exists.\n\n4. I am not an expert in this research direction, and I feel that this paper is not easy to follow because there are many terms. I suggest that the paper could add a table to explain the terms used in the paper to improve the readability.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. We will implement your suggestions to make our paper more broadly accessible.\n\nStatistical queries are basic building blocks in ML and statistics. Our result is about the possibility of accurately answering adaptively chosen statistical queries and hence has consequences to ML and statistics. \n\nThe problem we are addressing is not new and our lower bound improves over previously known bounds. Overall, our and previous bounds show that it is impossible to construct efficient mechanisms that answer more than $n^2$ queries adaptively. However, prior work left open the possibility that such mechanisms exist when the underlying distribution is not chosen by the analyst. Our lower bound closes this gap.\n\nLower bounds such as ours show that no general solution exists for a problem. They often use unnatural inputs or distributions and rely on cryptographic assumptions (our lower bound relies on a well accepted assumption). They are important as guidance for how to proceed with a problem, e.g., search for mechanisms that would succeed if the underlying distribution is from a \"nice\" family of distributions.\n"}, {"review_id": "pfRiPCUEG0", "reviewer": "Reviewer_CEqx", "summary": "Adaptive data analysis considers the setting where a mechanism and an analyst play a game against each other, where for $k$ sequential rounds, the analyst issues queries to a mechanism which holds a dataset of size $n$ sampled from a distribution, the mechanism returns a response, and the analyst chooses the next query accordingly. The mechanism wins the game if all responses are close to the expected value of the queries on the dataset.\n\nUsing tools developed in the context of differential privacy, it was proven that a mechanism can respond to up to $k = O(n^{2})$ queries, while winning the game with high probability. At the same time, it was proven that if the number of queries exceeds $O(n^{2})$, there exists an analyst that can win the game. This lower bound assumes the analyst can choose the distribution, and is based on the cryptographic assumption of the existence of fingerprinting codes. This imposes an asymmetry between the power and knowledge of the analyst and mechanism which is unnatural, since an analyst that knows the distribution has no reason to query the mechanism.\n\nThe current work solves this problem, by proving a similar lower bound for a balanced setting, where the distribution is chosen by a third player. This proof is based on the stronger cryptographic assumption of the existence of public-key cryptography. The authors also prove that the lower bound does not hold, without this assumption, proving a separation between the balanced and unbalanced settings.", "questions": "In section 2.4 the authors mention the sample size, number of queries and dimensions are provided in unary representation. I would appreciate if the authors can clarify how this affects the computational complexity, and how they justify this decision.", "limitations": "N/A", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The deep asymmetry that was used in the proof the previous lower bounds was undesired, and left an open question whether it is essential, since it is not justified in most natural settings. Solving this open question is an important step in understanding the dynamics of adaptive data analysis. They are based on a novel addition to the existing lower bound framework, and are presented in a clear and formal way.\n\nThe distinction between the two cryptographic assumptions required in both cases, might hold implications for cryptography as well.", "weaknesses": "I have only one minor comment to add. It seems like the authors use another implicit assumption throughout the paper, that the mechanism knows the analyst it is playing against. If this was not the case, the separation of the analyst into two analysts (one choosing the distribution and the other issuing the queries) will be meaningless, as we could always consider the case where the first analyst always chooses the same distribution, and so the second one can use that information while the mechanism cannot. \n\nI do not bring this up as a limitation of the work, but as a recommendation to clarify the setting, so to avoid confusion by the reader.\n\n=======\n\n**Edit after rebuttal discussion:**\n\nI have no further concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your positive review. In the following we would like to respond to specific points you make.\n\nRegarding the weakness:\n\nIn our model, the sampler $A_1$ is publicly known (similar to the Bayesian ADA model of Elder [2016] as we note in Section 1.2). This way, $A_1$ captures knowledge about the underlying distribution which is known to both the mechanism $M$ and the analyst $A_2$. In principle, it suffices that the lowerbound would hold even if the code of the analyst $A_2$ is not publicly known. However, our lower bound in Thm 1.5 holds even if $A_2$ is publicly known (this makes it a stronger bound). We plan to include text to clarify this point.\n\nRegarding the question:\n\nThe unary representation is commonly used in the cryptography community to allow algorithms run in polynomial time in a parameter. We basically want to say that an algorithm $A$, given ($n,\\ell,d$), runs in poly($n,\\ell,d$) time (i.e., that $A$ is a PPT algorithm). But the binary description of $n,\\ell,d$ is of logarithmic size in $n, \\ell, d$. The unary representation is a convenient way to allow $A$ run in time polynomial in the values $n,\\ell,d$. \n"}, {"review_id": "6EooTNu88H", "reviewer": "Reviewer_Ejfp", "summary": "The paper considers balanced adversaries that do not have access to the underlying distribution and instead interact with an oracle adversary that chooses the distribution and samples points from it. The authors show that with this more realistic adversarial setting, they can improve the previous known lower bounds for adaptive data analysis.", "questions": "I am confused why the authors have the value 2000n in Theorem 2.4. Is there something particular about this value 2000, and if so how do they arrive at this? Can this be a parameter k where k does not take large values?", "limitations": "I don't feel there is any direct or evident negative societal impact of this work.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The authors consider a more realistic balanced adversary that does not have access to the underlying distribution. This adversarial setting is novel and allows for better bounds on the adaptive data analysis.", "weaknesses": "While considering this balanced adversary is more practical, I would suggest the authors to include a summary table comparing their setting, assumptions and their bounds with respect to the prior works. This would better highlight the differences and focus more on the key contribution of the paper.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. In the following we would like to respond to the specific points you make:\n\nRegarding the weakness:\nThank you for the suggestion. We will add a comparison table.\n\nRegarding your question:\nWe are following Steinke and Ullman [2015a] who used 2000n as a large enough domain size that allows their attack against natural mechanisms to work. For the theoretical result, the constant 2000 is not important; any large enough constant would work (see Sections 3.3-3.4 in their arxiv version - CoRR, abs/1410.1228). The same constant is also used in other works that rely on their lower bound (e.g., see Algorithm 4 in Dinur et al. [2023] - CoRR, abs/2302.05707)."}]

Author rebuttal:

Meta-review: This paper gives a lower bound for answering adaptive statistical queries about a dataset. Prior work has established the lower bound using an adversary that knows the distribution from which the dataset is sampled, making it rather unrealistic. This work introduces a weaker \emph{balanced} adversary which consists of two separated algorithms (a sampler that chooses the distribution and provides the samples to the mechanism, and the analyst who chooses the adaptive queries, but does not have a prior knowledge of the underlying distribution). It extends known lower bounds to this weaker adversary. This result significantly improves our understanding of the hardness of adaptive data analysis.
Decision: Accept (spotlight)