The Security of Cryptosystems Based on Error-Correcting Codes

Abstract

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.

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.

$F_{2^m}$: a finite field of $2^m$ elements.

$K\left[x\right]$: the ring of polynomials with an indeterminate.

$K\left[x\right]/\left(P\right)$: the quotient ring $K\left[x\right]$ de modulo $P$.

$K^{\ast }$: a private set of the element 0.

$\mathit{dQ}\left(x\right)$: the degree of the polynomial $Q\left(x\right)$.

$F_2^m$: the set of length vectors $m$ and components 0 and 1.

$F^n$: the scalar product $n$ times of the set $F$.

$\left[x\right]$: the integer part of $x.$

$A^t$: the transpose of the matrix $A$.

$I_k$: the identity matrix of order $k$.

$\mathit{gcd}$: greatest common divisor.

$C_n^t$: 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 ${\mathrm{F}}_{2^{\mathrm{m}}}$ and the calculations on these fields. Finite fields are generally constructed from primitive polynomials [3].

Definitions

The minimal polynomial of an element $\mathrm{\beta }$ on a finite field $\mathrm{F}$is the unit polynomial with coefficients in $\mathrm{F}$ smaller degree and its value in $\mathrm{\beta }$ is zero.

Proposition

1. The ring $\mathrm{K}\left[\mathrm{x}\right]/\left(\mathrm{P}\right)$ is a field if and only if the polynomial $\mathrm{P}\left(\mathrm{x}\right)$ is irreducible on the field $\mathrm{K}$.

2. If $\mathrm{P}\left(\mathrm{x}\right)$ is irreducible of degree $\mathrm{m}$and $\mathrm{K}$ a finite field of $\mathrm{q}$ elements then $\mathrm{K}\left[\mathrm{x}\right]/\left(\mathrm{P}\right)$ is field of ${\mathrm{q}}^{\mathrm{m}}$ elements.

This proposition gives us a way to build a finite field: Take a polynomial $\mathrm{P}$ irreducible over a field $\mathrm{K}$ et former le quotient $\mathrm{K}\left[\mathrm{x}\right]/\left(\mathrm{P}\right)$.

Theorem (the primitive element)

If $\mathrm{K}$ is a finite field of order $\mathrm{q}$, then the multiplicative group ${\mathrm{K}}^{\ast }$ is cyclic generated by an element $\mathrm{\alpha }$ called primitive element of $\mathrm{K}$ and we write ${\mathrm{K}}^{\ast }=\left\{{\mathrm{\alpha }}^{\mathrm{i}},\mathrm{i}=1\dots \mathrm{q}-\right\}$. Any generator of this group is called a primitive element of $\mathrm{K}$.

Definition (primitive polynomial)

We say that a polynomial $\mathrm{P}\in {\mathrm{F}}_2\left[\mathrm{x}\right]$ of degree $\mathrm{m}$ is primitive if it is the minimal polynomial of a generator of ${\mathrm{F}}_{2^{\mathrm{m}}}^{\ast }$.

Lemma

Let ${\mathrm{F}}_2{\left[\mathrm{x}\right]}^{\left(\mathrm{m}\right)}=\left\{\mathrm{Q}\left(\mathrm{x}\right)\in {\mathrm{F}}_2\left[\mathrm{x}\right],\mathrm{dQ}\left(\mathrm{x}\right)\le \mathrm{m}-1\right\}$, $\mathrm{P}\left(\mathrm{x}\right)\in {\mathrm{F}}_2{\left[\mathrm{x}\right]}^{\left(\mathrm{m}\right)}$ primitive and $\mathrm{\alpha }$ a root of $\mathrm{P}\left(\mathrm{x}\right)$, so we have: ${\mathrm{F}}_2^{\mathrm{m}}\approx {\mathrm{F}}_2{\left[\mathrm{x}\right]}^{\left(\mathrm{m}\right)}\approx {\mathrm{F}}_2\left[\mathrm{x}\right]/\left(\mathrm{P}\left(\mathrm{x}\right)\right)\approx {\mathrm{F}}_{2^{\mathrm{m}}}\approx \left\{0\right\}\cup \left\{1,\mathrm{\alpha },\dots {\mathrm{\alpha }}^{2^{\mathrm{m}}-1}\right\}$.

It follows from this lemma that we can represent the nonzero elements of a finite field ${\mathrm{F}}_{2^{\mathrm{m}}}$ by nonzero vectors of ${\mathrm{F}}_2^{\mathrm{m}}$ and that the ${\mathrm{\alpha }}^{\mathrm{i}}$ have representatives of ${\mathrm{x}}^{\mathrm{i}}\text{modP}\left(\mathrm{x}\right)$ and consequently ${\mathrm{\alpha }}^{\mathrm{i}}={\mathrm{x}}^{\mathrm{i}}\text{modP}\left(\mathrm{x}\right)$. In what follows we denote by $\mathrm{\alpha }$ a primitive element of ${\mathrm{F}}_{2^{\mathrm{m}}}$.

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 $\mathrm{F}$ of $\mathrm{q}$ elements. Each message $\left({\mathrm{x}}_0,{\mathrm{x}}_1,\dots {\mathrm{x}}_{\mathrm{k}-1},\right)$ is an element of the set of ${\mathrm{F}}^{\mathrm{k}}$ (message space). We then have ${\mathrm{q}}^{\mathrm{k}}$ possible messages. We assume that all the code words are of the same length $\mathrm{n}>\mathrm{k}$. Encode $\mathrm{m}$ messages of length $\mathrm{k},\left(\mathrm{m}\le {\mathrm{q}}^{\mathrm{k}}\right)$ consists in choosing an integer $\mathrm{n}>\mathrm{k}$, and associate with each message from ${\mathrm{F}}^{\mathrm{k}}$ a word from ${\mathrm{F}}^{\mathrm{n}}$ (injectively). The coding introduces a redundancy equal to $\mathrm{n}-\mathrm{k}$. Decoding consists of receiving a word $\mathrm{x}$ of ${\mathrm{F}}^{\mathrm{n}}$ to determine if $\mathrm{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 $\mathrm{x}=\left({\mathrm{x}}_0,{\mathrm{x}}_1,\dots {\mathrm{x}}_{\mathrm{n}-1}\right)≔{\mathrm{x}}_0{\mathrm{x}}_1\dots {\mathrm{x}}_{\mathrm{n}-1}$ and $\mathrm{y}=\left({\mathrm{y}}_0,{\mathrm{y}}_1,\dots {\mathrm{y}}_{\mathrm{n}-1}\right)≔{\mathrm{y}}_0{\mathrm{y}}_1\dots {\mathrm{y}}_{\mathrm{n}-1}$ of ${\mathrm{F}}^{\mathrm{n}}$. We call the Hamming distance between words $\mathrm{x}$ and $\mathrm{y}$, and we note ${\mathrm{d}}_{\mathrm{H}}\left(\mathrm{x},\mathrm{y}\right)=\mathrm{d}\left(\mathrm{x},\mathrm{y}\right)$ the number of index $\mathrm{i}\in \left\{0,1,2\dots \mathrm{n}-1\right\}$ such as ${\mathrm{x}}_{\mathrm{i}}\ne {\mathrm{y}}_{\mathrm{i}}$, we call Hamming’s weight of a word $\mathrm{x}$ the number of nonzero components of $\mathrm{x}$, we note$\mathrm{w}\left(\mathrm{x}\right)=\mathrm{d}\left(\mathrm{x},0\right)$.

Definitions

We call the minimum distance of a code $\mathrm{C}$ an integer $\mathrm{d}$ such as $\mathrm{d}=min\left\{\mathrm{d}\left(\mathrm{m},{\mathrm{m}}^{\prime }\right),\mathrm{m}\in \mathrm{C},{\mathrm{m}}^{\prime }\in \mathrm{C},\mathrm{m}\ne \mathrm{m}\prime \right\}$. We call the weight of a word $\mathrm{x}$ of code $\mathrm{C}$on integer $\mathrm{w}\left(\mathrm{x}\right)=\mathrm{d}\left(\mathrm{x},0\right)$.

Proposal (correction capacity)

Let $\mathrm{C}$ a minimum distance code $\mathrm{d}$, and $\mathrm{x}\in {\mathrm{F}}^{\mathrm{n}}$ a received message assigned to $\mathrm{r}$ errors, with $\mathrm{r}\ge 1$.

1. If $2\mathrm{r}<\mathrm{d}$ that is to say that $\mathrm{r}\le \left[\frac{\mathrm{d}-1}{2}\right]$, the code $\mathrm{C}$correct $\mathrm{r}$ errors.

2. If $\left[\frac{\mathrm{d}-1}{2}\right]<\mathrm{r}=\left[\frac{\mathrm{d}}{2}\right]$, the $\mathrm{C}$ code detects the existence of $\mathrm{r}$ errors but cannot always correct them.

3. If $\left[\frac{\mathrm{d}}{2}\right]<\mathrm{r}\le \mathrm{d}-1$, the $\mathrm{C}$ code detects the existence d’ errors but risk of making an erroneous correction.

The integer $\mathrm{t}=\left[\frac{\mathrm{d}-1}{2}\right]$ is called code correction capability, we also say that $\mathrm{C}$ is a t-corrector code.

Proof

Let $\mathrm{m}$ the code word transmitted and $\mathrm{x}$ the message received and assigned from $\mathrm{r}$ errors then $\mathrm{d}\left(\mathrm{m},\mathrm{x}\right)=\mathrm{r}$.

1. We show that the code word $\mathrm{m}$ is the only code word such as $\mathrm{d}\left(\mathrm{m},\mathrm{x}\right)\le \mathrm{r}$.

Otherwise it exists $\mathrm{m}\prime$ of $\mathrm{C}$ such as $\mathrm{d}\left({\mathrm{m}}^{\prime },\mathrm{x}\right)\le \mathrm{r}$, we are $\mathrm{d}\left(\mathrm{m},{\mathrm{m}}^{\prime }\right)\le \mathrm{d}\left(\mathrm{m},\mathrm{x}\right)+\mathrm{d}\left(\mathrm{x},{\mathrm{m}}^{\prime }\right)\le 2\mathrm{r}<\mathrm{d}$, then $\mathrm{m}=\mathrm{m}\prime$.

1. There is no code word $\mathrm{m}\prime$ of $\mathrm{C}$ such as $\mathrm{d}\left(\mathrm{x},{\mathrm{m}}^{\prime }\right)<\mathrm{d}\left(\mathrm{m},\mathrm{x}\right)=\mathrm{r}$, but the code word $\mathrm{m}$ is not necessarily the only one to check $\mathrm{d}\left(\mathrm{m},\mathrm{x}\right)=\mathrm{r}$. Indeed be $\mathrm{m}={\mathrm{m}}_1{\mathrm{m}}_2\dots {\mathrm{m}}_{\mathrm{n}}$ and $\mathrm{m}\prime =\mathrm{m}{\prime }_1\mathrm{m}{\prime }_2\dots \mathrm{m}{\prime }_{\mathrm{n}}$ two code words and if we receive the message $\mathrm{x}={\mathrm{m}}_1{\mathrm{m}}_2\dots {\mathrm{m}}_{\mathrm{r}}\mathrm{m}{\prime }_1\dots \mathrm{m}{\prime }_{\mathrm{r}}$, we’ll have $\mathrm{d}\left(\mathrm{x},\mathrm{m}\right)=\mathrm{d}\left(\mathrm{x},{\mathrm{m}}^{\prime }\right)=\mathrm{r}$.

2. We know there is an error because $\mathrm{x}\notin \mathrm{C}$, but there may be a code word $\mathrm{m}\prime \notin \mathrm{C}$ such as $\mathrm{d}\left({\mathrm{m}}^{\prime },\mathrm{x}\right)<\mathrm{d}\left(\mathrm{m},\mathrm{x}\right)=\mathrm{r}$.

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

2.3 Linear codes

Definitions

A linear code $\mathrm{C}$ of size $\mathrm{n}$ and dimension $\mathrm{k}$ on the finite field ${\mathrm{F}}_{\mathrm{q}}$ is a vector subspace of ${\mathrm{F}}_{\mathrm{q}}^{\mathrm{n}}$. We note it ${\left[\mathrm{n},\mathrm{k},\mathrm{d}\right]}_{\mathrm{q}}$ with $\mathrm{d}$ its minimum distance.

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

A linear code is characterized by its generator matrix $\mathrm{G}$, we have $\mathrm{C}=\left\{\mathrm{y}=\mathrm{xG}/\mathrm{x}\in {\mathrm{F}}_{\mathrm{q}}^{\mathrm{k}}\right\}$.

let $\mathrm{H}$$\left(\mathrm{n}-\mathrm{k}\right)\times \mathrm{n}$ matrix with coefficients in ${\mathrm{F}}_{\mathrm{q}}$. $\mathrm{H}$ is called the parity control matrix of $\mathrm{C}$ if “$\mathrm{x}\in \mathrm{C}\iff \mathrm{H}{\mathrm{x}}^{\mathrm{t}}$”.

${\mathrm{F}}_{\mathrm{q}}^{\mathrm{k}}$: the message space.

The systematic code

The matrix $\mathrm{G}$ defines a bijective function ${\mathrm{F}}_{\mathrm{q}}^{\mathrm{k}}\to \mathrm{C}$ by $\mathrm{x}\to \mathrm{xG}$ which we represent ${\mathrm{q}}^{\mathrm{k}}$ messages, its length $\mathrm{k}$ by code words, of length$\mathrm{n}$.

The generator matrix $\mathrm{G}$ of a $\mathrm{C}$ code is not unique; $\mathrm{G}$ can be transformed into ${\mathrm{G}}^{\prime }=\left({\mathrm{I}}_{\mathrm{k}}|\mathrm{A}\right)$ with ${\mathrm{I}}_{\mathrm{k}}$ the identity matrix with $\mathrm{k}$ order and $\mathrm{A}$ the matrix of $\mathrm{k}$ lines and $\mathrm{n}-\mathrm{k}$ columns.

$\mathrm{G}$ and $\mathrm{G}\prime$ generate the same $\mathrm{C}$ subspace; $\mathrm{G}\prime$ is called canonical generator matrix and if the generator matrix of a code is of the form $\mathrm{G}=\left({\mathrm{I}}_{\mathrm{k}}|\mathrm{A}\right)$, this code is said systematic.

Theorem

Let $\mathrm{C}$ a ${\left[\mathrm{n},\mathrm{k}\right]}_{\mathrm{q}}$ linear code.

1. If $\mathrm{G}$ is a generator matrix of $\mathrm{C}$ and $\mathrm{H}$ a parity control matrix of $\mathrm{C}$ then ${\mathrm{GH}}^{\mathrm{t}}=0$.

2. If $\mathrm{G}$ is a $\mathrm{k}\times \mathrm{n}$ matrix of rank $\mathrm{k}$ and $\mathrm{H}$ is a $\left(\mathrm{n}-\mathrm{k}\right)\times \mathrm{n}$ matrix of rank $\mathrm{n}-\mathrm{k}$ such as $\mathrm{G}{\mathrm{H}}^{\mathrm{t}}=0$ then we have:

$\mathrm{H}$ is a parity control matrix of $\mathrm{C}$ if and only if $\mathrm{G}$ is a generator matrix of $\mathrm{C}$.

Proof

1. We know that ${\mathrm{H}}^{\mathrm{t}}=0$, $\forall \mathrm{x}\in \mathrm{C}$, in particular we have ${\mathrm{G}}_{\mathrm{i}}{\mathrm{H}}^{\mathrm{t}}=0$ for all $\mathrm{i}=1\dots \mathrm{k}$ with ${\mathrm{G}}_{\mathrm{i}}$ is line of $\mathrm{G}$. It follows that $\mathrm{G}{\mathrm{H}}^{\mathrm{t}}=0$.

2. $\Rightarrow )$ Since $\mathrm{G}{\mathrm{H}}^{\mathrm{t}}=0$, then we have ${\mathrm{G}}_{\mathrm{i}}{\mathrm{H}}^{\mathrm{t}}=0$. For all $\mathrm{i}=1\dots \mathrm{k}$. And since $\mathrm{H}$ is a parity control matrix of $\mathrm{C}$, we have the ${\mathrm{G}}_{\mathrm{i}}$ belong to $\mathrm{C}$. $\mathrm{rg}\left(\mathrm{G}\right)=\mathrm{k}$, then $\left\{{\mathrm{G}}_{\mathrm{i}},\mathrm{i}=1\dots \mathrm{k}\right\}$ constitute a basis of $\mathrm{C}$. It follows that $\mathrm{G}$ is a generator matrix of $\mathrm{C}$.

$\Leftarrow )$ we have $\mathrm{y}\in \mathrm{C}$ if and only if it exists $\mathrm{x}\in {\mathrm{F}}_{\mathrm{q}}^{\mathrm{k}}$ such as $\mathrm{y}=\mathrm{xG}$. Then $\mathrm{y}\in \mathrm{C}$ if and only if $\mathrm{y}{\mathrm{H}}^{\mathrm{t}}=\mathrm{xG}{\mathrm{H}}^{\mathrm{t}}=0$. Then $\mathrm{H}$ is a parity control matrix of $\mathrm{C}$.

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

Corollary

Let $\mathrm{C}$ a ${\left[\mathrm{n},\mathrm{k}\right]}_{\mathrm{q}}$ linear code

1. If $\mathrm{G}=\left({\mathrm{I}}_{\mathrm{k}}|\mathrm{A}\right)$ a canonical generator matrix of $\mathrm{C}$ then $\mathrm{H}=\left(-{\mathrm{A}}^{\mathrm{t}}|{\mathrm{I}}_{\mathrm{n}-\mathrm{k}}\right)$ is a parity control matrix of$\mathrm{C}$.

2. If $\mathrm{H}=\left(\mathrm{B}|{\mathrm{I}}_{\mathrm{n}-\mathrm{k}}\right)$ is a parity control matrix of $\mathrm{C}$ then, $\mathrm{G}=\left({\mathrm{I}}_{\mathrm{k}}|-{\mathrm{B}}^{\mathrm{t}}\right)$ is a generator matrix of $\mathrm{C}$.

Proof

By applying the preceding theorem

1. we have $\mathrm{G}{\mathrm{H}}^{\mathrm{t}}=\left({\mathrm{I}}_{\mathrm{k}}|\mathrm{A}\right){\left(-{\mathrm{A}}^{\mathrm{t}}|{\mathrm{I}}_{\mathrm{n}-\mathrm{k}}\right)}^{\mathrm{t}}=-\mathrm{A}+\mathrm{A}=0$, if $\mathrm{G}$ is a generator matrix of $\mathrm{C}$ then, $\mathrm{H}$ is a parity control matrix of$\mathrm{C}$.

2. we have $\mathrm{G}{\mathrm{H}}^{\mathrm{t}}=\left({\mathrm{I}}_{\mathrm{k}}|-{\mathrm{B}}^{\mathrm{t}}\right){\left(\mathrm{B}|{\mathrm{I}}_{\mathrm{n}-\mathrm{k}}\right)}^{\mathrm{t}}={\mathrm{B}}^{\mathrm{t}}-{\mathrm{B}}^{\mathrm{t}}=0$ then if $\mathrm{H}$ is a parity control matrix of $\mathrm{C}$ we will have $\mathrm{G}$ is a generator matrix of $\mathrm{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. $\mathrm{H}{\mathrm{x}}^{\mathrm{t}}$ is called syndrome. Suppose the word $\mathrm{x}$ is sent through a noisy channel and the word received is $\mathrm{y}$ so the error vector is $\mathrm{e}=\mathrm{y}-\mathrm{x}$.

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

Theorem

Let $\mathrm{C}$ a ${\left[\mathrm{n},\mathrm{k},\mathrm{d}\right]}_{\mathrm{q}}$ linear code then,

1. $\mathrm{u}$ and $\mathrm{v}$ are of the same coset class of $\mathrm{C}$ if and only if $\mathrm{u}-\mathrm{v}\in \mathrm{C}$.

2. Any vector of ${\mathrm{F}}_{\mathrm{q}}^{\mathrm{n}}$ is in a coset of $\mathrm{C}$.

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

Proof

1. If $\mathrm{u},\mathrm{v}\in \mathrm{x}+\mathrm{C}$ then, it exists $\mathrm{y},\mathrm{z}\in \mathrm{C}$ such as $\mathrm{u}=\mathrm{x}+\mathrm{y}$ and $\mathrm{v}=\mathrm{x}+\mathrm{z}$, then $\mathrm{u}-\mathrm{v}=\mathrm{y}-\mathrm{z}\in \mathrm{C}$, because $\mathrm{C}$ is a vector subspace of ${\mathrm{F}}_{\mathrm{q}}^{\mathrm{n}}$.

If $\mathrm{u}-\mathrm{v}\in \mathrm{C}$ it exists $\mathrm{x}\in \mathrm{C}$ such as $\mathrm{u}-\mathrm{v}=\mathrm{x}$ then $\mathrm{u}=\mathrm{v}+\mathrm{x}\in \mathrm{v}+\mathrm{C}$ and we have $\mathrm{v}=\mathrm{v}+0\in \mathrm{v}+\mathrm{C}$.

1. Let $\mathrm{a}\in {\mathrm{F}}_{\mathrm{q}}^{\mathrm{n}}$, on a $0\in \mathrm{C}$ then$\mathrm{a}=\mathrm{a}+0\in \mathrm{a}+\mathrm{C}$.

2. Suppose that $\left(\mathrm{a}+\mathrm{C}\right)\cap \left(\mathrm{b}+\mathrm{C}\right)\ne \varnothing$, the nit exists $\mathrm{v}\in {\mathrm{F}}_{\mathrm{q}}^{\mathrm{n}}$ such as $\left(\mathrm{a}+\mathrm{C}\right)\cap \left(\mathrm{b}+\mathrm{C}\right)$ contains the element $\mathrm{v}$, the nit exists $\mathrm{x},\mathrm{y}\in \mathrm{C}$ such as $\mathrm{v}=\mathrm{a}+\mathrm{x}=\mathrm{b}+\mathrm{y}$ hence $\mathrm{b}=\mathrm{a}+\left(\mathrm{x}-\mathrm{y}\right)$ and $\mathrm{a}=\mathrm{b}+\left(\mathrm{y}-\mathrm{x}\right)$. $\forall \mathrm{b}+\mathrm{c}\in \mathrm{b}+\mathrm{C}$ we have $\mathrm{b}+\mathrm{c}=\mathrm{a}+\left(\mathrm{x}-\mathrm{y}\right)+\mathrm{c}\in \mathrm{a}+\mathrm{C}$ (then $\mathrm{b}+\mathrm{C}\subset \mathrm{a}+\mathrm{C}$). $\forall \mathrm{a}+\mathrm{c}\in \mathrm{a}+\mathrm{C}$ We have $\mathrm{a}+\mathrm{c}=\mathrm{b}+\left(\mathrm{y}-\mathrm{x}\right)+\mathrm{c}\in \mathrm{b}+\mathrm{C}$ (then $\mathrm{a}+\mathrm{C}\subset \mathrm{b}+\mathrm{C}$), hence $\mathrm{b}+\mathrm{C}=\mathrm{a}+\mathrm{C}$.

Principle

We construct the standard array of $\mathrm{C}$ which is a matrix of ${\mathrm{q}}^{\mathrm{n}-\mathrm{k}}$ lines and ${\mathrm{q}}^{\mathrm{k}}$ columns. It contains all the vectors of ${\mathrm{F}}_{\mathrm{q}}^{\mathrm{n}}$; its first line corresponds to the words of $\mathrm{C}$ with vector 0 on the left. The other lines represent the cosets ${\mathrm{u}}_{\mathrm{i}}+\mathrm{C}$ with the class leader ${\mathrm{u}}_{\mathrm{i}}$ to the left. The procedure is as follows:

1. We list the words of $\mathrm{C}$ starting with 0 on the first line.

2. We choose a vector ${\mathrm{u}}_1$ of minimum weight that does not belong to the first line and we list in the second line the elements ${\mathrm{u}}_1+\mathrm{C}$, by entering below 0 the class leader ${\mathrm{u}}_1$ and below each element $\mathrm{x}\in \mathrm{C}$ the element ${\mathrm{u}}_1+\mathrm{x}$.

3. We choose ${\mathrm{u}}_2$ 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 ${\mathrm{F}}_{\mathrm{q}}^{\mathrm{n}}$ appear only once.

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

Remark

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 $\mathrm{r}\le 2$ redundancy is a linear code ${\left[2^{\mathrm{r}}-1,2^{\mathrm{r}}-1-\mathrm{r}\right]}_2$ its parity control matrix $\mathrm{H}$, with $\mathrm{H}$ is a matrix of $\mathrm{r}$ lines and $2^{\mathrm{r}}-1$ columns that correspond to the set of all nonzero vectors of ${\mathrm{F}}_2^{\mathrm{r}}$.

Theorem

The minimum distance of the Hamming ${\left[2^{\mathrm{r}}-1,2^{\mathrm{r}}-1-\mathrm{r}\right]}_2$ code is $\mathrm{d}=3$ (it therefore corrects a single error).

Proof

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

It exists $\mathrm{x}\in \mathrm{C}$ such as $\mathrm{w}\left(\mathrm{x}\right)=3$, indeed by definition of the parity control matrix $\mathrm{H}$, the first 3 columns are $\left(\begin{array}{cccc}0& 0& 0& \dots \\ ⋮& ⋮& ⋮& \dots \\ 0& 0& 0& \dots \\ 0& 1& 1& \dots \\ 1& 0& 1& \dots \end{array}\right)$ then the vector $\mathrm{x}=\left(1110\cdots 0\right)$ its weight $\mathrm{w}\left(\mathrm{x}\right)=3$ and belongs to $\mathrm{C}$ because $\mathrm{H}{\mathrm{x}}^{\mathrm{t}}=0$.

Decoding

The vector syndrome $\mathrm{x}$ of which only the jth component is nonzero is none other than the transpose of the jth column of $\mathrm{H}$. If the columns of $\mathrm{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 $\mathrm{y}$ a message received, we calculate $\mathrm{H}{\mathrm{y}}^{\mathrm{t}}$. If $\mathrm{H}{\mathrm{y}}^{\mathrm{t}}=0$ then, $\mathrm{y}$ corresponds to the message transmitted. If $\mathrm{H}{\mathrm{y}}^{\mathrm{t}}\ne 0$ and assuming there is only one error, $\mathrm{H}{\mathrm{y}}^{\mathrm{t}}$ directly gives the position of the error written in binary in the form $\cdots {\mathrm{b}}_3{\mathrm{b}}_2{\mathrm{b}}_1{\mathrm{b}}_0$. We can then correct $\mathrm{y}={\mathrm{y}}_1\cdots {\mathrm{y}}_{\mathrm{n}}$ like $\mathrm{x}+{\mathrm{e}}_{\mathrm{j}}$ for $\mathrm{j}={\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{b}}_{\mathrm{i}}{2}^{\mathrm{i}}$ and ${\mathrm{e}}_{\mathrm{j}}$ the vector of which only the jth coordinate is nonzero.

2.5 The Reed-Solomon codes

Let $\mathrm{n}=\mathrm{q}-1$ with $\mathrm{q}=2^{\mathrm{m}}$ et ${\mathrm{F}}_{\mathrm{q}}{\left[\mathrm{x}\right]}^{\left(\mathrm{k}\right)}$ The set of polynomials of degree strictly less than $\mathrm{k}$ on ${\mathrm{F}}_{2^{\mathrm{m}}}$. Let us build a length code $\mathrm{n}$ and dimension $\mathrm{k}$. Let $\mathrm{L}=\left({\mathrm{\alpha }}_1,{\mathrm{\alpha }}_2,\cdots {\mathrm{\alpha }}_{\mathrm{n}},\right)$ a vector formed of distinct elements of ${\mathrm{F}}_{2^{\mathrm{m}}}^{\ast }=\left\{{\mathrm{\alpha }}^{\mathrm{i}},\mathrm{i}=1\dots \mathrm{n}\right\}$, with $\mathrm{\alpha }$ primitive of ${\mathrm{F}}_{2^{\mathrm{m}}}$. Each word of the code is the evaluation of a function $\mathrm{f}$ of ${\mathrm{F}}_{\mathrm{q}}{\left[\mathrm{x}\right]}^{\left(\mathrm{k}\right)}$ on $\mathrm{L}$ then, we have a length code $\mathrm{n}$ and dimension $\mathrm{k}$ and generator matrix

$$G=\left(\begin{array}{cccc}1& 1& \dots & 1\\ {\alpha }_1& {\alpha }_2& \dots & {\alpha }_n\\ \mathrm{..}& \mathrm{..}& \dots & \mathrm{..}\\ {\alpha }_1^{k-1}& {\alpha }_2^{k-1}& \dots & {\alpha }_n^{k-1}\end{array}\right).$$

By its structure, this code has a minimum distance of at least $\mathrm{n}-\mathrm{k}+1$, because two polynomials of degrees less than $\mathrm{k}$ distinct cannot be equal in addition to $\mathrm{k}-1$ positions. This distance is exactly equal to $\mathrm{n}-\mathrm{k}+1$, since the evaluation of a polynomial of the form ${\prod }_{\mathrm{i}=1}^{\mathrm{k}-1}\left(\mathrm{x}-{\mathrm{\alpha }}_{\mathrm{i}}\right)$ his weight is $\mathrm{n}-\mathrm{k}+1$. So we have a code on ${\mathrm{F}}_{2^{\mathrm{m}}}$ of the form ${\left[\mathrm{n},\mathrm{k},\mathrm{n}-\mathrm{k}+1\right]}_{\mathrm{q}}$ which can have both good transmission rate and good correction ability.

Remark

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

Definition

Let $\left({\mathrm{v}}_1,{\mathrm{v}}_2,\dots {\mathrm{v}}_{\mathrm{n}}\right)$ a vector of length $\mathrm{n}$ in ${\mathrm{F}}_{2^{\mathrm{m}}}^{\ast }$ et $\left({\mathrm{\alpha }}_1,{\mathrm{\alpha }}_2,\cdots {\mathrm{\alpha }}_{\mathrm{n}},\right)$ a vector of length $\mathrm{n}$ in ${\mathrm{F}}_{2^{\mathrm{m}}}^{\ast }$, with the ${\mathrm{\alpha }}_{\mathrm{i}}$ are distinct two by two.

The set of codes with the generator matrix $\mathrm{G}$ of the form $G=\left(\begin{array}{cccc}{v}_1& v_2& \dots & v_n\\ v_1{\alpha }_1& v_2{\alpha }_2& \dots & v_n{\alpha }_n\\ \dots & \mathrm{..}& \dots & \dots \\ v_1{\alpha }_1^{k-1}& v_2{\alpha }_2^{k-1}& \dots & v_n{\alpha }_n^{k-1}\end{array}\right)$ is called the family of generalized Reed-Solomon codes.

2.6 The classical Goppa codes

Definition

Let $\mathrm{L}=\left({\mathrm{\alpha }}_1,{\mathrm{\alpha }}_2,\dots {\mathrm{\alpha }}_{\mathrm{n}}\right)$ a suite of $\mathrm{n}$ distinct elements of ${\mathrm{F}}_{2^{\mathrm{m}}}$ and $\mathrm{g}\left(\mathrm{z}\right)\in {\mathrm{F}}_{2^{\mathrm{m}}}\left[\mathrm{z}\right]$ a unit polynomial of degree r irreducible in ${\mathrm{F}}_{2^{\mathrm{m}}}\left[\mathrm{z}\right]$. The irreducible binary Goppa code, its support $\mathrm{L}$ (generator vector) and its generator polynomial $\mathrm{g}$ noted $\mathrm{\Gamma }\left(\mathrm{L},\mathrm{g}\right)$ is the set of words $\mathrm{a}=\left({\mathrm{a}}_1,\dots {\mathrm{a}}_{\mathrm{n}}\right)\in {\mathrm{F}}_2^{\mathrm{n}}$ such that one of the following equivalent characterizations is verified:

1. ${\mathrm{R}}_{\mathrm{a}}\left(\mathrm{z}\right)={\sum }_{\mathrm{i}=1}^{\mathrm{n}}\frac{{\mathrm{a}}_{\mathrm{i}}}{\mathrm{z}-{\mathrm{\alpha }}_{\mathrm{i}}}=0\text{modg}\left(\mathrm{z}\right).$

2. $\mathrm{H}{\mathrm{a}}^{\mathrm{t}}=0$ with $H=\left(\begin{array}{cccc}1& 1& \dots & 1\\ {\alpha }_1& {\alpha }_2& \dots & {\alpha }_n\\ \mathrm{..}& .\dots & \dots & \dots \\ {\alpha }_1^{r-1}& {\alpha }_2^{r-1}& \dots & {\alpha }_n^{r-1}\end{array}\right)\left(\begin{array}{cccc}g{\left({\alpha }_1\right)}^{-1}& & & \\ & \mathrm{..}& & \\ & & \mathrm{..}& \\ & & & g{\left({\alpha }_n\right)}^{-1}\end{array}\right)$ parity check matrix.

3. $\mathrm{g}\left(\mathrm{z}\right)$ divided $\frac{\mathrm{d}{\mathrm{\sigma }}_{\mathrm{a}}\left(\mathrm{z}\right)}{\mathrm{dz}}$ with c ${\mathrm{\sigma }}_{\mathrm{a}}\left(\mathrm{z}\right)={\prod }_{\mathrm{i}=1}^{\mathrm{n}}{\left(\mathrm{z}-{\mathrm{\alpha }}_{\mathrm{i}}\right)}^{{\mathrm{a}}_{\mathrm{i}}}$ locator polynomial.

The construction of a code Goppa:

Goppa’s code is a linear code on the field ${\mathrm{F}}_2$, its construction requires the use of an extension ${\mathrm{F}}_{2^{\mathrm{m}}}$. Each element of the matrix $\mathrm{H}$ is then broken down into $\mathrm{m}$ elements of ${\mathrm{F}}_2$ placed in columns, using a projection of ${\mathrm{F}}_{2^{\mathrm{m}}}$ in ${\mathrm{F}}_2^{\mathrm{m}}$; we go from a size matrix $\mathrm{r}\times \mathrm{n}$ on ${\mathrm{F}}_{2^{\mathrm{m}}}$ to a matrix of size $\mathrm{rm}\times n$ on $F_2$ so it is a length code $\mathrm{n}=\left|\mathrm{L}\right|$ and dimension $\mathrm{k}=\mathrm{n}-\mathrm{mr}$ and has a minimum distance at least equal to $\mathrm{d}=\mathrm{r}+1$. Indeed the parity check matrix $\mathrm{H}$ is written as the product of a Vandermonde matrix and an invertible matrix therefore all under a square matrix $\mathrm{r}\times \mathrm{r}$ of $\mathrm{H}$ is invertible, then there are no code words with a weight less than or equal to $\mathrm{r}$.

The decoding of a Goppa code:

Several techniques exist to decode Goppa codes but they work by the same principle. Let ${\mathrm{c}}^{\prime }=\mathrm{c}+\mathrm{e}$ and $\mathrm{w}\left(\mathrm{e}\right)<\frac{\mathrm{r}}{2}$. We start by calculating the syndrome ${\mathrm{R}}_{\mathrm{c}\prime }\left(\mathrm{z}\right)$ on ${\mathrm{F}}_{2^{\mathrm{m}}}$; from this syndrome we will write a key equation, and we will finish the decoding by solving the key equation to find$\mathrm{e}$.

If ${\mathrm{R}}_{\mathrm{a}}\left(\mathrm{z}\right)=0$ the word will belong to the code.

The key equation

Let ${\mathrm{\sigma }}_{\mathrm{e}}\left(\mathrm{z}\right)={\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\left(\mathrm{z}-{\mathrm{\alpha }}_{\mathrm{i}}\right)}^{{\mathrm{e}}_{\mathrm{i}}}$ of degree <$\frac{\mathrm{r}}{2}$. On introduit le polynôme ${\mathrm{w}}_{\mathrm{e}}\left(\mathrm{z}\right)={\mathrm{\sigma }}_{\mathrm{e}}\left(\mathrm{z}\right){\mathrm{R}}_{\mathrm{e}}\left(\mathrm{z}\right)mod\mathrm{g}\left(\mathrm{z}\right)$ called evaluator polynomial.

$${\mathrm{\sigma }}_{\mathrm{e}}\left(\mathrm{z}\right){\mathrm{R}}_{\mathrm{e}}\left(\mathrm{z}\right)=\sum _{\mathrm{i}=1}^{\mathrm{n}}\frac{{\mathrm{e}}_{\mathrm{i}}}{\mathrm{z}-{\mathrm{\alpha }}_{\mathrm{i}}}\prod _{\mathrm{j}=1}^{\mathrm{n}}{\left(\mathrm{z}-{\mathrm{\alpha }}_{\mathrm{j}}\right)}^{{\mathrm{e}}_{\mathrm{j}}}mod\mathrm{g}\left(\mathrm{z}\right)=\sum _{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{e}}_{\mathrm{i}}\prod _{\begin{array}{c}\mathrm{j}=1\\ \mathrm{j}\ne \mathrm{i}\end{array}}^{\mathrm{n}}{\left(\mathrm{z}-{\mathrm{\alpha }}_{\mathrm{j}}\right)}^{{\mathrm{e}}_{\mathrm{j}}}mod\mathrm{g}\left(\mathrm{z}\right).$$

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 ${\mathrm{w}}_{\mathrm{e}}$ and ${\mathrm{\sigma }}_{\mathrm{e}}$ of degree <$\frac{\mathrm{r}}{2}$ such as ${\mathrm{w}}_{\mathrm{e}}\left(\mathrm{z}\right)={\mathrm{\sigma }}_{\mathrm{e}}\left(\mathrm{z}\right){\mathrm{R}}_{\mathrm{e}}\left(\mathrm{z}\right)mod\mathrm{g}\left(\mathrm{z}\right)={\mathrm{\sigma }}_{\mathrm{e}}\left(\mathrm{z}\right){\mathrm{R}}_{\mathrm{e}}\left(\mathrm{z}\right)+\mathrm{k}\left(\mathrm{z}\right)\mathrm{g}\left(\mathrm{z}\right)$. If we try to calculate the $gcd$ of $\left(\mathrm{g},{\mathrm{R}}_{\mathrm{e}}\right)$ with the extended Euclidean algorithm, we will calculate at each step the polynomials ${\mathrm{u}}_{\mathrm{i}},{\mathrm{v}}_{\mathrm{i}},{\mathrm{r}}_{\mathrm{i}}$ checking ${\mathrm{R}}_{\mathrm{e}}{\mathrm{u}}_{\mathrm{i}}+\mathrm{g}{\mathrm{v}}_{\mathrm{i}}={\mathrm{r}}_{\mathrm{i}}.$ At each step the polynomials ${\mathrm{u}}_{\mathrm{i}}$ and ${\mathrm{v}}_{\mathrm{i}}$ will be of degree <$\mathrm{i}$ and the degree of ${\mathrm{r}}_{\mathrm{i}}$ is equal to $\mathrm{r}-\mathrm{i}$. There is therefore a step at which if we stop the algorithm we will find a solution of the equation ${\mathrm{\sigma }}_{\mathrm{e}}={\mathrm{u}}_{{\mathrm{i}}_0}$ and ${\mathrm{w}}_{{\mathrm{i}}_0}={\mathrm{r}}_{{\mathrm{i}}_0}$ to a scalar coefficient.

3. Encryption/decryption systems

3.1 The basic system (McEliece)

We start by generating a code ${\left[\mathrm{n},\mathrm{k},\mathrm{d}\right]}_{\mathrm{q}}$ linear of a well-chosen family and its generator matrix $\mathrm{G}$. We are going to mix this matrix to make it indistinguishable from a random matrix, so we need a permutation matrix $\mathrm{P}$ her size is $\mathrm{n}\times \mathrm{n}$ (having 1 in each row and column and 0 everywhere) and an invertible matrix $\mathrm{S}$ her size $\mathrm{k}\times \mathrm{k}$ ($\mathrm{S}$ is jammer). The public key will be ${\mathrm{G}}^{\prime }=\mathrm{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 $\mathrm{S}$, $\mathrm{P}$ and $\mathrm{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

Input

A family of linear codes ${\left[\mathrm{n},\mathrm{k},\mathrm{d}\right]}_{\mathrm{q}}$ chosen for design.

Procedure

Choose a generator matrix $\mathrm{G}$ in systematic form of the design code.

Choose an invertible matrix $\mathrm{S}$ her size $\mathrm{k}$ with coefficients in ${\mathrm{F}}_{\mathrm{q}}$.

Choose a permutation matrix $\mathrm{P}$ her size is $\mathrm{n}\times \mathrm{n}$.

Calculate ${\mathrm{G}}^{\prime }=\mathrm{SGP}$.

Output

The public key ${\mathrm{G}}^{\prime }$.

The private key $\left(\mathrm{S},\mathrm{G},\mathrm{P}\right)$.

Encryption of the plaintext.

Input

The public key ${\mathrm{G}}^{\prime }$.

The plaintext $\mathrm{x}\in {\mathrm{F}}_{\mathrm{q}}^{\mathrm{k}}$.

Procedure

Choose a vector $\mathrm{e}\in {\mathrm{F}}_{\mathrm{q}}^{\mathrm{n}}$ (an error) his weight less than or equal to the design code correction capacity.

Calculate $\mathrm{y}=\mathrm{x}{\mathrm{G}}^{\prime }+\mathrm{e}$.

Output: The cipher text $\mathrm{y}$.

Decryption of cipher text

Input: the cipher text $\mathrm{y}$, The private key $\left(\mathrm{S},\mathrm{G},\mathrm{P}\right)$.

Procedure

Calculate $\mathrm{u}=\mathrm{y}{\mathrm{P}}^{-1}$.

Calculate ${\mathrm{x}}^{\prime }={\mathrm{f}}_{\mathrm{G}}\left(\mathrm{u}\right)$ with ${\mathrm{f}}_{\mathrm{G}}$ the design code decoding algorithm, whose generator matrix is $\mathrm{G}$.

Calculate $\mathrm{x}=\mathrm{x}\prime {\mathrm{S}}^{-1}$.

Output: the plaintext $\mathrm{x}$.

Remark

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: $\mathrm{m}=10,\mathrm{n}=2^{\mathrm{n}}=1024,\mathrm{r}=50,\mathrm{k}=\mathrm{n}-\mathrm{mr}=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.

Example

We use the Hamming code with its generator matrix $\mathrm{G}=\left[\begin{array}{ccccccc}1& 0& 0& 0& 1& 0& 1\\ 0& 1& 0& 0& 0& 1& 1\\ 0& 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 1& 1& 1& 1\end{array}\right]$ and parity check matrix$\mathrm{H}=\left[\begin{array}{ccccccc}1& 0& 1& 1& 1& 0& 0\\ 0& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 0& 0& 1.\end{array}\right]$

The generation of keys

Let the private key $\mathrm{S},\mathrm{G},\mathrm{P}$.

$\mathrm{S}=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 1\\ 0& 0& 0& 1\end{array}\right]={\mathrm{S}}^{-1}$, $\mathrm{P}=\left[\begin{array}{ccccccc}0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 1& 0\end{array}\right]$, ${\mathrm{P}}^{-1}=\left[\begin{array}{ccccccc}0& 0& 0& 1& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0\end{array}\right]$

The public key: ${\mathrm{G}}^{\prime }=\mathrm{SGP}=\left[\begin{array}{ccccccc}0& 1& 0& 0& 1& 1& 1\\ 1& 0& 0& 1& 0& 0& 1\\ 1& 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 0& 1& 1& 1\end{array}\right]$

Encryption

Let the plaintext $\mathrm{x}=\left(0110\right)$ and let error vector $\mathrm{e}=\left(0010000\right)$.

The cipher text is $\mathrm{y}=\mathrm{xG}\prime +\mathrm{e}=\left(0111000\right)+\left(0010000\right)=\left(0101000\right)$.

Decryption

We decipher the text received $\mathrm{y}=\left(0101000\right)$. We have $\mathrm{y}=\mathrm{x}{\mathrm{G}}^{\prime }+\mathrm{e}=\text{xSGP}+\mathrm{e}$ then ${\mathrm{P}}^{-1}=\mathrm{xSG}+\mathrm{e}{\mathrm{P}}^{-1}=\left(1100000\right)=\mathrm{y}\prime$. $\mathrm{Hy}{\prime }^{\mathrm{t}}=\left(\begin{array}{c}1\\ 1\\ 0\end{array}\right)$, so the error is in the third position hence $\mathrm{u}=\left(1110000\right)=\mathrm{xSG}$. And since $\mathrm{G}$ is generator matrix of the systematic system then $\mathrm{xS}=\left(1110\right)$ then $\mathrm{x}=\left(1110\right){\mathrm{S}}^{-1}=\left(0110\right)$. $\mathrm{x}$. Then the plaintext sought.

3.2 The Niederreiter variant

Let $\mathrm{C}$ a linear t-corrector code of length $n$ and dimension $k$. Let $\mathrm{H}$ a parity check matrix of $\mathrm{C}$ her size is $\left(\mathrm{n}-\mathrm{k}\right)\times \mathrm{n}$. We randomly choose an invertible matrix $\mathrm{S}$ and $\mathrm{P}$ a permutation matrix. We calculate ${\mathrm{H}}^{\prime }=\mathrm{SHP}$. We will have $\mathrm{H}\prime$ a public key and $\left(\mathrm{S},\mathrm{H},\mathrm{P}\right)$ the private key, with the knowledge of a syndrome decoding algorithm in $\mathrm{C}$. Let $\mathrm{x}$ a plaintext of length $n$ and weight $t$, we calculate the cipher text $\mathrm{y}=\mathrm{H}\prime {\mathrm{x}}^{\mathrm{t}}$. The recipient receives $y$ knowing the secret key, he can calculate ${\mathrm{S}}^{-1}\mathrm{y}=\mathrm{HP}{\mathrm{x}}^{\mathrm{t}}$. Using the syndrome decoding algorithm of $\mathrm{C}$, he can find $\mathrm{P}{\mathrm{x}}^{\mathrm{t}}$ and applying ${\mathrm{P}}^{-1}$ the plaintext $\mathrm{x}$ is found.

The algorithms of the Niederreiter cryptosystem [5]

The generation of keys

Input

A linear code ${\left[\mathrm{n},\mathrm{k},\mathrm{d}\right]}_{\mathrm{q}}$ is chosen for the design, of which we know a decoding algorithm by syndrome.

Procedure

Choose a parity check matrix $\mathrm{H}$ of design code.

Choose a matrix $\mathrm{S}$, invertible of size $k$ with coefficients in${\mathrm{F}}_{\mathrm{q}}$.

Choose a permutation matrix $P$ of size$\mathrm{n}\times \mathrm{n}$.

Calculate ${\mathrm{H}}^{\prime }=\mathrm{SHP}$.

Output

The public key ${\mathrm{H}}^{\prime }$.

The private key$\left(\mathrm{S},\mathrm{H},\mathrm{P}\right)$.

Encryption

Input

The public key $\mathrm{H}\prime$.

The plaintext $\mathrm{x}\in {\mathrm{F}}_{\mathrm{q}}^{\mathrm{n}}$ of weight less than or equal to the correction capacity.

Procedure

Calculate $\mathrm{y}=\mathrm{H}\prime {\mathrm{x}}^{\mathrm{t}}$.

Output

The cipher text$\mathrm{y}$.

Decryption

Input

The private key $\left(\mathrm{S},\mathrm{H},\mathrm{P}\right)$.

The cipher text$\mathrm{y}$.

Procedure

Calculate ${\mathrm{y}}^{\prime }={\mathrm{S}}^{-1}\mathrm{y}$.

Calculate ${\mathrm{x}}^{\prime }={\mathrm{f}}_{\mathrm{H}}\left({\mathrm{y}}^{\prime }\right)$ with ${\mathrm{f}}_{\mathrm{H}}$ the code syndrome decoding algorithm, its parity check matrix is $\mathrm{H}$.

Calculate $\mathrm{x}=\mathrm{x}\prime {\mathrm{P}}^{-1}$.

Output

The plaintext $\mathrm{x}$.

Remark

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\times n$, generator of a $C$ code of dimension $k$. $x$a random word of ${\mathrm{F}}_2^{\mathrm{n}}$ and $\mathrm{t}$ a positive integer, find if there is an error word $\mathrm{e}$ of ${\mathrm{F}}_2^{\mathrm{n}}$ such as $\mathrm{w}\left(\mathrm{e}\right)\le \mathrm{t}$ and $\mathrm{x}+\mathrm{e}\in \mathrm{C}$.

Problem 2

Given $\mathrm{H}$ a binary random parity matrix; her size $\left(\mathrm{n}-\mathrm{k}\right)\times \mathrm{n}$ of a $C$ code its dimension $\mathrm{k}$, $\mathrm{s}$a random vector of ${\mathrm{F}}_2^{\mathrm{n}-\mathrm{k}}$ and $\mathrm{t}$a positive integer, find if there is a word $\mathrm{x}$ of ${\mathrm{F}}_2^{\mathrm{n}}$ such as $\mathrm{w}\left(\mathrm{x}\right)\le \mathrm{t}$ and $\mathrm{H}{\mathrm{x}}^{\mathrm{t}}=\mathrm{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.

Definition

Let $\mathrm{C}$ a linear code of generator matrix $\mathrm{G}$ and length $\mathrm{n}$. A set of information $\mathrm{I}$ is a subset of $\left\{1,2,\dots \mathrm{n}\right\}$ such as ${\mathrm{G}}_{\mathrm{I}}$, her size $\mathrm{k}\times \mathrm{k}$ formed of columns of $\mathrm{G}$ labeled by the elements of $\mathrm{I}$, is invertible.

Remark

The matrix $\left({\mathrm{G}}_{\mathrm{I}}|{\mathrm{G}}_{\mathrm{J}}\right)$ with $\mathrm{I}\cup \mathrm{J}=\left\{1,2,\dots \mathrm{n}\right\}$ is equivalent to $\mathrm{G}$.

Algorithm

Input

$\mathrm{G}$: a matrix generating of a code $\mathrm{C}$.

$\mathrm{t}$: a positive integer.

$\mathrm{y}$: a word of ${\mathrm{F}}_2^{\mathrm{n}}$ such as $\mathrm{d}\left(\mathrm{y},\mathrm{C}\right)\le \mathrm{t}$.

Output

The couple $\left(\mathrm{x},\mathrm{e}\right)$ such as $\mathrm{y}=\mathrm{xG}+\mathrm{e}$ where$\mathrm{w}\left(\mathrm{e}\right)\le \mathrm{t}$.

Procedure

Randomly draw a set of information $\mathrm{I}$ of the code $\mathrm{C}$ (let $\mathrm{J}$ such as $\mathrm{I}\cup \mathrm{J}=\left\{1,2,\dots \mathrm{n}\right\}$).

Calculate $\mathrm{R}={\mathrm{G}}_{\mathrm{I}}^{-1}{\mathrm{G}}_{\mathrm{J}}$.

Write $\mathrm{y}=\left({\mathrm{y}}_{\mathrm{I}}|{\mathrm{y}}_{\mathrm{J}}\right)$.

Calculate ${\mathrm{e}}_{\mathrm{J}}={\mathrm{y}}_{\mathrm{J}}-{\mathrm{y}}_{\mathrm{I}}\mathrm{R}$.

Repeat the previous operations until you find ${\mathrm{e}}_{\mathrm{J}}$ such as $\mathrm{w}\left({\mathrm{e}}_{\mathrm{J}}\right)\le \mathrm{t}$.

Return$\mathrm{e}=\left(0|{\mathrm{e}}_{\mathrm{J}}\right)$.

Determine the word $\mathrm{x}$ such as $\mathrm{y}-\mathrm{e}=\mathrm{xG}$.

Proof

We have a $\mathrm{y}=\mathrm{xG}+\mathrm{e}$ and $\mathrm{y}=\left({\mathrm{y}}_{\mathrm{I}}|{\mathrm{y}}_{\mathrm{J}}\right)=\mathrm{x}\left({\mathrm{G}}_{\mathrm{I}}|{\mathrm{G}}_{\mathrm{J}}\right)+\left({\mathrm{e}}_{\mathrm{I}}|{\mathrm{e}}_{\mathrm{J}}\right)$. Hence ${\mathrm{e}}_{\mathrm{I}}={\mathrm{y}}_{\mathrm{I}}-\mathrm{x}{\mathrm{G}}_{\mathrm{I}}$ and ${\mathrm{e}}_{\mathrm{J}}={\mathrm{y}}_{\mathrm{J}}-\mathrm{x}{\mathrm{G}}_{\mathrm{J}}$.

If the set of information $\mathrm{I}$ does not contain an error position $\left({\mathrm{e}}_{\mathrm{I}}=0\right)$ and like ${\mathrm{G}}_{\mathrm{I}}$ is invertible, we obtain ${\mathrm{y}}_{\mathrm{I}}=\mathrm{x}{\mathrm{G}}_{\mathrm{I}}$, ${\mathrm{e}}_{\mathrm{J}}={\mathrm{y}}_{\mathrm{J}}-{\mathrm{y}}_{\mathrm{I}}{\mathrm{G}}_{\mathrm{I}}^{-1}{\mathrm{G}}_{\mathrm{J}}$. Then $\mathrm{e}=\left(0|{\mathrm{y}}_{\mathrm{J}}-{\mathrm{y}}_{\mathrm{I}}{\mathrm{G}}_{\mathrm{I}}^{-1}{\mathrm{G}}_{\mathrm{J}.}\right)$ is the solution sought.

Remark

We have ${\mathrm{C}}_{\mathrm{n}}^{\mathrm{k}}$ possibilities to choose $\mathrm{k}=\left|\mathrm{I}\right|$ positions of $\left\{1,2,\dots \mathrm{n}\right\}$ ($\left|\mathrm{I}\right|$ is a cardinally of $\mathrm{I}$). And we have ${\mathrm{C}}_{\mathrm{n}-\mathrm{t}}^{\mathrm{k}}$ possibilities to choose $\mathrm{k}=\left|\mathrm{I}\right|$ positions among $\mathrm{n}-\mathrm{t}$ positions where ${\mathrm{e}}_{\mathrm{i}}=0$. So the probability of getting the set of information $\mathrm{I}$ with ${\mathrm{e}}_{\mathrm{I}}=0$ is $\mathrm{p}=\frac{{\mathrm{C}}_{\mathrm{n}-\mathrm{t}}^{\mathrm{k}}}{{\mathrm{C}}_{\mathrm{n}}^{\mathrm{k}}}$ and the average number of iterations will be $\frac{1}{\mathrm{p}}$.

Example

Let us try to attack the following system by this method: We have$\mathrm{G}=\left[\begin{array}{cccccccc}1& 1& 1& 0& 0& 1& 0& 1\\ 0& 1& 0& 1& 1& 1& 1& 0\end{array}\right]$.

The cipher text $\mathrm{y}=\left(10101011\right)$ et$\mathrm{t}=1$.

looking $\left(\mathrm{m},\mathrm{e}\right)$ such as $\mathrm{mG}+\mathrm{e}=\mathrm{y}$.

Let $\mathrm{I}=\left\{1,5\right\}\subset \left\{1,2,\dots 8\right\}$ then ${\mathrm{G}}_{\mathrm{I}}=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]={\mathrm{G}}_{\mathrm{I}}^{-1}$ and${\mathrm{G}}_{\mathrm{J}}=\left[\begin{array}{cccccc}1& 1& 0& 1& 0& 1\\ 1& 0& 1& 1& 1& 0\end{array}\right]$.

${\mathrm{y}}_{\mathrm{I}}=\left(1,1\right)$ and ${\mathrm{y}}_{\mathrm{J}}=\left(0,1,0,0,1,1\right)$. Then ${\mathrm{e}}_{\mathrm{J}}={\mathrm{y}}_{\mathrm{J}}-{\mathrm{y}}_{\mathrm{I}}{\mathrm{G}}_{\mathrm{I}}^{-1}{\mathrm{G}}_{\mathrm{J}}=\left(001000\right)$, it follows that $\left({\mathrm{e}}_{\mathrm{I}}|{\mathrm{e}}_{\mathrm{J}}\right)=\left(00001000\right)$.

$$\left({\mathrm{y}}_{\mathrm{I}}|{\mathrm{y}}_{\mathrm{J}}\right)+\left({\mathrm{e}}_{\mathrm{I}}|{\mathrm{e}}_{\mathrm{J}}\right)=\left(11010011\right)+\left(00001000\right)=\left(11011011\right)=\mathrm{m}\left({\mathrm{G}}_{\mathrm{I}}|{\mathrm{G}}_{\mathrm{J}}\right)=\mathrm{m}\left[\begin{array}{cccccccc}1& 0& 1& 1& 0& 1& 0& 1\\ 0& 1& 1& 0& 1& 1& 1& 0\end{array}\right]$$

then $\mathrm{m}=\left(11\right)$.

• Decoding by paradox of birthdays

Consider an instance of problem 2. For a parity check matrix $\mathrm{H}$ of size $\mathrm{r}\times \mathrm{n}$, a syndrome $\mathrm{s}$ and a weight $\mathrm{t}$. If the weight $\mathrm{t}$ is even, let us separate the columns of $\mathrm{H}$ in two sets of the same size ${\mathrm{H}}_1$ and ${\mathrm{H}}_2$ such as $\mathrm{H}=\left({\mathrm{H}}_1|{\mathrm{H}}_2\right)$.

Let us build ${\mathrm{L}}_1=\left\{{\mathrm{H}}_1{\mathrm{e}}_1^{\mathrm{t}},{\mathrm{e}}_1\text{of length}\frac{\mathrm{n}}{2}\text{and the weight}\frac{\mathrm{t}}{2}\right\}$ et ${\mathrm{L}}_2=\left\{\mathrm{s}+{\mathrm{H}}_2{\mathrm{e}}_{2,}^{\mathrm{t}}{\mathrm{e}}_2\text{of length}\frac{\mathrm{n}}{2}\text{and the weight}\frac{\mathrm{t}}{2}\right\}$. Common elements of ${\mathrm{L}}_1$ and ${\mathrm{L}}_2$ are such that ${\mathrm{H}}_1{\mathrm{e}}_1^{\mathrm{t}}=\mathrm{s}+{\mathrm{H}}_2{\mathrm{e}}_2^{\mathrm{t}}$, that is to say $\left({\mathrm{e}}_1|{\mathrm{e}}_2\right)$ is solution of problem 2.

The probability that one of the solutions splits into two equal parts of the parity matrix is $\mathrm{p}=\frac{{\left({\mathrm{C}}_{\mathrm{n}/2}^{\mathrm{t}/2}\right)}^2}{{\mathrm{C}}_{\mathrm{n}}^{\mathrm{t}}}$; to solve problem 2 you have to repeat these operations $\frac{1}{\mathrm{p}}$ 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 $\mathrm{x}$ is encrypted in two different ways. We will have ${\mathrm{y}}_1=\mathrm{xG}+{\mathrm{e}}_1$, ${\mathrm{y}}_2=\mathrm{xG}+{\mathrm{e}}_2$ où ${\mathrm{e}}_1$ et ${\mathrm{e}}_2$ sont deux vecteurs d’erreur distincts de poids $\mathrm{t}$. We get the word ${\mathrm{y}}_1-{\mathrm{y}}_2={\mathrm{e}}_1-{\mathrm{e}}_2$ which is less than or equal to $2\mathrm{t}$. Once an attacker has detected that the two cipher texts ${\mathrm{y}}_1$ and ${\mathrm{y}}_2$ 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 $2\mathrm{t}$ in general ($\mathrm{t}$the correction capacity).

Algorithm

Input

$\mathrm{G}$: The public key of size$\mathrm{k}\times \mathrm{n}$.

Two words ${\mathrm{y}}_1$ and ${\mathrm{y}}_2$ such as ${\mathrm{y}}_1=\mathrm{xG}+{\mathrm{e}}_1$, ${\mathrm{y}}_2=\mathrm{xG}+{\mathrm{e}}_2$ where ${\mathrm{e}}_1$ and ${\mathrm{e}}_2$ are two distinct error vectors of weight$\mathrm{t}$.

Output

The plaintext $\mathrm{x}$.

Procedure

Calculate ${\mathrm{y}}_1-{\mathrm{y}}_2$.

Randomly draw a set of information $\mathrm{I}\subset \left\{1,2,\dots \mathrm{n}\right\}$ which label the zero positions of ${\mathrm{y}}_1-{\mathrm{y}}_2$.

Calculate ${\mathrm{e}}_{\mathrm{J}}={\mathrm{y}}_{\mathrm{J}}-{\mathrm{y}}_{\mathrm{I}}{\mathrm{G}}_{\mathrm{I}}^{-1}{\mathrm{G}}_{\mathrm{J}}$ où ${\mathrm{y}}_1=\left({\mathrm{y}}_{\mathrm{I}}|{\mathrm{y}}_{\mathrm{J}}\right)$ et$\mathrm{I}\cup \mathrm{J}=\left\{1,2\dots \mathrm{n}\right\}$.

Repeat the previous operations until the weight of $\mathrm{e}$ ($\le \mathrm{t}$).

Return $\mathrm{x}={\mathrm{y}}_{\mathrm{I}}{\mathrm{G}}_{\mathrm{I}}^{-1}$.

Example

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

$$\mathrm{G}=\left[\begin{array}{cccccccc}1& 1& 1& 0& 0& 1& 0& 1\\ 0& 1& 0& 1& 1& 1& 1& 0\end{array}\right].$$

$${\mathrm{y}}_1=\mathrm{mG}+{\mathrm{e}}_1=\left(11\right)\left[\begin{array}{cccccccc}1& 1& 1& 0& 0& 1& 0& 1\\ 0& 1& 0& 1& 1& 1& 1& 0\end{array}\right]+\left(00010000\right)=\left(10101011\right)$$

$${\mathrm{y}}_2=\mathrm{mG}+{\mathrm{e}}_2=\left(11\right)\left[\begin{array}{cccccccc}1& 1& 1& 0& 0& 1& 0& 1\\ 0& 1& 0& 1& 1& 1& 1& 0\end{array}\right]+\left(00100000\right)=\left(10011011\right)$$

$${\mathrm{y}}_1+{\mathrm{y}}_2=\left(00110000\right).$$

Draw a set of information that labels the zero positions of ${\mathrm{y}}_1+{\mathrm{y}}_2$ let $\mathrm{I}=\left\{7,8\right\}$.

${\mathrm{G}}_{\mathrm{I}}=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]={\mathrm{G}}_{\mathrm{I}}^{-1}$, ${\mathrm{G}}_{\mathrm{J}}=\left[\begin{array}{cccccc}1& 1& 1& 0& 0& 1\\ 0& 1& 0& 1& 1& 1\end{array}\right]$; ${\mathrm{y}}_1=\left(10101011\right),{\mathrm{y}}_{\mathrm{I}}=\left(11\right),{\mathrm{y}}_{\mathrm{J}}=\left(101010\right)$.

$${\mathrm{e}}_{\mathrm{J}}={\mathrm{y}}_{\mathrm{J}}-{\mathrm{y}}_{\mathrm{I}}{\mathrm{G}}_{\mathrm{I}}^{-1}{\mathrm{G}}_{\mathrm{J}}=\left(101010\right)-\left(11\right)\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\left[\begin{array}{cccccc}1& 1& 1& 0& 0& 1\\ 0& 1& 0& 1& 1& 1\end{array}\right]=\left(000100\right).$$

$$\left({\mathrm{y}}_{\mathrm{I}}|{\mathrm{y}}_{\mathrm{J}}\right)+\left({\mathrm{e}}_{\mathrm{I}}|{\mathrm{e}}_{\mathrm{J}}\right)=\left(11101010\right)+\left(00000100\right)=\left(11101110\right)=\mathrm{m}\left[\begin{array}{cccccccc}0& 1& 1& 1& 1& 0& 0& 1\\ 1& 0& 0& 1& 0& 1& 1& 1\end{array}\right]$$

So we extract $\mathrm{m}=\left(11\right)$.

4.2 Structural attack

The attacker tries to find a decomposition of the key ${\mathrm{G}}^{\prime }={\mathrm{S}}_1{\mathrm{G}}_1{\mathrm{P}}_1$, 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 $\mathit{GRS}$ code can be obtained from the following proposition:

Proposal

Let $G=\left(\begin{array}{cccc}{v}_1& v_2& \dots & v_n\\ v_1{\alpha }_1& v_2{\alpha }_2& \dots & v_n{\alpha }_n\\ \dots & \mathrm{..}& \dots & \dots \\ v_1{\alpha }_1^{k-1}& v_2{\alpha }_2^{k-1}& \dots & v_n{\alpha }_n^{k-1}\end{array}\right)$ a matrix generating a Reed-Solomon code generalized on ${\mathrm{F}}_{{\mathrm{q}}^{\mathrm{m}}}$ then there is a matrix $\mathrm{k}\times \mathrm{k}$ invertible $\mathrm{S}$ coefficient in ${\mathrm{F}}_{{\mathrm{q}}^{\mathrm{m}}}$ and a matrix $\mathrm{R}={\left({\mathrm{R}}_{\mathrm{ij}}\right)}_{\begin{array}{l}\mathrm{i}=1\dots \mathrm{k}\\ \mathrm{j}=\mathrm{k}+1\dots \mathrm{n}\end{array}}$ such that $\left(\mathrm{I}|\mathrm{R}\right)=\mathrm{SG}$ and ${\mathrm{R}}_{\mathrm{ij}}=\frac{{\mathrm{v}}_{\mathrm{j}}}{{\mathrm{v}}_{\mathrm{i}}}{\prod }_{\begin{array}{c}\mathrm{s}=1\\ \mathrm{s}\ne \mathrm{i}\end{array}}^{\mathrm{k}}\frac{{\mathrm{\alpha }}_{\mathrm{j}}-{\mathrm{\alpha }}_{\mathrm{s}}}{{\mathrm{\alpha }}_{\mathrm{i}}-{\mathrm{\alpha }}_{\mathrm{s}}}$

Proof

For $\mathrm{i}=1,2\dots \mathrm{k}$ we define the following interpolation polynomial ${\mathrm{f}}_{\mathrm{i}}\left(\mathrm{x}\right)={\prod }_{\begin{array}{c}\mathrm{s}=1\\ \mathrm{s}\ne \mathrm{i}\end{array}}^{\mathrm{k}}\frac{{\mathrm{\alpha }}_{\mathrm{j}}-{\mathrm{\alpha }}_{\mathrm{s}}}{{\mathrm{\alpha }}_{\mathrm{i}}-{\mathrm{\alpha }}_{\mathrm{s}}}={\sum }_{\mathrm{j}=1}^{\mathrm{k}}{\mathrm{f}}_{\mathrm{ij}}{\mathrm{x}}^{\mathrm{j}-1}$ of degree $\mathrm{k}-1$ such that ${\mathrm{f}}_{\mathrm{i}}\left({\mathrm{\alpha }}_{\mathrm{i}}\right)=1$, ${\mathrm{f}}_{\mathrm{i}}\left({\mathrm{\alpha }}_{\mathrm{j}}\right)=0$ for $\mathrm{j}=1,2\dots \mathrm{k}$ and $\mathrm{j}\ne \mathrm{i}$. We note$\mathrm{S}={\left(\frac{{\mathrm{f}}_{\mathrm{ij}}}{{\mathrm{v}}_{\mathrm{i}}}\right)}_{\begin{array}{c}\mathrm{i}=1\dots \mathrm{k}\\ \mathrm{j}=1\dots .\mathrm{k}\end{array}}$.

The ith row of the matrix produces $\mathrm{SG}$ is $\left({\mathrm{f}}_{\mathrm{i}}\left({\mathrm{\alpha }}_1\right)\frac{{\mathrm{v}}_1}{{\mathrm{v}}_{\mathrm{i}}},{\mathrm{f}}_{\mathrm{i}}\left({\mathrm{\alpha }}_2\right)\frac{{\mathrm{v}}_2}{{\mathrm{v}}_{\mathrm{i}}},\dots {\mathrm{f}}_{\mathrm{i}}\left({\mathrm{\alpha }}_{\mathrm{n}}\right)\frac{{\mathrm{v}}_{\mathrm{n}}}{{\mathrm{v}}_{\mathrm{i}}}\right)$

By construction of polynomials ${\mathrm{f}}_{\mathrm{i}}$, the $\mathrm{k}$first columns of the matrix $\mathrm{SG}$ form the identity matrix, therefore $\mathrm{S}$ is invertible and $\mathrm{SG}=\left(\mathrm{I}|\mathrm{R}\right)$ where $\mathrm{R}={\mathrm{R}}_{\mathrm{ij}}$ and ${\mathrm{R}}_{\mathrm{ij}}={\mathrm{f}}_{\mathrm{i}}\left({\mathrm{\alpha }}_{\mathrm{j}}\right)\frac{{\mathrm{v}}_{\mathrm{j}}}{{\mathrm{v}}_{\mathrm{i}}}$.

Corollary

Let $\mathrm{I}$ the identity matrix its order $\mathrm{k}$ and $\mathrm{R}={\left({\mathrm{R}}_{\mathrm{ij}}\right)}_{\begin{array}{c}\mathrm{i}=1\dots \mathrm{k}\\ \mathrm{j}=\mathrm{k}+1\dots \mathrm{n}\end{array}}$ where ${\mathrm{R}}_{\mathrm{ij}}=\frac{{\mathrm{v}}_{\mathrm{j}}}{{\mathrm{v}}_{\mathrm{i}}}{\prod }_{\begin{array}{c}\mathrm{s}=1\\ \mathrm{s}\ne \mathrm{i}\end{array}}^{\mathrm{k}}\frac{{\mathrm{\alpha }}_{\mathrm{j}}-{\mathrm{\alpha }}_{\mathrm{s}}}{{\mathrm{\alpha }}_{\mathrm{i}}-{\mathrm{\alpha }}_{\mathrm{s}}}$. Alors la matrice $\left(\mathrm{I}|\mathrm{R}\right)$ is the generator matrix in systematic form of the generator matrix $\mathit{GRS}$ code $G=\left(\begin{array}{cccc}{v}_1& v_2& \dots & v_n\\ v_1{\alpha }_1& v_2{\alpha }_2& \dots & v_n{\alpha }_n\\ \dots & \mathrm{..}& \dots & \dots \\ v_1{\alpha }_1^{k-1}& v_2{\alpha }_2^{k-1}& \dots & v_n{\alpha }_n^{k-1}\end{array}\right)$.

Proof

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

Algorithm

Input

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

The public key ${\mathrm{G}}^{\prime }$.

Results

The matrix $\mathrm{G}={\left({\mathrm{v}}_{\mathrm{j}}{\mathrm{\alpha }}_{\mathrm{j}}^{\mathrm{i}}\right)}_{\begin{array}{c}\mathrm{i}=0,..\mathrm{k}-1\\ \mathrm{j}=1\dots \mathrm{n}\end{array}}$ and $\mathrm{S}$ invertible matrix its size $\mathrm{k}\times \mathrm{k}$ such that ${\mathrm{G}}^{\prime }=\mathrm{SG}$.

Procedure

Put the matrix $\mathrm{G}\prime$ in form $\left(\mathrm{I}|\mathrm{R}\right)$ by Gaussian elimination.

Determine the matrix $\mathrm{G}={\left({\mathrm{v}}_{\mathrm{j}}{\mathrm{\alpha }}_{\mathrm{j}}^{\mathrm{i}}\right)}_{\begin{array}{c}\mathrm{i}=0,..\mathrm{k}-1\\ \mathrm{j}=1\dots \mathrm{n}\end{array}}$ such that ${\mathrm{\alpha }}_1,\dots {\mathrm{\alpha }}_{\mathrm{n}}$ et ${\mathrm{v}}_1,\dots {\mathrm{v}}_{\mathrm{n}}$ check the equations ${\mathrm{R}}_{\mathrm{ij}}=\frac{{\mathrm{v}}_{\mathrm{j}}}{{\mathrm{v}}_{\mathrm{i}}}{\prod }_{\begin{array}{c}\mathrm{s}=1\\ \mathrm{s}\ne \mathrm{i}\end{array}}^{\mathrm{k}}\frac{{\mathrm{\alpha }}_{\mathrm{j}}-{\mathrm{\alpha }}_{\mathrm{s}}}{{\mathrm{\alpha }}_{\mathrm{i}}-{\mathrm{\alpha }}_{\mathrm{s}}}$.

Determine the matrix $S$ such that ${\mathrm{G}}^{\prime }=\mathrm{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.