Deniable Group Testing

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 $\delta$-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 $v$ there are at least $\delta$ possible defective sets not containing $v$ that give the same testing results. In other words, unless an observer could test negatively any $\delta$ 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 $\log (\delta +1)+1$ times bigger than the number of defective elements, for some defective sets under binary testing feedback. For $\ell$-capped quantitative feedback, $\ell \le \delta$, the size of some output sets could be at least $\frac{\delta +1}{\ell }$ times bigger than the input set. On the positive side, we design a few testing strategies and prove that they guarantee $\delta$-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.