Privacy Preserving Computation with Fully Homomorphic Encryption

Abstract

Målet med denne oppgaven er å vise hvordan personvernbevarende beregninger kan oppnås gjennom homomorf kryptering. Oppgaven utforsker BGV-kryptosystemet og hvordan det kan brukes til å beregne vilkårlige polynomer på data. Vi etablerer forskjellige måter å representere data i klartekstrommet på og hvordan funksjoner i datarommet kan emuleres i klartekstrommet. Vi utforsker SIMD-strukturen til klartekstrommet og viser hvordan vi kan implementere forskjellige lineær algebra-teknikker. En rigorøs definisjon av personvernbevarende blir gitt, og vi beviser at vår personvernbevarende modell tilfredsstiller IND-CPA sikkerhet. Til slutt viser vi potensialet med homomorf kryptering ved å se på noen statistiske beregningsmetoder og maskinlæringsmetoder, og diskuterer hvordan vi kan implementere dem homomorft. Vi gir en oversikt over hvor grensene går for de eksisterene sikre implementasjonene av BGV-kryptosystemet.

The goal of this thesis is to show how privacy preserving computation can be achieved through homomorphic encryption. The thesis explores the BGV cryptosystem and how it can be used to compute arbitrary polynomials on data. We establish different ways of encoding real world data into the plaintext space and how functions in the data space can be emulated in the plaintext space. We explore the SIMD structure of the plaintext space and show how we can implement different linear algebra algorithms. A rigorous definition of privacy preserving is given and we prove that our privacy preserving model satisfies IND-CPA security. Lastly we show the potential of homomorphic encryption by looking at some statistical and machine learning techniques and discuss how we can implement them homomorphically. We give an overview of the limits of the current secure implementations of the BGV cryptosystem.