Cryptographic Algorithms on Lattices: Randomized Nearest Plane by Klein

Oct 2025

MathPQC

1. Randomized Nearest Plane by Klein

1.1 Babai’s Nearest Plane

Babai’s nearest plane is a deterministic algorithm that approximately solves the Closest Vector Problem on a given lattice. It can be formulated in different ways. In this note we present a formulation such that its randomized modification can be conveniently analyzed.

Let $B \in \mathbb{R}^{n \times m}$ be a matrix of full row rank. Then we denote the $n$-dimensional lattice generated by the rows of $B$ by $\mathcal{L}(B) \subset \mathbb{R}^m$.

Let $B = L\tilde B$ be the Gram–Schmidt Orthogonalization of $B$. The iterative nature of the Gram–Schmidt process ensures that for every $1 \le j \le n$, we have

\[ \mathrm{span}[b_1, \ldots, b_j] = \mathrm{span}[\tilde b_1, \ldots, \tilde b_j] := S_j. \]

The input to Babai’s algorithm is a vector $t \in \mathbb{R}^n$ such that the point $tB$ is the target point. The algorithm ensures the integer vector $z$ such that the lattice point $zB$ is “close” to the target $tB$. The algorithm is defined recursively as follows.

  1. We first solve for the last coordinate $z_n$ of $z$ as if the problem was in 1 dimension, that is, in the space $\mathrm{span}[b_n]$. Then $z_n = \lfloor t_n \rceil$.
  2. We identify $tB - z_nb_n$ as what remains to be solved. If we find a close lattice vector to this, we also solve our original problem of finding a close lattice vector to $t$. Crucial now is the step of reducing the dimension. We project this vector to the space $S_{n-1}$, and solve the smaller problem. Let $P$ be the orthoprojection onto $S_{n-1}$. A little calculation will show that $P(b_n) = b_n - \tilde b_n$. Using this, and the GSO factor $L$ of $B$, we compute
    \[ \begin{aligned} P(tB - z_nb_n) &= P\big([tB - t_nb_n] + [t_n - z_n]b_n\big) \\ &= tB - t_nb_n + (t_n - z_n)(b_n - \tilde b_n) \\ &= tB - z_nb_n + (z_n - t_n)\tilde b_n \\ &= tB - z_nb_n + (z_n - t_n)\Big[b_n + \sum_{j=1}^{n-1} L_{nj}^{-1} b_j\Big] \\ &= \sum_{j=1}^{n-1} \Big[t_j + (z_n - t_n) L_{nj}^{-1}\Big] b_j. \end{aligned} \]
  3. We feed the above as the target vector coordinates $\big[t_j + (z_n - t_n)L_{nj}^{-1}\big]_j$ to solve Babai's algorithm in the $(n-1)$-dimensional space $S_{n-1}$ and proceed recursively.

We formally summarize the steps in Algorithm 1. The algorithm implicitly has access to the matrices $B$ and $\tilde B$.

Algorithm 1 — $\mathrm{NP}(n, t)$

Require: target vector coordinates $t \in \mathbb{R}^n$
Ensure: $z \in \mathbb{Z}^n$, such that the lattice vector $z_1b_1 + \cdots + z_nb_n$ is close to the target vector $t_1b_1 + \cdots + t_nb_n$.

  1. $z_n = \lfloor t_n \rceil$
  2. $t' = \big[t_j + (z_n - t_n)L_{nj}^{-1}\big]_{j=1}^{n-1}$
  3. $z' = \mathrm{NP}(n-1, t')$
  4. return $(z', z_n)$
Theorem 1 — Quality of Babai's Algorithm

The vector $z$ produced by Algorithm 1 satisfies \[ (t-z)B \in \Big[-\tfrac12, \tfrac12\Big]^n \tilde B. \]

Proof. We proceed by induction on the dimension $n$. When $n=1$ the algorithm just outputs $\lfloor t_1 \rceil$, and satisfies the requirement. Now follow the definitions of $t'$ and $z'$ in Algorithm 1 and observe that

\[ \begin{aligned} tB - zB &= \big[tB - z_nb_n - P(tB - z_nb_n)\big] + \Big[P(tB - z_nb_n) - (z_1'b_1 + \cdots + z_{n-1}'b_{n-1})\Big] \\ &= (z_n - t_n)\tilde b_n + \Big[(t_1' - z_1')b_1 + \cdots + (z_{n-1}' + t_{n-1}')b_{n-1}\Big] \\ &\in (\lfloor t_n \rceil - t_n)\tilde b_n + \Big[-\tfrac12,\tfrac12\Big]\tilde b_1 + \cdots + \Big[-\tfrac12,\tfrac12\Big]\tilde b_{n-1} \\ &\in \Big[-\tfrac12,\tfrac12\Big]^n \tilde B, \end{aligned} \]

where the second equality follows from equation (1), and the next inclusion follows from the inductive hypothesis. $\blacksquare$

Corollary 1.1

The vector $z$ produced by Algorithm 1 satisfies \[ \lVert (t-z)B \rVert \le \frac{\sqrt n}{2} \max_j \lVert \tilde b_j \rVert. \]

1.2 Gaussian Sampler on Integers

Before defining the Randomized Nearest Plane algorithm of Klein, we first introduce a sampler for integers. Essentially, given an integer $t$, we modify the nearest integer function $\lfloor t \rceil$ to a randomized variant $\lceil \dot t \rfloor$. The random variable $\lceil \dot t \rfloor$ takes values in the integers in a discrete gaussian fashion. That is, the probability that $\lceil \dot t \rfloor$ takes the integer value $z$ is inversely proportional to $e^{\lvert t-z\rvert^2}$. Let us define this formally.

For a fixed $t \in \mathbb{Z}$, the random variable $\lceil \dot t \rfloor_c$ parametrized by $c$ takes values in $\mathbb{Z}$ such that

\[ \Pr\big(\lceil \dot t \rfloor_c = z\big) = s_c \cdot e^{-c\lvert t-z\rvert^2}, \]

where $s_c$ is the suitable normalizer computed as $s_c = \sum_{z=-\infty}^{\infty} e^{-c\lvert t-z\rvert^2}$.

Before proceeding further we must show that the above sum converges for the parameter $c$ in a meaningful range. Let $t = \lfloor t \rfloor + {t}$ be the decomposition of $t$ as the sum of its integer part and fractional part. Then we rewrite the above sum as

\[ s_c = \sum_{z=-\infty}^{\infty} e^{-c\lvert t-z\rvert^2} = \sum_{z=-\infty}^{\infty} e^{-c\lvert (t+\lfloor t\rfloor)+\{t\}-z\rvert^2} = \sum_{z=-\infty}^{\infty} e^{-c\lvert \{t\}-z\rvert^2} \tag{2} \]

Consider the scaled Gaussian curve $e^{-c({t}-x)^2}$. We know that the area under this curve is $\sqrt{\pi/c}$. Now draw rectangles under the curve whose horizontal sides are of unit length across the $x$-axis starting from ${t}$ and continuing on either side. The height of the rectangles is the value of the Gaussian function at the lesser of the two bottom corners. An illustration is displayed in Figure 1.

A Gaussian curve with unit-width rectangles inscribed under it, approximating the sum by an integral.
Figure 1: Approximating the sum by integral.

Observe that the combined area of the rectangles is precisely the sum in equation (2) barring the term $z=0$. But it is also true that the combined area of the rectangles is smaller than the area under the Gaussian curve. This gives us the relation

\[ s_c \le \sqrt{\frac{\pi}{c}} + e^{-c\{t\}^2} \le \sqrt{\frac{\pi}{c}} + e^{-c} < \sqrt{\frac{2\pi}{c}}. \tag{3} \]

Since the Gaussian curve is well defined for $c > 0$, the above approximation for $s$ is also valid in this parameter range.

2. Klein’s Randomized Variant of Babai’s Algorithm

Klein’s variant of the Nearest Plane algorithm relies on Klein’s sampler of integers as described in section 1.2. The modification is straightforward. The $\lfloor t_n \rceil$ in step 1 of Babai’s algorithm (1.1) is replaced by $\lceil \dot t_n \rfloor_{c_n}$ for a suitable parameter choice $c_n$. Klein’s choice for this is $c_n = A\lVert \tilde b_n \rVert^2$, where $A$ is passed as a parameter to the algorithm, which can be determined as per preferences in the final analysis.

We formally state this as Algorithm 2.

Algorithm 2 — $\mathrm{NP}^*_A(n, t)$

Require: target vector coordinates $t \in \mathbb{R}^n$
Ensure: A random $z \in \mathbb{Z}^n$ with probability $e^{-A\lVert (t_1-z_1)b_1 + \cdots + (t_n-z_n)b_n \rVert^2} \prod_{j=1}^n \frac{1}{s_{c_j}}$.

  1. $c_n = A\lVert \tilde b_n \rVert^2$
  2. $z_n = \lceil \dot t_n \rfloor_{c_n}$
  3. $t' = \big[t_j + (z_n - t_n)L_{nj}^{-1}\big]_{j=1}^{n-1}$
  4. $z' = \mathrm{NP}(n-1, t')$
  5. return $(z', z_n)$
Lemma 1 — Correctness of Algorithm 2

Let $t, B$ be as in Algorithm 2. Let $Z$ be the random variable $\mathrm{NP}^*_A(n,t)$. Then \[ \Pr(Z=z) = e^{-A\lVert tB - zB \rVert^2} \prod_{j=1}^n \frac{1}{s_{c_j}}. \]

Proof. We proceed by induction on the dimension $n$. In 1 dimension $Z$ is exactly the sampler on integers. For $n$ dimensions, let $Z'$ be the random variable of the recursive call $\mathrm{NP}^*_A(n-1, t')$. Then

\[ \begin{aligned} \Pr(Z=z \mid Z_n = z_n) &= \Pr(Z' = z - z_ne_n) \\ &= e^{-A\lVert [tB - z_nb_n + (z_n-t_n)\tilde b_n] - [zB - z_nb_n] \rVert^2} \prod_{j=1}^{n-1} \frac{1}{s_{c_j}} \\ &= e^{-A\lVert (t-z)B + (z_n-t_n)\tilde b_n \rVert^2} \prod_{j=1}^{n-1} \frac{1}{s_{c_j}}. \end{aligned} \]

Here the second equality follows from the equality about $t'$ in (1). Now, we un-condition the above probability as

\[ \begin{aligned} \Pr(Z=z) &= \Pr(Z=z \mid Z_n=z_n)\Pr(Z_n=z_n) \\ &= e^{-A\lVert (t-z)B + (z_n-t_n)\tilde b_n \rVert^2} \left(\prod_{j=1}^{n-1} \frac{1}{s_{c_j}}\right) e^{-A\lVert \tilde b_n \rVert^2 \lvert t_n - z_n \rvert^2} \left(\frac{1}{s_{c_n}}\right) \\ &= e^{-A\lVert tB - zB \rVert^2} \prod_{j=1}^n \frac{1}{s_{c_j}}, \end{aligned} \]

where for the last equality, we note that the quantities in the norm in the exponent of the first term are in the space $S_{n-1}$ which is orthogonal to $\tilde b_n$. Therefore, while clubbing the exponents together the sum of the norms can be equated to the norm of the sum. $\blacksquare$

Choice of parameter $A$. Let $\Sigma_A = (2AB B^T)^{-1}$. Then we calculate

\[ \frac{1}{\det \Sigma_A} = (2A)^n \det(L\tilde B \tilde B^TL^T) = (2A)^n \det(\tilde B \tilde B^T) = (2A)^n \prod_{j=1}^n \lVert \tilde b_j \rVert^2, \]

where the second-last equality follows from the observation that $L$ is a unit lower triangular matrix, and therefore both $L$ and $L^T$ have unit determinant. We use this observation along with equation (3) to obtain

\[ \prod_{j=1}^n \frac{1}{s_{c_j}} \ge \prod_{j=1}^n \frac{\sqrt{c_j}}{3} = \left(\sqrt{\frac{A}{2\pi}}\right)^n \prod_{j=1}^n \lVert \tilde b_j \rVert = \frac{2^{n/2}}{(\sqrt{2\pi})^n \sqrt{\det \Sigma_A}}. \]

Now using this identification with Lemma 1 we note that

\[ \Pr(Z=z) = \Omega\big(2^{n/2} \cdot \mathcal{N}_{t,\Sigma_A}(z)\big) \]

where $\mathcal{N}_{t,\Sigma_A}$ is the multivariate Gaussian distribution centered at $t$ with covariance matrix $\Sigma_A$. One notes further here that the effect of increasing the parameter $A$ is making the Gaussian surface steeper, thereby increasing the likelihood of sampling lattice points nearer to $t$. However, steepening the Gaussian surface too much can push all nearby lattice points to the outer low-probability zones.