On the properties of algebraic geometric codes as copy protection codes

V. M. Deundyak ; D. V. Zagumennov

Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 1, pp. 22-38.

Résumé

Traceability schemes which are applied to the broadcast encryption can prevent unauthorized parties from accessing the distributed data. In a traceability scheme a distributor broadcasts the encrypted data and gives each authorized user unique key and identifying word from selected error-correcting code for decrypting. The following attack is possible in these schemes: groups of c malicious users are joining into coalitions and gaining illegal access to the data by combining their keys and identifying codewords to obtain pirate key and codeword. To prevent this attacks, classes of error-correcting codes with special c-FP and c-TA properties are used. In particular, c-FP codes are codes that make direct compromise of scrupulous users impossible and c-TA codes are codes that make it possible to identify one of the a ackers. We are considering the problem of evaluating the lower and the upper boundaries on c, within which the L-construction algebraic geometric codes have the corresponding properties. In the case of codes on an arbitrary curve the lower bound for the c-TA property was obtained earlier; in this paper, the lower bound for the c-FP property was constructed. In the case of curves with one infinite point, the upper bounds for the value of c are obtained for both c-FP and c-TA properties. During our work, we have proved an auxiliary lemma and the proof contains an explicit way to build a coalition and a pirate identifying vector. Methods and principles presented in the lemma can be important for analyzing broadcast encryption schemes robustness. Also, the c-FP and c-TA boundaries monotonicity by subcodes are proved.

Détail

Keywords: error-correcting codes, traceability schemes, algebraic geometry codes.

Bibliographie

[1] D. R. Stinson, R. Wei, “Combinatorial properties and constructions of traceability schemes and frameproof codes”, SIAM Journal on Discrete Mathematics, 11:1 (1998), 41–53 | MR | Zbl

[2] J. N. Staddon, D. R. Stinson, R. Wei, “Combinatorial properties of frameproof and traceability codes”, Information Theory, IEEE Transactions, 47:3 (2001), 1042–1049 | MR | Zbl

[3] A. Silverberg, J. Staddon, J. Walker, “Applications of list decoding to tracing traitors”, Information Theory, IEEE Transactions, 49:5 (2003), 1312–1318 | MR | Zbl

[4] G. A. Kabatyansky, “Traceability codes and their generalizations”, Problems of Information Transmission, 55:3 (2019), 93–105 | MR

[5] V. M. Deundyak, V. V. Mkrtichyan, “Issledovaniye granits primeneniya skhemy zashchity informatsii, osnovannoy na RS-kodakh”, Diskretn. Anal. Issled. Oper., 18:3 (2011), 21–38 | MR | Zbl

[6] V. M. Deundyak, S. A. Yevpak, V. V. Mkrtichyan, “Analysis of properties of $q$-ary Reed–Muller error-correcting codes viewed as codes for copyright protection”, Problems of Information Transmission, 51:4 (2015), 398–408 | MR | Zbl

[7] D. V. Zagumennov, V. V. Mkrtichyan, “On application of algebraic geometry codes of $l$-construction in copy protection”, Prikladnaya Diskretnaya Matematika, 44 (2019), 67–93 | MR

[8] F. J. MacWilliams, N. J. A. Sloane, The theory of error-correcting codes, North-Holland Mathematical Library, 16, Elsevier, 1977 | MR

[9] S. A. Evpak, V. V. Mkrtichyan, “Usloviya primeneniya $q$-ichnyh kodov Rida–Mallera v special'nyh skhemah zashchity informacii ot nesankcionirovannogo dostupa”, Vladikavk. matem. zhurn., 16:2 (2014), 38–45 | MR | Zbl

[10] T. Høholdt, J. H. van Lint, R. Pellikaan, “Algebraic geometry codes”, Handbook of coding theory, 1, no. 1, 1998, 871–961 | MR

[11] S. G. Vladets, D. Y. Nogin, M. A. Tsfasman, Algebrogeometricheskie kody. Osnovnye ponyatiya, MCCME, 2003