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).
A 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$.
Previous 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$.
This 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.
In summary, the main result of the paper is bootstrap the previous lower bound to a model to a weaker adversarial model.
In more detail, the contributions of this paper are as follow:
1. 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.
2. 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.
3. 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).
Strengths
The main strengths of the paper:
* 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.
* revisiting a previous lower bound for an important problem from a natural practical perspective.
Weaknesses
My criticisms of the paper are the following:
1. 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$).
I 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$.
2. 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.
3. 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.
update: the issues above were discussed and I am happy with author(s)' response.
Questions
My main question is about the meaningfulness of the balanced attack model which is described above.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The limitations are also elaborated in the "weakness" section of the review above.