On application of algebraic geometry codes of~$L$-construction in copy protection

D. V. Zagumennov ; V. V. Mkrtichyan

Prikladnaâ diskretnaâ matematika, no. 2 (2019), pp. 67-93

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 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.

Détail

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