Dense sphere packings and lattice-based cryptography

There are a few authors who have explored dense sphere packings for cryptography. They fall into (roughly) two camps

1. More efficient instantiations of cryptosystems based on the lattice isomorphism problem, and
2. More efficient (LWE-based) encryption.

For the first, see this. The underlying hardness assumption is still rather niche, but it does seem to benefit from instantiations with dense sphere packings. Still, one can't simply appeal to dense sphere packings --- the constructions in the paper need these sphere packings to have some other additional properties.

For the second, there are really quite a number of references. For a short summary, see

1. Cryptographic decoding of the Leech lattice by Alex van Poppelen

2. Wyner-Ziv reconciliation for key exchange based on Ring-LWE by Saliba et al.

3. Optimal Key Consensus in Presence of Noise by Jin and Zhao

there are many more papers, but that should give a taste of what is known in the literature. For the most part, efficient schemes (say NIST-PQC candidates) tend to ignore all of this for several reasons. This is because there are (roughly) two distinct settings for lattice-based encryption

1. KEMs : Here, you need to transmit an $\leq 256$ bit key, and have $n\geq 512$ dimensions to do it with (and are transmitting $\approx n\log_2 q$ "data" bits). As a result, even a relatively poor sphere packing suffices to transmit this (relatively) small quantity of data in a small ciphertext. There can sort of be benefits in very specific circumstances, but it doesn't appear to be anything generic. I think it's also a little less clear how to efficiently build IND-CCA2 KEMs using these cryptosystems (they give IND-CPA KEMs. You could convert these to IND-CPA PKE, then an IND-CCA2 KEM, but this is indirect. There might be smarter transformations known though). There are additionally some weird patent concerns --- see NewHope, which used the semi-dense sphere packing $D_4^{n/4}$ in a key way, and NewHope without Reconciliation, which removed this part of the scheme.

2. FHE: For many FHE schemes, it doesn't suffice to solely encode your message into a good sphere packing. Instead (for GSW-type multiplication at least), this message additionally needs to be a "gadget". It is not clear at all that dense sphere packings can be leveraged to construct dense gadgets (or, similar to the LIP, the sphere packings need to have some separate properties).

This is all to say that

• there are plausibly applications of dense sphere packings to cryptosystems built from the lattice isomorphism problem, and
• there are plausibly applications of dense sphere packings to FHE

but in both settings you really want more from your sphere packing than solely density. There are some caveats, but to first approximation the above is all true.

A separate point is that often cryptographers assume the underlying LWE noise is bounded in the $\ell_\infty$-norm, i.e. they want dense $\ell_\infty$-norm packings, rather than dense $\ell_2$-norm packings. It is relatively straightforward to find these --- the lattice packing defined by $\mathbb{Z}^n$ is "perfect" in the $\ell_\infty$-norm (meaning $\mathbb{Z}^n + [-1/2, 1/2)^n = \mathbb{R}^n$ is a partition, and there is no "wasted space" in the cube packing). (Scalings of) this "dense $\ell_\infty$ lattice" is used all the time in lattice-based cryptography, so one could additionally answer your question as "people do use them, just in the $\ell_\infty$-norm rather than $\ell_2$-norm".

Again separately, one motivation for dense lattices in cryptography could plausibly be found in the preliminaries of papers that cryptographers write giving fast decoding algorithms for dense lattices. If there were obvious cryptographic applications, one would expect them to be described here (as is customary). These papers tend not to describe (cryptographic) applications. See for example

• Peikert's papers list decoding Barnes Sloane lattices, or Barnes Wall lattices,
• Micciancio's bounded distance decoder for barnes wall lattices,
• Ducas' papers solving CVP in $A_p\otimes A_q$ (and its dual), and giving quasi-optimal density lattices that admit efficient BDD algorithms.

All three are well-known lattice-based cryptographers. I don't believe any of the papers talk about cryptographic applications, although I believe the above Wyner-Ziv paper does use the Micciancio Nicolosi BDD algorithm (which may have been improved here). This is to say that there are some small applications, but nothing that makes it into things like standardized KEMs (which uniformly use scalings of $\mathbb{Z}^n$, rather than dense $\ell_2$-norm lattices).