Project topics and materials
Get Complete Project Material File(s) Now! »
Introduction to algebraic geometry
In this section, we introduce some definitions and properties about algebraic curves that will be used in this thesis, we refer to [Mor93] and [Ful08]. This background will permit us to define algebraic geometry (AG) codes and some properties of these codes. Details for this part can be found in [TVN07] and [HvLP98]. For some technical results, we will also use the language of function field theory, for more details see [Sti09].
Later on, we will denote F any field algebraically closed. We denote by An the n-dimensional affine space over F.
Algebraic curves
In this section, we only treat projective curve and in order to give a definition for this object, we need first to define the notion of projective space. The n-dimensional projective space over F, denoted by Pn(F) or for short Pn, consists in all equivalence classes of (n + 1)-tuples, denoted
P := (x1 : : xn+1), with xi 2 F and not all zero, under the relation:
(x1 : : xn+1) (y1 : : yn+1) () 9 2 F s.t 8i 2 f1; : : : ; n + 1g; xi = yi:
The equivalent classes P , described just above, are called points of the projective space Pn and any (n + 1)-tuple defining a point P is called a set of homogeneous coordinates of P . There is a natural embedding An ,! Pn given by (x1; : : : ; xn) 7!(x1 : : xn : 1). The points of the complementary set of An in Pn, that is the points of Pn such that xn+1 = 0, are called points at infinity.
Definition 1.11. A polynomial F 2 F[X1; : : : ; Xn+1] is homogeneous of degree d if for any (n + 1)-tuple (x1; : : : ; xn+1) 2 Fn+1 and any scalar 2 F , we have F ( x1; x2; : : : ; xn+1) = dF (x1; : : : ; xn+1):
The “evaluation” of a polynomial F 2 F[X1; : : : ; Xn+1] in a point P of Pn does not make sense since it depends on the choice of the set of homogeneous coordinate defining P . However, if the polynomial is homogeneous then its zero set is well-defined. Let S F[X1; : : : ; Xn+1] be any set of homogeneous polynomials, we associate with S the following set, called the zero set of S:
Z(S) := fP 2 Pn j f(P ) = 0 for every f 2 Sg:
A subset Y Pn is a projective algebraic set if there exists S Fq[X1; : : : ; Xn+1] of homogeneous polynomials such that Y = Z(S). The set Y is called irreducible if Y is non-empty and cannot be written as the union of two proper algebraic subset Y = Y1 [ Y2, such that Y1 * Y2 and Y2 * Y1. A topology can be defined on projective algebraic sets as follows:
Definition 1.12 (Zariski topology). The Zariski topology on Pn is defined by taking the open sets to be the complement of algebraic sets.
Definition 1.13. A projective variety is an irreducible closed subset of Pn. An open subset of a projective variety is a quasi-projective variety.
Let Y be an algebraic set, the homogeneous ideal of Y is the ideal I(Y) generated by the set ff 2 F[X1; : : : ; Xn+1] homogeneous polynomial s.t. f(P ) = 0; 8P 2 Yg.
Definition 1.14 (Coordinate ring). Let Y be an algebraic set, we define the coordinate ring of Y to be Fq[Y] := Fq[X1; : : : ; Xn+1]=I(Y).
Later on, a projective or a quasi-projective variety will be referred to as a variety. Let Y be a variety and F; G 2 F[X1; : : : ; Xn+1] be homogeneous polynomials of same degree with G 2= I(Y).
Then the fraction GF 2 F(X1; : : : ; Xn+1) is called a rational function on Y. The elements GF and GF00 define the same rational function if the polynomial F G0 F 0G vanishes at all P 2 Y.
Definition 1.15. The function field F(Y) of a variety Y is the field of rational functions on Y and the dimension of Y is the transcendence degree of F(Y) over F.
Then we can define what is a projective algebraic curve as follows.
Definition 1.16 (Projective curve). A projective curve over F, denoted X =F or for short X , is defined as a variety of dimension one over the field F.
Example 1. In the affine plane over a finite field Fq, we consider the variety X defined by the homogeneous polynomial Y 3 X3 Z3. Let x := XZ and y := YZ , the function field F(X ) consists of all elements of the form QP with P; Q 2 Fq[x; y]. Since y satisfies y3 = x3 + 1 the transcendence degree of F(X ) over F is 1, that is the variety X is a curve.
As we see in Definition 1.15, we can associate to any curve X an object that we call function field of X . The function fields will be studied in the following section. For now, we speak about a notion that we use all the time in this thesis, the smoothness of a curve. The first definition holds for projective plane curves, that is projective curve X P2. This case is easier to understand and actually for results presented in this thesis it is the only one that we consider.
Definition 1.17. Let X be a projective plane curve defined by the homogeneous polynomial F 2 F[X; Y; Z]. Let P be a point on X . Then P is said to be nonsingular if at least one of the partial derivative @X@F ; @Y@F ; @F@Z is not zero at P . The curve X is called nonsingular or smooth if all its points are nonsingular.
Example 2. Consider the plane curve X defined by the polynomial F (X; Y; Z) := Y 3 X3 Z3 over a finite field Fq. The partials derivatives are 3X2, 3Y 2 and 3Z2, so the curve is smooth if the characteristic is not 3.
Definition 1.18. Let X be a projective curve and P be a point of this curve. Then a function f 2 F(X ) is called regular at the point P if it admits a representation f = GF with G non zero at P .
Definition 1.19 (Local ring of a point). Let P be a point on a projective curve X . The set of regular functions at the point P from a ring, denoted OP , and called the local ring of P .
The terminology for the ring OP makes sense since it is a local ring, that is OP has a unique maximal ideal. More precisely, we have the following proposition.
Proposition 1.8. The subset mP OP consisting of functions f 2 OP such that f(P ) = 0, is the unique maximal ideal of OP .
Proof. The subset mP OP is obviously an ideal, we show that it is maximal. Let N be an ideal of OP such that mP ( N. We consider f 2 N such that f 2= mP and we write f = GF . Since f 2 OP we have G(P ) 6= 0. Moreover f 2= mP , then F (P ) 6= 0. That is the function GF 2 OP and then 1 = GF f 2 N. Hence N = OP and mP is maximal.
To complete the proof we notice that actually OP nmP = OP , that is any invertible element of OP . Then mP contains any proper ideal of OP .
Curve over finite field. In our application, we need to consider finite field Fq and not its algebraic closure Fq. A way to define curve over finite field is the following.
A projective curve X =Fq over the finite field Fq is a projective curve X Pn(Fq) such that the homogeneous polynomials defining this curve have coefficients in Fq. The field of rational functions on X with coefficients in Fq will be denoted as Fq(X ) and we say it is the function field of X =Fq. Moreover, we denote by X (Fq) the set of points of X with coordinates lying in Fq, such points are called rational points.
Example 3. Consider the Klein curve K3 defined, over F4, by the homogeneous equation X3Y +Y3Z+Z3X =0:
We denote the element of F4 as 0; 1; ; + 1, then we have K3(F4) = f(0 : 0 : 1); ( : + 1 : 1); ( + 1 : : 1); (1 : 0 : 0); (0 : 1 : 0)g :
Example 4 (Hermitian curve). Let q = q02 and consider the curve H over Fq defined by the equation Y q0 Z + Y Zq0 Xq0+1 = 0:
This curve is called the Hermitian curve over the field Fq. The curve H has q03 + 1 rational points described by H(Fq) = P ; := ( : : 1) j q0+1 = q0 + [ P1; where P1 := (0 : 1 : 0) 2 P2.
Definition 1.20. A closed point P of a projective plane curve X , defined over Fq, is an orbit under the Frobenius automorphism fq : (x : y : z) 7!(xq : yq : zq). The degree of a closed point is defined as the cardinality of the orbit.
Function fields
In this section, it is not necessary that the field F is algebraically closed. To avoid misunder-standing we keep notation of previous section and in any of the following results and definitions, F can be replaced by a finite field Fq. This algebraic point of view will be useful in Section 5 that is why here we give a small dictionary between projective curves and function fields in one variable. If there is no mention, details about this section can be found in [Sti09]. First, let us recall what is a function field in one variable.
Definition 1.21. An algebraic function field F=F in one variable over the field F is an extension field F F such that F is a finite algebraic extension of F(x), where x 2 F is transcendental over F.
By Definitions 1.15 and 1.16, we know that the field of rational functions F(X ) of a projective curve is a function field in one variable. The converse is also true. This result can be found in [TVN07] as follows and a proof is given in [Mor93].
Theorem 1.9 ([Mor93, Theorem 1.1]). Let F=F be a function field in one variable, then there ex-ist a smooth irreducible projective curve X such that the field F(X ) is isomorphic (as an extension of F) to F .
Definition 1.22. A valuation ring of the function field F=F is a ring O F such that (1) F(O(F (2) for any x 2 F , we have x 2 O or x 1 2 O.
In Section 1.2.1 we defined the local ring OP of a point P the function field F(X ), that is why the notations are similar. valuation rings.
Proposition 1.10. Let O be a valuation ring of a function field F=F.
(1) O is a local ring, i.e. O has a unique maximal ideal P = OnO .
(2) Let x 2 F , then x 2 P () x 1 2= O.
(3) The maximal ideal P of O is a principal ideal.
Now we define the notion of place, which replaces that of points of a curve (or closed points if we consider a curve over Fq) when we use the language of function field.
Definition 1.23. A place P of the function field F=F is the maximal ideal of some valuation ring O of F . We denote by PF the set of all places of the function field F . Every element t such that P = tO is called a local parameter for P .
By Proposition 1.10 (2), we know that the valuation ring O is uniquely determined by its maximal ideal P . We can denote by OP = fx 2 F j x 1 2= P g the valuation ring of the place P .
Remark 3. For the case where F is algebraically closed, let F = F(X ) for some smooth projective curve X . There is a one-to-one correspondence between the set of places PF and the points of X . Then the valuation ring of a place P 2 PF coincides with the local ring of a point Q 2 X . That is why there is no ambiguity in the notation OP in this case.
By this correspondence and Proposition 1.10 (3), the maximal ideal mP , where P is a point of a smooth curve X , is principal. As in Definition 1.23 we call a local parameter of the point P , any element t 2 F(X ) such that mP = tOP .
Proposition 1.11. If P = tOP , then any function x 2 F has a unique representation of the form x = tnu, with n 2 Z and u 2 OP .
We consider x 2 OP a function such that its unique representation is x = t nu, where t is a local parameter of P . If n > 0 then we say that P is a zero of x, if n < 0 we say that P is a pole of x. We denote vP (x) = n the valuation of x at P . For any place P , vP is a discrete valuation of F=F, that is it satisfies the following properties.
(1) vP (x) = 1 () x = 0.
(2) vP (xy) = vP (x) + vP (y) for all x; y 2 F .
(3) vP (x + y) minfvP (x); vP (y)g for all x; y 2 F .
(4) There exists an element z 2 F such that vP (z) = 1.
(5) vP (a) = 0 for all a 2 F .
Note that the definition of vP depends only of the place P and not on the choice of the local parameter. Indeed, if we consider t0 another local parameter of P , then we have t = t0w, with w 2 OP . Hence x = (t0w)nu = t0n(wnu) and wnu 2 OP .
Proposition 1.12. Any non-zero function x of a function field F , has only finitely many zeros and poles.
Definition 1.24. The field FP := OP =P is called the residue class field of P . Then the degree of P is defined as deg(P ) := [FP : F]. A place of degree 1 is also called a rational place.
The degree of a place is always finite (see [Sti09, Proposition 1.1.15]).
Correspondence with curves over a finite field. In Remark 3, we talked about the one-to-one correspondence between points and places in the case where the defining field F is alge-braically closed. What happens now if we consider curve defined over a finite field Fq? Let X =Fq be a projective curve defined over Fq and Fq(X ) its function field. In this case the places of Fq(X ) are in one-to-one correspondence with the closed points of X . This correspondence permits to transfer notions from the language of curve to the language of function field (and reciprocally).
Automorphisms and fixed field. Let F=Fq be a function field, we consider Aut(F ) the (field) automorphism group of F . For a finite subgroup G Aut(F ), we denote by F G the function field consisting in all functions of F fixed by every element of G. Then the field extension F=F G is Galois of degree jGj. Let X be a smooth projective curve associated to F . The curve associated to F G is called the quotient curve of X by G and denoted by X =G.
Definition 1.25. Let F be a function field and G Aut(F ). Let P 2 PF and P 0 2 PF G be two places.
(i) P is said to lie over P 0 if P 0 P , and we write P jP 0.
(ii) The integer e(P jP 0) such that
vP (x) = e(P jP 0)vP 0(x); 8x 2 F
is called the ramification index of P over P 0. We say that P jP 0 is ramified if e(P jP 0) > 1 and unramified otherwise.
The following property will be useful in Section 5.
Proposition 1.13. Let F be a function field and 2 Aut(F ). Let P 2 PF and P 0 2 PF h i such that P jP 0, then (P ) := f (z) j z 2 P g is a place of F such that (P )jP 0 and e( (P )jP 0) = e(P jP 0):
Divisors
In this section we choose to present the different notions in the geometric point of view, that is we speak about curve and points rather than function field and places. As we saw in the previous section all theses notions can be transferred in the algebraic language. Through this section X denotes a smooth irreducible projective curve over a finite field Fq.
Definition 1.26 (Divisors). The divisor group of a projective curve X is defined as the free abelian group which is generated by the closed points of X . This group is denoted by Div(X ). A divisor G on X , is an element of Div(X ) and so has the following form G = nP P ; P 2X
where P are closed points of X and nP are integers all zero but finitely many. The support of G is defined as Supp(G) := fP 2 X j nP 6= 0g:
For a place Q 2 X and a divisor G = nP P , we define vQ(D) := nQ. If for all place P 2 Supp(G), we have vP (G) > 0 then G is called an effective divisor. Finally we define the degree of G as
X deg(G) := vP (G) deg(P ): P 2X
The group Div(X ) has a partial order defined as X X nP P mP P () 8P 2 X ; nP mP : P2X P2X
In particular, if G 2 Div(X ) is an effective divisor we note G 0. Now consider a non-zero function x 2 Fq(X ) , we assign to x the divisor (x) := vP (x)P :
This definition is consistent since, by Proposition 1.12, x has a finite number of zeros and poles on X . Such divisors are called principal divisors and form a subgroup of Div(X ), denoted by Princ(X ), since for x; y 2 Fq(X) we have (xy) = (x) + (y).
Example 5. Let f 2 Fq[x] be a polynomial function and Z := fx1; : : : ; xsg be the set of zero of f. We denote mi the multiplicity of the zero xi for all i 2 f1; : : : ; sg. Then the divisor of f on the projective line is (f) := miPi + deg(f)P1; i=0
where Pi := (xi : 1) and P1 is the unique pole of x on the projective line.
Definition 1.27. Two divisors G1; G2 2 Div(X ), are said to be linearly equivalent if G1 G2 2 Princ(X ), that is to say there exists a function x 2 Fq(X ) such that G1 = G2 + (x). Then we write G1 G2. This is an equivalence relation and the class group of X is Cl(X ) := Div(X )= Princ(X ):
Proposition 1.14. The degree of a principal divisor is zero.
Let us denote by Div0(X ) the group of divisors of X of degree 0. By the previous proposition Princ(X ) Div0(X ) and then we define the group of divisor classes of degree 0 as Cl0(X ) := Div0(X )= Princ(X ). Moreover, Proposition 1.14 implies that all divisors in a same equivalent class have the same degree.
Proposition 1.15 ([Mor93, Chap. 3]). For any integer r, the number of divisor classes in Cl(X ) of degree r is independent of r and is equal to the cardinality of Cl0(X ).
For the following result, we need to know what is the genus of a curve. We choose to give this definition later when it will be possible (Definition 1.31). For now, we admit that the genus is an invariant of the curve X and it is a non negative integer.
Theorem 1.16 ([TVN07, Proposition 3.1.23]). Let X be a projective curve defined over Fq. The number of divisor classes in Cl0(X ), called the class number and denoted by h(X ), satisfies:
(pq 1)2g h(X ) (pq + 1)2g;
where g is the genus of X .
The following consequence about the specific case of divisors on the projective line will be useful in Section 5.
Corollary 1.17. Let P1 be the projective line and G1; G2 2 Div(P1), such that deg(G1) = deg(G2). Then G1 G2.
The following definition will be useful to define algebraic geometry codes on a projective curve X . Algebraic geometry (AG) codes are evaluation codes on a curve X , the vector space which is evaluated is the following.
Definition 1.28. Let G be a divisor on X =Fq, we define L(G) the Riemann-Roch space of G by:
L(G) := ff 2 F(X ) j (f) Gg [ f0g:
L(G) is a vector space over Fq and its dimension over Fq is denoted by ‘(G) := dimFq L(G).
The computation of the dimension ‘(G) of a Riemann-Roch space L(G) is very important to know the dimension of an AG code. For now, we cannot estimate exactly this dimension but we provide the following bound.
Lemma 1.18. For a projective curve X and a divisor G 2 Div(X ), we have ‘(G) maxf0; deg(G) + 1g:
In particular, if deg(G) < 0 then ‘(G) = 0, that is L(G) = f0g.
Example 6. Consider the point at infinity P1 on the projective line over Fq, and let k > 0 be an integer. Then the Riemann-Roch space L(kP1) =< 1; x; : : : ; xk > has dimension k + 1 over Fq.
Lemma 1.19. Let G1; G2 2 Div(X ) be two linearly equivalent divisors. By definition, there exists h 2 Fq(X ) such that G1 = G2 + (h). Now, consider the following Fq-linear map
L(G1) ! L(G2) ;
f 7! hf it defines an isomorphism between L(G1) and L(G2). Then for a divisor G the value of ‘(G) depends only on its linear equivalence class.
Riemann-Roch Theorem
In this section we introduce some definitions and results in order to present the Riemann-Roch theorem. This theorem gives an explicit expression of the dimension ‘(G) for any divisor G. Before presenting this result we need to give the definition of differential forms on a curve and some basic properties of these objects. In the following, X denotes a smooth projective plane curve over Fq. For this part we refer to [HvLP98].
A derivation over Fq(X ) is an Fq-linear map D : Fq(X ) ! Fq(X ), satisfying the Leibnitz rule D(xy) = xD(y) + yD(x) for any function x; y 2 Fq(X ). The set of derivations, that we denote by Der(Fq(X )), is a vector space over the field Fq(X ).
Table of contents :
Introduction
Résumé
1 Algebraic geometry codes
1.1 Coding theory
1.2 Introduction to algebraic geometry
1.3 AG codes: definition and properties
2 Code-based cryptography
2.1 McEliece encryption scheme
2.2 Information Set Decoding (ISD)
2.3 Key recovery problem
2.4 Algebraic cryptanalysis of McEliece schemes using alternant codes
3 McEliece scheme using quasi-cyclic alternant codes
3.1 Quasi-cyclic alternant codes
3.2 Structural analysis of the invariant code
3.3 Security reduction to the key security of the invariant code
3.4 Proposition of a scheme: BIG QUAKE
4 A structural attack on a scheme using quasi-dyadic alternant codes
4.1 Presentation of the NIST submission: DAGS
4.2 Schur products and conductors
4.3 Using the QD structure to compute a conductor
4.4 Description of the attack
4.5 Algorithm, work factor and implementation
5 Short McEliece keys from codes on curves with positive genus
5.1 Construction of quasi-cyclic SSAG codes
5.2 Structure of the invariant code
5.3 QC codes from a cyclic cover of the projective line
5.4 The McEliece scheme with QC Hermitian codes
Bibliography
