###
**Holzer, Patrick** (2017)

*Recovering Short Generators of Principal Fractional Ideals in Cyclotomic Fields of Conductor p^\alpha q^\beta. *

Technische Universität Darmstadt

Master Thesis, Primary publication

## Abstract

Some recent cryptographic schemes rely on the hardness of finding a shortest generator of a principal (fractional) ideal in an algebraic number field $K$ in the logarithmic embedding with some guaranteed small generator, given some $\mathbb{Z}$-basis of the principal ideal. This problem can be split into two parts. First, recover some arbitrary generator of the ideal, which is known as the principal ideal problem (PIP). Second, transform this generator into some shortest generator.

The first part is known to be solvable in polynomial time on quantum computers for cyclotomic fields of prime-power conductor and for arbitrary number fields under the generalized Riemann hypothesis, see Campbell, Biasse et al. The second part is known to be solvable in polynomial time on classical computers for cyclotomic number fields of prime-power conductor, see Cramer, Ducert Peikert and Regev.

In this work we entirely focus on the second task and extend the work of Cramer, Ducas, Peikert and Regev to cyclotomic fields $K=\Q(\xi_m)$ of conductor $m=p^\alpha q^\beta$, where $p,q$ are distinct odd primes. Their algorithmic approach mainly relies on the fact that there is a well suited basis of the group of cyclotomic units which are a subgroup of $\OK^\times=\mathbb{Z}[\xi_m]^\times$ with small enough finite index. We consider the group generated by these elements in the case that $m=p^\alpha q^\beta$ and introduce a new notion for odd prime pairs $(p,q)$, named generator prime pairs, which provides a criterion to check whether the index of this subgroup in $\OK^\times$ is finite or not. We prove, that this basis is well suited to recover some shortest generator of a principal ideal in quantum polynomial time in the finite case, i.e., if $m=p^\alpha q^\beta$ for some generator prime pair $(p,q)$ with sufficiently large $\alpha,\beta \in \mathbb{n}$ with bounded distance.

Further, we consider the approximate ideal shortest vector problem in cyclotomic fields $\Q(\xi_m)$, where the task is to find short elements in arbitrary ideals $\mathfrak{a}$ in $\OK$ in the Minkowski embedding. In our second main contribution, we generalize the results of Cramer and argue, that one can efficiently solve the ideal shortest vector problem with an approximation factor $\exp(O(\sqrt{m}))$ in cyclotomic fields of conductor $m=p^\alpha q^\beta$ on quantum computers, if $(p,q)$ is an $(\alpha,\beta)$-generator prime pair.

Item Type: | Master Thesis |
---|---|

Erschienen: | 2017 |

Creators: | Holzer, Patrick |

Type of entry: | Primary publication |

Title: | Recovering Short Generators of Principal Fractional Ideals in Cyclotomic Fields of Conductor p^\alpha q^\beta |

Language: | English |

Referees: | Buchmann, Prof. Dr. Johannes ; Wunderer, Thomas |

Date: | 2017 |

Place of Publication: | Darmstadt |

Refereed: | March 2017 |

URL / URN: | http://tuprints.ulb.tu-darmstadt.de/6155 |

Abstract: | Some recent cryptographic schemes rely on the hardness of finding a shortest generator of a principal (fractional) ideal in an algebraic number field $K$ in the logarithmic embedding with some guaranteed small generator, given some $\mathbb{Z}$-basis of the principal ideal. This problem can be split into two parts. First, recover some arbitrary generator of the ideal, which is known as the principal ideal problem (PIP). Second, transform this generator into some shortest generator. The first part is known to be solvable in polynomial time on quantum computers for cyclotomic fields of prime-power conductor and for arbitrary number fields under the generalized Riemann hypothesis, see Campbell, Biasse et al. The second part is known to be solvable in polynomial time on classical computers for cyclotomic number fields of prime-power conductor, see Cramer, Ducert Peikert and Regev. In this work we entirely focus on the second task and extend the work of Cramer, Ducas, Peikert and Regev to cyclotomic fields $K=\Q(\xi_m)$ of conductor $m=p^\alpha q^\beta$, where $p,q$ are distinct odd primes. Their algorithmic approach mainly relies on the fact that there is a well suited basis of the group of cyclotomic units which are a subgroup of $\OK^\times=\mathbb{Z}[\xi_m]^\times$ with small enough finite index. We consider the group generated by these elements in the case that $m=p^\alpha q^\beta$ and introduce a new notion for odd prime pairs $(p,q)$, named generator prime pairs, which provides a criterion to check whether the index of this subgroup in $\OK^\times$ is finite or not. We prove, that this basis is well suited to recover some shortest generator of a principal ideal in quantum polynomial time in the finite case, i.e., if $m=p^\alpha q^\beta$ for some generator prime pair $(p,q)$ with sufficiently large $\alpha,\beta \in \mathbb{n}$ with bounded distance. Further, we consider the approximate ideal shortest vector problem in cyclotomic fields $\Q(\xi_m)$, where the task is to find short elements in arbitrary ideals $\mathfrak{a}$ in $\OK$ in the Minkowski embedding. In our second main contribution, we generalize the results of Cramer and argue, that one can efficiently solve the ideal shortest vector problem with an approximation factor $\exp(O(\sqrt{m}))$ in cyclotomic fields of conductor $m=p^\alpha q^\beta$ on quantum computers, if $(p,q)$ is an $(\alpha,\beta)$-generator prime pair. |

URN: | urn:nbn:de:tuda-tuprints-61555 |

Divisions: | 04 Department of Mathematics > Algebra 04 Department of Mathematics > Algebra > Automorphic Forms, Number Theory, Algebraic Geometry 04 Department of Mathematics |

Date Deposited: | 23 Apr 2017 19:55 |

Last Modified: | 23 Apr 2017 19:55 |

PPN: | |

Referees: | Buchmann, Prof. Dr. Johannes ; Wunderer, Thomas |

Refereed / Verteidigung / mdl. Prüfung: | March 2017 |

Export: | |

Suche nach Titel in: | TUfind oder in Google |

Send an inquiry |

**Options (only for editors)**

Show editorial Details |