Abstract : In non-adaptive group testing (NAGT), the time for decoding is a crucial problem. Given an unknown string x ∈ {0, 1}N with at most d ones, the problem is how to determine xi = 1 using as few tests as possible so that x can be decoded as fast as possible. A NAGT can be represented by a t ×N matrix. Although we do not know x, this matrix, which is called d-disjunct matrix, can reconstruct it exactly. In this paper, we consider a general problem, in which x is an array of N non-negative integer elements and has up to d positive integers. From nonrandom construction, we prove that we can decode a d-disjunct matrix, which is built from [n, k]q-Reed-Solomon codes and identity matrix Iq, and recover x defined above in poly(d) ·t log2t + O(d3n log(d logN)) with t = O(d2log2N). We also discuss this problem when x contains negative integer elements.Pay-Television internet-based can be applied these results directly. Since the number of customers is very large, our system must be prevented from illegal buyers. This problem is called traitor tracing. To the best of our knowledge, this is the first result that raises a variant of NAGT and gets how to trace traitors without using probability.
David Hutchison; Takeo Kanade; Madhu Sudan; Demetri Terzopoulos; Doug Tygar; Moshe Y. Vardi; Gerhard Weikum; Khabib Mustofa; Erich J. Neuhold; A Min Tjoa; Edgar Weippl; Ilsun You; Josef Kittler; Jon M. Kleinberg; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan; Bernhard Steffen. 1st International Conference on Information and Communication Technology (ICT-EurAsia), Mar 2013, Yogyakarta, Indonesia. Springer, Lecture Notes in Computer Science, LNCS-7804, pp.324-330, 2013, Information and Communicatiaon Technology. 〈10.1007/978-3-642-36818-9_35〉
https://hal.inria.fr/hal-01480238
Contributeur : Hal Ifip
<>
Soumis le : mercredi 1 mars 2017 - 11:21:11
Dernière modification le : jeudi 2 mars 2017 - 01:04:26
Document(s) archivé(s) le : mardi 30 mai 2017 - 15:01:24
Thach Bui, Oanh Nguyen, Van Dang, Nhung Nguyen, Thuc Nguyen. A Variant of Non-Adaptive Group Testing and Its Application in Pay-Television via Internet. David Hutchison; Takeo Kanade; Madhu Sudan; Demetri Terzopoulos; Doug Tygar; Moshe Y. Vardi; Gerhard Weikum; Khabib Mustofa; Erich J. Neuhold; A Min Tjoa; Edgar Weippl; Ilsun You; Josef Kittler; Jon M. Kleinberg; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan; Bernhard Steffen. 1st International Conference on Information and Communication Technology (ICT-EurAsia), Mar 2013, Yogyakarta, Indonesia. Springer, Lecture Notes in Computer Science, LNCS-7804, pp.324-330, 2013, Information and Communicatiaon Technology. 〈10.1007/978-3-642-36818-9_35〉. 〈hal-01480238〉
