3 years ago

Omer Gurewitz, Sidharth Jaggi, Alejandro Cohen, Asaf Cohen

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.

In this paper, we consider Secure Adaptive GT. Specifically, when an adaptive algorithm has access to a private feedback link of rate $R_f$, we prove that the number of tests required for both correct reconstruction at the legitimate user, with high probability, and negligible mutual information at the eavesdropper is $1/min\{1,1-\delta+R_f\}$ times the number of tests required with no secrecy constraint. Thus, unlike non-secure GT, where an adaptive algorithm has only a mild impact, under a security constraint it can significantly boost performance. A key insight is that not only the adaptive link should disregard test results and send keys, these keys should be enhanced through a "secret sharing" scheme before usage.

Publisher URL: http://arxiv.org/abs/1801.04735

DOI: arXiv:1801.04735v1

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.