Search

The study of new error correcting codes has raised attention in the last years, especially because of their use in cryptosystems that are resistant to attacks running on quantum computers. In 2006, while leaving a more in-depth analysis for future research, Stakhov gave some interesting ideas on how to exploit Fibonacci numbers to derive an original error correcting code with a compact representation. In this paper, we provide an explicit formula to compute the redundancy of Stakhov codes, we identify some flows in the initial decoding procedure described by Stakhov, whose crucial point is to solve some non-trivial Diophantine equations, and provide a detailed discussion on how to avoid solving such equations in some cases and on how to detect and correct errors more efficiently. [ABSTRACT FROM AUTHOR]

Abstract Let H be the Hermitian curve defined over a finite field F q 2 . In this paper we complete the geometrical characterization of the supports of the minimum-weight codewords of the algebraic-geometry codes over H , started in [26] : if d is the distance of the code, the supports are all the sets of d distinct F q 2 -points on H complete intersection of two curves defined by polynomials with prescribed initial monomials w.r.t. DegRevLex. For most Hermitian codes, and especially for all those with distance d ≥ q 2 − q studied in [26] , one of the two curves is always the Hermitian curve H itself, while if d < q the supports are complete intersection of two curves none of which can be H. Finally, for some special codes among those with intermediate distance between q and q 2 − q , both possibilities occur. We provide simple and explicit numerical criteria that allow to decide for each code what kind of supports its minimum-weight codewords have and to obtain a parametric description of the family (or the two families) of the supports. [ABSTRACT FROM AUTHOR]

We study locally recoverable codes on algebraic curves. In the first part of the manuscript, we provide a bound on the generalized Hamming weight of these codes. In the second part, we propose a new family of algebraic geometric LRC codes, which are LRC codes from the Norm-Trace curve. Finally, using some properties of Hermitian codes, we improve the bounds on the distance proposed in Barg et al. (2015) [1] of some Hermitian LRC codes. [ABSTRACT FROM AUTHOR]

For any affine-variety code we show how to construct an ideal whose solutions correspond to codewords with any assigned weight. We are able to obtain geometric characterizations for small-weight codewords for some families of Hermitian codes over any F q 2 . From these geometric characterizations, we obtain explicit formulas. In particular, we determine the number of minimum-weight codewords for all Hermitian codes with d ≤ q and all second-weight codewords for distance- 3 , 4 codes. [ABSTRACT FROM AUTHOR]

Abstract: We classify completely the intersections of the Hermitian curve with parabolas in the affine plane. To obtain our results we employ well-known algebraic methods for finite fields and geometric properties of the curve automorphisms. In particular, we provide explicit counting formulas that have also applications to some Hermitian codes. [Copyright &y& Elsevier]

Abstract: General error locator polynomials are polynomials able to decode any correctable syndrome for a given linear code. Such polynomials are known to exist for all cyclic codes and for a large class of linear codes. We provide some decoding techniques for affine-variety codes using some multidimensional extensions of general error locator polynomials. We prove the existence of such polynomials for any correctable affine-variety code and hence for any linear code. We propose two main different approaches, that depend on the underlying geometry. We compute some interesting cases, including Hermitian codes. To prove our coding theory results, we develop a theory for special classes of zero-dimensional ideals, that can be considered generalizations of stratified ideals. Our improvement with respect to stratified ideals is twofold: we generalize from one variable to many variables and we introduce points with multiplicities. [Copyright &y& Elsevier]

In addition to their usefulness in proving one's identity electronically, identification protocols based on zero-knowledge proofs allow designing secure cryptographic signature schemes by means of the Fiat–Shamir transform or other similar constructs. This approach has been followed by many cryptographers during the NIST (National Institute of Standards and Technology) standardization process for quantum-resistant signature schemes. NIST candidates include solutions in different settings, such as lattices and multivariate and multiparty computation. While error-correcting codes may also be used, they do not provide very practical parameters, with a few exceptions. In this manuscript, we explored the possibility of using the error-correcting codes proposed by Stakhov in 2006 to design an identification protocol based on zero-knowledge proofs. We showed that this type of code offers a valid alternative in the error-correcting code setting to build such protocols and, consequently, quantum-resistant signature schemes. [ABSTRACT FROM AUTHOR]

In this paper we consider the Hermitian codes defined as the dual codes of one-point evaluation codes on the Hermitian curve H over the finite field F q 2 . We focus on those with distance d ≥ q 2 − q and give a geometric description of the support of their minimum-weight codewords. We consider the unique writing μ q + λ (q + 1) of the distance d with μ , λ non negative integers, and μ ≤ q , and consider all the curves X of the affine plane A F q 2 2 of degree μ + λ defined by polynomials with x μ y λ as leading monomial with respect to the DegRevLex term ordering (with y > x). We prove that a zero-dimensional subscheme Z of A F q 2 2 is the support of a minimum-weight codeword of the Hermitian code with distance d if and only if it is made of d simple F q 2 -points and there is a curve X such that Z coincides with the scheme theoretic intersection H ∩ X (namely, as a cycle, Z = H ⋅ X). Finally, exploiting this geometric characterization, we propose an algorithm to compute the number of minimum weight codewords and we present comparison tables between our algorithm and MAGMA command MinimumWords. [ABSTRACT FROM AUTHOR]

The correctness in decrypting a ciphertext after some operations in the DGVH scheme depends heavily on the dimension of the secret key. In this paper we compute two bounds on the size of the secret key for the DGHV scheme to decrypt correctly a ciphertext after a fixed number of additions and a fixed number of multiplication. Moreover we improve the original bound on the dimension of the secret key for a general circuit. [ABSTRACT FROM AUTHOR]