Paper 2025/1448
Dimension-Reducing Algorithms for Quaternion Ideal-SVP
, Imperial College LondonAbstract
We study the approximate Hermite Shortest Vector Problem (HSVP) in ideal lattices in orders of quaternion algebras. For one- and two-sided ideals respectively, we show that for almost all ideals we may solve HSVP in a sublattice of dimension at most one half (respectively, one quarter) of the original lattice dimension, with only small losses in the approximation factor. For two-sided ideals in a cryptographically-relevant family of maximal orders, we obtain approximation factors independent of the algebraic norm of the ideal. For one-sided ideals, we obtain a similar result for a large and natural family of ideal lattices. Finally, we turn our mathematical results into algorithms, and give an unconditional quantum polynomial time algorithm to solve HSVP in ideals of maximal orders of quaternion algebras, given an oracle for HSVP in ideals of maximal orders of number fields, in lower dimension.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2026
- Keywords
- shortest vector problemquaternionsideal latticeslattice isomorphism
- Contact author(s)
-
c ling @ imperial ac uk
am3518 @ ic ac uk
c porter17 @ imperial ac uk - History
- 2026-02-13: last of 2 revisions
- 2025-08-09: received
- See all versions
- Short URL
- https://ia.cr/2025/1448
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1448,
author = {Cong Ling and Andrew Mendelsohn and Christian Porter},
title = {Dimension-Reducing Algorithms for Quaternion Ideal-{SVP}},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1448},
year = {2025},
url = {https://eprint.iacr.org/2025/1448}
}
