Real cyclo-multiquadratic number fields in lattice-based cryptography

Thumbnail Image

Files

Koistinen_Konsta_2025.pdf (497.76 KB)

URL

Journal Title

Journal ISSN

Volume Title

Sähkötekniikan korkeakoulu | Bachelor's thesis
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

2025-09-16

Department

Major/Subject

Elektroniikka ja sähkötekniikka

Mcode

ELEC3013

Degree programme

Sähkötekniikan kandidaattiohjelma

Language

en

Pages

42

Series

Abstract

Advances in quantum computing threaten the cryptographic protocols protecting private messaging and other sensitive data. Post-quantum cryptography (PQC) aims to address this threat by researching and developing new cryptographic protocols, which are secure even against quantum algorithms. Lattice-based cryptography (LBC) is one of the leading approaches to PQC. LBC studies and develops cryptographic algorithms relying on lattice problems which are believed to be hard even for quantum computers. Two of the most prominent paradigms used in LBC are ring learning with errors (RLWE) and polynomial learning with errors (PLWE), which utilize the structure of rings of integers of algebraic number fields and polynomial rings to build secure and efficient cryptoschemes. This thesis describes the RLWE and PLWE problems and the conditions under which they are equivalent, and reviews known RLWE/PLWE equivalence results. The main result of this thesis is an RLWE/PLWE equivalence proof for a subset of a family of fields we call real cyclo-multiquadratic, defined as the compositum of the maximal real subfield of a cyclotomic field and a multiquadratic field. Equivalence is shown in the case where the conductor of the maximal real subfield of a cyclotomic field is p^s or 2^rp^s for an odd prime p. This is done in order to broaden the family of suitable number fields for potential applications of LBC. Additionally, an improved upper bound for the condition number of the RLWE to PLWE transformation matrix for real quadratic fields is presented. Computational efficiency of these fields will be studied in subsequent work. Research into the distribution of weak instances of real cyclo-multiquadratic fields is suggested.

Kvanttilaskennan kehitys uhkaa kryptografisia protokollia, jotka suojaavat arkaluontoista dataa ja yksityistä viestintää. Kvanttiturvallinen kryptografia (Post-Quantum Cryptography, PQC) pyrkii vastaamaan tähän uhkaan tutkimalla ja kehittämällä uusia kryptografisia protokollia, jotka ovat turvallisia myös kvanttialgoritmeja hyödyntäviä hyökkääjiä vastaan. Yksi johtavista lähestymistavoista kvanttiturvallisen kryptografian kehityksessä on hilakryptografia (Lattice-Based Cryptography, LBC). Hilakryptografia tutkii ja kehittää vaikeisiin hilaongelmiin perustuvia kryptografisia algoritmeja, joiden uskotaan olevan vaikeita murtaa myös kvanttitietokoneilla. Kaksi merkittävimmistä hilakryptografiassa käytetyistä ongelmista ovat kohinainen oppiminen renkaassa (Ring Learning With Errors, RLWE) ja kohinainen oppiminen polynomirenkaassa (Polynomial Learning With Errors, PLWE), jotka hyödyntävät algebrallisten kokonaislukurenkaiden ja polynomirenkaiden rakenteita turvallisten ja suorituskykyisten kryptojärjestelmien rakentamisessa. Tämä opinnäytetyö kuvailee RLWE- ja PLWE-ongelmia ja ehtoja, joiden täyttyessä ne ovat ekvivalentteja, sekä käy läpi tunnettuja RLWE/PLWE-ekvivalenssituloksia. Työn päätulos on todistus RLWE/PLWE-ekvivalenssista osajoukolle niin kutsuttuja reaalisia syklo-multikvadraattisia kuntia, jotka on määritelty syklotomisen kunnan maksimaalisen reaalisen alikunnan ja multikvadraattisen kunnan komposiittikuntana. Ekvivalenssi osoitetaan tapauksessa, jossa syklotomisen kunnan maksimaalisen reaalisen alikunnan johtaja (engl. conductor) on p^s tai 2^rp^s, missä p on pariton alkuluku. Saatu tulos laajentaa mahdollisissa hilakryptografisissa sovelluksissa käytettävissä olevien lukukuntien joukkoa. Opinnäytetyö esittää lisäksi parannetun ylärajan reaalisten kvadraattisten kuntien RLWE-PWLE muunnosmatriisin häiriöalttiudelle. Reaalisten syklo-multikvadraattisten kuntien laskennallista tehokkuutta tutkitaan tulevissa töissä. Lisäksi lisätutkimusta näiden lukukuntien heikkojen instanssien jakaumasta toivotaan.

Description

Supervisor

Turunen, Markus

Thesis advisor

Nchiwo, Rahinatou

Keywords

number theory, cryptography, lattices, ring learning with errors, polynomial learning with errors, condition number

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202509237228

Collections

[kand] Sähkötekniikan korkeakoulu / ELEC