Let us describe here a toy-example showing an execution of our cryptosystem. Let \(F=\mathbb {F}_{16}=\frac{\mathbb {F}_{2}[a]}{\left\langle a^4 + a + 1 \right\rangle }\) be the field with \(2^4\) elements such that \(a^4+a+1 = 0\). The elements of F may be represented by a hexadecimal character. For instance, \(a^3 + a + 1 = 1011 = \texttt{B}\). Set \(n=16\) and \(t=2\). In this case, we can only consider \(m=2\) and \(\delta =4\). Then \(\mu = 2\) and we choose randomly \(s=4\).
Let
\(L=\frac{F[b]}{\langle b^2 + \texttt{F} b + \texttt{B} \rangle }\), and consider
\(\{1,b\}\) a basis as
F-vector space. We choose randomly
\(\gamma = \texttt{B} b + \texttt{2}\), a primitive element in
L, and
\(\alpha = \texttt{9} b + \texttt{8}\in L\), an element that generates a normal basis. We also choose randomly 16 position points in
\(L\),
$$\begin{aligned}{4} \alpha _0&= \texttt{4} b + \texttt{5}&\quad \alpha _1&= \texttt{1} b + \texttt{F}&\quad \alpha _2&= \texttt{8} b + \texttt{3}&\quad \alpha _3&= \texttt{3} b + \texttt{D} \\ \alpha _4&= \texttt{3} b + \texttt{7}&\quad \alpha _5&= \texttt{9}&\quad \alpha _6&= \texttt{8} b + \texttt{B}&\quad \alpha _7&= \texttt{3} b + \texttt{A} \\ \alpha _8&= \texttt{4} b + \texttt{9}&\quad \alpha _9&= \texttt{5} b + \texttt{2}&\quad \alpha _{10}&= \texttt{C} b + \texttt{6}&\quad \alpha _{11}&= \texttt{7} b + \texttt{6} \\ \alpha _{12}&= \texttt{2} b + \texttt{4}&\quad \alpha _{13}&= \texttt{A} b + \texttt{B}&\quad \alpha _{14}&= \texttt{C} b + \texttt{1}&\quad \alpha _{15}&= \texttt{1} b + \texttt{1}, \end{aligned}$$
and 16 non-zero elements in
L,
$$\begin{aligned}{4} \eta _0&= \texttt{F} b + \texttt{D}&\quad \eta _1&= \texttt{5} b + \texttt{F}&\quad \eta _2&= \texttt{1} b + \texttt{9}&\quad \eta _3&= \texttt{3} b + \texttt{4} \\ \eta _4&= \texttt{3} b + \texttt{4}&\quad \eta _5&= \texttt{1} b + \texttt{D}&\quad \eta _6&= \texttt{4} b + \texttt{F}&\quad \eta _7&= \texttt{7} b + \texttt{B} \\ \eta _8&= \texttt{7} b&\quad \eta _9&= \texttt{2} b + \texttt{8}&\quad \eta _{10}&= \texttt{D} b + \texttt{F}&\quad \eta _{11}&= \texttt{9} b + \texttt{7} \\ \eta _{12}&= \texttt{2} b + \texttt{6}&\quad \eta _{13}&= \texttt{A} b + \texttt{B}&\quad \eta _{14}&= \texttt{3} b + \texttt{6}&\quad \eta _{15}&= \texttt{A} b + \texttt{8}. \end{aligned}$$
We choose randomly the Goppa polynomial
$$\begin{aligned} g=x^{4} + \texttt{7} x^{2} + \texttt{9}\in L[x;\tau ^4] \end{aligned}$$
which allows the calculation of the parity check polynomials
$$\begin{aligned} h_0&= \texttt{2} x^{3} + \left( \texttt{8} b + \texttt{B}\right) x^{2} \\ h_1&= \texttt{D} x^{3} + \texttt{D} b x^{2} + \texttt{3} x + \texttt{3} b \\ h_2&= \texttt{D} x^{3} + \left( \texttt{2} b + \texttt{9}\right) x^{2} + \texttt{3} x + \texttt{B} b + \texttt{6} \\ h_3&= \texttt{8} x^{3} + \left( \texttt{B} b + \texttt{1}\right) x^{2} + \texttt{8} x + \texttt{B} b + \texttt{1} \\ h_4&= \texttt{3} x^{3} + \left( \texttt{5} b + \texttt{F}\right) x^{2} + x + \texttt{3} b + \texttt{5}\\ h_5&= \texttt{9} x^{3} + \texttt{D} x^{2} + \texttt{5} x + \texttt{B} \\ h_6&= \texttt{F} x^{3} + \left( b + \texttt{C}\right) x^{2} + x + \texttt{8} b + \texttt{A} \\ h_7&= \texttt{3} x^{3} + \left( \texttt{5} b + \texttt{B}\right) x^{2} + \texttt{8} x + \texttt{B} b + \texttt{C}\\ h_8&= \texttt{3} x^{3} + \texttt{C} b x^{2} + \texttt{8} x + \texttt{6} b \\ h_9&= \texttt{9} x^{3} + \left( \texttt{B} b + \texttt{2}\right) x^{2} + \texttt{5} x + \texttt{2} b + \texttt{7} \\ h_{10}&= \texttt{8} x^{3} + \left( \texttt{A} b + \texttt{9}\right) x^{2} + \texttt{5} x + \texttt{9} b + \texttt{3} \\ h_{11}&= \texttt{2} x^{3} + \left( \texttt{E} b + \texttt{9}\right) x^{2} \\ h_{12}&= \texttt{F} x^{3} + \left( \texttt{D} b + \texttt{E}\right) x^{2} + \texttt{A} x + \texttt{7} b + \texttt{5} \\ h_{13}&= \texttt{B} x^{3} + \left( \texttt{2} b + \texttt{4}\right) x^{2} + \texttt{A} x + \texttt{8} b + \texttt{3} \\ h_{14}&= \texttt{9} x^{3} + \left( \texttt{6} b + \texttt{D}\right) x^{2} + \texttt{F} x + \texttt{8} b + \texttt{E} \\ h_{15}&= \texttt{E} x^{3} + \left( \texttt{E} b + \texttt{B}\right) x^{2} + \texttt{F} x + \texttt{F} b + \texttt{5}. \end{aligned}$$
Hence, a parity check matrix is given by
$$\begin{aligned} \left( \begin{array}{cccccccc} \texttt{0} &{} \texttt{8} b + \texttt{3} &{} \texttt{9} b + \texttt{A} &{} \texttt{C} b + \texttt{C} &{} \texttt{5} b + \texttt{6} &{} \texttt{B} b + \texttt{6} &{} \texttt{B} b + \texttt{3} &{} \texttt{2} b + \texttt{7} \\ \texttt{0} &{} \texttt{F} b + \texttt{2} &{} \texttt{3} b + \texttt{8} &{} \texttt{B} b + \texttt{6} &{} \texttt{3} b + \texttt{4} &{} \texttt{5} b + \texttt{C} &{} \texttt{4} b + \texttt{F} &{} \texttt{D} b + \texttt{7} \\ \texttt{E} b + \texttt{D} &{} \texttt{F} b + \texttt{D} &{} \texttt{5} b + \texttt{8} &{} \texttt{C} b + \texttt{C} &{} \texttt{F} b + \texttt{A} &{} \texttt{D} b + \texttt{E} &{} \texttt{3} b + \texttt{2} &{} \texttt{4} b + \texttt{E} \\ \texttt{D} b + \texttt{9} &{} \texttt{C} b + \texttt{7} &{} \texttt{D} b + \texttt{F} &{} \texttt{B} b + \texttt{6} &{} \texttt{5} b + \texttt{C} &{} \texttt{9} b + \texttt{F} &{} \texttt{9} b + \texttt{A} &{} \texttt{9} b + \texttt{E} \end{array}\right. \\ \left. \begin{array}{cccccccc} \texttt{F} b + \texttt{B} &{} \texttt{4} b + \texttt{7} &{} \texttt{1} &{} \texttt{0} &{} \texttt{E} b + \texttt{5} &{} \texttt{D} &{} \texttt{7} b + \texttt{B} &{} \texttt{D} b + \texttt{3} \\ \texttt{D} b &{} \texttt{A} b + \texttt{E} &{} \texttt{C} b + \texttt{6} &{} \texttt{0} &{} \texttt{7} b + \texttt{9} &{} \texttt{8} b + \texttt{2} &{} \texttt{2} b + \texttt{4} &{} \texttt{C} b + \texttt{1} \\ \texttt{D} b + \texttt{5} &{} \texttt{5} b + \texttt{2} &{} \texttt{7} &{} \texttt{A} b + \texttt{E} &{} \texttt{9} b + \texttt{E} &{} \texttt{E} &{} \texttt{F} b + \texttt{A} &{} \texttt{F} b + \texttt{8} \\ \texttt{9} b &{} b + \texttt{4} &{} \texttt{2} b + \texttt{1} &{} b + \texttt{E} &{} \texttt{D} b + \texttt{4} &{} \texttt{2} b + \texttt{9} &{} \texttt{8} b + \texttt{3} &{} \texttt{6} b + \texttt{9} \end{array}\right) , \end{aligned}$$
whose expansion with coefficients in
F is given by
$$\begin{aligned} H = \left( \begin{array}{rrrrrrrrrrrrrrrr} \texttt{0} &{} \texttt{3} &{} \texttt{A} &{} \texttt{C} &{} \texttt{6} &{} \texttt{6} &{} \texttt{3} &{} \texttt{7} &{} \texttt{B} &{} \texttt{7} &{} \texttt{1} &{} \texttt{0} &{} \texttt{5} &{} \texttt{D} &{} \texttt{B} &{} \texttt{3} \\ \texttt{0} &{} \texttt{8} &{} \texttt{9} &{} \texttt{C} &{} \texttt{5} &{} \texttt{B} &{} \texttt{B} &{} \texttt{2} &{} \texttt{F} &{} \texttt{4} &{} \texttt{0} &{} \texttt{0} &{} \texttt{E} &{} \texttt{0} &{} \texttt{7} &{} \texttt{D} \\ \texttt{0} &{} \texttt{2} &{} \texttt{8} &{} \texttt{6} &{} \texttt{4} &{} \texttt{C} &{} \texttt{F} &{} \texttt{7} &{} \texttt{0} &{} \texttt{E} &{} \texttt{6} &{} \texttt{0} &{} \texttt{9} &{} \texttt{2} &{} \texttt{4} &{} \texttt{1} \\ \texttt{0} &{} \texttt{F} &{} \texttt{3} &{} \texttt{B} &{} \texttt{3} &{} \texttt{5} &{} \texttt{4} &{} \texttt{D} &{} \texttt{D} &{} \texttt{A} &{} \texttt{C} &{} \texttt{0} &{} \texttt{7} &{} \texttt{8} &{} \texttt{2} &{} \texttt{C} \\ \texttt{D} &{} \texttt{D} &{} \texttt{8} &{} \texttt{C} &{} \texttt{A} &{} \texttt{E} &{} \texttt{2} &{} \texttt{E} &{} \texttt{5} &{} \texttt{2} &{} \texttt{7} &{} \texttt{E} &{} \texttt{E} &{} \texttt{E} &{} \texttt{A} &{} \texttt{8} \\ \texttt{E} &{} \texttt{F} &{} \texttt{5} &{} \texttt{C} &{} \texttt{F} &{} \texttt{D} &{} \texttt{3} &{} \texttt{4} &{} \texttt{D} &{} \texttt{5} &{} \texttt{0} &{} \texttt{A} &{} \texttt{9} &{} \texttt{0} &{} \texttt{F} &{} \texttt{F} \\ \texttt{9} &{} \texttt{7} &{} \texttt{F} &{} \texttt{6} &{} \texttt{C} &{} \texttt{F} &{} \texttt{A} &{} \texttt{E} &{} \texttt{0} &{} \texttt{4} &{} \texttt{1} &{} \texttt{E} &{} \texttt{4} &{} \texttt{9} &{} \texttt{3} &{} \texttt{9} \\ \texttt{D} &{} \texttt{C} &{} \texttt{D} &{} \texttt{B} &{} \texttt{5} &{} \texttt{9} &{} \texttt{9} &{} \texttt{9} &{} \texttt{9} &{} \texttt{1} &{} \texttt{2} &{} \texttt{1} &{} \texttt{D} &{} \texttt{2} &{} \texttt{8} &{} \texttt{6} \end{array}\right) . \end{aligned}$$
Now, we compute the public key. Since
\(k=8\) and the rank of
H is
\(n-k = 8\), no additional random row is needed, so the public key
\(H_{\textrm{pub}}\) is simply the row reduced echelon form of
H, that is,
$$\begin{aligned} H_{\textrm{pub}} = \left( \begin{array}{rrrrrrrrrrrrrrrr} \texttt{1} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{C} &{} \texttt{2} &{} \texttt{3} &{} \texttt{2} &{} \texttt{9} &{} \texttt{9} &{} \texttt{A} &{} \texttt{4} \\ \texttt{0} &{} \texttt{1} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{9} &{} \texttt{1} &{} \texttt{A} &{} \texttt{C} &{} \texttt{7} &{} \texttt{3} &{} \texttt{8} &{} \texttt{6} \\ \texttt{0} &{} \texttt{0} &{} \texttt{1} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{A} &{} \texttt{8} &{} \texttt{2} &{} \texttt{4} &{} \texttt{D} &{} \texttt{6} &{} \texttt{5} &{} \texttt{B} \\ \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{1} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{9} &{} \texttt{0} &{} \texttt{1} &{} \texttt{3} &{} \texttt{B} &{} \texttt{7} &{} \texttt{8} &{} \texttt{9} \\ \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{1} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{E} &{} \texttt{9} &{} \texttt{B} &{} \texttt{C} &{} \texttt{F} &{} \texttt{2} &{} \texttt{6} &{} \texttt{6} \\ \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{1} &{} \texttt{0} &{} \texttt{0} &{} \texttt{A} &{} \texttt{B} &{} \texttt{1} &{} \texttt{6} &{} \texttt{9} &{} \texttt{1} &{} \texttt{1} &{} \texttt{5} \\ \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{1} &{} \texttt{0} &{} \texttt{3} &{} \texttt{F} &{} \texttt{1} &{} \texttt{2} &{} \texttt{F} &{} \texttt{B} &{} \texttt{E} &{} \texttt{1} \\ \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{0} &{} \texttt{1} &{} \texttt{A} &{} \texttt{D} &{} \texttt{8} &{} \texttt{6} &{} \texttt{4} &{} \texttt{1} &{} \texttt{2} &{} \texttt{B} \end{array}\right) . \end{aligned}$$
We select now the shared secret, a vector
\(e\in F^{16}\) with
\(t=2\) non-zero components,
$$\begin{aligned} \left( \texttt{4},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{C},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,0\right) . \end{aligned}$$
In this case the non-zero components correspond to the positions 0 and 9. We encrypt the secret by multiplying by the transpose of
\(H_{\textrm{pub}}\) obtaining a cyphertext
$$\begin{aligned} c=\left( \texttt{F},\,\texttt{C},\,\texttt{A},\,\texttt{0},\,\texttt{6},\,\texttt{D},\,\texttt{8},\,\texttt{3}\right) \in F^8. \end{aligned}$$
The receiver solves the linear system
\(c = y H^{\texttt{T}}_{\textrm{pub}}\) obtaining, for instance,
$$\begin{aligned} y=\left( \texttt{F},\,\texttt{C},\,\texttt{A},\,\texttt{0},\,\texttt{6},\,\texttt{D},\,\texttt{8},\,\texttt{3},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,\texttt{0},\,0\right) . \end{aligned}$$
Finally, applying the decoding algorithm in Algorithm 2 to
y, we find the vector
e, decrypting the secret.