Dual lattice attacks for bounded distance decoding, revisited
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.
Related
- Iterative Bounded Distance Decoding With 2-Bit Reliability Marker For Product-Like Codes
- Extended States on the Bethe Lattice Revisited
- Insdel Decoding Algorithms for Maximum Distance Separable Codes
- Limits of Weight-Bounded Redundant Checks for Peeling Decoding of Random Regular LDPC Codes
- Achievability of CSS codes performance limits over Pauli channels under separate ML decoding with bounded graphical complexity
BibTeX
@misc{laarhoven2026dual,
title = {{Dual lattice attacks for bounded distance decoding, revisited}},
author = {Thijs Laarhoven},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37483},
eprint = {2609.37483},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37483},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Dual lattice attacks for bounded distance decoding, revisited
AU - Thijs Laarhoven
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.37483
UR - https://arxiv.org/abs/2609.37483
AB - 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.
ER -