# 1. Code-based Cryptography: Lecture Notes

## 1.1 Introduction

A **linear code**

To represent an **generator matrix**

Conversely, any matrix

A

subspaceof a vector space is a nonempty subset that satisfies the requirements for avector space: Linear combinations stay in the subspace. (i) If we add any vectorand $x$ in the subspace, then $y$ is in the subspace. $x+y$ (ii) If we multiply any vector

in the subspace by any scalar $x$ , then $c$ is in the subspace. $cx$

The **dual code** of an

Its generator matrix is the **parity-check matrix** of

The linear code

Conversely, any matrix

Solutions to

form the $\mathbf{Gx}=\mathbf{0}$ nullspaceof. $\mathbf{G}$ Elimination simplifies a system of linear equations without changing the solutions, i.e., if

is row reduced to $\mathbf{G}$ , then ${\mathbf{G}}^{\prime}=[{\mathbf{I}}_{\mathbf{k}}|\mathbf{A}]$ and $\mathbf{Gx}=\mathbf{0}$ give the same solutions ${\mathbf{G}}^{\prime}\mathbf{x}=\mathbf{0}$ . Therefore, the nullspace of $\mathbf{x}$ is the same as the nullspace of $\mathbf{G}$ . ${\mathbf{G}}^{\prime}$ Since

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

Left multiplication by an invertible matrix does not change the code (

If

Let **syndrome** of

**Syndrome Decoding:** Given

Any solver of syndrome decoding can be turned in polynomial time into an algorithm solving

Noisy Codeword Decoding:Given

of rank $\mathbf{G}\in {\mathbb{F}}_{q}^{k\times n}$ , $k$ , $\mathbf{y}\in {\mathbb{F}}_{q}^{n}$ , find $t\in \{0,\dots ,n\}$ with weight $\mathbf{e}$ such that $t$ for some $\mathbf{y}=\mathbf{mG}+\mathbf{e}$ . $\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$ __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

Decoding Problem is a problem parametrized by

## 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

The introduction of the function

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

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)$ provides a flexible framework for $p(n)$ capturing these variations.

As all the parameters are functions of **asymptotic** results will always hold for

The is defined as

It is equal to the entropy of a random variable

It can be verified that

Let

Asymptotically, we have

Probability

Defining

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

**Lemma 2.2.3.** Given

This lemma gives the probability over all random codes that a fixed non-zero word

*Proof.* We assume

Since

**Question:** given a random code __codewords__ __error vectors__

Let **number of solutions** of

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

A trivial solution to solve

If there is only one solution

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

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

It is therefore crucial to know the value of **running time** of our algorithm.

**Solution:**

The expectation of

where

where

Quantaties

The average number of solutions of

The **expected minimum distance** of a code is given by the so-called Gilbert-Varshamov distance, i.e.,

*Proof.*

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 **information set**, which uniquely determines every codewords.

This idea comes from that in the nullspace (

) there are $\mathbf{H}$ free variables, and their positions are fixed. $n-k$

Let

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

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

**The algorithm:**

Pick the information set: Let

be a random set of size$\mathcal{J}\in \{1,\dots ,n\}$ . If$k$ is not full-rank, pick another set${\mathbf{H}}_{\overline{\mathcal{J}}}\in {\mathbb{F}}_{q}^{(n-k)\times (n-k)}$ .$\mathcal{J}$ Linear Algebra. Calculate

.${\mathsf{H}}_{\overline{\mathcal{J}}}^{-1}$ Test step: Pick

according to distribution${\mathbf{e}}_{\mathcal{J}}=\mathbf{x}\in {\mathbb{F}}_{q}^{k}$ , and let${\mathcal{D}}_{t}$ be such that$\mathbf{e}\in {\mathbb{F}}_{q}^{n}$

If

Picking

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

If

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

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

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

**Rough Analysis:**

Assume

where

Since __any weight__ in

by carefully choosing

**Precise Analysis:**

....

### Dumer's approach: collision search

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

**Lemma 3.2.1.** Let