Real cyclo-multiquadratic number fields in lattice-based cryptography

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.