Back to search

University of South Florida

Recovering generators of principal ideals using subfield structure and applications to cryptography

Abstract

dc:description

The 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 × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/10463

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Youmans, William. Recovering generators of principal ideals using subfield structure and applications to cryptography. Dissertation thesis, University of South Florida, 2023. https://digitalcommons.usf.edu/etd/10463