Application of Automorphic Forms to Lattice Problems

Abstract

In this paper, we propose a new approach to the study of lattice problems used in cryptography. We specifically focus on module lattices of a fixed rank over some number field. An essential question is the hardness of certain computational problems on such module lattices, as the additional structure may allow exploitation. The fundamental insight is the fact that the collection of those lattices are quotients of algebraic manifolds by arithmetic subgroups. Functions on these spaces are studied in mathematics as part of number theory. In particular, those form a module over the Hecke algebra associated with the general linear group. We use results on these function spaces to define a class of distributions on the space of lattices. Using the Hecke algebra, we define Hecke operators associated with collections of prime ideals of the number field and show a criterion on distributions to converge to the uniform distribution, if the Hecke operators are applied to the chosen distribution. Our approach is motivated by the work of de Boer, Ducas, Pellet-Mary, and Wesolowski (CRYPTO'20) on self-reduction of ideal lattices via Arakelov divisors.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Journal of Mathematical Cryptology
Keywords
lattice-based cryptography module lattices automorphic representations algebraic groups
Contact author(s)
samed duzlu @ ur de
juliane kraemer @ ur de
History
2022-06-14: approved
See all versions
Short URL
https://ia.cr/2022/742

CC BY-NC

BibTeX

@misc{cryptoeprint:2022/742,
author = {Samed Düzlü and Juliane Krämer},
title = {Application of Automorphic Forms to Lattice Problems},
howpublished = {Cryptology ePrint Archive, Paper 2022/742},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/742}},
url = {https://eprint.iacr.org/2022/742}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.