The problem of constructing a secure encryption scheme that allows for computation on encrypted data was an open problem for more than 30 years. In 2009, Craig Gentry solved the problem, constructing the first fully homomorphic encryption (FHE) scheme. The challenge of constructing a homomorphic encryption scheme can be divided into three main components: 1) Constructing a decryption algorithm that is a ring homomorphism. 2) Proving CPA security. 3) Managing noise growth of evaluated ciphertexts. This thesis presents a formal mathematical background to FHE and discusses these three components. To compute on ciphertexts, the decryption algorithm needs to be homomorpic with respect to multiplication and addition operation. This means, theoretically, computing and then decrypting is equivalent to decrypting and then computing. Security is proved by reductions and hardness assumptions. The standard hardness assumptions used today is the $\operatorname{LWE}$ and $\operatorname{RLWE}$ assumptions. All existing encryption schemes are based on introducing noise when encrypting. This noise grows with each ciphertext operation and without controlling noise, decryption fails given sufficiently many operations. Gentry showed that a scheme that can evaluate its own decryption circuit can be used to reduce the noise and bootstrapped into a fully homomorphic encryption scheme. / Problemet med att konstruera ett säkert krypteringssystem som tillåter beräkning på krypterad data var ett öppet problem i över 30 år. År 2009 löste Craig Gentry problemet genom att konstruera det första fullt homomorfa krypteringssystemet (FHE). Utmaningen med att konstruera ett homomorft krypteringssystem kan delas upp i tre huvudsakliga komponenter: 1) Konstruktion av en dekrypteringsalgoritm som är en ringhomomorfism. 2) Bevisning av CPA-säkerhet. 3) Hantering av brusökning i utvärderade chiffertexter. Denna uppsats presenterar en formell matematisk bakgrund till FHE och diskuterar dessa tre komponenter. För att göra beräkningar på chiffertexter måste dekrypteringsalgoritmen vara homomorf med avseende på multiplikation och addition. Detta betyder att det, teoretiskt sett, är ekvivalent att beräkna och sedan dekryptera som med att dekryptera och sedan beräkna. Säkerheten bevisas genom reduktioner och svårhetsantaganden. De standardmässiga svårhetsantaganden som används idag är LWE och RLWE-antagandena. Alla befintliga krypteringssystem är baserade på att införa brus vid kryptering. Detta brus ökar vid varje chiffertext operation och i avsaknad av kontroll över bruset kommer dekryptering misslyckas efter tillräckligt många operationer. Gentry visade att ett krypteringssystem som kan utvärdera sin egen dekrypteringskrets kan användas för att minska bruset och omvandlas till ett fullt homomorft krypteringssystem.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-342451 |
| Date | January 2023 |
| Creators | Sanaee, Daniel |
| Publisher | KTH, Matematik (Avd.) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-SCI-GRU ; 2023:401 |
Page generated in 0.0017 seconds