University of South Florida
Recovering generators of principal ideals using subfield structure and applications to cryptography
Abstract
dc:descriptionThe principal ideal problem (PIP) is the problem of determining if a given ideal of a number field is principal, and if so, of finding a generator.Algorithms for resolving the PIP can be efficiently adapted to solve many hard problems in algebraic number theory, such as the computation of the class group, unit group, or $S$-unit group of a number field. The PIP is also connected to the search for approximate short vectors, known as the γ-Shortest Vector Problem (γ-SVP), in certain structured lattices called ideal lattices, which are prevalent in cryptography. We present an algorithm for resolving the PIP that leverages the norm relation techniques of Biasse, Fieker, Hofmann, and Page to efficiently reduce the PIP in a non-cyclic number field to instances of the PIP in subfields. Our algorithm is focused on practical performance and we demonstrate its viability by resolving instances of the PIP in cyclotomic fields of degree up to 1800. We further adapt this technique to the problem of finding mildly short vectors, solutions to γ-SVP for γ = 2\tilde{O}(\sqrt{n}), in an ideal lattice of a cyclotomic field. Cramer, Ducas, and Wesolowski show that the search for mildly short vectors in such a lattice reduces efficiently to the PIP on a quantum computer. We describe a classical variant of this reduction that applies to non-cyclic cyclotomic fields. We show that there are infinite families of cyclotomic fields where this approach achieves a superpolynomial improvement over the state of the art.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy (Ph.D.)
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Mathematics and Statistics
- Grantor
- University of South Florida
- Year dc:date
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Youmans, William
- Contributors dc:contributor
-
- Jean-Francois Biasse, Ph.D.
- Dmytro Savchuk, Ph.D.
- Natasa Jonoska, Ph.D.
- Giacomo Micheli, Ph.D.
- Attila Yavuz, Ph.D.
Subjects
dc:subject × 6Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.usf.edu/etd/10463