TY - GEN

T1 - A Construction of Traceability Set Systems with Polynomial Tracing Algorithm

AU - Egorova, Elena

AU - Fernandez, Marcel

AU - Kabatiansky, Grigory

N1 - Funding Information:
ACKNOWLEDGMENTS The work of M. Fernandez has been supported by the Spanish Government Grant TEC2015-68734-R (MINECO/FEDER) “ANFORA” and Catalan Government Grant 2017 SGR 782. The work of E. Egorova and G. Kabatiansky has been supported by the RFBR Grants 18-07-01427.
Publisher Copyright:
© 2019 IEEE.

PY - 2019/7

Y1 - 2019/7

N2 - A family F of w-subsets of a finite set X is called a set system with the identifiable parent property if for any w-subset contained in the union of some t sets, called traitors, of F at least one of these sets can be uniquely determined, i.e. traced. A set system with traceability property (TSS, for short) allows to trace at least one traitor by minimal distance decoding of the corresponding binary code, and hence the complexity of tracing procedure is of order O(M), where M is the number of users or the code's cardinality. We propose a new construction of TSS which is based on the old Kautz-Singleton concatenated construction with algebraic-geometry codes as the outer code and Guruswami-Sudan decoding algorithm. The resulting codes (set systems) have exponentially many users (codevectors) M and polylog(M) complexity of code construction and decoding, i.e. tracing traitors. This is the first construction of traceability set systems with such properties.

AB - A family F of w-subsets of a finite set X is called a set system with the identifiable parent property if for any w-subset contained in the union of some t sets, called traitors, of F at least one of these sets can be uniquely determined, i.e. traced. A set system with traceability property (TSS, for short) allows to trace at least one traitor by minimal distance decoding of the corresponding binary code, and hence the complexity of tracing procedure is of order O(M), where M is the number of users or the code's cardinality. We propose a new construction of TSS which is based on the old Kautz-Singleton concatenated construction with algebraic-geometry codes as the outer code and Guruswami-Sudan decoding algorithm. The resulting codes (set systems) have exponentially many users (codevectors) M and polylog(M) complexity of code construction and decoding, i.e. tracing traitors. This is the first construction of traceability set systems with such properties.

UR - http://www.scopus.com/inward/record.url?scp=85073143061&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2019.8849353

DO - 10.1109/ISIT.2019.8849353

M3 - Conference contribution

AN - SCOPUS:85073143061

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2739

EP - 2742

BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019

Y2 - 7 July 2019 through 12 July 2019

ER -