EE Seminar: Secure Group Testing
(The talk will be given in English)
Speaker: Dr. Asaf Cohen
Department of Communication Systems Engineering,Ben Gurion University
Monday, May 15th, 2017
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering
Secure Group Testing
Abstract
The principal mission of Group Testing (GT) is to identify a small subset of defective items from a large population, by grouping items into as little as possible test pools. The test outcome of a pool is positive if it contains at least one defective item, and is negative otherwise. GT algorithms are utilized in numerous applications, and in most of them the privacy of the tested subjects, namely, whether they are defective or not, is critical. In this talk, we consider a scenario where there is an eavesdropper (Eve) which is able to observe a subset of the GT outcomes (pools). We propose a new non-adaptive Secure Group Testing (SGT) algorithm based on information theoretic principles, which keeps the eavesdropper ignorant regarding the items’ status. Specifically, when the fraction of tests observed by Eve is 0 ≤ δ < 1, via random coding, ML decoding and a matching converse, we prove that the number of tests required for both correct reconstruction at the legitimate user (with high probability) and negligible mutual information at Eve’s side is 1/(1−δ) times the number of tests required with no secrecy constraint. We conclude with a practical SGT decoding algorithm, and asses its performance as well.
Based on joint work with Alejandro Cohen, Omer Gurewitz and Sidharth Jaggi.
