Open access peer-reviewed chapter

The Security of Cryptosystems Based on Error-Correcting Codes

Written By

Ahmed Drissi

Submitted: July 3rd, 2020 Reviewed: August 27th, 2020 Published: August 18th, 2021

DOI: 10.5772/intechopen.93782

Chapter metrics overview

294 Chapter Downloads

View Full Metrics


Quantum computers are distinguished by their enormous storage capacity and relatively high computing speed. Among the cryptosystems of the future, the best known and most studied which will resist when using this kind of computer are cryptosystems based on error-correcting codes. The use of problems inspired by the theory of error-correcting codes in the design of cryptographic systems adds an alternative to cryptosystems based on number theory, as well as solutions to their vulnerabilities. Their security is based on the problem of decoding a random code that is NP-complete. In this chapter, we will discuss the cryptographic properties of error-correcting codes, as well as the security of cryptosystems based on code theory.


  • McEliece cipher
  • hash function
  • syndrome decoding
  • correcting codes
  • random code

1. Introduction

Like all asymmetric cryptographic systems, the idea is to base security on the difficulty of reversing a one-way function with a trap door. The theory of error-correcting codes contains well-structured and difficult problems to solve, more or less suitable for use in cryptography. The first who had the idea of using error-correcting codes for cryptographic purposes was McEliece in 1978 and he proposed an asymmetric encryption algorithm. In 1986, Niederreiter proposed another cryptographic system equivalent to that of McEliece [1]. The two systems of McEliece and Niederreiter are of equivalent security against a passive attack; however, they are not against an active attack [2]. In the following paragraph, we give an overview of the theory of error-correcting codes. In the third paragraph, we will only deal with the basic systems based on this theory. The last paragraph is devoted to the discussion of security settings and the most well-known attacks. In what follows we note.

F2m: a finite field of 2m elements.

Kx: the ring of polynomials with an indeterminate.

Kx/P: the quotient ring Kx de modulo P.

K: a private set of the element 0.

dQx: the degree of the polynomial Qx.

F2m: the set of length vectors m and components 0 and 1.

Fn: the scalar product n times of the set F.

x: the integer part of x.

At: the transpose of the matrix A.

Ik: the identity matrix of order k.

gcd: greatest common divisor.

Cnt: the combination of t elements among n elements.


2. Error-correcting codes

2.1 Finite fields

Finite fields are the basis of many error-correcting codes and cryptographic systems, it is therefore essential to recall the theory of finite fields in order to understand the functioning of linear codes. In this paragraph we present some properties of finite fields and a method of representing them for later use. We are interested in constructing finite fields F2m and the calculations on these fields. Finite fields are generally constructed from primitive polynomials [3].


The minimal polynomial of an element β on a finite field Fis the unit polynomial with coefficients in F smaller degree and its value in β is zero.


  1. The ring Kx/P is a field if and only if the polynomial Px is irreducible on the field K.

  2. If Px is irreducible of degree mand K a finite field of q elements then Kx/P is field of qm elements.

This proposition gives us a way to build a finite field: Take a polynomial P irreducible over a field K et former le quotient Kx/P.

Theorem (the primitive element)

If K is a finite field of order q, then the multiplicative group K is cyclic generated by an element α called primitive element of K and we write K=αii=1q. Any generator of this group is called a primitive element of K.

Definition (primitive polynomial)

We say that a polynomial PF2x of degree m is primitive if it is the minimal polynomial of a generator of F2m.


Let F2xm=QxF2xdQxm1, PxF2xm primitive and α a root of Px, so we have: F2mF2xmF2x/PxF2m01αα2m1.

It follows from this lemma that we can represent the nonzero elements of a finite field F2m by nonzero vectors of F2m and that the αi have representatives of ximodPx and consequently αi=ximodPx. In what follows we denote by α a primitive element of F2m.

2.2 Principle of error-correcting codes

In order to transmit a message, it must be coded, it consists in temporarily giving it a certain form, the coding mode depends on the means of transmission, it can be disturbed by noise, hence the need for coding which allows the receiver to find the initial message even if it has been altered. Such coding is called channel coding. The principle of error-correcting codes is to add to a message to be transmitted additional information called redundant or control information, so that transmission errors can be detected and corrected. This operation is called coding and its result is a code word, each message is associated, therefore a code word of length greater than that of the message.

The code is the set of code words thus obtained. We assume that all messages are words of the same length >0, written using an alphabet F of q elements. Each message x0x1xk1 is an element of the set of Fk (message space). We then have qk possible messages. We assume that all the code words are of the same length n>k. Encode m messages of length k,mqk consists in choosing an integer n>k, and associate with each message from Fk a word from Fn (injectively). The coding introduces a redundancy equal to nk. Decoding consists of receiving a word x of Fn to determine if x is a code word and if not correct it thanks to the redundancy. This is done using the Hamming distance.

Definition (hamming distance)

let x=x0x1xn1x0x1xn1 and y=y0y1yn1y0y1yn1 of Fn. We call the Hamming distance between words x and y, and we note dHxy=dxy the number of index i012n1 such as xiyi, we call Hamming’s weight of a word x the number of nonzero components of x, we notewx=dx0.


We call the minimum distance of a code C an integer d such as d=mindmmmCmCmm. We call the weight of a word x of code Con integer wx=dx0.

Proposal (correction capacity)

Let C a minimum distance code d, and xFn a received message assigned to r errors, with r1.

  1. If 2r<d that is to say that rd12, the code Ccorrect r errors.

  2. If d12<r=d2, the C code detects the existence of r errors but cannot always correct them.

  3. If d2<rd1, the C code detects the existence d’ errors but risk of making an erroneous correction.

The integer t=d12 is called code correction capability, we also say that C is a t-corrector code.


Let m the code word transmitted and x the message received and assigned from r errors then dmx=r.

  1. We show that the code word m is the only code word such as dmxr.

Otherwise it exists m of C such as dmxr, we are dmmdmx+dxm2r<d, then m=m.

  1. There is no code word m of C such as dxm<dmx=r, but the code word m is not necessarily the only one to check dmx=r. Indeed be m=m1m2mn and m=m1m2mn two code words and if we receive the message x=m1m2mrm1mr, we’ll have dxm=dxm=r.

  2. We know there is an error because xC, but there may be a code word mC such as dmx<dmx=r.

The most used codes are the linear codes which we discuss in the next part.

2.3 Linear codes


A linear code C of size n and dimension k on the finite field Fq is a vector subspace of Fqn. We note it nkdq with d its minimum distance.

Linear codes are codes in which each code word y is obtained by linear transformation of the components of the initial word (information) x.

A linear code is characterized by its generator matrix G, we have C=y=xG/xFqk.

let Hnk×n matrix with coefficients in Fq. H is called the parity control matrix of C if “xCHxt”.

Fqk: the message space.

The systematic code

The matrix G defines a bijective function FqkC by xxG which we represent qk messages, its length k by code words, of lengthn.

The generator matrix G of a C code is not unique; G can be transformed into G=IkA with Ik the identity matrix with k order and A the matrix of k lines and nk columns.

G and G generate the same C subspace; G is called canonical generator matrix and if the generator matrix of a code is of the form G=IkA, this code is said systematic.


Let C a nkq linear code.

  1. If G is a generator matrix of C and H a parity control matrix of C then GHt=0.

  2. If G is a k×n matrix of rank k and H is a nk×n matrix of rank nk such as GHt=0 then we have:

H is a parity control matrix of C if and only if G is a generator matrix of C.


  1. We know that Ht=0, xC, in particular we have GiHt=0 for all i=1k with Gi is line of G. It follows that GHt=0.

  2. ) Since GHt=0, then we have GiHt=0. For all i=1k. And since H is a parity control matrix of C, we have the Gi belong to C. rgG=k, then Gii=1k constitute a basis of C. It follows that G is a generator matrix of C.

) we have yC if and only if it exists xFqk such as y=xG. Then yC if and only if yHt=xGHt=0. Then H is a parity control matrix of C.

In the case of systematic code, we have the following corollary.


Let C a nkq linear code

  1. If G=IkA a canonical generator matrix of C then H=AtInk is a parity control matrix ofC.

  2. If H=BInk is a parity control matrix of C then, G=IkBt is a generator matrix of C.


By applying the preceding theorem

  1. we have GHt=IkAAtInkt=A+A=0, if G is a generator matrix of C then, H is a parity control matrix ofC.

  2. we have GHt=IkBtBInkt=BtBt=0 then if H is a parity control matrix of C we will have G is a generator matrix of C.

Encoding and decoding

The coding is obtained by applying the generator matrix. Decoding consists in applying the control matrix to the message; if the result is 0 then the message is valid otherwise look for errors and correct them. Hxt is called syndrome. Suppose the word x is sent through a noisy channel and the word received is y so the error vector is e=yx.

Given y, the decoder must decide which word of the code x has been transmitted (which error vector?). For a vector u and a code C we call coset class of C, the set u+C=u+ccC. A representative of a class of C of minimum weight is called a leader of this class.


Let C a nkdq linear code then,

  1. u and v are of the same coset class of C if and only if uvC.

  2. Any vector of Fqn is in a coset of C.

  3. Given two coset classes, they are either disjoint or identical.


  1. If u,vx+C then, it exists y,zC such as u=x+y and v=x+z, then uv=yzC, because C is a vector subspace of Fqn.

If uvC it exists xC such as uv=x then u=v+xv+C and we have v=v+0v+C.

  1. Let aFqn, on a 0C thena=a+0a+C.

  2. Suppose that a+Cb+C, the nit exists vFqn such as a+Cb+C contains the element v, the nit exists x,yC such as v=a+x=b+y hence b=a+xy and a=b+yx. b+cb+C we have b+c=a+xy+ca+C (then b+Ca+C). a+ca+C We have a+c=b+yx+cb+C (then a+Cb+C), hence b+C=a+C.


We construct the standard array of C which is a matrix of qnk lines and qk columns. It contains all the vectors of Fqn; its first line corresponds to the words of C with vector 0 on the left. The other lines represent the cosets ui+C with the class leader ui to the left. The procedure is as follows:

  1. We list the words of C starting with 0 on the first line.

  2. We choose a vector u1 of minimum weight that does not belong to the first line and we list in the second line the elements u1+C, by entering below 0 the class leader u1 and below each element xC the element u1+x.

  3. We choose u2 in the same way and we repeat the same operation.

  4. We iterate this process until all the side classes are listed and all the vectors of Fqn appear only once.

When the word y is received, we look for its position in the standard table. The decoder then decides that the error vector e corresponds to the class leader who is located in the first column of the same row of y and decode y like x=ye, by choosing the code word of the first line on the same column ofy.


The standard table provides nearest neighbor decoding. Note that this process is too slow and too expensive in memory for large codes. In practice each code has by its structure a decoding algorithm.

2.4 The hamming code

A Hamming code with r2 redundancy is a linear code 2r12r1r2 its parity control matrix H, with H is a matrix of r lines and 2r1 columns that correspond to the set of all nonzero vectors of F2r.


The minimum distance of the Hamming 2r12r1r2 code is d=3 (it therefore corrects a single error).


This code does not contain any element of weight 1 and 2 otherwise we would have a column of H which would be zero or two columns of H would be identical.

It exists xC such as wx=3, indeed by definition of the parity control matrix H, the first 3 columns are 000000011101 then the vector x=11100 its weight wx=3 and belongs to C because Hxt=0.


The vector syndrome x of which only the jth component is nonzero is none other than the transpose of the jth column of H. If the columns of H are ordered in increasing order of binary numbers, the jth column corresponds to the binary writing of j, hence the following decoding algorithm:

Let y a message received, we calculate Hyt. If Hyt=0 then, y corresponds to the message transmitted. If Hyt0 and assuming there is only one error, Hyt directly gives the position of the error written in binary in the form b3b2b1b0. We can then correct y=y1yn like x+ej for j=i=1nbi2i and ej the vector of which only the jth coordinate is nonzero.

2.5 The Reed-Solomon codes

Let n=q1 with q=2m et Fqxk The set of polynomials of degree strictly less than k on F2m. Let us build a length code n and dimension k. Let L=α1α2αn a vector formed of distinct elements of F2m=αii=1n, with α primitive of F2m. Each word of the code is the evaluation of a function f of Fqxk on L then, we have a length code n and dimension k and generator matrix


By its structure, this code has a minimum distance of at least nk+1, because two polynomials of degrees less than k distinct cannot be equal in addition to k1 positions. This distance is exactly equal to nk+1, since the evaluation of a polynomial of the form i=1k1xαi his weight is nk+1. So we have a code on F2m of the form nknk+1q which can have both good transmission rate and good correction ability.


Reed-Solomon codes represent a special case of a slightly more general class called generalized Reed-Solomon codes GRS whose definition is as follows.


Let v1v2vn a vector of length n in F2m et α1α2αn a vector of length n in F2m, with the αi are distinct two by two.

The set of codes with the generator matrix G of the form G=v1v2vnv1α1v2α2vnαn..v1α1k1v2α2k1vnαnk1 is called the family of generalized Reed-Solomon codes.

2.6 The classical Goppa codes


Let L=α1α2αn a suite of n distinct elements of F2m and gzF2mz a unit polynomial of degree r irreducible in F2mz. The irreducible binary Goppa code, its support L (generator vector) and its generator polynomial g noted ΓLg is the set of words a=a1anF2n such that one of the following equivalent characterizations is verified:

  1. Raz=i=1naizαi=0modgz.

  2. Hat=0 with H=111α1α2αn...α1r1α2r1αnr1gα11....gαn1 parity check matrix.

  3. gz divided dσazdz with c σaz=i=1nzαiai locator polynomial.

The construction of a code Goppa:

Goppa’s code is a linear code on the field F2, its construction requires the use of an extension F2m. Each element of the matrix H is then broken down into m elements of F2 placed in columns, using a projection of F2m in F2m; we go from a size matrix r×n on F2m to a matrix of size rm×n on F2 so it is a length code n=L and dimension k=nmr and has a minimum distance at least equal to d=r+1. Indeed the parity check matrix H is written as the product of a Vandermonde matrix and an invertible matrix therefore all under a square matrix r×r of H is invertible, then there are no code words with a weight less than or equal to r.

The decoding of a Goppa code:

Several techniques exist to decode Goppa codes but they work by the same principle. Let c=c+e and we<r2. We start by calculating the syndrome Rcz on F2m; from this syndrome we will write a key equation, and we will finish the decoding by solving the key equation to finde.

If Raz=0 the word will belong to the code.

The key equation

Let σez=i=1nzαiei of degree <r2. On introduit le polynôme wez=σezRezmodgz called evaluator polynomial.


We can solve the key equation in two different ways: Berlekamp Massey’s algorithm and the extended Euclidean algorithm. The latter has the advantage of being easier to present. Indeed we seek to find we and σe of degree <r2 such as wez=σezRezmodgz=σezRez+kzgz. If we try to calculate the gcd of gRe with the extended Euclidean algorithm, we will calculate at each step the polynomials ui,vi,ri checking Reui+gvi=ri. At each step the polynomials ui and vi will be of degree <i and the degree of ri is equal to ri. There is therefore a step at which if we stop the algorithm we will find a solution of the equation σe=ui0 and wi0=ri0 to a scalar coefficient.


3. Encryption/decryption systems

3.1 The basic system (McEliece)

We start by generating a code nkdq linear of a well-chosen family and its generator matrix G. We are going to mix this matrix to make it indistinguishable from a random matrix, so we need a permutation matrix P her size is n×n (having 1 in each row and column and 0 everywhere) and an invertible matrix S her size k×k (S is jammer). The public key will be G=SGP which is indistinguishable from a random matrix (The definition of a random matrix comes from the definition of random code which be introduced in section four). The knowledge of S, P and G allows us to find the structure of the design code and provides us with the decoding algorithm.

3.1.1 The algorithms of the McEliece system

We cite the component algorithms of the McEliece cryptosystem [4].

The generation of keys


A family of linear codes nkdq chosen for design.


Choose a generator matrix G in systematic form of the design code.

Choose an invertible matrix S her size k with coefficients in Fq.

Choose a permutation matrix P her size is n×n.

Calculate G=SGP.


The public key G.

The private key SGP.

Encryption of the plaintext.


The public key G.

The plaintext xFqk.


Choose a vector eFqn (an error) his weight less than or equal to the design code correction capacity.

Calculate y=xG+e.

Output: The cipher text y.

Decryption of cipher text

Input: the cipher text y, The private key SGP.


Calculate u=yP1.

Calculate x=fGu with fG the design code decoding algorithm, whose generator matrix is G.

Calculate x=xS1.

Output: the plaintext x.


The use of binary Goppa code as a secret key is initially proposed by McEliece in its original version. Where he took the following parameters: m=10,n=2n=1024,r=50,k=nmr=524. So far it seems that this choice is perfectly safe, but it is not used in practice because the size of its public key is very large.


We use the Hamming code with its generator matrix G=1000101010001100101100001111 and parity check matrixH=101110001110101101001.

The generation of keys

Let the private key S,G,P.

S=1000010110110001=S1, P=0100000000100000100001000000000000100001000000010, P1=0001000100000000100000100000000001000000010000100

The public key: G=SGP=0100111100100111100011000111


Let the plaintext x=0110 and let error vector e=0010000.

The cipher text is y=xG+e=0111000+0010000=0101000.


We decipher the text received y=0101000. We have y=xG+e=xSGP+e then P1=xSG+eP1=1100000=y. Hyt=110, so the error is in the third position hence u=1110000=xSG. And since G is generator matrix of the systematic system then xS=1110 then x=1110S1=0110. x. Then the plaintext sought.

3.2 The Niederreiter variant

Let C a linear t-corrector code of length n and dimension k. Let H a parity check matrix of C her size is nk×n. We randomly choose an invertible matrix S and P a permutation matrix. We calculate H=SHP. We will have H a public key and SHP the private key, with the knowledge of a syndrome decoding algorithm in C. Let x a plaintext of length n and weight t, we calculate the cipher text y=Hxt. The recipient receives y knowing the secret key, he can calculate S1y=HPxt. Using the syndrome decoding algorithm of C, he can find Pxt and applying P1 the plaintext x is found.

The algorithms of the Niederreiter cryptosystem [5]

The generation of keys


A linear code nkdq is chosen for the design, of which we know a decoding algorithm by syndrome.


Choose a parity check matrix H of design code.

Choose a matrix S, invertible of size k with coefficients inFq.

Choose a permutation matrix P of sizen×n.

Calculate H=SHP.


The public key H.

The private keySHP.



The public key H.

The plaintext xFqn of weight less than or equal to the correction capacity.


Calculate y=Hxt.


The cipher texty.



The private key SHP.

The cipher texty.


Calculate y=S1y.

Calculate x=fHy with fH the code syndrome decoding algorithm, its parity check matrix is H.

Calculate x=xP1.


The plaintext x.


Reed-Solomon codes were originally proposed by Niederreiter as a family of codes that could be considered by his cryptosystem. In 1992 Sidelnikov and Shestakov have shown that it is easy to attack this cryptosystem [2].


4. The security of cryptosystems based on correcting codes

The security of cryptosystems based on error-correcting codes is based on the problem of distinguishing the design code (hidden) from a random code. We first give the following definitions:

  • Code equivalence

Two codes are said to be equivalent if their generator matrices (respectively parity) are deduced from each other by permutation of columns.

  • Random code

A random code is a linear code of which the k linearly independent lines of the generator matrix (or the n linearly independent columns of the parity matrix) have been generated randomly.

The main parameters for securing an McEliece cryptosystem and its variants are then the structure of the code family chosen for the design, which it is desirable that it will be difficult to find an equivalent code. Since the robustness of such a system lies in the difficulty of decoding and the hidden structure of the design code, then the attacker can attempt to attack the system by two methods: decoding attack and structural attack. The resistance of the system to these two attack methods depends on the family of codes chosen for the design. The choice of code family is the essential point in the design of the cryptosystem.

4.1 Decoding attack

The attacker directly attempts to decode the cipher text in the C code (generator matrix G or public key parity H); the principle consists of decoding the intercepted cipher text relative to the public code using general decoding algorithms. We cite two decoding problems in a random code:

Problem 1

Given G a random binary matrix of size k×n, generator of a C code of dimension k. xa random word of F2n and t a positive integer, find if there is an error word e of F2n such as wet and x+eC.

Problem 2

Given H a binary random parity matrix; her size nk×n of a C code its dimension k, sa random vector of F2nk and ta positive integer, find if there is a word x of F2n such as wxt and Hxt=s.

Decoding in random code is behind the following attacks:

  • Algorithme de décodage par ensemble d’information

The principle is based on two steps: the selection of a set of information and the search for low-weight word. There are several variants which propose to optimize one or the other of these two steps.


Let C a linear code of generator matrix G and length n. A set of information I is a subset of 12n such as GI, her size k×k formed of columns of G labeled by the elements of I, is invertible.


The matrix GIGJ with IJ=12n is equivalent to G.



G: a matrix generating of a code C.

t: a positive integer.

y: a word of F2n such as dyCt.


The couple xe such as y=xG+e wherewet.


Randomly draw a set of information I of the code C (let J such as IJ=12n).

Calculate R=GI1GJ.

Write y=yIyJ.

Calculate eJ=yJyIR.

Repeat the previous operations until you find eJ such as weJt.


Determine the word x such as ye=xG.


We have a y=xG+e and y=yIyJ=xGIGJ+eIeJ. Hence eI=yIxGI and eJ=yJxGJ.

If the set of information I does not contain an error position eI=0 and like GI is invertible, we obtain yI=xGI, eJ=yJyIGI1GJ. Then e=0yJyIGI1GJ. is the solution sought.


We have Cnk possibilities to choose k=I positions of 12n (I is a cardinally of I). And we have Cntk possibilities to choose k=I positions among nt positions where ei=0. So the probability of getting the set of information I with eI=0 is p=CntkCnk and the average number of iterations will be 1p.


Let us try to attack the following system by this method: We haveG=1110010101011110.

The cipher text y=10101011 ett=1.

looking me such as mG+e=y.

Let I=15128 then GI=1001=GI1 andGJ=110101101110.

yI=11 and yJ=010011. Then eJ=yJyIGI1GJ=001000, it follows that eIeJ=00001000.


then m=11.

  • Decoding by paradox of birthdays

Consider an instance of problem 2. For a parity check matrix H of size r×n, a syndrome s and a weight t. If the weight t is even, let us separate the columns of H in two sets of the same size H1 and H2 such as H=H1H2.

Let us build L1=H1e1te1of lengthn2and the weightt2 et L2=s+H2e2,te2of lengthn2and the weightt2. Common elements of L1 and L2 are such that H1e1t=s+H2e2t, that is to say e1e2 is solution of problem 2.

The probability that one of the solutions splits into two equal parts of the parity matrix is p=Cn/2t/22Cnt; to solve problem 2 you have to repeat these operations 1p on different permutations of the public code.

  • The recovery of a plaintext encrypted twice by the same McEliece system

This is an active attack that only applies to the McEliece encryption system (because it is not deterministic) and does not apply to the Niederreiter system. Suppose the plaintext x is encrypted in two different ways. We will have y1=xG+e1, y2=xG+e2e1 et e2 sont deux vecteurs d’erreur distincts de poids t. We get the word y1y2=e1e2 which is less than or equal to 2t. Once an attacker has detected that the two cipher texts y1 and y2 correspond to the same plaintext, this information will reduce the number of iterations of the decoding algorithm set of information. Message forwarding is detected by observing the weight of the two cipher texts. If the two plaintexts are identical then, the weight of the sum of the two numerical texts remains less than 2t in general (tthe correction capacity).



G: The public key of sizek×n.

Two words y1 and y2 such as y1=xG+e1, y2=xG+e2 where e1 and e2 are two distinct error vectors of weightt.


The plaintext x.


Calculate y1y2.

Randomly draw a set of information I12n which label the zero positions of y1y2.

Calculate eJ=yJyIGI1GJy1=yIyJ etIJ=12n.

Repeat the previous operations until the weight of e (t).

Return x=yIGI1.


Let us try to attack by this method the system of the previous example.

Either plaintext encrypted two ways in which the public key is


Draw a set of information that labels the zero positions of y1+y2 let I=78.

GI=0110=GI1, GJ=111001010111; y1=10101011,yI=11,yJ=101010.


So we extract m=11.

4.2 Structural attack

The attacker tries to find a decomposition of the key G=S1G1P1, which allows it to develop its own decoding algorithm. Succeeding in a structural attack generally amounts to finding a code equivalent to the public code for which we know a decoding algorithm. This attack depends exclusively on the structure of the space of the keys used. We quote here a successful attack on an McEliece system with the Reed-Solomon code as the design code.

  • The attack of Sidelnikov and Shestakov

Sidelnikov and Shestakov showed [6] that generalized Reed-Solomon codes were so structured that one could find a decoder of the public code in polynomial time. The systematic form of the matrix generating a GRS code can be obtained from the following proposition:


Let G=v1v2vnv1α1v2α2vnαn..v1α1k1v2α2k1vnαnk1 a matrix generating a Reed-Solomon code generalized on Fqm then there is a matrix k×k invertible S coefficient in Fqm and a matrix R=Riji=1kj=k+1n such that IR=SG and Rij=vjvis=1sikαjαsαiαs


For i=1,2k we define the following interpolation polynomial fix=s=1sikαjαsαiαs=j=1kfijxj1 of degree k1 such that fiαi=1, fiαj=0 for j=1,2k and ji. We noteS=fijvii=1kj=1.k.

The ith row of the matrix produces SG is fiα1v1vifiα2v2vifiαnvnvi

By construction of polynomials fi, the kfirst columns of the matrix SG form the identity matrix, therefore S is invertible and SG=IR where R=Rij and Rij=fiαjvjvi.


Let I the identity matrix its order k and R=Riji=1kj=k+1n where Rij=vjvis=1sikαjαsαiαs. Alors la matrice IR is the generator matrix in systematic form of the generator matrix GRS code G=v1v2vnv1α1v2α2vnαn..v1α1k1v2α2k1vnαnk1.


Can be deducted from the definition of the generalized Reed-Solomon code and the latest proposal.



A family of generalized Reed-Solomon code of length n, of dimension k constituting the key space.

The public key G.


The matrix G=vjαjii=0,..k1j=1n and S invertible matrix its size k×k such that G=SG.


Put the matrix G in form IR by Gaussian elimination.

Determine the matrix G=vjαjii=0,..k1j=1n such that α1,αn et v1,vn check the equations Rij=vjvis=1sikαjαsαiαs.

Determine the matrix S such that G=SG.


5. Conclusion

In conclusion, the security of cryptosystems based on error-correcting codes is strongly linked to the family of code used in the design of the system. The cryptosystem based on the Reed-Solomon code was broken by Sidelnikov and Shestakov in 1992. The version of McEliece using Goppa codes has been studied for 40 years and it seems perfectly secure from a cryptographic point of view; but it is not used in practice because the size of its public key is much larger that we know how to do with systems from other fields (RSA for example), hence the importance of finding a way to reduce the size of their public key. In the end, the McEliece system based on Goppa’s code remains a preferred system as a post-quantum cryptosystem. We have not covered in this chapter other cryptographic applications of error-correcting codes, including hash functions [3, 7, 8, 9, 10, 11], pseudo-random generators, identification protocols, etc.


  1. 1. Cayrel PL. Nouveaux résultats en cryptographie basée sur les codes correcteurs d’erreurs
  2. 2. Loidreau P. Etude et optimisation de cryptosystèmes à clé publique fondés sur la théorie des codes correcteurs [doctoral dissertation]; Thèse de doctorat. ENSTA Paris. 2001
  3. 3. Drissi A. Formation doctorale [doctoral dissertation]. Thèse de doctorat. Université Ibn Zohr; 2014
  4. 4. McEliece RJ. A Public-Key Cryptosystem Based on Algebraic Coding Theory, 42441978. pp. 114-116
  5. 5. Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory. 1986;15(2):159-166
  6. 6. Sidelnikov VM, Shestakov SO. On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics and Applications. 1992;2(4):439-444
  7. 7. Drissi A, Asimi A. One-way hash function based on goppa codes «OHFGC». Applied Mathematical Sciences. 2013;7(143):7097-7104
  8. 8. Dallot L. Sécurité de protocoles cryptographiques fondés sur les codes correcteurs d’erreurs [doctoral dissertation]; France: Université de Caen/Basse-Normandie; 2010
  9. 9. Merkle R. One way hash functions and DES. In: Crypto 1989, LNCS. Vol. 435. 1990
  10. 10. Pretzel O. Error-Correcting Codes and Finite Fields. Student ed. Oxford University Press, Inc.; 1996
  11. 11. Kumar R, Naidu AS, Singh A, Tentu AN. McEliece cryptosystem: Simulation and security vulnerabilities. International Journal of Computing Science and Mathematics. 2020;12(1):64-81

Written By

Ahmed Drissi

Submitted: July 3rd, 2020 Reviewed: August 27th, 2020 Published: August 18th, 2021