Paper 2023/1735
Exploiting the Symmetry of $\mathbb{Z}^n$: Randomization and the Automorphism Problem
Abstract
$\mathbb{Z}^n$ is one of the simplest types of lattices, but the computational problems on its rotations, such as $\mathbb{Z}$SVP and $\mathbb{Z}$LIP, have been of great interest in cryptography. Recent advances have been made in building cryptographic primitives based on these problems, as well as in developing new algorithms for solving them. However, the theoretical complexity of $\mathbb{Z}$SVP and $\mathbb{Z}$LIP are still not well understood. In this work, we study the problems on rotations of $\mathbb{Z}^n$ by exploiting the symmetry property. We introduce a randomization framework that can be roughly viewed as `applying random automorphisms’ to the output of an oracle, without accessing the automorphism group. Using this framework, we obtain new reduction results for rotations of $\mathbb{Z}^n$. First, we present a reduction from $\mathbb{Z}$LIP to $\mathbb{Z}$SCVP. Here $\mathbb{Z}$SCVP is the problem of finding the shortest characteristic vectors, which is a special case of CVP where the target vector is a deep hole of the lattice. Moreover, we prove a reduction from $\mathbb{Z}$SVP to $\gamma$$\mathbb{Z}$SVP for any constant $\gamma = O(1)$ in the same dimension, which implies that $\mathbb{Z}$SVP is as hard as its approximate version for any constant approximation factor. Second, we investigate the problem of finding a nontrivial automorphism for a given lattice, which is called LAP. Specifically, we use the randomization framework to show that $\mathbb{Z}$LAP is as hard as $\mathbb{Z}$LIP. We note that our result can be viewed as a $\mathbb{Z}^n$analogue of Lenstra and Silverberg's result in [JoC2017], but with a different assumption: they assume the $G$lattice structure, while we assume the access to an oracle that outputs a nontrivial automorphism.
Note: extended version
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2023
 Keywords
 ZLIPLattice automorphismRandomized reductionGradient descent
 Contact author(s)

jkj21 @ mails tsinghua edu cn
anyuwang @ tsinghua edu cn
luohengyi23 @ mails ucas ac cn
lgx22 @ mails tsinghua edu cn
yuyang @ tsinghua edu cn
xiaoyunwang @ tsinghua edu cn  History
 20231113: approved
 20231109: received
 See all versions
 Short URL
 https://ia.cr/2023/1735
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1735, author = {Kaijie Jiang and Anyu Wang and Hengyi Luo and Guoxiao Liu and Yang Yu and Xiaoyun Wang}, title = {Exploiting the Symmetry of $\mathbb{Z}^n$: Randomization and the Automorphism Problem}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1735}, year = {2023}, url = {https://eprint.iacr.org/2023/1735} }