# What The Dual?

> Source: https://rot256.dev/post/dual-lattice/
> Author: Mathias Hall-Andersen
> Date: 2026-09-03
> Tags: Cryptography, Lattices, Mathematics
> License: CC BY 4.0 — reuse permitted with attribution to Mathias Hall-Andersen (rot256.dev).

Math macros in scope (KaTeX, `\name = expansion`):

```text
\Bas = \mathbf{B}
\Bd = \mathbf{D}
\Bdi = \mathbf{d}_{#1}
\Bi = \mathbf{b}_{#1}
\Bp = \mathbf{B}^\perp
\Bpi = \mathbf{b}^\perp_{#1}
\Div = \mathrm{Div}
\FF = \mathbb{F}
\GG = \mathbb{G}
\Lat = L
\Ldual = L^*
\Lgen = \mathcal{L}(#1)
\Lperp = L^\perp
\NN = \mathbb{N}
\Norm = \mathrm{N}
\PRF = \mathsf{PRF}
\RR = \mathbb{R}
\Sperp = S^\perp
\Sspace = S
\Tr = \mathrm{Tr}
\ZZ = \mathbb{Z}
\adv = \mathscr{A}
\bin = \{0, 1\}
\coloneqq = \mathrel{\mathop:}=
\defeq = \coloneqq
\deg = \text{deg}
\divides =  \ | \ 
\gcd = \text{gcd}
\hash = \mathsf{H}
\img = \text{img}
\ip = \langle #1, #2 \rangle
\ker = \text{ker}
\language = \mathcal{L}
\lc = \mathrm{lc}
\lcm = \text{lcm}
\msg = \mathsf{msg}
\negl = \text{negl}(\lambda)
\nrm = \left\| #1 \right\|
\pk = \mathsf{pk}
\prob = \mathbb{P}
\sample = \overset{\$}{\gets}
\secpar = \lambda
\sig = \sigma
\sign = \mathsf{Sign}
\sk = \mathsf{sk}
\support = \mathrm{Supp}
\tensor = \otimes
\va = \mathbf{a}
\vc = \mathbf{c}
\vcp = \mathbf{c}^\perp
\ve = \mathbf{e}
\verify = \mathsf{Verify}
\vv = \mathbf{v}
\vx = \mathbf{x}
```


The dual lattice is:

$$
\begin{align}
\Ldual &= \left\{ \vx \in \RR^n \mid  \forall \vv \in \Lat. \ip{\vx}{\vv} \in \ZZ \right\} \\
      &= \left\{ \vx \in \RR^n \mid  \forall \vv \in \Lat. \ip{\vx}{\vv} \equiv 0 \pmod{\ZZ} \right\}
\end{align}
$$

Spiritually, it serves a very similar role to the orthogonal complement for linear spaces:

$$
\Sperp = \left\{ \vx \in \RR^n \mid \forall \vv \in \Sspace. \ip{\vx}{\vv} = 0 \right\}
$$

The difference accounts for the "discrete" structure of lattices vs the continuous nature of linear subspaces:

1. Lattices have full rank over $\RR$, hence $\Lperp = \{0\}$ is *uninteresting*.
2. Lattices require *integer* combinations and so we need to capture that *instead* somehow.

## Orthogonal Complements

The reason why the orthogonal complement is useful, is that it in some ways captures "everything outside" the original space $\Sspace$, i.e. the "complement space", everything else.

Because the world is made of everything inside a space, and everything outside of it, with nothing in-between,
$\RR^n = \Sspace \oplus \Sperp$, 
to check that some $\vx \in \RR^n$ is in $\Sspace$, you can check that it has no "component" in $\Sperp$, 
by "measuring" it with $\langle \cdot, \vv \rangle$ for every $\vv$ in the dual $\Sperp$, i.e.
check that it is orthogonal to the orthogonal complement of $\Sspace$:

$$
\vx \in \Sspace \iff \forall \vv \in \Sperp. \ip{\vx}{\vv} = 0
$$

And instead of checking against all of $\Sperp$ you can check against a basis $\Bp$ for $\Sperp$:

$$
\vx \in \Sspace \iff \forall i. \ip{\vx}{\Bpi{i}} = 0
$$

This is advantageous, because, for instance, testing membership of $\Sspace$ otherwise requires Gaussian elimination, which takes cubic time.

Additionally, the complement dual basis also allows checking if you are *almost* in the space $\Sspace$, 
by checking that you are *almost not* in the dual $\Sperp$, i.e.
part of $\vx$ which is in $\Sperp$ is small:
if $\ip{\vx}{\Bpi{i}}$ is small, relative to $\nrm{\vx}, \nrm{\Bpi{i}}$ then you are *almost* orthogonal to every vector in the complement space, which means that if you write $\vx$ in the basis $\Bas, \Bp$ (which span the whole space):

$$
\vx = \Bas \vc + \Bp \vcp \in \RR^n
$$

Then the coefficients $\vcp$ of $\Bp$ are small, so see this:

$$
\ip{\vx}{\Bpi{j}} = \sum_i c_i \ip{\Bi{i}}{\Bpi{j}} + \sum_i c^\perp_i \ip{\Bpi{i}}{\Bpi{j}} = \sum_i c^\perp_i \ip{\Bpi{i}}{\Bpi{j}}
$$

If the complement basis $\Bp$ is also *orthogonal*, i.e. $\langle \Bpi{i}, \Bpi{j} \rangle = 0$ for all $i \neq j$, then:

$$
\ip{\vx}{\Bpi{j}} = c^\perp_j \cdot \ip{\Bpi{j}}{\Bpi{j}} = c^\perp_j \cdot \nrm{\Bpi{j}}^2
$$

So if the vectors in $\Bp$ "small" and (almost) orthogonal, 
then so is $\ve = \Bp \vcp \in \RR^n$,
which means $\vx = \Bas \vc + \ve$ lies *close* to $\Sspace$: 
by the triangle inequality, $\nrm{\Bp \vcp} \leq \sum_i |c^\perp_i| \cdot \nrm{\Bpi{i}}$.

Remember:  this requires $\Bp$ to have short vectors, sounds familiar?

## Dual Lattices

The same intuition applies to the dual of a lattice:

$$
\vx \in \Lat \iff \forall \vv \in \Ldual. \ip{\vv}{\vx} \in \ZZ
$$

Again, you don't need to check all of $\Ldual$, a basis $\Bd$ for $\Ldual$ suffices:

$$
\vx \in \Lat \iff \forall i. \ip{\vx}{\Bdi{i}} \in \ZZ
$$

Again, nice, because it makes checking if you are *in* a lattice easy.
In a vector space, every basis is more/less interchangeable: 
you can simply rescale the basis elements to make them "short" without it affecting the vector space.
That is, famously, not the case for lattices: some bases are nicer than others and you can't easily make a "bad basis" with:

- Large vectors, very "skewed" vectors.

Into a "nice basis" with:

- Short vectors, almost orthogonal vectors.

The good/bad distinction is *exactly* the same that decides if the basis $\Bp$ of the orthogonal complement $\Sperp$ able to test "proximity" to the space $\Sspace$ or not:
there we also needed a "good basis", but producing a "good basis" for a linear space is trivially easy because of its continuous nature (which enables Gaussian elimination).
Completely analogously, the following is true: $\ip{\vx}{\Bdi{i}}$ is *almost* an *integer* (i.e. small in $\RR / \ZZ$) if $\vx$ is *close* to the lattice $\Lat$ 
as long as $\Bd$ has *short vectors*.

To see this, let $\vx \in \Lat$, $\vv \in \Ldual$ and let $\ve$ be "small/short", then:

$$
\ip{\vx + \ve}{\vv} = \ip{\ve}{\vv} + \ip{\vx}{\vv} = \ip{\ve}{\vv} + k
$$

Where $k \in \ZZ$.

By Cauchy–Schwarz, $|\ip{\ve}{\vv}| \leq \nrm{\ve} \cdot \nrm{\vv}$. Now $\ve$ is short, 
i.e. $\vx + \ve$ is close to a lattice point, but when is $\nrm{\vv}$ short for the basis vectors $\vv$ of $\Bd$?

If we have a good basis $\Bas$ for $\Lat$, where the basis elements are *almost* orthogonal, 
i.e. $\ip{\Bi{i}}{\Bi{j}}$ is small whenever $i \neq j$, then *we can also get a good basis* for the dual lattice i.e. every $\nrm{\Bdi{j}}$ is as short as it can be, namely $\approx 1 / \nrm{\Bi{j}}$.

## The Dual Basis

The dual lattice for $\Lgen{\Bas}$ has basis $\Bd$ with the property that:

$$
\ip{\Bdi{i}}{\Bi{j}} = \delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases}
$$

$\implies$:
Anything in $\Lgen{\Bd}$ lies in $\Ldual$:

> Since every $\vv \in \Lgen{\Bas}$ is an integer combination of $\Bas$ and every $\vx \in \Lgen{\Bd}$ is an integer combination of $\Bd$.

$\impliedby$:
Conversely, anything that lies in $\Ldual$ also lies in $\Lgen{\Bd}$: 

> Let $\vx \in \Ldual$, we can write $\vx$ in the basis $\Bd$ since it has full rank over $\RR^n$.
> $$ \vx = \sum_i a_i \cdot \Bdi{i} $$
>
> For some $\va \in \RR^n$. We can then consider:
>
> $$ \ip{\vx}{\Bi{j}} = \sum_i a_i \cdot \ip{\Bdi{i}}{\Bi{j}} = a_j $$
>
> Since $\vx \in \Ldual$, we have $\forall \vv \in \Lgen{\Bas}. \ip{\vv}{\vx} \in \ZZ$, but $\Bi{j}$ is also clearly in $\Lgen{\Bas}$ so by letting $\vv = \Bi{j}$ we see that $a_j$ is actually an integer and *we just wrote $\vx$ as an integer combination of $\Bd$*.

### Finding $\Bd$

The dual basis $\Bd$ pairs one-to-one with the basis elements in $\Bas$: 
if you fix $n-1$ vectors $\Bi{1}, \ldots, \Bi{j-1}, \Bi{j+1}, \ldots, \Bi{n}$ in $\RR^n$, 
and require that a vector $\Bdi{j}$ is orthogonal to all of them, that fixes a unique direction for $\Bdi{j}$, 
the condition $\langle \Bdi{j}, \Bi{j} \rangle = 1$ then fixes the length of $\Bdi{j}$.

So when is $\Bdi{j}$ short?

Observe that $\langle \Bdi{j}, \Bi{j} \rangle = 1$ does not imply that either $\Bdi{j}$ or $\Bi{j}$ are short,
just that $\Bdi{j}$ is *short in the $\Bi{j}$ direction*, in particular, if they *point in very different directions* both may be long, 
while $\langle \Bdi{j}, \Bi{j} \rangle$ stays 1.


`[embedded:fig "dual-height.html"]`



If we subtract from each $\Bi{j}$ its projection onto the span of the other $\Bi{i}$:

$$
\Bi{j}' = \Bi{j} - \mathsf{Proj}_{\Bi{1}, \ldots, \Bi{j-1}, \Bi{j+1}, \ldots, \Bi{n}}\left(\Bi{j}\right)
$$

Then we get $\Bi{j}'$, and we define the "height" of $\Bi{j}$ above the $n-1$ 
dimensional basis $\Bi{1}, \ldots, \Bi{j-1}, \Bi{j+1}, \ldots, \Bi{n}$ as $h_j = \nrm{\Bi{j}'}$.

Since $\Bdi{j}$ is orthogonal to every $\Bi{i}$ with $i \neq j$, it is orthogonal to their entire span,
which leaves exactly one line for it to live on: the line through $\Bi{j}'$.
Hence $\Bdi{j} = \lambda \cdot \Bi{j}'$ for some $\lambda \in \RR$, and since $\Bi{j} - \Bi{j}'$ lies in the span of the other basis vectors it is orthogonal to $\Bi{j}'$:

$$
1 = \ip{\Bdi{j}}{\Bi{j}} = \lambda \cdot \ip{\Bi{j}'}{\Bi{j}} = \lambda \cdot \nrm{\Bi{j}'}^2
$$

Which pins down $\lambda$, and with it the length of $\Bdi{j}$:

$$
\nrm{\Bdi{j}} = \frac{1}{\nrm{\Bi{j}'}} = \frac{1}{h_j}
$$

So $\Bdi{j}$ is short exactly when $\Bi{j}$ is *almost orthogonal* to the other basis vectors: subtracting the projection only ever shortens the vector, so $h_j \leq \nrm{\Bi{j}}$, with equality if and only if $\Bi{j}$ is orthogonal to all the others:

$$
\nrm{\Bdi{j}} \cdot \nrm{\Bi{j}} = \frac{\nrm{\Bi{j}}}{h_j} \geq 1
$$

For a fixed lattice, $\det(\Lat) = \left| \det \Bas \right|$ is the same for every basis and $\det(\Lat) \leq \prod_j \nrm{\Bi{j}}$, so the lengths cannot all be made small.
$\Bas$ is in turn the dual basis of $\Bd$, so the height of $\Bdi{j}$ above the other dual vectors is $1 / \nrm{\Bi{j}}$.

Written with the basis vectors as columns, the inner products $\ip{\Bdi{i}}{\Bi{j}}$ are the entries of $\Bd^\top \Bas$, so we can write the relation between the dual and the original basis as:

$$
\Bd^\top \Bas = I \iff \Bd = \left(\Bas^{-1}\right)^\top
$$

## Bonus: Decode with The Dual

Let $\vx = \vv + \ve$ with $\vv \in \Lat$ and $\ve$ short, then by Cauchy–Schwarz:

$$
\ip{\vx}{\Bdi{j}} = \ip{\vv}{\Bdi{j}} + \ip{\ve}{\Bdi{j}} \quad \text{where} \quad \left| \ip{\ve}{\Bdi{j}} \right| \leq \nrm{\ve} \cdot \nrm{\Bdi{j}} = \frac{\nrm{\ve}}{h_j}
$$

Where the first term is an integer, in fact a very particular one: for $\vv = \sum_i c_i \cdot \Bi{i}$ with $\vc \in \ZZ^n$:

$$
\ip{\vv}{\Bdi{j}} = \ip{\textstyle\sum_i c_i \cdot \Bi{i}}{\Bdi{j}} = \sum_i c_i \cdot \ip{\Bi{i}}{\Bdi{j}} = c_j
$$

Which is the $j$-th coefficient of $\vv$ in the basis $\Bas$.

Hence if $\nrm{\ve} < h_j / 2$ for every $j$, then every $\ip{\vx}{\Bdi{j}}$ lies within $1/2$ of an integer and rounding it to the nearest integer recovers $c_j$, i.e. recovers $\vv$ itself.
This is Babai's rounding algorithm, and the radius it is guaranteed to decode is:

$$
\frac{1}{2} \cdot \min_j h_j = \frac{1}{2 \cdot \max_j \nrm{\Bdi{j}}}
$$