×

On the unique representation of very strong algebraic geometry codes. (English) Zbl 1312.14075

Given an algebraic geometry code \(\mathcal{C}=\mathcal{C}_{\mathcal{L}}(\mathcal{X},\mathcal{P},E)\), where \(\mathcal{X}\) is an algebraic curve over the finite field \(\mathbb{F}_q\), \(\mathcal{P}\) is a set of \(n\) \(\mathbb{F}_q\)–rational points on \(\mathcal{X}\), and \(E\) is a divisor on \(\mathcal{X}\). The problem of retrieving the triple \((\mathcal{X},\mathcal{P},E)\) from the generator matrix of \(\mathcal{C}\) is of great interest. In this paper, the author shows (under some condition on \(\deg(E)\)) how to find an AG–representation \((\mathcal{Y},\mathcal{Q},F)\) of the code \(\mathcal{C}\), where \(\mathcal{Y}\) is the image of \(\mathcal{X}\) under the embedding of the linear series of the divisor of \(E\) and \(Q\) is the image of the points in \(P\) and \(F\) is the image of \(E\) under the embedding \(\phi_E:X \to Y\). Moreover, \((\mathcal{X},\mathcal{P},E)\) and \((\mathcal{Y},\mathcal{Q},F)\) are stictly isomorphic, i.e., \(\phi_E(E) \equiv_\mathcal{Q} F\).
The main result of this paper is that under the hypothesis \(2g+2 \leq \deg(E) \leq \frac{n}{2}\), an AG–representation \((\mathcal{Y},\mathcal{Q},F)\) of \(\mathcal{C}\) can be obtained using only the generator matrix of \(\mathcal{C}\), where \(\mathcal{Y}\) is as above, a normal curve in \(\mathbb{P}^{\deg(E)-g}\). Moreover, The vanishing ideal of \(\mathcal{Y}\) is generated by degree two homogeneous elements, i.e., \(I(Y)=I_2(Y)\). The authors shows also that under the hypothesis above, \(I_2(Y)=I_2(Q)\), i.e., the quadratic polynomials that vanish on \(\mathcal{Q}\) generate the ideal of \(\mathcal{Y}\). Also an efficient algorithm to compute \(I_2(Q)\) is provided.
This means an efficient decoding algorithm can be found to decode very strong algebraic geometry code (VSAG) from its generator matrix. This means a McEliece public key cryptosystem is vulnerable to cryptanalysis if it is used with VASG for some range of \(\deg(E)\).

MSC:

14G50 Applications to coding theory and cryptography of arithmetic geometry
94A60 Cryptography
94B27 Geometric methods (including applications of algebraic geometry) applied to coding theory
94B35 Decoding

Software:

McEliece
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbott J., Bigatti A., Kreuzer M., Robbiano L.: Computing ideals of points. J. Symb. Comput. 30(4), 341-356 (2000) · Zbl 0977.13011 · doi:10.1006/jsco.2000.0411
[2] Arbarello E., Sernesi E.: Petri’s approach to the study of the ideal associated to a special divisor. Invent. Math. 49, 99-119 (1978) · Zbl 0399.14019 · doi:10.1007/BF01403081
[3] Arbarello E., Cornalba M., Griffiths P.A., Harris J.: Geometry of Algebraic Curves. Springer, New York (1985) · Zbl 0559.14017 · doi:10.1007/978-1-4757-5323-3
[4] Babbage D.: A note on the quadrics through a canonical curve. J. Lond. Math. Soc. 14, 310-315 (1939) · JFM 65.1398.03 · doi:10.1112/jlms/s1-14.4.310
[5] Berger T., Loidreau P.: How to mask the structure of codes for a cryptographic use. Des. Codes Cryptogr. 35, 63-79 (2005) · Zbl 1136.11327 · doi:10.1007/s10623-003-6151-2
[6] Bernstein, D.; Bernstein, D. J. (ed.); Buchmann, J. (ed.); Dahmen, E. (ed.), Introduction to post-quantum cryptography, 1-14 (2009), Berlin · Zbl 1158.81311 · doi:10.1007/978-3-540-88702-7_1
[7] Bordiga G.: Studio generale della quartica normale. Atti. R. Ist. Veneto Sci. Lett. Arti. 6: 503-525 (1885-1886). · JFM 18.0605.02
[8] Bruns W., Vetter U.: Determinantal rings. In: Lecture Notes in Mathematics, vol. 1327. Springer, Berlin (1988). · Zbl 0673.13006
[9] Carlini E., Catalisano M.: Existence results for rational normal cuurves. J. Lond. Math. Soc. 76(2), 73-86 (2007) · Zbl 1134.14022 · doi:10.1112/jlms/jdm042
[10] Cascudo I., Chen H., Cramer R., Xing X.: Asymptotically good ideal linear secret sharing with strong multiplication overy any fixed finite field. In: Halevi S. (ed.) Advances in Cryptology—CRYPTO 2009, Lecture Notes in Computer Science, vol. 5677, pp. 466-486. Springer, Berlin (2009). · Zbl 1252.94106
[11] Castelnuovo G.: Studio dellinvoluzione generale sulle curve razionali. Atti. R. Ist. Veneto Sci. Lett. Arti. 6, 1167-1199 (1885-1886).
[12] Cioffi F.: Minimally generating ideals of points in polynomial time using linear algebra. Ric. Mat. XLVIII 1, 55-63 (1999) · Zbl 0982.13015
[13] Enriques F.: Sulle curve canoniche di genere p dello spazio a p−1 dimensioni. Rend. Accad. Sci. Ist. Bologna 23, 80-82 (1919)
[14] Faure C., Minder L.: Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes. In: Proceedings of the 11th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT 2008, Pamporovo, pp. 99-107 (2008). · Zbl 0847.94012
[15] Fortuna E., Gianni P., Trager B.: Ideals of curves given by points. In: Seppälä M., Volcheck E. (eds.) Computational Algebraic and Analytic Geometry, vol. 572, pp. 71-88. American Mathematical Society, Providence (2012). · Zbl 1317.13062
[16] Goppa V.: Codes associated with divisors. Probl. Inf. Transm. 13, 22-26 (1977) · Zbl 0415.94005
[17] Griffiths P., Harris J.: Principles of Algebraic Geometry. Wiley-Interscience, New York (1978) · Zbl 0408.14001
[18] Harris J.: Algebraic Geometry, a First Course. Springer, New York (1978) · Zbl 0779.14001
[19] Hirschfeld J.W.P., Kochmáros G., Torres F.: Algebraic Curves Over a Finite Field. Princeton University Press, Princeton (2008) · Zbl 1200.11042
[20] Høholdt T., Pellikaan R.: On decoding algebraic-geometric codes. IEEE Trans. Inf. 41, 1589-1614 (1995) · Zbl 0847.94012 · doi:10.1109/18.476214
[21] Høholdt T., Lint J.v., Pellikaan R.: Algebraic geometry codes. In: Pless V., Huffman W. (eds.) Handbook of Coding Theory, vol. 1, pp. 871-961. North-Holland, Amsterdam (1998). · Zbl 0922.94015
[22] Homma M.: On the equations defining a projective curve embedded by a nonspecial divisor. Tsukuba J. Math. 3(2), 31-39 (1979) · Zbl 0442.14011
[23] Huffman W.C., Pless V.: Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge (2003) · Zbl 1099.94030 · doi:10.1017/CBO9780511807077
[24] Janwa H., Moreno O.: McEliece public crypto system using algebraic-geometric codes. Des. Codes Cryptogr. 8, 293-307 (1996) · Zbl 0859.94008 · doi:10.1023/A:1027351723034
[25] Lakshman Y.N.: A single exponential bound on the complexity of computing Gröbner bases of zero-dimensional ideals. In: Effective Methods in Algebraic Geometry (Castiglioncello, 1990), Progress in Mathematics, vol. 94, pp. 227-234. Birkhäuser, Boston (1991). · Zbl 0859.94008
[26] Mancini M.: Projectively normal curves defined by quadrics. Rend. Semin. Mat. Univ. Politech. Torino 59(4), 269-275 (2001) · Zbl 1172.14318
[27] Márquez-Corbella I., Martínez-Moro E., Pellikaan R.: Cryptanalysis of public-key cryptosystems based on algebraic geometry codes. Oberwolfach Prepr. OWP 2012-01, 1-17 (2012).
[28] Márquez-Corbella I., Martínez-Moro E., Pellikaan R.: The non-gap sequence of a subcode of a generalized Reed-Solomon code. Des. Codes Cryptogr. doi:10.1007/s10623-012-9694-2 (2012). · Zbl 1263.94039
[29] McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep. 42-44, 114-116 (1978). · Zbl 0977.13011
[30] Möller H.M., Buchberger B.: The construction of multivariate polynomials with preassigned zeros. In: Computer Algebra (Marseille, 1982), Lecture Notes in Computer Science, vol. 144, pp. 24-31. Springer, Berlin (1982). · Zbl 0549.68026
[31] Mumford D.: Varieties defined by quadratic equations. In: Questions on Algebraic Varieties, C.I.M.E., III Ciclo, Varenna, 1969, pp. 29-100. Edizioni Cremonese, Rome (1970). · Zbl 0982.13015
[32] Mumford D.: Curves and Their Jacobians. University of Michigan Press, Ann Arbor (1975) · Zbl 0316.14010
[33] Munuera C., Pellikaan R.: Equality of geometric Goppa codes and equivalence of divisors. J. Pure Appl. Algebra 90(3), 229-252 (1993) · Zbl 0795.94015 · doi:10.1016/0022-4049(93)90043-S
[34] Niederreiter H.: Knapsack-type crypto systems and algebraic coding theory. Probl. Control Inf. Theory 15(2), 159-166 (1986) · Zbl 0611.94007
[35] Pellikaan R., Shen B.Z., van Wee G.J.M.: Which linear codes are algebraic-geometric? IEEE Trans. Inf. Theory 37, 583-602 (1991) · Zbl 0731.94012 · doi:10.1109/18.79915
[36] Petri K.: Über die invariante Darstellung algebraischer Funktionen einer Veränderlichen. Math. Ann. 88(3-4), 242-289 (1923) · JFM 49.0264.02 · doi:10.1007/BF01579181
[37] Piggott H.E., Steiner A.: Isogonal conjugates. A new approach to certain geometrical theorems and to a general theory of conics. Math. Gaz. 31, 130-144 (1947) · Zbl 0029.07101
[38] Room T.: The Geometry of Determinantal Loci. Cambridge University Press, Cambridge (1938) · Zbl 0020.05402
[39] Saint-Donat B.: Sur les équations définissant une courbe algébrique. C. R. Acad. Sci. Paris 274, 324-327, 487-489 (1972). · Zbl 0234.14012
[40] Saint-Donat B.: On Petri’s analysis of the linear system of quadrics through a canonical curve. Math. Ann. 206, 157-175 (1973) · Zbl 0315.14010 · doi:10.1007/BF01430982
[41] Sidelnikov V.M., Shestakov S.O.: On the insecurity of cryptosystems based on generalized Reed-Solomon codes. Discret. Math. Appl. 2, 439-444 (1992) · Zbl 0796.94006
[42] Stichtenoth H.: The automorphisms of geometric Goppa codes. J. Algebra 130, 113-121 (1990) · Zbl 0696.94012 · doi:10.1016/0021-8693(90)90104-V
[43] Stichtenoth H.: Algebraic function fields and codes. In: Graduate Texts in Mathematics, vol. 254, 2nd edn. Springer, Berlin (2009). · Zbl 1155.14022
[44] Tsfasman M.A., Vlǎduţ S.: Algebraic-Geometric Codes. Kluwer, Dordrecht (1991) · Zbl 0727.94007 · doi:10.1007/978-94-011-3810-9
[45] Veronese G.: Behandlung der projectivischen Verhältnisse der Räume von verschiedenen Dimensionen durch das Princip des Projectirens und Schneidens. Math. Ann. 19, 161-234 (1882) · JFM 13.0485.01 · doi:10.1007/BF01446461
[46] Wieschebrink C.: An attack on the modified Niederreiter encryption scheme. In: PKC 2006, Lecture Notes in Computer Science, vol. 3958, pp. 14-26. Springer, Berlin (2006). · Zbl 1151.94583
[47] Wieschebrink C.: Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. In: Post-quantum Cryptography, Lecture Notes in Computer Science, vol. 6061, pp. 61-72. Springer, Berlin (2010). · Zbl 1284.94124
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.