Code-based cryptography

Code-based Problems

1. Syndrome Decoding

SDP – Syndrome Decoding

Let $n,k,w$ be positive integers. A ${\text{SD}}(n,k,w)$ distribution is sampled by choosing $H\in \mathbb {F} _{q}^{(n-k)\times n}$ and $x\in \mathbb {F} _{q}^{n}$ where ${\text{wt}}(x)\leq w$, and ouputing $(H,Hx^{T})$.

PROBLEM. Search-SDP

Given a vector $s\in \mathbb {F} _{q}^{(n-k)\times n}$, $H\in \mathbb {F} _{q}^{(n-k)\times n}$ , and a positive interger $w\in \mathbb {N} ^{*}$.
Goal. Find vector $x\in \mathbb {F} _{q}^{n}$ such that $Hx^{T}=s$ and ${\text{wt}}(x)\leq w$.

PROBLEM. Decisional-SDP

Goal. Distinguish with a non-negligible advantage between samples from the SD distribution and samples from the uniform distribution over ${F}_{q}^{(n-k)\times n}\times \mathbb {F} _{q}^{n}$.

RSD – Rank Syndrome Decoding

Let $n,k,r$ be positive integers. A ${\text{RSD}}(n,k,r)$ distribution is sampled by choosing $H\in \mathbb {F} _{q^{m}}^{(n-k)\times n}$ and $x\in \mathbb {F} _{q^{m}}^{n}$ where ${\text{wt}}(x)\leq r$, and ouputing $(H,Hx^{T})$.

PROBLEM. Search-RSD

Given a vector $s\in \mathbb {F} _{q^{m}}^{n-k}$, $H\in \mathbb {F} _{q^{m}}^{(n-k)\times n}$, and a positive interger $w\in \mathbb {N} ^{*}$.
Goal. Find vector $x\in \mathbb {F} _{q^{m}}^{n}$ such that ${\text{wt}}(x)\leq r$ and $Hx^{T}=s^{T}$.

PROBLEM. Decisional-RSD

Goal. Distinguish with a non-negligible advantage between samples $(H,x^{T})$ from ${\text{RSD}}(n,k,r)$ distribution and samples from the uniform distribution over $\mathbb {F} _{q^{m}}^{(n-k)\times n}\times \mathbb {F} _{q^{m}}^{n}$.

RELATED PAPERS

An Algebraic Attack on Rank Metric Code-Based Cryptosystems
Magali Bardet and Pierre Briaud and Maxime Bros and Philippe Gaborit and Vincent Neiger and Olivier Ruatta and Jean-Pierre Tillich.
arXiv, 2019.

New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications
A. V. Ourivski and T. Johansson.
Problems of Information Transmission, 2002.

On the complexity of the Rank Syndrome Decoding problem
Philippe Gaborit and Olivier Ruatta and Julien Schrek.
arXiv, 2013.

Ideal RSD – Ideal Rank Syndrome Decoding

Let $P\in \mathbb {F} _{q}[X]$ be an irreducilbe polynomial of degree $n$ and $n,w,s$ be positive integers. Let $S(n,w,s)$ be the set of parity-check matrices ${\text{H}}$ under systematic form of $s-$ ideal codes of type $[sn,n]$. The $s-$IRSD distribution is sampled by choosing uniformly at random a matrix H from $S(n,w,s)$, a vector $x=(x_{1},\ldots ,x_{s})$ from $\mathbb {F} _{q^{m}}{sn}$ such that ${\text{wt}}(x)\leq w$ and, and ouputing $(H,Hx^{T})$.

PROBLEM. Search Ideal RSD

Given $P\in \mathbb {F} _{q}[X]$ be an irreducilbe polynomial of degree $n$ and $n,w,s$ be positive integers. Given a random parity check matrix ${\text{H}}$ under systematic form of $s-$ ideal codes and $y\in \mathbb {F} _{q^{m}}^{sn-n}$.
Goal. Find $x=(x_{1},\ldots ,x_{s})$ from $\mathbb {F} _{q^{m}}{sn}$ such that ${\text{wt}}(x)\leq w$ and, and ouputing $(H,Hx^{T})$.

PROBLEM. Decisional Ideal RSD

Given $P\in \mathbb {F} _{q}[X]$ be an irreducilbe polynomial of degree $n$ and $n,w,s$ be positive integers. Let $S(n,w,s)$ be the set of parity-check matrices ${\text{H}}$ under systematic form of $s-$ ideal codes of type $[sn,n]$.
Goal. Distinguish with a non-negligible advantage between samples $(H,x^{T})$ from $s-{\text{IRSD}}(n,w)$ distribution and samples from the uniform distribution over $S(n,w,s)\times \mathbb {F} _{q^{m}}^{sn-n}$.

QC-SDP – Quasi-Cyclic Syndrome Decoding

DEFINITION. Quasi-cyclic code (QC)

A linear code ${\mathcal {C}}$ of length $n=ln_{0}$ is a QC code of order $l$ and index $n_{0}$ if ${\mathcal {C}}$ is generated by parity-check matrix $H=\{H_{i,j}\}$ where $H_{i,j}$ is an $l\times l$ circulant matrix.

PROBLEM. Search QC-SDP

Given a set of $l$ matrices $\{C_{i}\}_{i=1}^{l}\subset \mathbb {F} _{q}^{r\times n}$, a positive integer $w<ln$ and a vector $s\in \mathbb {F} _{q}^{lr}$. Define $C$ as the $lr\times ln$ circulant matrix generated by $\{C_{i}\}_{i=1}^{l}$.
Goal. Find vector $x\in \mathbb {F} _{q}^{ln}$ with ${\text{wt}}(x)\leq w$ and $Cx^{T}=s$.

2. Ideal LRPC – Ideal Low Rank Parity Check

The definition of the Low Rank Parity Check (LRPC) codes was proposed by Gaborit, Murat, Ruatta, and Zémor in 2013.

DEFINITION. Low Rank Parity Check codes (LRPC)

A LRPC code of rank $d$, length $n$ and dimension $k$ over $F_{q^{m}}$is a code where it has a parity-check matrix $H=(h_{i,j})\in \mathbb {F} _{q^{m}}^{(n-k)\times n}$. The coefficients of $H$ generate a sub-vector space $F$ of $\mathbb {F} _{q^{m}}$ of small dimension $d$.

DEFINITION. Ideal Low Rank Parity Check codes (Ideal LRPC)

Let $F$ be a $\mathbb {F} _{q}$ sub-vector space of a small dimension $d$ of $\mathbb {F} _{q^{m}}$, $(h_{1},h_{2})$ two vectors of $\mathbb {F} _{q^{m}}^{n}$ of support $F$ and $P\in \mathbb {F} _{q}[X]]$ a polynomial of degree $n$. Let $H_{1}={\begin{pmatrix}h_{1}\\Xh_{1}\mod P\\\vdots \\X^{n-1}h_{1}\mod P\\\end{pmatrix}},H_{2}={\begin{pmatrix}h_{2}\\Xh_{2}\mod P\\\vdots \\X^{n-1}h_{2}\mod P\\\end{pmatrix}}.$ The code ${\mathcal {C}}$ with parity-check matrix $H=(H_{1},H_{2})$ is an ideal LRPC code of type $[2n,n]_{q^{m}}$.

PROBLEM. Decisional Ideal LRPC

Given a polynomial $P\in \mathbb {F} _{q}[X]$ of degree $n$ and a vector $h\in \mathbb {F} _{q^{m}}^{n}$
Goal. Distinguish an ideal code ${\mathcal {C}}$ with the parity-check matrix generated by $h,P$ is a random linear code or if it is an ideal LRPC code of weight $d$.

Submissions in NIST

PKE/KEM (19 schemes) BIG QUAKE BIKE Classic McEliece DAGS Edon-K HQC LAKE LEDAkem LEDApkc Lepton LOCKER McNie NTS-KEM ROLLO Ouroboros-R QC-MDPC KEM Ramstake RLCE-KEM RQC

Signatures (3 schemes) pqsigRM RaCoSS RankSign

References

GENERAL