4
$\begingroup$

I am working on an implementation of the Mceliece Encryption system (MCE) and the Niederreiter encryption system. I have been through the basics of finite fields, polynomial arithmetic and some coding theory to understand it.

In brief given MCE parameters $n, k, t$, such that it is over $GF(2^m)$, $n = 2^m$, $k = n - mt$ is the dimension of the linear code and $t$ is the no. of errors the code will correct, the public key is $X = S.G.P$, where $S$ is a $k$ x $k$ non-singular matrix, $G$ is the $k$ x $n$ generator matrix for the linear code and $P$ is a $n$ x $n$ permutation matrix.

Figuring out how to get $G$ is the reason for the question. I'd like to better understand how the generator matrix is built such that its elements are only $0$ or $1$, once we have the irreducible polynomial of degree $t$, support $L$ and parity check matrix $H$. $L$ & $H$ are composed of the elements of $GF(2^m)$ represented as polynomials in binary form, e.g. $x^4 + x^2 + 1$ is represented as $10101$.

I understand there are many methods of getting to the generator matrix but found limited information online. I'd welcome a simplified explanation of the maths/algorithm or any pointers to sites/books which would help out on this.

$\endgroup$
2
  • $\begingroup$ Are you looking for an effective implementation, or an implementation that teaches you about the system? $\endgroup$
    – QuadrExAtt
    Aug 29, 2014 at 21:55
  • $\begingroup$ Also, when you say your code is over $GF(2^m)$, do you mean your code is a binary Goppa code with support in $GF(2^m)^n$ that is intersected with $GF(2)^n$, or do you mean that your code is actually over $GF(2^m)$ (which is a generalisation of the system McEliece originally proposed). $\endgroup$
    – QuadrExAtt
    Aug 29, 2014 at 22:09

1 Answer 1

0
$\begingroup$

I'm going to assume you are using binary Goppa codes. That means, that you take a support $\mathbf{L} \in \mathbb{F}_{2^m}$, a Goppa polynomial $\Gamma$ of degree t with coefficients in $\mathbb{F}_{2^m}$ and build all codewords of a GRS code, and then intersect these with $\mathbb{F}_2^n$, resulting in a code that is actually a subset of $\mathbb{F}_2^n$ (and not of $\mathbb{F}_{2^m}^n$). This is the classical definition used by McEliece in his original proposition.

As you might have already read, the binary Goppa code has a check matrix (there is an error in the Wikipedia article, this one is correct): $$H_{grs} = \begin{pmatrix} 1 & \dots & 1 \\ L_0 & \dots & L_{n-1}\\ L_0^2 & \dots & L_{n-1}^2\\ \vdots & & \vdots\\ L_0^{t-1} & \dots & L_{n-1}^{t-1}\end{pmatrix} \begin{pmatrix} \frac{1}{\Gamma(L_0)} & & \\ & \ddots & \\ & & \frac{1}{\Gamma(L_{n-1})} \end{pmatrix}$$

Now, are you are well aware, this is a $t \times n$ matrix in $\mathbb{F}_{2^m}$ and will thus give you codewords in $\mathbb{F}_{2^m}^n$. But we are interesed in code words only in $\mathbb{F}_{2}^n$. One can get a check matrix that gives only codewords in $\mathbb{F}_2$ by expanding every entry in the matrix in a basis of $\mathbb{F}_{2^m}$.

This means, if your entry of the matrix is represented as as vector $0101$ in $\mathbb{F}_2^4$ (for $m=4$), you would expand this entry as four entries and write them in four rows: 0, 1, 0, 1.

Example: Let one of your rows of your check matrix $H_{grs}$ be $$\begin{pmatrix}0101& 1010 &0001& 1000\end{pmatrix}$$ then you would write this as $$\begin{pmatrix} 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\end{pmatrix}$$ You do this for all your rows and you will end up with a check matrix $H$ of size $mt \times n$, since you are expanding every row by $m$ rows. From now on, you only work over $\mathbb{F}_2$; using this check matrix, you'll get code words in $\mathbb{F}_2^n$. Note: You will have to do Gauss elimination at this point to get rid of rows that give the same equation. This will reduce your row number and give you a reduced check matrix of size $(n-k) \times n$, where k is the dimension of your binary code.

Now, to get a generator matrix $G$ for that code, you look for a full-rank matrix with $H^\top G=0$. There are many ways to achieve this, and you should find enough material on this. For example: http://en.wikipedia.org/wiki/Parity-check_matrix. Keep in mind, that if $H$ is a check matrix for $G$, then $G$ is a check matrix for $H$. So you build $G$ by pretending $H$ is a generator and you want to find a check matrix for that code.

I hope this is what you asked for.

$\endgroup$
2
  • $\begingroup$ I can give mathematical reasonings for the different claims if you're interested. $\endgroup$
    – QuadrExAtt
    Aug 29, 2014 at 22:31
  • $\begingroup$ Looking at the wikipedia page $H = [-P^T|I_{n-k}]$ and $G = [I_k|P]$, so if I reduce $H$ to the standard form, extract $P$ and transpose it, I can construct $G$. A few questions though, for binary goppa codes generally $k = n - mt$, so wouldn't a $mt$ x $n$ matrix be the same $n-k$ x $n$ matrix? I guess if the $H$ I get doesn't have $n-k = mt$ I should discard it and try another code? $\endgroup$
    – gautam
    Aug 30, 2014 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.