Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I am by no means an expert in the PQC field and am just trying to self teach myself about it. I was hoping to look into error correcting in lattice. I want learn about error or fault detection as it applies to lattice, but I am unable to find many resources.
Does something like CRC apply to a lattice? Or are there lattice specific mechanisms?
I know this is a little broad, just looking for some insights.
Error-correction occurs within lattices in roughly two forms:
Binary error-correction is sometimes used within lattice-based protocols, although not all of the time. There are certain issues with doing this, namely that the errors in LWE-based encryption are not naturally of small hamming weight, while binary error-correction corrects errors of small hamming weight. Some analysis used a certain independence heuristic which ended up being invalid, leading to improper settings of parameters/attacks on NIST PQC candidates.
Error-correction with "lattice codes", or more properly codes for the Additive White Gaussian Noise (AWGN) channel. These are often called "sphere packings", and are used to correct the LWE error $e$ in an LWE sample $(A, As + e)$, which is of small $\ell_p$ norm (generally for $p = \infty$).
Lattice cryptography very often uses this second type of code. Basic examples are in Regev-style encryption, where one encrypts $m\in\{0,1\}$ via $(A, As + e + (q/2)m)$. Here, one can view $(q/2)m$ as the value of $m$ being encoded under the lattice code corresponding to $(q/2)\mathbb{Z}^n$. There are other more complex lattice codes used --- the Micciancio-Piekert "gadget matrix" $G$ can be seen as using the lattice $\bigoplus_i\Lambda_q(g^t)$, where $g = (1,2,\dots,2^{k-1})$. Van Poppelen's masters thesis looked into the potential benefits of using (direct sums of) the Leech lattice $\Lambda_{24}$.
There are more things you can do with lattice codes, but I hope the above is useful in understanding the "error correction" that most commonly occurs within lattice cryptography.
