- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper studies the group testing problem with the goal of providing formal privacy guarantees. They introduce a notion of plausible deniability for this setting called -deniability. We recall that in group testing, there is a ground set of items, and some unknown subset of `defective' items. The goal is to identify with a minimal number of group tests; each group test is a query corresponding to a subset . In the basic setting, the query returns the value of . This paper studies the setting where the responses to the queries are public, and suggests the notion of -deniability to help preserve the privacy of individuals (identified with the elements of ). A testing procedure (i.e. a choice of a family of subsets to query) is -deniable if for every element and every sequence of responses to tests , there are some distinct (admissible) subsets of that could also have generated the sequence of responses. The accuracy of a deniable group test is measured by the ratio of the number of admissible sets which are marked as potentially defective to the true number of defective element.
This paper has the following contributions:
- Posing the problem of deniable group testing described above.
- A non-adaptive DGT algorithm that for -deniability and , achieves accuracy.
- An adaptive DGT algorithm (named Submartingale) that achieves -deniability for . There is no theoretical accuracy bound for this problem.
- An empirical evaluation of Submartingale.
Critical strengths
I think this is a very interesting problem, and based on my AI-assisted survey of the literature, seems genuinely novel. I think the direction of investigation undertaken by the authors makes sense. The Submartingale algorithm is involved, and the authors give a proof of deniability as well.
Critical weaknesses
There are several points in the paper which I'm confused about, I've posed several questions below that I would ask the authors to address. I think this direction of investigation taken up in this work is very promising, but the paper requires much more polish before it is ready for publication. Also the comparison with related work needs to be more concrete, and quantitative, as far as possible.
Questions for authors
- Can you clarify why the definition requires admissible sets that can generate the same solution, as opposed to just uninfected individuals for any given individual that who (if infected) would explain the feedback vector equally well?
- Is the lower bound true only for non-adaptive algorithms, or also adaptive ones?
- What is the distribution of the defective set in the experiments? The text states only that has exactly ones and that inputs are random; please state whether the positions are a uniformly random -subset drawn independently in each of the runs. Note also that the average-case accuracy in Section 3 is defined with uniform over , whereas the experiments fix .
- The comparison with related work is too weak. I understand the advantages of deterministic algorithms over a randomized approach like a DP formulation, but a more comprehensive evaluation is needed, especially in terms of the `cost' i.e. the number of tests needed per infected person. How does this approach compares in quantitative terms with other attempts to achieve privacy in group testing?
Our response
Thank you very much for your comments and feedback.
Q1 Group Testing decodes a candidate set of infected elements; therefore, pointing out just δ infected elements may not be enough. In particular, there is no guarantee that they would result in the same test results as the unknown actual set of up to d infected elements (as parameters δ and d are independent of each other, in particular, δ could be much smaller than d). The intuition behind our definition is that, for any execution of testing algorithm that may involve a
denying'' element, there are at least $\delta$isomorphic'' executions of the testing algorithm (i.e., with same results) that do not involve the denying element. We have included an explanation in the revised version of the manuscript.Q2 It also holds for adaptive algorithm with a monotonic feedback, which is natural for several adaptive GT algorithms, for instance, a selector-based approach that applies a sequence of specific non-adaptive tests but each to the domain reduced by the elements decoded in the runs of the preceding non-adaptive iterations. Because tests are monotonic, in the sense that for each test number i and each pair of defective sets S1⊂S2, the i-th test applied while testing S1 is a superset of the i-th test applied while testing S2. We have claried this in the revised version of our paprer.
Q3 In each of the m runs, the defective set is drawn independently and uniformly at random among all d-subsets of N; In the revised version of our paper the Section 5.2 now states this explicitly. The reviewer is right that the plots show the average accuracy conditioned on ∣S∣=d, rather than under the uniform distribution over SD of Section 3. This choice is deliberate. The algorithm uses only the upper bound D, a standard assumption in group testing, and not the actual number d of defective elements; Parameter d largely determines its accuracy. We also stress that δ-deniability holds deterministically for every input (Theorem~2); only the accuracy Δ depends on the input. For this reason, we report the full distribution of Δ as box plots rather than only its mean: for unfavourable inputs, Δ may be far from its expectation, but, except for specific settings discussed in Section 5.2 and Appendix D, it remains of the order of δ+1.
Q4 Let us remark that historically, the first works on Group Testing focused only on a single aspect: the number of tests itself, trying to explore the impact of the number of defective elements to the number of tests, c.f., Dorfman 1943 and Kautz 1964. Similarly, the recent introduction of differential privacy in Group Testing of Gonen et al. focuses on a single aspect (privacy) on the number of tests. While that work applies only to randomized testing algorithms, our deniability applies also to deterministic tests. Moreover, our approach is more holistic, as we explore the impact of deniability on both the accuracy and the number of tests, leaving the investigation of other aspects to the follow-up work.
A quantitative comparison appears to be very challenging because, to the best of our knowledge, all existing related works rely on fundamentally different assumptions regarding the allowed techniques (in particular, our framework uses neither cryptography nor randomization). Nevertheless, we have expanded our discussion of the related work and strived to provide a more quantitative comparison (including a dedicated new section in the related work).
Please note that in addition to submitting the revised manuscript, we have also included a version with highlighted changes in the supplementary materials to facilitate the review of our revisions.