Algebraic methods for secure coded computing

Thumbnail Image

Files

isbn9789526427607.pdf (773.07 KB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Doctoral thesis (article-based) | Defence date: 2025-10-10
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

Department

Matematiikan ja systeemianalyysin laitos
Department of Mathematics and Systems Analysis

Major/Subject

Mcode

Degree programme

Language

en

Pages

83 + app. 78

Series

Aalto University publication series Doctoral Theses, 195/2025

Abstract

Outsourcing a large computational task to a distributed computational system, such as a cloud computing platform, is a great way to handle the ever-growing datasets in machine learning, scientific computing and other applications. However, utilizing such resources introduces problems with unreliable nodes, variable response times, and a lack of trust. The benefits of parallelization and distribution can be outweighed by unreliability, while data confidentiality may make it impossible to hand data over to third parties. Secure coded computing has been developed to mitigate these problems using coding-theoretic and cryptographic tools. The primary focus of this thesis is on two particular protocols: secure distributed matrix multiplication (SDMM) and private information retrieval (PIR). We utilize methods from algebraic coding theory, namely algebraic geometry (AG) codes. These codes are constructed by taking evaluation vectors of rational functions on an algebraic curve. Due to their algebraic structure, AG codes behave nicely under coordinatewise multiplication, which makes them ideal for constructing coding schemes for bilinear functions in SDMM and PIR. Security is provided by so called secret sharing, which can be studied through linear coset codes, where codewords are cosets instead of vectors. This thesis presents a unifying framework for linear SDMM schemes and derives lower bounds on the number of computing nodes required. We also construct state-of-the-art SDMM and secure PIR schemes using AG codes over hyperelliptic curves by generalizing methods based on Reed–Solomon codes. Many applications in scientific computing and data science require computations with real numbers instead of finite fields which are used in algebraic coding theory. Hence, we also study secret sharing and secure computing over the field of real numbers and analyze its numerical stability.

Suuren laskennallisen tehtävän ulkoistaminen hajautettuun laskentajärjestelmään, kuten pilvilaskenta-alustaan, on erinomainen tapa käsitellä jatkuvasti kasvavia aineistoja koneoppimisessa, tieteellisessä laskennassa sekä muissa sovelluksissa. Tällaisten resurssien hyödyntäminen tuo kuitenkin mukanaan ongelmia epäluotettavien palvelimien, vaihtelevien vasteaikojen ja luottamuksen puutteen vuoksi. Rinnakkaisuuden ja hajauttamisen edut voivat jäädä epäluotettavuuden varjoon, samalla kun tietojen luottamuksellisuus voi tehdä tietojen luovuttamisen kolmansille osapuolille mahdottomaksi. Turvallinen koodattu laskenta on kehitetty lievittämään näitä ongelmia käyttämällä koodausteoreettisia ja kryptografisia työkaluja. Tämän väitöskirjan pääpaino on kahdessa protokollassa: turvallisessa hajautetussa matriisikertolaskussa (engl. secure distributed matrix multiplication, SDMM) ja yksityisessä tiedonhaussa (engl. private information retrieval, PIR). Tässä väitöskirjassa hyödynnetään menetelmiä algebrallisesta koodausteoriasta, erityisesti algebrallisen geometrian (AG) koodeja, jotka muodostetaan rationaalifunktioiden arvoista algebrallisen käyrän pisteillä. Algebrallisen rakenteensa ansiosta AG-koodit käyttäytyvät hyvin koordinaatittaisen kertolaskun suhteen, mikä tekee niistä ihanteellisia koodausjärjestelmien rakentamiseen bilineaarisille funktioille SDMM- ja PIR-menetelmissä. Turvallisuus varmistetaan niin kutsutulla salaisella jakamisella, jota voidaan tutkia lineaaristen sivuluokkakoodien avulla, joissa koodisanat ovat vektoreiden sijaan sivuluokkia. Tämä väitöskirja esittelee yhdistävän kehyksen lineaarisille SDMM-menetelmille ja johtaa alarajat tarvittavien laskentapalvelimien määrälle. Määrittelemme myös uusia SDMM- ja turvallisia PIRmenetelmiä käyttämällä AG-koodeja hyperelliptisten käyrien yli ja yleistämällä Reed–Solomonkoodeihin perustuvia menetelmiä. Monet sovellukset tieteellisessä laskennassa ja datatieteessä vaativat laskentaa reaaliluvuilla äärellisten kuntien sijaan, joita käytetään algebrallisessa koodausteoriassa. Siksi tutkimme lisäksi salaista jakamista ja turvallista laskentaa reaalilukujen kunnan yli ja analysoimme sen numeerista vakautta.

Description

Supervising professor

Hollanti, Camilla, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland

Thesis advisor

Hollanti, Camilla, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland

Keywords

secure coded computing, algebraic geometry codes, secret sharing, private information, retrieval, secure distributed matrix multiplication, turvallinen koodattu laskenta, algebrallisen geometrian koodit, salainen jakaminen, yksityinen tiedonhaku, turvallinen hajautettu matriisikertolasku

Other note

Englanninkielisen tiivistelmän otsikossa virhe.
An error in the title of the English abstract.

Parts

  • [Publication 1]: Okko Makkonen and Camilla Hollanti. General Framework for Linear Secure Distributed Matrix Multiplication with Byzantine Servers. IEEE Transactions on Information Theory, vol. 70, no. 6, pp. 3864–3877, June 2024.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202406054132
    DOI: 10.1109/TIT.2024.3359355 View at publisher
  • [Publication 2]: Okko Makkonen. Flexible Field Sizes in Secure Distributed Matrix Multiplication via Efficient Interference Cancellation. In 2024 IEEE International Symposium on Information Theory (ISIT), Athens, Greece, pp. 2562–2567, July 2024.
    DOI: 10.1109/ISIT57864.2024.10619357 View at publisher
  • [Publication 3]: Okko Makkonen, Elif Saçıkara, and Camilla Hollanti. Algebraic Geometry Codes for Secure Distributed Matrix Multiplication. IEEE Transactions on Information Theory, vol. 71, no. 4, pp. 2373–2382, April 2025.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202506044257
    DOI: 10.1109/TIT.2025.3535091 View at publisher
  • [Publication 4]: Okko Makkonen and Camilla Hollanti. Analog Secure Distributed Matrix Multiplication. Submitted to IEEE Transactions on Information Theory, August 2025.
    DOI: 10.48550/arXiv.2508.17479 View at publisher
  • [Publication 5]: Okko Makkonen, David A. Karpuk, and Camilla Hollanti. Secret Sharing for Secure and Private Information Retrieval: A Construction Using Algebraic Geometry Codes. Submitted to IEEE Transactions on Information Theory, March 2025.
    DOI: 10.48550/arXiv.2408.00542 View at publisher

Citation

Permanent link to this item

https://urn.fi/URN:ISBN:978-952-64-2760-7

Collections

[diss] Perustieteiden korkeakoulu / SCI