CS Paper Radar

Dual lattice attacks for bounded distance decoding, revisited

Thijs Laarhoven

cs.CR cs.CGcs.DSmath.MG ·submitted 2026-09-28 02:05 UTC · v1
theory

Abstract

Analyses of dual lattice attacks have often assumed that the individual scores associated with short dual vectors are mutually independent. Laarhoven-Walter used this heuristic to derive explicit trade-offs between the target radius and query time for bounded distance decoding (BDD) with preprocessing. Ducas-Pulles subsequently demonstrated theoretical and experimental failures of this heuristic and proposed an alternative model conditioned on the target norm. In this note, we prove an explicit asymptotic trade-off for (decision-)BDD with preprocessing in the Haar-random lattice model, without heuristic assumptions. Using moment identities of Siegel and Rogers, we analyze cosine scores over complete dual balls and bound both error probabilities when distinguishing targets planted at a prescribed radius from uniform targets modulo the lattice. Optimizing the dual radius yields a trade-off between target radius and query time that matches the asymptotic prediction from the conditional model of Ducas-Pulles.

Comment
7 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Smooth Sailing through Spherical Shells: Provable Random-Lattice Sieving in Time $2^{0.292n}$

cs.CR cs.DSmath.MG ·2026-09-26 ·Emmanouil Doulgerakis, Thijs Laarhoven
similarity 0.60
Abstract · 46 pages

In an attempt to close the gap between the best provable and heuristic algorithms for hard lattice problems, such as the shortest (SVP) and closest vector problem (CVP), we analyze lattice sieving on Haar-random unimodular lattices. With well-chosen modifications to heuristic sieving, we show that the heuristic assumptions are no longer necessary, and we can provably achieve the same complexities as heuristic sieving on Haar-random lattices for various lattice problems. Concretely, with probability $1 - o(1)$ over the randomness of the Haar-random lattice and the algorithmic randomness, we show how to: 1. Solve SVP in time $2^{0.2924\ldots n + o(n)}$ and space $2^{0.2075\ldots n + o(n)}$; 2. Solve CVP for random targets with the same complexities; 3. Produce $2^{0.2075\ldots n + o(n)}$ discrete Gaussian samples at any width with these complexities, up to a $2^{-Ω(n)}$ error in the joint distribution. This improves on the SVP complexities for Haar-random lattices of Pouly-Shen [Eurocrypt, 2026] running in time $2^{0.633n + o(n)}$ and space $2^{0.5n + o(n)}$, as well as the recent worst-case SVP (and average-case CVP) improvements of Gao-Feng-Hu and Hhan [Cryptology ePrint Archive, 2026], both running in time and space $2^{0.5n + o(n)}$ or higher. Similar to standard sieving methods, our approach proceeds through a series of thin spherical shells, starting from a large radius and iteratively combining vectors to obtain vectors from shells with smaller radius. Our main technical contribution is making a series of adjustments to guarantee that for each sieve list generated at each spherical shell, each list vector is independent and uniformly random over all lattice points within this shell. Once this invariant is satisfied, it is a matter of smooth sailing through the spherical shells until we find a solution.

0.26

A General Plotkin-type Bound on Function-Correcting Codes with Wyner-Graham Distance

cs.IT cs.DM ·2026-08-30 ·Kanchana Lokshmii Jagatti, K. Hareesh, N. T. Rashid Ummer, B. Sundar Rajan
similarity 0.60
Abstract · 22 pages; Submitted to a journal

Function correcting codes (FCCs) are designed to protect a specified function evaluation of messages at a higher level than the level of protection for messages, against errors while reducing the redundancy required for reliable communication. FCCs have thus far been studied for channels matched to various distances, including the Hamming and Lee distances. Every function partitions the message space into preimage sets corresponding to its distinct function values. Existing Plotkin-type bounds on the optimal redundancy of FCCs under the studied distances, applicable to arbitrary functions on the message space, depend on the pairwise distances among all the message vectors. This makes these bounds difficult to compute. We derive a general Plotkin-type bound on the optimal redundancy of FCCs under Wyner Graham distances, which include the Hamming and Lee distances as special cases. Our bound depends only on the cardinalities of the preimage sets and the sum of pairwise distances only among vectors within each preimage set. This approach significantly reduces the computations required to evaluate the existing Plotkin-type bounds and yields simplified bounds that are easier to compute for specific functions. We obtain simplified Plotkin-type bound for linear functions under the Wyner-Graham distance. Furthermore, the existing simplified bounds for linear functions under the Hamming and Lee distances are recovered as special cases of the proposed bound. We also obtain simplified bounds for several important classes of functions, including the Hamming weight function, the Hamming weight distribution function, the monomial functions under the Hamming distance, and the modular sum function, the Lee weight function, and the Lee weight distribution function under the Lee distance.

0.11

Provable Subexponential Algorithms for NIST Third-Round Lattice Families

cs.CR ·2026-10-08 ·Yiming Gao, Xuyuan Han, Honggang Hu
hot direction similarity 0.58
Abstract

We give provable classical subexponential algorithms for secret recovery in growing parameter families associated with NIST third-round lattice candidates. For the Kyber/ML-KEM, FrodoKEM, SABER, NTRU LPRime, and Dilithium/ML-DSA families studied here, polynomial moduli and polylogarithmic coefficient scales yield recovery of the short secret component in expected time and space $2^{(1/2+o(1))n/\ln\ln n}$. For noisy or rounded linear relations, we exploit an exact gap in the squared Euclidean norm of a comparison vector defined by each coordinate guess. One Gaussian list suffices to identify every secret coordinate by binary search, without enumerating the others. We establish the required sampling guarantees through new geometric bounds for structured public operators over prime and power of two moduli. The construction builds on the Wagner-style Gaussian sampling framework of Ducas, Engelberts, and Loyer (CRYPTO 2025) and the low-error decision-LWE algorithm of Han, Gao, and Hu (2026). For quotient relations of NTRU type, we develop an affine slice search: fixing coordinates restricts candidate pairs to slices of the public lattice, and their estimated Gaussian masses guide the choice of each next coordinate. In the stated modulus window, Falcon's key generation quality condition supplies the required mass bound. The algorithm then recovers an equivalent signing key with high probability in time and space $2^{O(n/\ln\ln n)}$. The same search recovers the short key core for cyclic NTRU-HPS/HRSS. Together, these results give subexponential algorithms for problem families associated with all seven NIST third-round lattice candidates. Despite the subexponential complexity, our results do not establish a reduction in the concrete security of the currently specified parameter sets.

0.55

On the Kissing Number of Craig's Lattice and Spherical List Decoding

cs.IT ·2026-11-17 ·Léo Ducas, Julian Nowakowski, Ailsa Robertson
theory similarity 0.57
Abstract

Craig's lattices $A_{p-1}^k$ are a family of lattices with large kissing numbers, i.e., relative to their dimension $n = p-1$, they contain a large number of shortest nonzero vectors. Specifically, for small $k = o(\log p / \log \log p)$, a lower bound of Bacher (2015) shows that $A_{p-1}^k$ has a super-polynomial kissing number of $ω(n^k)$. Craig's lattices are therefore attractive candidates for the construction of spherical codes. In this work, we introduce a polynomial-time list decoder for spherical codes obtained from Craig's lattices for angular distance below $45^\circ$. Our second main result shows that Bacher's lower bound is asymptotically tight for $k = o(\log p / \log \log p)$. Finally, we introduce an efficient algorithm for computing the kissing number of $A_{p-1}^k$. Using this algorithm, we compute their kissing number in dimensions up to 521. Based on this data, we pose the open question whether the kissing number of $A_{p-1}^k$ with $k \approx \sqrt{p}$ grows like $e^{Θ(\sqrt{n})}$ in dimension $n=p-1$. Concurrent work by Laarhoven and Kominers as well as Bennett, Hhan, Li and Stephens-Davidowitz proves such a bound for very closely related lattices.

0.15

No Escape from the Quadratic Barrier: Adaptive Attacks on Linear $\ell_2$ Sketches

cs.DS cs.LG ·2026-10-18 ·Edith Cohen, Uri Stemmer
similarity 0.54
Abstract

Linear sketches estimate properties of high-dimensional inputs from a fixed low-dimensional projection. At constant accuracy, randomized Euclidean-norm sketches, notably the Johnson-Lindenstrauss transform, support exponentially many nonadaptive queries in sketch dimension $k$. For adaptive black-box queries, known privacy-based defenses guarantee $\widetildeΩ(k^2)$ and it remained open whether stronger guarantees were possible. Prior attacks used more queries, restricted the responder, or provided weaker failure guarantees. We show that the quadratic guarantee is optimal up to logarithmic factors, even with a computationally unbounded responder that knows the matrix, attack algorithm, history, and query distributions and may change its randomized rule after every query. For every fixed hidden $A\in\mathbb{R}^{k\times n}$ with $n>40k$ and target accuracy $α\in (0,1]$, our black-box attack uses $O(k+α^2k^2\log(2+α^2k))$ queries in $\widetilde{O}(1+α^2k)$ adaptive rounds to force, with constant probability, a round in which a constant fraction of answers have $Ω(α)$ relative error. This fraction can be taken arbitrarily close to one half. Our results clarify the limits of defending a fixed compressive linear representation by adapting the prediction rule.

0.25

Non-asymptotic Sphere-Packing Bounds for Finite-Blocklength Scalar Gaussian Multiple-Access and Broadcast Channels

cs.IT ·2026-11-03 ·Kaixuan Bao, Wei Xu, Xiaohu You
theory similarity 0.54
Abstract · 51 pages, 6 figures

This paper investigates non-asymptotic achievable rate regions of Gaussian multiple-access channels (MACs) and broadcast channels (BCs) in the finite-blocklength regime. By employing a proposed volume-uniform random coding (VURC) codebook that distributes codewords uniformly within an $n$-dimensional power sphere, together with successive interference cancellation (SIC) decoding, we derive a closed-form achievability bound, a scheme-specific lower bound on the average error probability, and a fourth-order asymptotic characterization. The proposed SIC achievability bound admits a simple and analytically interpretable closed-form expression, enabling direct performance evaluation without iterative computation. The structure of the proposed SIC asymptotic bound offers a highly extensible framework, allowing advances in single-user finite-blocklength theory to be systematically incorporated into the multiuser setting. Futhermore, to characterize the performance benefit of joint decoding, we further derive numerical and closed-form achievability bounds for the two-user Gaussian MAC under joint nearest-neighbor (JNN) decoding. Numerical results illustrate the performance differences among the proposed SIC and JNN bounds and existing benchmarks.

0.22

Has MIMO decoding been proved hard from lattice problems?

cs.CR cs.IT ·2026-09-04 ·Yang Li
similarity 0.54
Abstract

Multiple-input multiple-output (MIMO) technology is fundamental to modern wireless communication. Physical layer security seeks to protect transmitted information by exploiting properties of the noisy communication channel. Dean and Goldsmith proposed a polynomial time reduction from lattice problems to MIMO decoding by adapting Regev's reduction for learning with errors (LWE). If valid, this reduction would give physical layer security a strong computational foundation based on the hardness of established lattice problems. Subsequent works presented attacks and counterexamples against the resulting construction, casting doubt on its security but leaving the precise validity and limitations of the underlying reduction incompletely understood. We provide a theoretical examination of the revised reduction and identify the structural features of the LWE reduction that fail to carry over to the non-modular MIMO setting, hence showing that its published proof does not establish the claimed hardness of MIMO decoding. Our results distinguish flaws in the hardness proof from direct attacks on particular parameter choices and clarify what would be required of any attempted repair. We do not rule out physical layer security for MIMO systems in general, but show that the claimed lattice hardness guarantee does not follow from the existing reduction.

0.28

Gaussian mass inequalities for lattices

cs.IT math.NT ·2026-11-15 ·Minjia Shi, Xinguang Dai, Patrick Solé
similarity 0.53
Abstract · 50 pages

The Gaussian mass of a lattice is the evaluation of its theta series at a real nome and is relevant to lattice coding for the wiretap Gaussian channel. The ratio of the Gaussian mass of stable lattices to the Gaussian mass of the integer lattice was conjectured to be $\le 1$ (Regev et al., 2024). Kominers proved this bound recently for lattices obtained by Construction~A from binary self-dual codes. Building on Kominers' bound, we establish corresponding inequalities on average for Construction~$A_4$ lattices obtained from free self-dual quaternary codes and for Construction~$A_6$ lattices obtained from self-dual senary codes. We also prove the strict Gaussian-mass inequality for extremal unimodular lattices of both Type~II and Type~I. The Type~I result uses the Rains--Sloane definition of extremality. Its proof combines a universal theta truncation with an exact inversion of the shadow coefficients, and a Gaussian inequality for translated lattices. In addition, we obtain an averaging bound over the genus of Type~II lattices, and extend the binary Construction~A inequality to Siegel theta series of arbitrary genus, with further quaternary results under conditions on the residue code.

0.39