Chebyshev Polynomials Over Finite Fields in Lattice-Based Cryptography
No Thumbnail Available
Files
Ahola_Joonas_2024.pdf (1 MB) (opens in new window)
Aalto login required (access for Aalto Staff only).
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.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
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, CamillaThesis advisor
Blanco-Chacón, IvánKeywords
cryptography, lattice-based cryptography, learning with errors, Chebyshev polynomials, number theory, algebraic number theory