2
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

Error-correction occurs within lattices in roughly two forms:

  1. 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.

  2. 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.

$\endgroup$
1
  • $\begingroup$ Thank you for this excellent response! I am beginning a masters program and want to look at error-correction/fault-detection in hardware for lattice designs. It has been tricky to find resources, this is very helpful for me to start looking into some of these suggestions. $\endgroup$
    – Daftyler
    Apr 15, 2021 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.