q-polynomial and Rank Decoding Problem

savecancel

Dear all,

For the Rank Decoding (RD) problem: Given $y=mG+e$ , random row full-rank matrix $G = (g_{ij})\in GF({q^m})^{k \times n}$, one solves $m$ and $e$.

Here $m=(m_1,m_2,...,m_k)\in GF({q^m})^{k}$, $y = (y_1,y_2,\ldots,y_n)\in GF({q^m})^{n}$, all coordinates of $e=(e_1,e_2,...,e_n)\in GF({q^m})^{n}$ of weight $r$ lie in a subspace of $GF({q^m})$ over $GF({q})$ of dimension $r$.

Since all coordinates of $e=(e_1,e_2,...,e_n)$ of weight $r$ lie in a subspace of $GF({q^m})$ over $GF({q})$ of dimension $r$, then there exists a unique monic $q$-polynomial $P(x) = \sum_{l=0}^{r}p_lx^{q^l}$ of $q$-degree $r$ such that

$\forall \ j \in {1...n}, \qquad P\left(y_j-\sum_{i=1}^{k}m_ig_{ij}\right)= \sum_{l=0}^{r}\left(p_ly_j^{q^l}- \sum_{i=1}^{k}p_lm_i^{q^l}g_{ij}^{q^l}\right)= P\left(e_j\right) = 0$.

This gives a equations system with $n$ equations and unknowns $p_l$ and $m_i$.

To solve the RD problem, one needs to solve $p_l$ or $m_i$. For this purpose, one views $(r+1)(k+1)-1$ monomials in $p_l$ and $m_i$ as unknowns:

1. $kr$ terms of the form: $p_l m_i^{q^l}$;
2. $k$ terms of the form: $m_i^{q^r}$ due to $p_r$ = 1;
3. $r$ terms of the form: $p_j$.

I want to know how to construct this equations system with $n$ equations and $(r+1)(k+1)-1$ unknowns (monomials) by constructing a q-polynomial?

Thanks for the idea of all!