Paper 2015/024 Original: eprint.iacr.org/2015/024 ↗
Non-Abelian Analogs of Lattice Rounding
Abstract
Lattice rounding in Euclidean space can be viewed as finding the nearest point in the orbit of an action by a discrete group, relative to the norm inherited from the ambient space. Using this point of view, we initiate the study of non-abelian analogs of lattice rounding involving matrix groups. In one direction, we give an algorithm for solving a normed word problem when the inputs are random products over a basis set, and give theoretical justification for its success. In another direction, we prove a general inapproximability result which essentially rules out strong approximation algorithms (i.e., whose approximation factors depend only on dimension) analogous to LLL in the general case.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2015-01-12: last updated
- 2015-01-12: published
- Short URL
- https://ia.cr/2015/024
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2015/024,
author = {Evgeni Begelfor and Stephen D. Miller and Ramarathnam Venkatesan},
title = {Non-Abelian Analogs of Lattice Rounding},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/024},
year = {2015},
url = {https://eprint.iacr.org/2015/024}
}