Appendix: Code problems

A quick primer to essential notions useful in post-quantum cryptography. While this aims to be precise, it cannot and will not be exhaustive; please check out the wealth of resources available to students of cryptography1 2.

Decoding problem

Informally, a code $C$ maps message vectors $m$ of length $k$ into code words $c$ of a greater length $n$. If transmission over a noisy channel3 modifies received messages $b = c + e$ by a sufficiently small error vector $e$, for appropriately chosen $C$, these errors can be corrected by an efficient decoding algorithm.

Linear code

An $\lbrack n,k,d\rbrack_q$ linear code of length $n$ and dimension $k$ is a subspace $C$ of the vector space $\mathbb {F}_{q}^{n}$, where $\mathbb {F} _{q}$ is the finite field with $q$ elements.

$C$ can be represented by

  • the row space of a generating matrix $G \in \mathbb{F}^{k\times n}$ $$\begin{align*} C &= \lbrace mG \mid m \in \mathbb{F}^k \rbrace\end{align*}$$
  • the kernel space of a parity-check matrix $H \in \mathbb{F}^{(n-k)\times n}$ $$\begin{align*} C &= \lbrace c \mid Hc^T=0, c \in \mathbb{F}^n \rbrace\end{align*}$$

If $q = 2$, the code is called binary.

  • The size of a code is the number of codewords: $$|C|=q^k.$$
  • The Hamming weight of a codeword is the number of its non-zero elements: $$w(c)=\left| \lbrace j \mid c(j)\neq 0 \rbrace \right|.$$
  • The Hamming distance between two codewords is the number of elements in which they differ: $$d(c_1,c_2)=\left|\lbrace j \mid c_1(j) \neq c_2(j) \rbrace \right|.$$
  • The distance of a code is, equivalently:
    • the minimum weight of its non-zero codewords;
    • the distance between the non-zero codeword with smallest Hamming weight, and the zero codeword;
    • the minimum distance between any two distinct codewords $$d(C)=\min \lbrace d(c_1,c_2) \mid c_1,c_2 \in C, c_1 \neq c_2 \rbrace.$$
  • The rows of $G$ are codewords forming a basis of $C$.

Decoding problem

Given

  • $x\in \mathbb{F}^n$,

find the closest codeword $c\in C$ to $x$.

For specific code families and known codes, efficient decoding algorithms exist. In general, the problem is considered hard.

Equivalence: syndrome decoding

Syndrome decoding problem

The syndrome of $b$ is $s=Hb$, for a parity check matrix $H$. Note that $Hb=H(c+e)=He$.

Given $s$, compute $e$ such that $He=s$, and $w(e)$ is sufficiently small.

This is equivalent to the decoding problem because, computed $e$, $c=b-e$.

References

  1. Lange, T. (2019). Code-based cryptography. Executive school on post-quantum cryptography. https://www.hyperelliptic.org/tanja/talks.html. https://pqcschool.org/slides/20190702-exec.pdf ↩︎

  2. Menezes, A. J. (2024). Cryptography 101. https://cryptography101.ca/. ↩︎

  3. Shannon, C. E. (1948). A mathematical theory of communication. The Bell System Technical Journal, 27(3), 379–423. https://doi.org/10.1002/j.1538-7305.1948.tb01338.x ↩︎

Last updated on