Chebyshev Polynomials Over Finite Fields in Lattice-Based Cryptography

No Thumbnail Available

Files

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.

Date

2024-04-09

Department

Major/Subject

Matematiikka ja systeemitieteet

Mcode

SCI3029

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

en

Pages

53

Series

Abstract

In this work we aim to investigate the feasibility of the use of Chebyshev polynomials of the first and the second kind in lattice-based cryptography protocols. This is achieved by using earlier results regarding the use of this family of polynomials in algebraically structured variants of the so-called learning with errors (LWE) problem. Moreover, we test an attack against selected instances of these problems by considering number fields attached to them, evaluating minimal polynomials at small values and observing whether they vanish over the relevant finite prime fields. If this condition is satisfied, the attack might succeed. We employ Sections 1, 2 and 3 to introduce relevant concepts in field theory, Galois theory, algebraic number theory and cryptography whereas Section 4 is used to explain and introduce the Chebyshev polynomials in the context of lattice-based cryptography. Finally, we present our findings and numerical results in Sections 5 and 6. Our results demonstrate that the use of Chebyshev polynomials can give rise to insecure instantiations of algebraically structured LWE problems, which is due to the aforementioned number theoretic attack and a considerable number of vanishing minimal polynomials over relevant finite prime fields. However, we are only able to give a lower bound for relevant parameters in which the attack is unconditionally successful. Consequently, we cannot calculate the exact probabilities for this attack to be successful under our lower bound. Our numerical examples do not reach this lower bound and tightening it would require further results.

Description

Supervisor

Hollanti, Camilla

Thesis advisor

Blanco-Chacón, Iván

Keywords

cryptography, lattice-based cryptography, learning with errors, Chebyshev polynomials, number theory, algebraic number theory

Other note

Citation