1. Code-based Cryptography: Lecture Notes

1.1 Introduction

A linear code $\mathcal{C}$$\mathcal{C}$ of length $n$$n$ and dimension $k$$k$ over ${\mathbb{F}}_q$$\mathbb{F}_q$, i.e., an $[n,k{]}_q$$[n,k]_q$-code, is a subspace of ${\mathbb{F}}_q^n$$\mathbb{F}_q^n$ of dimension $k$$k$.

To represent an $[n,k{]}_q$$[n,k]_q$-code, we may take any basis of it, namely a set of $k$$k$ linearly independent vectors. We use them as rows to form the generator matrix $\mathbf{G}\in {\mathbb{F}}_q^{k\times n}$$\mathbf{G}\in\mathbb{F}_q^{k\times n}$, then $\mathcal{C}$$\mathcal{C}$ can be written as $\mathcal{C}=\{\mathbf{c}=\mathbf{mG}:\mathbf{m}\in {\mathbb{F}}_q^k\}$$\mathcal{C}=\{\mathbf{c}=\mathbf{mG}:\mathbf{m}\in\mathbb{F}_q^k\}$.

Conversely, any matrix $\mathbf{G}\in {\mathbb{F}}_q^{k\times n}$$\mathbf{G}\in\mathbb{F}_q^{k\times n}$ with rank $k$$k$ defines an $[n,k{]}_q$$[n,k]_q$-code.

A subspace of a vector space is a nonempty subset that satisfies the requirements for a vector space: Linear combinations stay in the subspace. (i) If we add any vector $x$$x$ and $y$$y$ in the subspace, then $x+y$$x+y$ is in the subspace.

(ii) If we multiply any vector $x$$x$ in the subspace by any scalar $c$$c$, then $cx$$cx$ is in the subspace.

The dual code of an $[n,k{]}_q$$[n,k]_q$-code $\mathcal{C}$$\mathcal{C}$ is defined as ${\mathcal{C}}^{\ast }=\{{\mathbf{c}}^{\ast }\in {\mathbb{F}}_q^n:\mathrm{\forall }\mathbf{c}\in \mathcal{C},⟨\mathbf{c},{\mathbf{c}}^{\ast }⟩=0\}$$\mathcal{C}^*=\{\mathbf{c}^*\in\mathbb{F}_q^n:\forall\mathbf{c}\in\mathcal{C},\langle\mathbf{c},\mathbf{c}^*\rangle=0\}$. Since $\mathbf{c}=\mathbf{mG}$$\mathbf{c}=\mathbf{mG}$, ${\mathcal{C}}^{\ast }$$\mathcal{C}^*$ is the nullspace of $\mathbf{G}$$\mathbf{G}$, and is an $[n,n-k{]}_q$$[n,n-k]_q$-code.

Its generator matrix is the parity-check matrix of $\mathcal{C}$$\mathcal{C}$, i.e., $\mathbf{H}\in {\mathbb{F}}_q^{(n-k)\times n}$$\mathbf{H}\in\mathbb{F}_q^{(n-k)\times n}$ , whose rows are basis of the nullspace.

The linear code $\mathcal{C}$$\mathcal{C}$ can also be written as $\mathcal{C}=\{\mathbf{c}\in {\mathbf{F}}_q^n:{\mathbf{Hc}}^{⊺}=\mathbf{0}\}$$\mathcal{C}=\{\mathbf{c}\in\mathbf{F}_q^n:\mathbf{Hc^{\intercal}}=\mathbf{0}\}$.

Conversely, any matrix $\mathbf{H}\in {\mathbb{F}}_q^{(n-k)\times n}$$\mathbf{H}\in\mathbb{F}_q^{(n-k)\times n}$ of rank $n-k$$n-k$ defines an $[n,k{]}_q$$[n,k]_q$-code.

Solutions to $\mathbf{Gx}=\mathbf{0}$$\mathbf{Gx}=\mathbf{0}$ form the nullspace of $\mathbf{G}$$\mathbf{G}$.

Elimination simplifies a system of linear equations without changing the solutions, i.e., if $\mathbf{G}$$\mathbf{G}$ is row reduced to ${\mathbf{G}}^{\prime }=[{\mathbf{I}}_{\mathbf{k}}|\mathbf{A}]$$\mathbf{G'}=[\mathbf{I_{k}}|\mathbf{A}]$, then $\mathbf{Gx}=\mathbf{0}$$\mathbf{Gx}=\mathbf{0}$ and ${\mathbf{G}}^{\prime }\mathbf{x}=\mathbf{0}$$\mathbf{G'x}=\mathbf{0}$ give the same solutions $\mathbf{x}$$\mathbf{x}$. Therefore, the nullspace of $\mathbf{G}$$\mathbf{G}$ is the same as the nullspace of ${\mathbf{G}}^{\prime }$$\mathbf{G'}$.

Since ${\mathbf{G}}^{\prime }$$\mathbf{G'}$ has rank $k$$k$, there are $k$$k$ pivot variables and $n-k$$n-k$ free variables, so the nullspace has dimension $n-k$$n-k$. These $n-k$$n-k$ vectors are special solutions to $\mathbf{Gx}=\mathbf{0}$$\mathbf{Gx}=\mathbf{0}$ and form the basis of the nullspace.

Left multiplication by an invertible matrix does not change the code ($\mathbf{SG}$$\mathbf{SG}$ or $\mathbf{SH}$$\mathbf{SH}$), it just gives another basis.

If $\mathsf{RREF}(\mathbf{G})=[{\mathbf{I}}_{\mathbf{k}}|\mathbf{A}]$$\mathsf{RREF}(\mathbf{G})=[\mathbf{I_k}|\mathbf{A}]$, then $\mathbf{H}=[\mathbf{-}{\mathbf{A}}^{⊺}|{\mathbf{I}}_{\mathbf{n}\mathbf{-}\mathbf{k}}]$$\mathbf{H}=[\mathbf{-A^{\intercal}}|\mathbf{I_{n-k}}]$, and ${\mathbf{GH}}^{⊺}=\mathbf{0}$$\mathbf{GH^{\intercal}}=\mathbf{0}$.

Let $\mathbf{H}\in {\mathbb{F}}_q^{(n-k)\times n}$$\mathbf{H}\in\mathbb{F}_q^{(n-k)\times n}$, the syndrome of $\mathbf{y}$$\mathbf{y}$ with respect to $\mathbf{H}$$\mathbf{H}$ is defined as ${\mathbf{Hy}}^{⊺}$$\mathbf{Hy^{\intercal}}$. Any element of ${\mathbb{F}}_q^{n-k}$$\mathbb{F}_q^{n-k}$ is called a syndrome.

Syndrome Decoding: Given $\mathbf{H}\in {\mathbb{F}}_q^{(n-k)\times n}$$\mathbf{H}\in\mathbb{F}_q^{(n-k)\times n}$ of rank $n-k$$n-k$, $\mathbf{s}\in {\mathbb{F}}_q^{(n-k)}$$\mathbf{s}\in\mathbb{F}_q^{(n-k)}$, $t\in \{0,\dots ,n\}$$t\in\{0,\dots,n\}$, find $\mathbf{e}$$\mathbf{e}$ with weight $t$$t$ such that ${\mathbf{He}}^{⊺}={\mathbf{s}}^{⊺}$$\mathbf{He^{\intercal}}=\mathbf{s^{\intercal}}$.

Any solver of syndrome decoding can be turned in polynomial time into an algorithm solving Noisy Codeword Decoding:

Given $\mathbf{G}\in {\mathbb{F}}_q^{k\times n}$$\mathbf{G}\in\mathbb{F}_q^{k\times n}$ of rank $k$$k$, $\mathbf{y}\in {\mathbb{F}}_q^n$$\mathbf{y}\in\mathbb{F}_q^{n}$, $t\in \{0,\dots ,n\}$$t\in\{0,\dots,n\}$, find $\mathbf{e}$$\mathbf{e}$ with weight $t$$t$ such that $\mathbf{y}=\mathbf{mG}+\mathbf{e}$$\mathbf{y}=\mathbf{mG}+\mathbf{e}$ for some $\mathbf{m}\in {\mathbb{F}}_q^k$$\mathbf{m}\in\mathbb{F}_q^k$.

Hardness of Decoding Problem: From telecommunication side, the decoding problem should be easy to solve. From security side, the decoding problem should be hard to solve. All the subtlety lies in the inputs of the problem. There exist some codes and decoding distances where the problem is easy to solve. The existance of codes that are easy to decode is at the foundation of code-based cryptography.

• Decoding problem is hard in the worst case (NP-complete), which means that we cannot hope to solve the decoding problem in polynomial time for all inputs.

• Decoding problem is hard on average, which means that for well chose $t$$t$, almost all codes are intractable.

The NP–completeness of a problem for a cryptographic use is a nice property but it is not the panacea to ensure its hardness, since it is quite possible that the security of a cryptosystem relies on the difficulty to solve an NP–complete problem but at the same time breaking the scheme amounts to solve the problem on a subset of inputs for which make the problem easy to solve.

Instead of considering the hardness based on its inputs, we focus on the algorithmic hardness of this decoding problem. Assume a probabilistic algorithm $\mathcal{A}$$\mathcal{A}$ that solves the decoding problem with success probability $\epsilon$$\varepsilon$, and a single run of this algorithm costs a time $T$$T$. Then the algorithm solves the decoding problem in average time $T/\epsilon$$T/\varepsilon$ (complexity).

Decoding Problem is a problem parametrized by $n$$n$ and two functions of $n$$n$: $R=k/n$$R=k/n$ and $\tau =t/n$$\tau=t/n$, i.e., $\mathsf{DP}(n,q,R,\tau )$$\mathsf{DP}(n,q,R,\tau)$. It can be solved in polynomial time as soon as $\tau \in [(1-R)\frac{q-1}{q},R+(1-R)\frac{q-1}{q}]$$\tau\in[(1-R)\frac{q-1}{q},R+(1-R)\frac{q-1}{q}]$. For other $\tau$$\tau$, the best algorithms are exponential in $\tau n$$\tau n$. (proof in 1.3)

1.2 Random Codes

Random codes' parity-check matrix or generator matrix is drawn unifromly at random.

In cryptography, negligible functions are often used to describe the probability of an event occurring with negligible probability. We say a function $f(n)$$f(n)$ is negligible, i.e., $f(n)\in \mathsf{negl}(n)$$f(n)\in\mathsf{negl}(n)$, if for all polynomial $p(n)$$p(n)$, $|f(n)|<1/|p(n)|$$|f(n)|<1/|p(n)|$ for all sufficiently large $n$$n$.

The introduction of the function $p(n)$$p(n)$ in the definition of negligible functions serves to formalize the idea that the function being considered becomes increasingly smaller as the input size $n$$n$ grows. It helps establish a quantitative measure for the rate at which the function approaches zero.

The use of $p(n)$$p(n)$ allows for generality in expressing the notion of negligibility. Different contexts and applications may require different rates of decay for a function to be considered negligible. The choice of $p(n)$$p(n)$ provides a flexible framework for capturing these variations.

As all the parameters are functions of $n$$n$, our asymptotic results will always hold for $n\to +\mathrm{\infty }$$n\rightarrow+\infin$.

The $q$$q$-ary entropy is defined as

It is equal to the entropy of a random variable $e$$e$ over ${\mathbb{F}}_q$$\mathbb{F}_q$ distributed like the error for a $q$$q$-ary symmetric channel of crossprobability $x$$x$.

It can be verified that $h_q$$h_q$ is an increasing function over $[0,\frac{q-1}{q}]$$\big[0,\frac{q-1}{q}\big]$ and a decreasing function over $[\frac{q-1}{q},1]$$\big[\frac{q-1}{q},1\big]$.

Let ${\mathcal{S}}_t$$\mathcal{S}_t$ denote the vectors that have Hamming distance $t$$t$, then $|{\mathcal{S}}_t|=(\genfrac{}{}{0ex}{}{n}{t})(q-1{)}^t$$|\mathcal{S}_t|={n\choose t}(q-1)^t$. We also have

Asymptotically, we have

Probability $P_X(A)$$P_X(A)$ represents the probability that random variable $X$$X$ is equal to event $A$$A$. We choose a random code by picking uniformly at random a parity-check matrix $\mathbf{H}\in {\mathbb{F}}_q^{(n-k)\times n}$$\mathbf{H}\in\mathbb{F}_q^{(n-k)\times n}$.

Defining $\mathsf{DP}$$\mathsf{DP}$ with generator or parity-check matrix is just a matter of personal taste, it does not change the average hardness.

Lemma 2.2.3. Given $\mathbf{s}\in {\mathbb{F}}_q^{n-k}$$\mathbf s\in\mathbb{F}_q^{n-k}$ and $\mathbf{y}\in {\mathbb{F}}_q^n$$\mathbf y\in\mathbb{F}_q^{n}$ such that $\mathbf{y}\ne \mathbf{0}$$\mathbf y\neq\mathbf 0$, we have for $\mathbf{H}$$\mathbf H$ being uniformly distributed at random in ${\mathbb{F}}_q^{n-k}$$\mathbb{F}_q^{n-k}$,

This lemma gives the probability over all random codes that a fixed non-zero word $\mathbf{y}$$\mathbf y$ reaches some syndrome $\mathbf{s}$$\mathbf s$ according to a certain code.

Proof. We assume $y_1=1$$y_1=1$, then we are looking for the probability of the following event

Since $h_{i,1}=s_i-\sum _{j=2}^n{h}_{i,j}{y}_j$$h_{i,1}=s_i-\sum_{j=2}^nh_{i,j}y_j$ only have $q$$q$ possible values, and $h_{i,j}$$h_{i,j}$'s are independent and equidistributed, the above $n-k$$n-k$ equations will be independently true with probability $1/q$$1/q$. This concludes the proof.

Question: given a random code $\mathcal{C}$$\mathcal{C}$ and a fixed vector $\mathbf{y}\in {\mathbb{F}}_q^n$$\mathbf y \in \mathbb{F}_q^n$, how many codewords $\mathbf{c}\in \mathcal{C}$$\mathbf c\in\mathcal{C}$ do we expect to be at Hamming distance $t$$t$ from $\mathbf{y}$$\mathbf y$, i.e., $\mathbf{y}=\mathbf{c}+\mathbf{e}$$\mathbf{y}=\mathbf{c}+\mathbf e$? Or equivalently, given a parity-check matrix of our random code $\mathcal{C}$$\mathcal{C}$ and a fixed syndrome $\mathbf{s}$$\mathbf s$, how many error vectors $\mathbf{e}$$\mathbf e$ of Hamming weight $t$$t$ do we expect to reach the syndrome $\mathbf{s}$$\mathbf s$ according to $\mathbf{H}$$\mathbf H$, i.e., ${\mathbf{eH}}^{⊺}=\mathbf{s}$$\mathbf{eH^{\intercal}}=\mathbf s$?

Let $N_t(\mathcal{C},\mathbf{s})=|\{\mathbf{e}\in {\mathcal{S}}_t:{\mathbf{eH}}^{⊺}=\mathbf{s}\}|$$N_t\big(\mathcal{C},\mathbf s\big)=|\{\mathbf e\in\mathcal{S}_t:\mathbf{eH^{\intercal}}=\mathbf s\}|$, which is a random variable that gives the number of solutions of $\mathsf{DP}$$\mathsf{DP}$ with input $(\mathbf{H},\mathbf{s})$$(\mathbf{H},\mathbf s)$, where $\mathbf{s}\in {\mathbb{F}}_q^{n-k}$$\mathbf s\in\mathbb{F}_q^{n-k}$ is fixed. On the other hand, $N_t(\mathcal{C},\mathbf{0})$$N_t\big(\mathcal{C},\mathbf 0\big)$ gives the number of codewords $\mathbf{c}\in \mathcal{C}$$\mathbf c\in\mathcal C$ of Hamming weight $t$$t$.

This number is crucial to know, the reason is as follows.

A trivial solution to solve $\mathsf{DP}$$\mathsf{DP}$ is to pick a ranfom error vector $\mathbf{e}\in {\mathcal{S}}_t$$\mathbf e\in\mathcal{S}_t$,

• If there is only one solution $\mathbf{e}$$\mathbf e$, then our success probability is $\frac{1}{(\genfrac{}{}{0ex}{}{n}{t})(q-1{)}^t}$$\frac{1}{{n\choose t}(q-1)^t}$.

• If there are $N$$N$ solutions $\mathbf{e}$$\mathbf e$, then the success probability is $\frac{N}{(\genfrac{}{}{0ex}{}{n}{t})(q-1{)}^t}$$\frac{N}{{n\choose t}(q-1)^t}$.

It is therefore crucial to know the value of $N$$N$ to be able to predict the running time of our algorithm.

Solution:

The expectation of $N_t(\mathcal{C},\mathbf{s})$$N_t\big(\mathcal{C},\mathbf s\big)$ is $(\genfrac{}{}{0ex}{}{n}{t})(q-1{)}^t/q^{n-k}$${n\choose t}(q-1)^t/q^{n-k}$. Then

where $0\le \tau ,R\le 1$$0\le\tau,R\le 1$. Since $h_q(0)=0$$h_q(0)=0$ and $h_q(1)={\log }_q(q-1)$$h_q(1)=\log_q(q-1)$, $N_t(\mathcal{C},\mathbf{s})$$N_t\big(\mathcal{C},\mathbf s\big)$ is expected to be exponentially small at one value ${\tau }^{-}$$\tau^-$ and potentially a second value ${\tau }^{+}$$\tau^+$ in the case that $(1-R)\ge {\log }_q(q-1)$$(1-R)\ge\log_q(q-1)$. The analytic expression of ${\tau }^{-}$$\tau^-$ and ${\tau }^{+}$$\tau^+$ is

where $g_q^{-}$$g_q^-$ (resp. $g_q^{+}$$g_q^+$) denotes the inverse of $h_q$$h_q$ over $[0,\frac{q-1}{q}]$$\big[0,\frac{q-1}{q}\big]$ (resp. $[\frac{q-1}{q},1]$$\big[\frac{q-1}{q},1\big]$).

Quantaties ${\tau }^{-}$$\tau^-$ and ${\tau }^{+}$$\tau^+$ give the boundaries between which we expect $N_t(\mathcal{C},\mathbf{s})$$N_t\big(\mathcal{C},\mathbf s\big)$ to be exponentially large.

The average number of solutions of $\mathsf{DP}(n,q,R,\tau )$$\mathsf{DP}(n,q,R,\tau)$ over the input distribution is given by

The expected minimum distance of a code is given by the so-called Gilbert-Varshamov distance, i.e., $t_{GV}(q,n,k)$$t_{GV}(q,n,k)$, which is defined as the largest integer such that

Proof. $\sum _{l=0}^{t_{GV}(q,n,k)}(\genfrac{}{}{0ex}{}{n}{l})(q-1{)}^l/q^{n-k}$$\sum_{l=0}^{t_{GV}(q,n,k)}{n\choose l}(q-1)^l/ q^{n-k}$ is the expected number of codewords in a sphere centered around a codeword, with a radius of $t_{GV}$$t_{GV}$.

The minimum Hamming weight of a code is defined as the smallest Hamming weight of all non-zero codewords.

It can be verified that

1.3 Information Set Decoding Algorithms

Prange's approach: using linearity.

We are looking for some codeword $\mathbf{c}\in \mathcal{C}$$\mathbf c\in\mathcal C$ at distance $t$$t$ from $\mathbf{y}$$\mathbf y$. Since $\mathcal{C}$$\mathcal C$ is a $k$$k$-dimensional subspace in ${\mathbb{F}}_q^n$$\mathbb F_q^n$, there exists some set of positions of size $k$$k$, called an information set, which uniquely determines every codewords.

This idea comes from that in the nullspace ($\mathbf{H}$$\mathbf H$) there are $n-k$$n-k$ free variables, and their positions are fixed.

Let $\mathcal{C}$$\mathcal C$ be an $[n,k]$$[n,k]$-code, and $\mathcal{J}\in \{1,\dots ,n\}$$\mathcal J\in\{1,\dots,n\}$ be of size $k$$k$, then

$\mathcal{J}$$\mathcal J$ is an information set means that positions in $\mathcal{J}$$\mathcal J$ are pivot variables, and those in $\overline{\mathcal{J}}$$\bar{\mathcal J}$ are free variables.

Prange's idea is to pick some ranfom information set, and compute the unique codeword based on those coordinates, and then check whether the calculated codeword has distance $t$$t$ with $\mathbf{y}$$\mathbf y$.

The algorithm:

1. Pick the information set: Let $\mathcal{J}\in \{1,\dots ,n\}$$\mathcal J\in\{1,\dots,n\}$ be a random set of size $k$$k$. If ${\mathbf{H}}_{\overline{\mathcal{J}}}\in {\mathbb{F}}_q^{(n-k)\times (n-k)}$$\mathbf H_{\bar{\mathcal J}}\in\mathbb{F}_q^{(n-k)\times(n-k)}$ is not full-rank, pick another set $\mathcal{J}$$\mathcal J$.

2. Linear Algebra. Calculate ${\mathsf{H}}_{\overline{\mathcal{J}}}^{-1}$$\mathsf H_{\bar{\mathcal J}}^{-1}$.

3. Test step: Pick ${\mathbf{e}}_{\mathcal{J}}=\mathbf{x}\in {\mathbb{F}}_q^k$$\mathbf e_{\mathcal J}=\mathbf x\in\mathbb F_q^k$ according to distribution ${\mathcal{D}}_t$$\mathcal D_t$, and let $\mathbf{e}\in {\mathbb{F}}_q^n$$\mathbf e\in\mathbb F_q^n$ be such that

If $|\mathbf{e}|\ne t$$|\mathbf e|\neq t$ go back to step $1$$1$, otherwise it is a solution.

Picking $\mathbf{x}$$\mathbf x$ in step $3$$3$ is like fixing $k$$k$ unknowns to the value that we want. Suppose we want to find a solution $\mathbf{e}$$\mathbf e$ of small Hamming weight, fixing $\mathbf{x}$$\mathbf x$ to zero vector would be helpful. If we want to find $\mathbf{e}$$\mathbf e$ with large weight, fixing $\mathbf{x}$$\mathbf x$ to non-zero vector will improve the success probability. Therefore, we define the distribution ${\mathcal{D}}_t$$\mathcal D_t$.

${\mathcal{D}}_t$$\mathcal D_t$ is defined as

• If $t<\frac{q-1}{q}(n-k)$$t<\frac{q-1}{q}(n-k)$, ${\mathcal{D}}_t$$\mathcal D_t$ only outputs $\mathbf{0}\in {\mathbb{F}}_q^k$$\mathbf 0\in\mathbb F_q^k$.

• If $t\in (\frac{q-1}{q}(n-k),k+\frac{q-1}{q}(n-k))$$t\in(\frac{q-1}{q}(n-k),k+\frac{q-1}{q}(n-k))$, ${\mathcal{D}}_t$$\mathcal D_t$ outputs uniform vectors of weight $t-\frac{q-1}{q}(n-k)$$t-\frac{q-1}{q}(n-k)$.

• If $t>k+\frac{q-1}{q}(n-k)$$t>k+\frac{q-1}{q}(n-k)$, ${\mathcal{D}}_t$$\mathcal D_t$ outputs uniform vectors of weight $k$$k$.

Rough Analysis:

Assume $\mathbf{s}$$\mathbf s$ is uniformly distributed over ${\mathbb{F}}_q^{n-k}$$\mathbb F_q^{n-k}$, which is equivalent to assuming that $t/n$$t/n$ belongs to $[{\tau }^{-},{\tau }^{+}]$$[\tau^-,\tau^+]$, the expected Hamming weight of $\mathbf{e}$$\mathbf e$ is given by

where $\frac{q-1}{q}(n-k)$$\frac{q-1}{q}(n-k)$ is the expected value of distribution $\mathcal{B}(n-k,\frac{q-1}{q})$$\mathcal B(n-k,\frac{q-1}{q})$.

Since $\mathbf{x}\in {\mathbb{F}}_q^k$$\mathbf x\in\mathbb F_q^k$, we can easily reach any weight in

by carefully choosing $|\mathbf{x}|\in \{0,\dots ,k\}$$|\mathbf x|\in\{0,\dots,k\}$. This explains why $\mathsf{DP}$$\mathsf{DP}$ is easy to solve in this interval.

Precise Analysis:

....

Dumer's approach: collision search

Dumer takes advantage of the birthday paradox to improve the search.

Lemma 3.2.1. Let ${\mathcal{L}}_1$$\mathcal L_1$, ${\mathcal{L}}_2$$\mathcal L_2$ be two lists of $L$$L$ random and independent elements in ${\mathbb{F}}_q^r$$\mathbb F_q^r$, we have

We expect one element in the intersection of the two lists when the list size is $L=\sqrt{q^r}$$L=\sqrt{q^r}$.