Private combinatorial group testing

Combinatorial group testing, given a set C of individuals ("customers"), consists of applying group tests on subsets of C for the purpose of identifying which members of C are infected (or, more generally, defective in some way). The outcome of a group test reveals only the presence or absence of infection(s) in that group, but a number of group tests exactly identifies all infected members. Although the main motivation for group testing is economic - it drastically cuts down the number of necessary tests - it has an interesting privacy side-effect, namely, that each individual customer is "hiding in a crowd" (the groups within which it is being tested). This privacy side-effect is currently thrown away because the analysis that pinpoints who is infected is carried out by the same entity that prepared the test samples. This paper gives a protocol in which these two duties are separated between Alice and Bob: The protocol informs each customer who is infected privately, and without either Alice or Bob learning who is infected. An interesting feature of our protocol is that a customer need not have any computational power, i.e., the customer can be notified by mailing her (possibly paper copies of) two random strings - one from Alice and one from Bob - so all she has to do is visually check whether these two strings are equal or not.