On the smoothing parameter and last minimum of random orthogonal lattices (Q2182065)

Let \(m > n \geq 1\) be integers and let \(X\) be an \(n \times m\) integer matrix. The orthogonal lattice of \(X\) is \[\Lambda^{\perp}(X) := \left\{\boldsymbol v\in\mathbb Z^m : X\boldsymbol v={\boldsymbol 0}\right\},\] which is a sublattice of \(\mathbb Z^n\) of rank \(m-n\). Orthogonal lattices are an important tool in cryptography, used for a variety of purposes from cryptanalysis to the design of cryptographic primitives. The successive minima of \(\Lambda^{\perp}(X)\) are \(1 \leq \lambda_1 \leq \dots \leq \lambda_{m-n}\), defined as \[\lambda_i := \min \left\{ \lambda \in\mathbb R_{>0} : \dim_{\mathbb R} \left( \Lambda^{\perp}(X) \cap \mathbb B_{m-n}(\lambda) \right) \geq i \right\},\] where \(\mathbb B_{m-n}(\lambda)\) is a Euclidean ball of radius \(\lambda\) centered at the origin in the \((m-n)\)-dimensional subspace \(\operatorname{span}_{\mathbb R} \Lambda^{\perp}(X)\) of \(\mathbb R^m\). The smoothing parameter of \(\Lambda^{\perp}(X)\) for a statistical error \(\varepsilon\) is \[\eta_{\varepsilon}(\Lambda^{\perp}(X)) := \min \left\{ s \in\mathbb R_{>0} : \sum_{\boldsymbol x \in \Lambda^{\perp}(X)^*} \exp(-\pi s^2 \|\boldsymbol x\|) \leq 1+\varepsilon\right\},\] where \(\Lambda^{\perp}(X)^*\) is the dual lattice of \(\Lambda^{\perp}(X)\). Successive minima and smoothing parameter are among important invariants of a lattice. The paper under review gives probabilistic upper bounds on the smoothing parameter \(\eta_{\varepsilon}(\Lambda^{\perp}(X))\) and the last successive minimum \(\lambda_{m-n}(\Lambda^{\perp}(X))\) as \(n \to \infty\). This work improves on the previous results of \textit{S. Agrawal} et al. [Lect. Notes Comput. Sci. 8269, 97--116 (2013; Zbl 1320.94059)] and \textit{D. Aggarwal} and \textit{O. Regev} [Chic. J. Theor. Comput. Sci. 2016, Article No. 7, 11 p. (2016; Zbl 1375.60062)] in particular with respect to the parameter range in which these bounds hold.