Geodesic
On application of algebraic geometry codes of~$L$-construction in copy protection
Prikladnaâ diskretnaâ matematika, no. 2 (2019), pp. 67-93.

Voir la notice de l'article provenant de la source Math-Net.Ru

Traceability schemes which are applied to the broadcast encryption can prevent unauthorized parties from accessing the distributed data. In a traceability scheme, a distributor encrypts the data and gives each authorized user a unique key suit to decrypt the data. This suit uniquely identifies the recipient and therefore allows the tracing of the source of an unauthorized redistribution. A widely used approach to the constructing good traceability scheme is the use of error-correcting codes with a suitable minimum distance and efficient decoding algorithms. The paper deals with the usage of algebraic geometry codes (AG-codes) of $L$-construction and Sudan–Guruswami list decoding algorithms in these schemes. We suggest the problem of constructing traceability AG-codes and obtain sufficient conditions for applying them. Let $C \subset {\mathbb F_q^n}$ be the algebraic geometry code constructed using curve of genus $g$ and divisor of degree $\alpha$. Firstly, if $c \sqrt{n/\alpha}$, then $C$ is a traceability code when the number of attackers is a maximum of $c$. Secondly, if $\alpha \ge \log_qN+g-1$, then $C$ can be used to build traceability schemes maintaining $N$ users. Finally, we obtain several cumbersome bounds on the number of intruders within which it is possible to use Sudan–Guruswami hard- and soft- decision list decoding algorithms for tracing the unauthorized redistribution source. Based on these derived conditions and some other lemmas, the algorithm for suitable one-point AG-code construction is presented. The algorithm can be polynomially reduced to the Riemann–Roch space basis construction problem. Much attention is given to the algorithm validity and its sample execution. Besides, the paper gives a brief description of AG-codes and Sudan–Guruswami hard- and soft- decision list decoding algorithms.
Keywords: error-correcting codes, traceability schemes, algebraic geometry codes. 
@article{PDM_2019_2_a5,
     author = {D. V. Zagumennov and V. V. Mkrtichyan},
     title = {On application of algebraic geometry codes of~$L$-construction in copy protection},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {67--93},
     publisher = {mathdoc},
     number = {2},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_2_a5/}
}
TY  - JOUR
AU  - D. V. Zagumennov
AU  - V. V. Mkrtichyan
TI  - On application of algebraic geometry codes of~$L$-construction in copy protection
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 67
EP  - 93
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_2_a5/
LA  - ru
ID  - PDM_2019_2_a5
ER  - 
%0 Journal Article
%A D. V. Zagumennov
%A V. V. Mkrtichyan
%T On application of algebraic geometry codes of~$L$-construction in copy protection
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 67-93
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_2_a5/
%G ru
%F PDM_2019_2_a5
D. V. Zagumennov; V. V. Mkrtichyan. On application of algebraic geometry codes of~$L$-construction in copy protection. Prikladnaâ diskretnaâ matematika, no. 2 (2019), pp. 67-93. http://geodesic.mathdoc.fr/item/PDM_2019_2_a5/

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

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

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

[4] Deundyak V. M., Mkrtichyan V. V., “Research of applying bounds of the information protection scheme based on RS-codes”, Diskretn. Anal. Issled. Oper., 18:3 (2011), 21–38 (in Russian) | MR | Zbl

[5] Deundyak V. M., Evpak S. A., Mkrtichyan V. V., “Analysis of properties of $q$-ary Reed–Muller error-correcting codes viewed as codes for copyright protection”, Probl. Inform. Transm., 51:4 (2015), 398–408 | DOI | MR | Zbl

[6] Goppa V. D., “Algebraic-geometric codes”, Izv. Akad. Nauk SSSR. Ser. Mat., 46:4 (1982), 762–781 (in Russian) | MR

[7] Guruswami V., Sudan M., “Improved decoding of Reed–Solomon and algebraic-geometric codes”, Foundations of Computer Science, IEEE, Palo Alto, 1998, 28–37 | MR

[8] Fernandez M., Soriano M., “Identification of traitors in algebraic-geometric traceability codes”, IEEE Trans. Signal Proc., 52:10 (2004), 3073–3077 | DOI | MR | Zbl

[9] Vladut S. G., Nogin D. Y., Tsfasman M. A., Algebraic Geometric Codes. Basic Notions, MCCME Publ., M., 2003, 504 pp. (in Russian)

[10] Fiat A., Naor M., “Broadcast encryption”, LNCS, 773, 1994, 480–491 | Zbl

[11] Chor B., Fiat A., Naor M., “Tracing traitors”, LNCS, 839, 1994, 257–270 | Zbl

[12] Hoholdt T., van Lindt J., Pellikaan R., “Algebraic geometry codes”, Handbook of Coding Theory, v. 1, eds. V. S. Pless, W. C. Huffman, R. A. Brualdi, Elsevier, Amsterdam, 1998, 871–961 | MR | Zbl

[13] Lang S., Algebra, Springer, 2002 | Zbl

[14] Hess F., “Computing Riemann–Roch spaces in algebraic function fields and related topics”, J. Symbolic Comput., 33:4 (2002), 425–445 | DOI | MR | Zbl

[15] Magma Computational Algebra System, http://magma.maths.usyd.edu.au/magma/

[16] Shokrollahi A., Wasserman H., “List decoding of algebraic-geometric codes”, IEEE Trans. Inform. Theory, 45:2 (1999), 432–437 | DOI | MR | Zbl

[17] Van Der Geer G., Van Der Vlugt M., “Tables of curves with many points”, Mathematics of Computation, 69:230 (2000), 797–810 | MR | Zbl

[18] MacWilliams F. J., Sloane N. J. A., The Theory of Error-Correcting Codes, Elsevier, 1977, 744 pp. | MR