Paper 2021/600

Subfield Algorithms for Ideal- and Module-SVP Based on the Decomposition Group

Christian Porter, Andrew Mendelsohn, and Cong Ling

Abstract

Whilst lattice-based cryptosystems are believed to be resistant to quantum attack, they are often forced to pay for that security with inefficiencies in implementation. This problem is overcome by ring- and module-based schemes such as Ring-LWE or Module-LWE, whose keysize can be reduced by exploiting its algebraic structure, allowing for neater and faster computations. Many rings may be chosen to define such cryptoschemes, but cyclotomic rings, due to their cyclic nature allowing for easy multiplication, are the community standard. However, there is still much uncertainty as to whether this structure may be exploited to an adversary's benefit. In this paper, we show that the decomposition group of a cyclotomic ring of arbitrary conductor may be utilised in order to significantly decrease the dimension of the ideal (or module) lattice required to solve a given instance of SVP. Moreover, we show that there exist a large number of rational primes for which, if the prime ideal factors of an ideal lie over primes of this form, give rise to an ``easy'' instance of SVP. However, it is important to note that this work does not break Ring-LWE or Module-LWE, since the security reduction is from worst case ideal or module SVP to average case Ring-LWE or Module-LWE respectively, and is one way.

Note: Submitted to ASIACRYPT 2021 - pending review.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Ideal LatticeModule LatticeRing-LWEModule-LWEShortest Vector Problem
Contact author(s)
c porter17 @ imperial ac uk
andrew mendelsohn18 @ imperial ac uk
c ling @ imperial ac uk
History
2021-05-26: revised
2021-05-10: received
See all versions
Short URL
https://ia.cr/2021/600
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/600,
      author = {Christian Porter and Andrew Mendelsohn and Cong Ling},
      title = {Subfield Algorithms for Ideal- and Module-SVP Based on the Decomposition Group},
      howpublished = {Cryptology ePrint Archive, Paper 2021/600},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/600}},
      url = {https://eprint.iacr.org/2021/600}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.