acceptodds
Under review as a conference paper at ICLR 2027

Deniable Group Testing

Abstract

Group Testing is a well-established area of searching and learning under uncertainty. One of its major applications is testing individuals for hidden defects, e.g., diseases or other sensitive characteristics. Surprisingly to these applications, very little has been done to assure privacy within the testing process and output. We introduce a new privacy concept, called -deniability, which guarantees the following with respect to the outputted set: (i) each of the defective individuals is in the outputted set; however, (ii) for each outputted individual there are at least possible defective sets not containing that give the same testing results. In other words, unless an observer could test negatively any pointed out individuals, it cannot be certain about defectiveness of any particular outputted individual. We show that any monotonic testing strategy can output a set at least times bigger than the number of defective elements, for some defective sets under binary testing feedback. For -capped quantitative feedback, , the size of some output sets could be at least times bigger than the input set. On the positive side, we design a few testing strategies and prove that they guarantee -deniability and smooth trade-off between the number of tests and the overhead of the size of the output set over the number of defective individuals, called accuracy.

Primary area:
learning theory
Keywords:
Group Testing (GT), Deniability

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_Sf6ZOpenReview ↗
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 δ\delta-deniability. We recall that in group testing, there is a ground set of NN items, and some unknown subset S⊂NS\subset N of `defective' items. The goal is to identify SS with a minimal number of group tests; each group test is a query corresponding to a subset T⊂NT\subset N. In the basic setting, the query TT returns the value of ∣T∩S∣|T\cap S|. This paper studies the setting where the responses to the queries are public, and suggests the notion of δ\delta-deniability to help preserve the privacy of individuals (identified with the elements of NN). A testing procedure (i.e. a choice of a family of subsets T\mathcal{T} to query) is δ\delta-deniable if for every element x∈Sx\in S and every sequence of responses to tests T1,…,TtT_1,\dots,T_t, there are some δ\delta distinct (admissible) subsets of NN 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:

  1. Posing the problem of deniable group testing described above.
  2. A non-adaptive DGT algorithm that for δ\delta-deniability and ℓ=1\ell=1, achieves δ+1\delta+1 accuracy.
  3. An adaptive DGT algorithm (named Submartingale) that achieves δ\delta-deniability for ℓ>1\ell>1. There is no theoretical accuracy bound for this problem.
  4. 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
  1. Can you clarify why the definition requires δ\delta admissible sets that can generate the same solution, as opposed to just δ\delta uninfected individuals for any given individual that who (if infected) would explain the feedback vector equally well?
  2. Is the lower bound true only for non-adaptive algorithms, or also adaptive ones?
  3. What is the distribution of the defective set in the experiments? The text states only that NN has exactly dd ones and that inputs are random; please state whether the dd positions are a uniformly random dd-subset drawn independently in each of the mm runs. Note also that the average-case accuracy in Section 3 is defined with SS uniform over SD\mathcal{S}_D, whereas the experiments fix ∣S∣=d|S| = d.
  4. 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?
1 comment
AuthorsOpenReview ↗

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 δ\delta 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 dd infected elements (as parameters δ\delta and dd are independent of each other, in particular, δ\delta could be much smaller than dd). 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 ii and each pair of defective sets S1⊂S2S_1\subset S_2, the ii-th test applied while testing S1S_1 is a superset of the ii-th test applied while testing S2S_2. We have claried this in the revised version of our paprer.

Q3 In each of the mm runs, the defective set is drawn independently and uniformly at random among all dd-subsets of NN; 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|S|=d, rather than under the uniform distribution over SD\mathcal{S}_D of Section 3. This choice is deliberate. The algorithm uses only the upper bound DD, a standard assumption in group testing, and not the actual number dd of defective elements; Parameter dd largely determines its accuracy. We also stress that δ\delta-deniability holds deterministically for every input (Theorem~2); only the accuracy Δ\Delta depends on the input. For this reason, we report the full distribution of Δ\Delta as box plots rather than only its mean: for unfavourable inputs, Δ\Delta 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\delta+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.

Reviewer_2ZuEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper formulates the problem of δ\delta-deniable group testing, i.e., for any element xx, there exist at least δ\delta sets of detective items that do not contain xx and satisfy all the test outcomes. The contributions of this paper include a reduction to classical group testing by the grouping algorithm, an adaptive partition-refinement algorithm SUBMARTINGALE, and lower bounds on accuracy for monotonic algorithms. The performance of the grouping algorithm and SUBMARTINGALE is validated by synthetic experiments.

Critical strengths
  • This paper formalizes a new notion of group testing, and provides both algorithms with theoretical guarantees and information-theoretic lower bounds for both binary outcomes and ℓ\ell-capped quantitative outcomes.
Critical weaknesses
  • The practical significance of the proposed deniable group testing problem remains unclear. The authors briefly mentioned deniable digital signatures as a potential application, but its connection to deniable group testing requires further justification.
  • The reduction to classical group testing via the grouping algorithm looks straightforward, while SUBMARTINGALE lacks analytical performance guarantees.
  • There are substantial gaps between the upper and lower bounds on Δ\Delta. For binary outcomes, the upper bound is δ+1\delta+1, while the lower bound is log⁡(δ+1)+1\log (\delta+1)+1. For ℓ\ell-capped quantitative outcomes, the upper bound is D+δD +\delta while the lower bound is (δ+1)/ℓ(\delta+1)/\ell.
Questions for authors
  • Can you further justify the practical implications of the deniable group testing problem and the proposed algorithms?
1 comment
AuthorsOpenReview ↗

Our response

Thank you very much for your comments and feedback.

CW1 We have expanded the motivation in the revised version of the paper.

CW2 We agree that grouping algorithm is simple, it is meant as a baseline. Please notehowever that guarantees are, not inherited from prior work: deniability relies on the exact characterization A(S)={S′∈SD:K(S′)=K(S)}A(S)=\{S'\in\mathcal{S}_D : K(S')=K(S)\}, obtained from DD-disjunctness. Let us note that the presented analysis turend out to be suprsingly complex.

CW3 We do not aim to (completely) solve a specific single problem. Instead, we propose a generic privacy framework for several models of Group Testing, demonstrate selected fundamental challenges by giving the best-we-can answers and emphasizing directions.}

Q1 Our approach allows an element to deny belonging to the defective set by pointing to a range of alternative scenarios that produce the same test outcome. This property can be leveraged whenever group testing (GT) is applied in sensitive domains. For example, no party will be able to prove that a given element belongs to a particular group. We have expanded the discussion of this aspect in the revised version of the paper.

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.

Reviewer_U7DaOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The authors discuss a new framework which guarantees privacy in a group testing setting. (δ,Δ)(\delta,\Delta)-deniability in group testing guarantees that for any query output vector ff which is produced upon input universe NN with some subset SS which are positive for the tested characteristic, for each element ss of SS, there are at least δ\delta sets S′S' such that s∉S′s \notin S', and a positive input S′S' produces the same vector ff deterministically. The consequence is that a given output cannot allow an observer to conclude that any s is positive because there are at least δ\delta possible SS not containing ss which produce such an output. The Δ\Delta parameter measures the utility of the output, giving the maximum ratio of cardinalities of the set containing all possible positive elements implied by ff to the set of true positive elements SS.

This framework is used to measure deterministic query regimes and queries themselves are public. They also give two algorithms in such a regime. The first splits NN into disjoint sets of size δ+1\delta+1. A matrix MM that is DD-Disjunct where, DD is the maximal cardinality of ∣S∣|S| can be constructed. This matrix gives a set of queries that guarantee a (δ,δ+1)(\delta, \delta+1)-deniability output. The second algorithm partitions N into smaller subsets until no additional splits can be made without losing the δ\delta-deniability guarantee. A utility guarantee is not provided for this algorithm. The authors also provide a general lower bound, and empirical testing results for this algorithm.

Critical strengths

The framework is interesting, and to my knowledge, there are no other works guaranteeing a number of alternative positive subsets in group testing which could lead to an outcome ff not containing a particular element xx. This opens opportunities for additional applications of this framework in areas besides group testing.

The analysis is sound, and the empirical results are extensive and demonstrate consistent Δ\Delta ratio for the second algorithm on many trials and dd values, making them convincing.

Critical weaknesses

First, the framework does not extend to randomized algorithms, so guarantees of deterministic algorithms cannot be compared with randomized results. This limits the scope of the framework extensively, as randomized algorithms are pervasive in privatization, and comparing this algorithm with existing techniques (such as those standard in differential privacy) would be useful in judging its applicability.

The framework leaves gaps which are covered by DP guarantees, so I think the claim is perhaps weaker than "plausible deniability". Given a DP guarantee, a user claims true plausible deniability because a neighboring dataset, not containing the user will produce a similar distribution of results, so by Bayes, an observer's perceived probability that some individual x∈Sx\in S cannot change significantly after observing ff. On the other hand, in this framework, observing ff can drastically affect the probability that x∈Sx\in S, even with a δ,Δ\delta, \Delta guarantee. For some xx and SS of size kk containing xx, it may be the case that all datasets producing ff contain xx, except δ\delta, whereas all others producing ff, of which there may be many, do contain xx. This can skew the probability that x∈Sx\in S, as there can by a large universe where a dataset containing xx is unlikely without knowledge of ff. This limitation should be addressed in the paper.

The grouping algorithm lacks novelty and is a direct application of others' work with stated guarantees, though these works are cited accordingly. The analytical techniques used are standard too. The Submartingale analysis only gives δ\delta-deniability with no theoretical guarantee of Δ\Delta utility. The analysis is just described as complex, but never provided. Lemma 2 is also never referenced in any theorem, which is confusing. Authors do not discuss why empirical \Delta results are not monotonic. While the plots are interesting, I would be interested to learn why the authors think the results are as shown and what theoretical ideas could support them.

Presentation is not ideal:

  • the grouping algorithm contains a definition and discussion of a blood testing application, which would better fit outside of the algorithm description.
  • The number of tests claim and analysis should also be included in the theorem, rather than left outside for consistency.
  • Paragraphs are not consistent in title's use of ending punctuation (i.e. "Accuracy:" vs. "Deniability" vs. "Algorithm.").
  • SS is used as the positive subset in the setting and throughout, but also defined as an element of P\mathcal{P} when describing the Submartingale algorithm.
  • Lemma 2 is also never referenced in any theorem, which is confusing.
  • d is treated as a parameter, when it is a property of the input set, unknown to the algorithm.
  • Authors failed to discuss a paper by Mikhail J. Atallah, Keith B. Frikken in ASIACCS '08 on Private Group Testing, which directly addresses the same topic using a different framework.
Questions for authors
  • In the empirical testing, how do you interpret these results and their lack of monotonicity? Did you compare the two algorithms provided?
  • Have you considered analyzing the guarantees provided by these algorithms under other privacy regimes?

Future work

  • How does this result carry over to multiple testing rounds? Many applications would require multiple rounds of tests. Would guarantees hold with composition?
1 comment
AuthorsOpenReview ↗

Our response

Thank you very much for your comments and feedback.

CW1 The framework is extendable to randomized algorithms. There are two main reasons why we did not include it in our paper. First, we focus on deterministic solutions, which have a lot of interesting and challenging aspects on their own and historically precede the randomized ones. Second, there are several ways to extend, e.g., each of the two conditions, deniability and accuracy, could hold with some threshold probability, or in expectation -discussing all these cases would take space and likely distract the readers (by diverting them from the main ideas). They may also be many subtle differences in performance in any of these cases. Therefore, we leave it for a follow-up work.

CW2 We agree with the reviewer regarding Bayesian-oriented approach to privacy. However, our alternative deniability approach, which works also for deterministic scenarios, is motivated by a deterministic legal-based approach. The more evidence there is to the contrary, the less credible any claim of involvement becomes. In our case: The more executions for set S′∌xS'\not\ni x result in ff, the less credible any claim of ``xx being in the actual set of infected elements'' becomes.

CW3

  1. We agree that grouping algorithm is simple, it is meant as a baseline. Its guarantees are, however, not inherited from prior work: deniability relies on the exact characterization A(S)={S′∈SD:K(S′)=K(S)}A(S)=\{S'\in\mathcal{S}_D : K(S')=K(S)\}, obtained from DD-disjunctness (proof of Theorem~\ref{thm:grouping}); the accuracy δ+1\delta+1 is attained; and for ℓ≥2\ell\ge 2, groups of size δ+1\delta+1 do not give deniability, so groups of size D+δD+\delta are needed.

  2. Problem with "Lemma 2" has been corrected.

  3. We have added partial analytical results regarding the accuracy parameter Δ\Delta, including a tight upper bound for the case ℓ=∞\ell = \infty.

  4. We have added an extensive comment regarding the lack of monotonicity to the Appendix. MONOTINICITY

CW4 We have fixed all the issues with the presentation that you pointed out, in particular the ones regarding Theorem 1 and the Grouping algorithm. (Except for the collision of the local and the global meanings of "S".)

CW5 Thank you very much for pointing out the work by Atallah and Frikken. Omitting it in the initial version of our manuscript was indeed an oversight, and the revised version now cites this paper and discusses the differences in detail.

In general, the cited work introduces a method for performing group testing on homomorphically encrypted data, which enables exact group testing while preserving full privacy during execution. Our work, however, relies on fundamentally different assumptions and a distinct approach to user protection based on the concept of plausible deniability. Furthermore, we do not use any encryption or cryptographic primitives; instead, our framework is purely combinatorial and information-theoretic.

Q1 Grouping is not a single algorithm - it is a framework that transfers classical group testing algorithms (DD-disjunct matrices, or adaptive algorithms that identify the positive groups) to the deniable setting, with worst-case accuracy δ+1\delta+1 for binary feedback (Theorem 1). Because there is a vast literature on the classical GT algorithms, their specific performance under the grouping framework may differ, and such analysis is beyond a scope of a single paper. Submartingale, on the other hand, is a specific algorithm designed directly for the deniable setting with quantitative feedback Fℓ\mathcal{F}_\ell; for ℓ=∞\ell=\infty, it guarantees Δ≤2δ+1\Delta\le 2\delta+1 (Theorem 3), with more detail results evaluated experimentally.

We have added an extensive comment regarding the lack of monotonicity to the Appendix.

Q2 Frankly, no. As a deterministic algorithm, ours naturally cannot provide DP guarantees in any non-trivial setting. While one might consider applying k-anonymity-type approaches, they appear largely inadequate in this context

Q3 Yes, we have thought about that. If we run our algorithms on the same input, deniability is preserved (which is a benefit of the deterministic approach). When different defective sets are used, everything depends on the relationship between the consecutive datasets.

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.

Reviewer_XiHJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces Deniable Group Testing (DGT), a framework for identifying potentially defective individuals while providing deterministic plausible deniability. The proposed (\delta)-deniability requires that, for each possibly defective individual, at least (\delta) alternative defective sets excluding that individual are consistent with the observed feedback. The authors propose a GROUPING algorithm based on classical disjunct group testing and an adaptive SUBMARTINGALE algorithm. They also derive lower bounds on the accuracy of monotonic testing strategies and evaluate SUBMARTINGALE through simulations.

Critical strengths
  1. The paper introduces an interesting combinatorial notion of plausible deniability, providing a different perspective from randomized privacy mechanisms.
  2. The GROUPING construction provides explicit deniability, accuracy, and query-complexity guarantees using established group testing techniques.
  3. The adaptive SUBMARTINGALE algorithm extends the framework to capped quantitative feedback, with empirical results exploring its performance across different parameter regimes.
Critical weaknesses
  1. The proof of the quantitative-feedback lower bound in Appendix B assumes that combining (\ell) singleton defective sets with identical feedback (f) produces feedback (\ell f). However, this does not generally hold for adaptive testing algorithms, even when the resulting feedback vectors are monotonic, since different intermediate feedback may lead to different subsequent queries.

For example, a counterexample can be constructed with (D=\delta=\ell=2): partition six elements into two groups of three, first test the entire domain, and then test one group if the first result is 1 (otherwise test the entire domain again). This algorithm is monotonic and satisfies (\delta)-deniability, yet two singleton sets can produce identical feedback ((1,0)) while their union produces ((2,2)), rather than ((2,0)). Thus, the current proof does not establish the claimed lower bound for the full class of monotonic adaptive algorithms.

  1. While SUBMARTINGALE appears to be the more interesting algorithmic contribution, the paper only establishes its deniability guarantee. Its accuracy is evaluated empirically, without a worst-case or expected approximation guarantee. The number of required tests is also not analyzed, despite query complexity being a central objective in group testing.
Questions for authors

The proposed (\delta)-deniability guarantees the existence of alternative explanations but does not account for their relative plausibility. Under nonuniform priors or additional side information, an adversary may still infer an individual's defectiveness with high confidence. The paper should better characterize the intended threat model and limitations of this combinatorial privacy guarantee.

1 comment
AuthorsOpenReview ↗

Our response

Thank you very much for your comments and feedback.

CW1: The reviewer is correct in that we cannot use the fact that F(U)F(U) is exactly ℓ⋅f\ell\cdot f in the proof. We corrected that part (the last part of the proof of Theorem 4, located in Appendix B) -- we no longer refer to the incorrect property F(U)=ℓ⋅fF(U)=\ell \cdot f, but instead we prove by induction that for any subsets S,S′S,S' of UU of size ℓ\ell, we have F(S)=F(S′)=F(U)F(S)=F(S')=F(U). This allows us to use the last centered derivation of the proof and derive the final conclusion. Note that the reviewer's example does not contradict the updated technical property of F(S)=F(S′)=F(U)F(S)=F(S')=F(U), for any subsets S,S′⊆US,S'\subseteq U of size ℓ\ell.

CW2: Motivated by the Reviewers' comments, we have added partial analytical results regarding the accuracy parameter Δ\Delta, including a tight upper bound for the case ℓ=∞\ell = \infty.

Indeed, we did not provide an analysis of the number of tests. For the grouping algorithm, this analysis is straightforward. Determining the number of required tests under the deniability constraint is an interesting open question, as it remains unclear whether deniability can reduce the required number of tests in general. We have explicitly highlighted this as future work.

Q1 The proposed (\delta)-deniability guarantees the existence of alternative explanations but does not account for their relative plausibility. Under nonuniform priors or additional side information, an adversary may still infer an individual's defectiveness with high confidence. The paper should better characterize the intended threat model and limitations of this combinatorial privacy guarantee.

The reviewer is right that some conditional inference by an adversary cannot be entirely avoided; however, our lower bound indicates that it comes at a cost. More specifically, if one proves deniability for a large δ\delta, the additional side information (e.g., about other non-infected elements) also has to be substantial in order to ``eliminate'' the possibility of other sets S′S' not containing the denied element.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.