Secure Adaptive Group Testing Academic Article uri icon


  • Abstract: Group Testing (GT) addresses the problem of identifying a small subset of defective items from a large population, by grouping items into as few test pools as possible. In Adaptive GT (AGT), outcomes of previous tests can influence the makeup of future tests. This scenario has been studied from an information theoretic point of view. Aldridge $2012 $ showed that in the regime of a few defectives, adaptivity does not help much, as the number of tests required for identification of the set of defectives is essentially the same as for non- adaptive GT. Secure GT considers a scenario where there is an eavesdropper who may observe a fraction $\delta $ of the outcomes, and should not be able to infer the status of the items. In the non-adaptive scenario, the number of tests required is $1/(1-\delta) $ times the number of tests without the secrecy constraint.

publication date

  • January 15, 2018