UVaDoc Colección: Dpto. Álgebra, Análisis Matemático, Geometría y Topología - Artículos de RevistaDpto. Álgebra, Análisis Matemático, Geometría y Topología - Artículos de Revistahttp://uvadoc.uva.es/handle/10324/11932019-03-26T08:00:01Z2019-03-26T08:00:01ZConstructing sequences with high nonlinear complexity using the Weierstrass semigroup of a pair of distinct points of a Hermitian curveGeil, OlavÖzbudak, FerruhRuano, Diegohttp://uvadoc.uva.es/handle/10324/324122018-11-04T19:33:54Z2018-01-01T00:00:00ZResumen: Using the Weierstrass semigroup of a pair of distinct points of a Hermitian curve over a finite field, we construct sequences with improved high nonlinear complexity. In particular we improve the bound obtained in [Theorem 3, IEEE Trans. Inform. Theory 60(10):6696-6701, 2014] considerably and the bound in [Theorem 4, IEEE Trans. Inform. Theory 60(10):6696-6701, 2014] for some parameters.2018-01-01T00:00:00ZBounding the number of points on a curve using a generalization of Weierstrass semigroupsBeelen, PeterRuano, Diegohttp://uvadoc.uva.es/handle/10324/317502018-09-30T18:33:46Z2013-01-01T00:00:00ZResumen: In this article we use techniques from coding theory to derive upper bounds for the number of rational places of the function field of an algebraic curve defined over a finite field. The used techniques yield upper bounds if the (generalized) Weierstrass semigroup for an n-tuple of places is known, even if the exact defining equation of the curve is not known. As shown in examples, this sometimes enables one to get an upper bound for the number of rational places for families of function fields. Our results extend results in [J. Pure Appl. Algebra, 213(6):1152-1156, 2009] .2013-01-01T00:00:00ZDecoding of matrix-product codes.Hernando, FernandoRuano, Diegohttp://uvadoc.uva.es/handle/10324/317482018-09-30T18:34:03Z2013-01-01T00:00:00ZResumen: We propose a decoding algorithm for the (u|u+v)-construction that decodes up to half of the minimum distance of the linear code. We extend this algorithm for a class of matrix-product codes in two different ways. In some cases, one can decode beyond the error correction capability of the code.2013-01-01T00:00:00ZGeneralization of the Lee-O'Sullivan list decoding for one-point AG codesMatsumoto, RyutarohRuano, DiegoGeil, Olavhttp://uvadoc.uva.es/handle/10324/317462018-09-30T18:33:37Z2013-01-01T00:00:00ZResumen: We generalize the list decoding algorithm for Hermitian codes proposed by Lee and O'Sullivan based on Gröbner bases to general one-point AG codes, under an assumption weaker than one used by Beelen and Brander. Our generalization enables us to apply the fast algorithm to compute a Gröbner basis of a module proposed by Lee and O'Sullivan, which was not possible in another generalization by Lax.2013-01-01T00:00:00ZList decoding of repeated codesHernando, FernandoO'Sullivan, Michael E.Ruano, Diegohttp://uvadoc.uva.es/handle/10324/317442018-09-30T18:33:32Z2013-01-01T00:00:00ZResumen: Assuming that we have a soft-decision list decoding algorithm of a linear code, a new hard-decision list decoding algorithm of its repeated code is proposed in this article. Although repeated codes are not used for encoding data, due to their parameters, we show that they have a good performance with this algorithm. We compare, by computer simulations, our algorithm for the repeated code of a Reed-Solomon code against a decoding algorithm of a Reed-Solomon code. Finally, we estimate the decoding capability of the algorithm for Reed-Solomon codes and show that performance is somewhat better than our estimates.2013-01-01T00:00:00ZFeng-Rao decoding of primary codesGeil, OlavMatsumoto, RyutarohRuano, Diegohttp://uvadoc.uva.es/handle/10324/317432018-09-30T18:33:26Z2013-01-01T00:00:00ZResumen: We show that the Feng-Rao bound for dual codes and a similar bound by Andersen and Geil for primary codes are consequences of each other. This implies that the Feng-Rao decoding algorithm can be applied to decode primary codes up to half their designed minimum distance. The technique applies to any linear code for which information on well-behaving pairs is available. Consequently we are able to decode efficiently a large class of codes for which no non-trivial decoding algorithm was previously known. Among those are important families of multivariate polynomial codes. Matsumoto and Miura derived from the Feng-Rao bound a bound for primary one-point algebraic geometric codes and showed how to decode up to
what is guaranteed by their bound. The exposition in Matsumoto-Miura requires the use
of differentials which was not needed in Andersen-Geil. Nevertheless we demonstrate a very strong connection between Matsumoto and Miura's bound and Andersen and Geil's bound when applied to primary one-point algebraic geometric codes.2013-01-01T00:00:00ZComputational Aspects of Retrieving a Representation of an Algebraic Geometry CodeMárquez-Corbella, IreneMartínez-Moro, EdgarPellikaan, RuudRuano, Diegohttp://uvadoc.uva.es/handle/10324/317382018-09-30T18:33:25Z2014-01-01T00:00:00ZResumen: Code-based cryptography is an interesting alternative to classic number-theoretic public key cryptosystem since it is conjectured to be secure against quantum computer attacks. Many families of codes have been proposed for these cryptosystems such as algebraic geometry codes. In [Designs, Codes and Cryptography, pages 1-16, 2012] -for so called very strong algebraic geometry codes $\mathcal C=C_L(\mathcal X, \mathcal P, E)$, where $\mathcal X$ is an algebraic curve over $\mathbb F_q$, $\mathcal P$ is an $n$-tuple of mutually distinct $\mathbb F_q$-rational points of $\mathcal X$ and $E$ is a divisor of $\mathcal X$ with disjoint support from $\mathcal P$ --- it was shown that an equivalent representation $\mathcal C=C_L(\mathcal Y, \mathcal Q, F)$ can be found. The $n$-tuple of points is obtained directly from a generator matrix of $\mathcal C$, where the columns are viewed as homogeneous coordinates of these points. The curve $\mathcal Y$ is given by $I_2(\mathcal Y)$, the homogeneous elements of degree $2$ of the vanishing ideal $I(\mathcal Y)$. Furthermore, it was shown that $I_2(\mathcal Y)$ can be computed efficiently as the kernel of certain linear map. What was not shown was how to get the divisor $F$ and how to obtain efficiently an adequate decoding algorithm for the new representation. The main result of this paper is an efficient computational approach to the first problem, that is getting $F$. The security status of the McEliece public key cryptosystem using algebraic geometry codes is still not completely settled and is left as an open problem2014-01-01T00:00:00ZRelative generalized Hamming weights of one-point algebraic geometric codesGeil, OlavMartin, StefanoMatsumoto, RyutarohRuano, DiegoLuo, Yuanhttp://uvadoc.uva.es/handle/10324/317372018-09-30T18:33:26Z2014-01-01T00:00:00ZResumen: Security of linear ramp secret sharing schemes can be characterized by the relative generalized Hamming weights of the involved codes. In this paper, we elaborate on the implication of these parameters and devise a method to estimate their value for general one-point algebraic geometric codes. As it is demonstrated, for Hermitian codes, our bound is often tight. Furthermore, for these codes, the relative generalized Hamming weights are often much larger than the corresponding generalized Hamming weights.2014-01-01T00:00:00ZNew quantum codes from evaluation and matrix-product codesGalindo, CarlosHernando, FernandoRuano, Diegohttp://uvadoc.uva.es/handle/10324/317322018-09-30T18:33:31Z2015-01-01T00:00:00ZResumen: Stabilizer codes obtained via the CSS code construction and the Steane's enlargement of subfield-subcodes and matrix-product codes coming from generalized Reed-Muller, hyperbolic and affine variety codes are studied. Stabilizer codes with good quantum parameters are supplied, in particular, some binary codes of lengths 127 and 128 improve the parameters of the codes in http://www.codetables.de. Moreover, non-binary codes are presented either with parameters better than or equal to the quantum codes obtained from BCH codes by La Guardia or with lengths that cannot be reached by them.2015-01-01T00:00:00ZStabilizer quantum codes from J-affine variety codes and a new Steane-like enlargementGalindo, CarlosHernando, FernandoRuano, Diegohttp://uvadoc.uva.es/handle/10324/317312018-09-30T18:33:37Z2015-01-01T00:00:00ZResumen: New stabilizer codes with parameters better than the ones available in the literature are provided in this work, in particular quantum codes with parameters [[127,63, >= 12]]_2 and [[63,45, >= 6]]_4 that are records. These codes are constructed with a new generalization of the Steane's enlargement procedure and by considering orthogonal subfield-subcodes -with respect to the Euclidean and Hermitian inner product- of a new family of linear codes, the J-affine variety codes.2015-01-01T00:00:00ZList decoding algorithm based on voting in Gröbner bases for general one-point AG codesMatsumoto, RyutarohRuano, DiegoGeil, Olavhttp://uvadoc.uva.es/handle/10324/317302018-09-30T18:33:27Z2017-01-01T00:00:00ZResumen: We generalize the unique decoding algorithm for one-point AG codes over the Miura-Kamiya Cab curves proposed by Lee, Bras-Amorós and O'Sullivan (2012) to general one-point AG codes, without any assumption. We also extend their unique decoding algorithm to list decoding, modify it so that it can be used with the Feng-Rao improved code construction, prove equality between its error correcting capability and half the minimum distance lower bound by Andersen and Geil (2008) that has not been done in the original proposal except for one-point Hermitian codes, remove the unnecessary computational steps so that it can run faster, and analyze its computational complexity in terms of multiplications and divisions in the finite field. As a unique decoding algorithm, the proposed one is empirically and theoretically as fast as the BMS algorithm for one-point Hermitian codes. As a list decoding algorithm, extensive experiments suggest that it can be much faster for many moderate size/usual inputs than the algorithm by Beelen and Brander (2010). It should be noted that as a list decoding algorithm the proposed method seems to have exponential worst-case computational complexity while the previous proposals (Beelen and Brander, 2010; Guruswami and Sudan, 1999) have polynomial ones, and that the proposed method is expected to be slower than the previous proposals for very large/special inputs.2017-01-01T00:00:00ZRefined analysis of RGHWs of code pairs coming from Garcia-Stichtenoth's second towerGeil, OlavMartin, StefanoMartínez-Peñas, UmbertoRuano, Diegohttp://uvadoc.uva.es/handle/10324/317292018-09-30T18:33:28Z2017-01-01T00:00:00ZResumen: Asymptotically good sequences of ramp secret sharing schemes were given in [arXiv:1502.05507] by using one-point algebraic geometric codes defined from asymptotically good towers of function fields. Their security is given by the relative generalized Hamming weights of the corresponding codes. In this paper we demonstrate how to obtain refined information on the RGHWs when the codimension of the codes is small. For general codimension, we give an improved estimate for the highest RGHW.2017-01-01T00:00:00ZOn the distance of stabilizer quantum codes from J-affine variety codesGalindo, CarlosGeil, OlavHernando, FernandoRuano, Diegohttp://uvadoc.uva.es/handle/10324/317242018-09-30T18:33:32Z2017-01-01T00:00:00ZResumen: Self-orthogonal J-affine variety codes have been successfully used to obtain quantum stabilizer codes with excellent parameters. In a previous paper we gave formulae for the dimension of this family of quantum codes, but no bound for the minimum distance was given. In this work, we show how to derive quantum stabilizer codes with designed minimum distance from J-affine variety codes and their subfield-subcodes. Moreover, this allows us to obtain new quantum codes, some of them either, with better parameters, or with larger distances than the previously known codes.2017-01-01T00:00:00ZOn asymptotically good ramp secret sharing schemesGeil, OlavMartin, StefanoMartínez-Peñas, UmbertoMatsumoto, RyutarohRuano, Diegohttp://uvadoc.uva.es/handle/10324/317232018-09-30T18:34:45Z2017-01-01T00:00:00ZResumen: Asymptotically good sequences of linear ramp secret sharing schemes have been intensively studied by Cramer et al. in terms of sequences of pairs of nested algebraic geometric codes. In those works the focus is on full privacy and full reconstruction. In this paper we analyze additional parameters describing the asymptotic behavior of partial information leakage and possibly also partial reconstruction giving a more complete picture of the access structure for sequences of linear ramp secret sharing schemes. Our study involves a detailed treatment of the (relative) generalized Hamming weights of the considered codes.2017-01-01T00:00:00ZImproved constructions of nested code pairsGalindo, CarlosGeil, OlavHernando, FernandoRuano, Diegohttp://uvadoc.uva.es/handle/10324/317222018-09-30T18:33:39Z2018-01-01T00:00:00ZResumen: Two new constructions of linear nested code pairs are given for which the codimension and the relative minimum distances of the codes and their duals are good. By this we mean that for any two out of the three parameters the third parameter of the constructed code pair is large. Such pairs of nested codes are indispensable for the determination of good linear ramp secret sharing schemes. They can also be used to ensure reliable communication over asymmetric quantum channels. The new constructions result from carefully applying the Feng-Rao bounds to a family of codes defined from multivariate polynomials and Cartesian product point sets.2018-01-01T00:00:00ZNew binary and ternary LCD codesGalindo, CarlosGeil, OlavHernando, FernandoRuano, Diegohttp://uvadoc.uva.es/handle/10324/317212018-09-30T18:34:09Z2018-01-01T00:00:00ZResumen: LCD codes are linear codes with important cryptographic applications. Recently, a method has been presented to transform any linear code into an LCD code with the same parameters when it is supported on a finite field with cardinality larger than 3. Hence, the study of LCD codes is mainly open for binary and ternary fields. Subfield-subcodes of J-affine variety codes are a generalization of BCH codes which have been successfully used for constructing good quantum codes. We describe binary and ternary LCD codes constructed as subfield-subcodes of J-affine variety codes and provide some new and good LCD codes coming from this construction.2018-01-01T00:00:00Z