# Fully Homomorphic Encryption Part One: A Gentle Intro

## Preface

recently I have taken **CS355 (Topics in Cryptography)** at Stanford. This was a comprehensive examination course on boost crypto topics .

Throughout the 3-month course, the instructors covered diverse topics that span the history of Cryptography, starting from One-way Functions, PRFs all the way to applied cryptosystems such as **MPC, Zero-Knowledge, and PIR**. This was very a great course to take, and I ’ ve surely learned a draw about modern cryptosystems .

In ordain to strengthen my understand of these topics, I ’ ve decided to start a series of blog posts that ( gently ) introduces these cool crypto topics. I ’ ll be summarizing lecture notes and paraphrase them into my own words. Hopefully, it should be an matter to ( and not obscure ) read that helps you understand these topics ampere good .

For the first gear series of posts, I want to talk about **Fully Homomorphic Encryption (FHE)**, a reasonably blistering topic in the security industry.

note that I ’ ll try to make my explanation deoxyadenosine monophosphate childlike as potential, but still make certain that you have some security/cryptography context before continuing…

## What is FHE?

I shall begin the post with a brief insertion of FHE, or **Fully Homomorphic Encryption** .

According to Wikipedia, the definition of Homomorphic Encryption is :

A shape of encoding that allows calculation on ciphertexts, generating an encrypted result which, when decrypted, matches the consequence of the operations as if they had been performed on the plaintext .

The definition is precisely right – Homomorphic Encryption is just the encoding dodge where one can combine encrypted ciphertexts and obtain interesting computations on the original plaintext in an code form without knowing the actual encoding key .

### An Overview of Encryption Schemes

If you are familiar with crypto/security materials, you might know a few park encoding schemes such as AES and RSA. Although there ’ s a difference between symmetrical and asymmetrical encoding schemes, every dodge could be generalized in the stick to shape .

graph LR ; G ( ( KeyGen ) ) -.- pk ( EncKey ) G -.- sk ( DecKey ) pk — > Encryption sk — > Decryption Plaintext — > Encryption Encryption — > Ciphertext Ciphertext — > Decryption Decryption — > Pt2 [ Plaintext ]

From the diagram, we can see the overall typography of an encoding scheme :

- There is a \(KeyGen\) algorithm that generates the key used for both encrypting and decrypting. Notice that in a symmetric scheme both keys are the same, and in an asymmetric scheme the keys are different. (One is called Public Key and the other is called Private Key)
- The \(Encryption\) algorithm applies encryption to a given plaintext using the encryption key. Then it produces the ciphertext, which is the encrypted plaintext.
- The \(Decryption\) algorithm inverts the encryption done on a ciphertext using the decryption key. It restores the ciphertext back to the original plaintext.

There it is. It doesn ’ thyroxine count which algorithm we use ( AES or RSA or something else ), the overall structure is always the same .

In Cryptography, we tend to always write about **properties** of a system after introducing it. Therefore, I should besides talk about it for the sake of completeness .

first, an encoding needs to have **Correctness**. This means that applying decoding on a ciphertext that was the result of applying encoding on some plaintext \ ( pt\ ), using the keys derived from \ ( KeyGen\ ), will always guarantee to result in the same plaintext \ ( pt\ ) as earlier. To capture this sexual intercourse in the speech of probability, we use the following expression :

\[\forall pt \in PT, (k_{enc}, k_{dec}) \leftarrow KeyGen(1^\lambda):\\

Pr[Decryption(k_{dec}, Encryption(k_{enc}, pt)) = pt] = 1\]

\ [ \forall platinum \in PT, ( k_ { enc }, k_ { dec } ) \leftarrow KeyGen ( 1^\lambda ) : \\ Pr [ Decryption ( k_ { declination }, Encryption ( k_ { enc }, platinum ) ) = platinum ] = 1\ ] This means that the **probability** of applying decoding on code ciphertext using the appropriate keys will **always result in the exact same plaintext** as earlier .

The irregular property that we want is **Semantic Security**. I ’ m not going to do the full proof here, but the basic idea is that, given two code ciphertexts \ ( ct_0, ct_1\ ) that corresponds to the encoding of \ ( pt_0, pt_1\ ), one can not distinguish which ciphertext is the encoding of \ ( ct_0\ ). This basically means that the code ciphertext looks random and doesn ’ deoxythymidine monophosphate provide any hint to its original plaintext, consequently ensuring that this outline is secure against listen in .

### Homomorphic Encryption – an unexpected property

If encrypted ciphertexts front just like random garbage to any viewers, does this mean that ciphertexts are wholly useless unless the represent decoding key is give ?

**Both luckily and unluckily, the answer is NO.**

Some encoding schemes actually exhibits an amazing property, where if you obtain the encoding of phone number 1 and number 2, although you have no theme what the original plaintexts are, you can simply add these two ciphertexts together, and obtain the code ciphertext for \ ( 1 + 2 = 3\ ) .

This place is called **Homomorphism** – where the algebraic relationship on plaintexts is besides preserved in the ciphertexts. And encoding schemes that exhibits this trait are therefore referred as **Homomorphic Encryption** .

The exemplar we gave above is just an example of Homomorphic Encryption. namely, this is an exemplify of **Additively Homomorphic Encryption**, where one can freely add ciphertexts together and obtain any analogue combination of the original plaintexts, in code form. Of course, there is besides **Multiplicative Homomorphic Encryption**, the counterpart of AHE. In a MHE scheme, one can freely multiply ciphertexts together and obtain any products of the original plaintexts .

reasonably interesting right ? however, if you think this concept is still a morsel undefined, allow me to provide an example .

#### Example: Anonymous Polling

We all know how poll works – for model, when a group of people want to vote on something ( say whether they want to order Japanese for lunch ), they could start a poll .

In the poll process, everyone will submit their choice of either **going (1)** or **not going (0)** to the host. then the host simply adds everyone ’ sulfur share together, and compares whether this final leave is larger than \ ( 1/2\ ) of the population .

however, the problem with this system is that the poll summons is not anonymous. This means that anyone who can see the datum traffic will know who likes and dislikes japanese food – just by looking at everyone ’ sulfur shares .

We can convert this protocol into an anonymous one well with the help of **Additively Homomorphic Encryption** .

first, the host will run the \ ( KeyGen\ ) algorithm that generates a pair of encoding identify \ ( pk\ ) and decoding key \ ( sk\ ). ( hera, we are using an asymmetrical encoding scheme. ) then the horde distributes the encoding key \ ( pk\ ) to the populace .

nowadays the poll begins. Every player will encrypt their choice ( either 1 or 0 ) under the encoding winder \ ( pk\ ) using the \ ( Encryption\ ) algorithm. then they will all send their ciphertexts to the host .

\[ct_i = Encryption(pk, pt_i):pt_i \in \{0,1\}\]

\ [ ct_i = Encryption ( pk, pt_i ) : pt_i \in \ { 0,1\ } \ ] The horde adds up all the encrypted ciphertexts and forms one ciphertext \ ( \hat { connecticut } \ ). finally the horde then runs the decoding algorithm on the ciphertext and obtain the consequence of the poll .

\[Decryption(sk, \sum_i ct_i) = \sum_i pt_i\]

\ [ Decryption ( sk, \sum_i ct_i ) = \sum_i pt_i\ ] This might not do the full justice to the true office of HE. But this should be a solid example where HE allows us to do some kind of **Secure Delegated Computation** – meaning that we can **delegate** some third party to compute on **secret inputs** we have by encrypting our inputs using HE schemes. The third base party then applies whatever calculation directly on the ciphertext and obtains the consequence ciphertext that is the encoding of the calculation result. ultimately we can decrypt that ciphertext and receive the solution .

### Levels of Homomorphic Encryption

We should be reasonably comfortable with what HE is, and what kind of application it enables us to do. immediately, I want to briefly go over different levels ( or stages ) of HE that will finally lead us to Fully Homomorphic Encryption .

#### Partially Homomorphic Encryption

This is the very foremost stage of HE. If there exists an encoding scheme that is **partially homomorphic**, this means that this scheme is **either additively homomorphic or multiplicatively homomorphic** .

In early words, let ’ s say that in the Delegated Computation example, we would like the distant server to compute some functionality \ ( F\ ). If the HE scheme we choose is lone partially homomorphic ( for exemplar, additively homomorphic ), it means that the alone thing we can do to the ciphertexts is to **obtain an encrypted linear combination of the plaintexts** .

consequently, if we have inputs \ ( ct_0, ct_1\ ) that corresponds to \ ( pt_0, pt_1\ ), this HE system allows us to compute \ ( Enc ( pk, c_0 \cdot pt_0 + c_1 \cdot pt_1 ) \ ) where \ ( c_0, c_1\ ) are some constants. however, with this system it is not possible to compute the product of the two plaintexts \ ( Enc ( pk, pt_0 \cdot pt_1 ) \ ) or anything like that .

To summarize, if the HE outline is just additively homomorphic, then the functionality \ ( F\ ) that the third gear party can compute is **limited to all the functions where their outputs can be expressed as linear combinations of all the inputs** .

This is precisely the same for schemes that are lone **multiplicatively homomorphic** – the functionality \ ( F\ ) then will be limited to all functions where their outputs can be expressed as products of their inputs .

#### Somewhat Homomorphic Encryption

This future category brings us closer to our ideal world. If we say that an HE scheme is **somewhat homomorphic**, this means that the HE dodge is capable of doing both addition and multiplication to the original plaintexts but its capability is heavily limited .

A typical HE dodge example would be – let ’ s say that there is a slightly homomorphic HE outline where you can perform outright additions but only one degree of multiplication to the ciphertext. In such outline, given \ ( ct_0, …, ct_2\ ), we can obtain something like \ ( Enc ( pk, c_0 \cdot pt_0 \cdot pt_1 + pt_2 ) \ ), but we can not go any far to get something like \ ( Enc ( pk, c_0 \cdot pt_0 \cdot pt_1 \cdot pt_2 ) \ ) .

To summarize again, in a reasonably homomorphic scheme, the functionality \ ( F\ ) is **limited to all functions where their outputs can be expressed as linear combinations of plaintexts and one-round products** .

#### Leveled Fully Homomorphic Encryption

now we are getting even closer. If there exists an HE scheme in this category, then we are able to obtain both additions and multiplications to the plaintexts **freely**. There wouldn ’ thyroxine be any limits on how we combine ciphertexts together .

however, the fact that this category is called “ leveled ” is because it introduces an upper complexity limite \ ( L\ ) to the functionality \ ( F\ ). **If the functionality \(F\) can be expressed in a boolean circuit \(C\) such that \(\mid C \mid \le L\) (the depth of the circuit is lower than the bound \(L\)), then it can be evaluated in the leveled FHE scheme.**

A good room to understand a charge outline is to think about that the HE addition and multiplication operations inescapably **introduces some “noise” into the ciphertext**. The noise level increases as the functionality \ ( F\ ) ’ mho boolean racing circuit goes deeper. When \ ( F\ ) ’ randomness complexity approaches \ ( L\ ), finally the **noise blows up and destroys the obsersable state** of the ciphertext and we can no longer recover the original plaintext from the ciphertext anymore .

#### Fully Homomorphic Encryption

ultimately, we arrived at our ultimate finish and the death class – **FHE**. In a FHE outline, we can do arbitrary calculation to the plaintexts by manipulating the ciphertexts. There ’ south no complexity requirements on the functionality \ ( F\ ). besides, a FHE scheme will constantly **gate the ciphertext noise at a manageable threshold** so it doesn ’ t blow up and destroy its discernible submit .

At this stage, we can truly enable **Secure Delegated Computing**. If we can find effective and hardheaded FHE schemes, then we can basically securely offload all of our computations to remote servers **without compromising a single bit of data** !

Before we switch gears, let ’ s give a formal definition of a FHE scheme. The syntax of a proper FHE outline should have **four essential algorithms** :

- \(KeyGen(1^\lambda) \rightarrow sk\): This is the key generation algorithm that produces the secret key. (This might vary depending on if it’s symmetric/asymmetric.)
- \(Enc(sk, \mu \in \{0, 1\}) \rightarrow ct\): This is the bit-wise encryption algorithm that encrypts
**a single bit**into some ciphertext. - \(Dec(sk, ct) \rightarrow \mu\): This is the decryption algorithm that recovers the bit \(\mu\) from the ciphertext.
- \(Eval(F, ct_1, …, ct_l) \rightarrow \hat{ct}\): This is the evaluation algorithm that combines \(l\) ciphertexts together to obtain an encrypted representation of the evaluation of functionality \(F\) under the original \(l\) plaintexts. Here the functionality \(F\) is represented by a boolean circuit on \(l\) inputs.

aside from the **Correctness** and **Semantic Security** properties that every encoding scheme needs to have, we need one more property here : **Compactness**. To be claim, the FHE schema needs to satisfy :

\[\forall F, sk, ct_i \leftarrow Enc(sk, \mu_i):\\

\mid Eval(F, ct_1, …, ct_l) \mid = poly(\lambda)\]

\ [ \forall F, sk, ct_i \leftarrow Enc ( sk, \mu_i ) : \\ \mid Eval ( F, ct_1, …, ct_l ) \mid = poly ( \lambda ) \ ] In other words, the size of the output from the evaluation algorithm needs to be mugwump from the complexity of the functionality \ ( F\ ) .

Why is this property important ? In fact, without this property, I can claim that there exists a super fiddling construction of a absolutely valid FHE scheme. This construction operates as the follow :

- The \(KeyGen, Enc\) algorithms work the same as before.
- When we want to evaluate a set of ciphertexts on functionality \(F\), the \(Eval\) algorithm will simply output ciphertext \(\hat{ct} = (F, ct_1, …, ct_i)\). Notice that we don’t restrict the output size here, so this size can just be as large as the input plus the description of the functionality \(F\).
- Finally, when we want to decrypt the result ciphertext \(\hat{ct}\), the decryption algorithm \(Dec\) simply reads the description of the functionality \(F\), decrypts all the following ciphertexts one-by-one, and then apply \(F\) on the decrypted plaintexts.

now you should get the idea – if we don ’ thymine restrict the end product size of the \ ( Eval\ ) algorithm, then **this scheme can basically just “cheat” by not doing any FHE computation at all**. All it needs to do is to keep appending the description of the functionality \ ( F\ ) into the ciphertext and let whoever decrypts the ciphertext do all the work .

## History of FHE

Before we proceed further into the theoretical state, I ’ d say let ’ s review the brief history of FHE together : )

The concept of FHE was proposed back in the belated 70s. In 1978, **Rivest, Adleman, and Dertouzos** in concert proposed a system that enables secret evaluations of plaintexts by manipulating merely the ciphertext without knowing the decoding key – basically FHE ! besides, this was **only two years after Diffie-Hellman public key exchange** was proposed in 1976 .

After this theme was proposed, the whole academia and industry started searching for the ideal candidate that has this amaze property. unfortunately, people **couldn’t find a worthy scheme** that both satisfies the FHE requirement and is unbroken by cryptanalysis attacks .

It was until 2009 when **Craig Gentry** ( a PhD at Stanford ) made a major breakthrough on FHE. In his PhD thesis, he gave the first structure of a valid FHE scheme based on the premise of **ideal lattices** .

In this dissertation, he besides introduced this novel mind of **bootstrapping**. With this bootstrapping trick, he was able to **turn a leveled FHE scheme into a complete FHE scheme**. The effect of this magic trick is to use some “ black charming ” to somehow **“refresh” and ameliorate the noise level** of a noisy ciphertext so the make noise never blows up when computing arbitrarily-complex functionality \ ( F\ ). We will come spinal column to this in approaching posts .

After Gentry ’ s discovery, the solid diligence started the irregular round of massive search for ideal FHE candidates .

In 2011, Brakerski, Vaikuntanathan proposed a new FHE outline – **a scheme that is based on a lattice-based crypto assumption called Learning With Errors (LWE)**. Later, Brakerski, Gentry, Vaikuntanathan concluded this exploit by formally proposing the **BGV FHE scheme**. This scheme is a level FHE scheme and is based on better lattice assumptions compared to Gentry 09 ’. normally, we refer to the BGV dodge as **the 2nd Generation FHE scheme** .

by and by in 2013, Gentry strikes back again ! Gentry, Sahai, Waters together proposed **the 3rd Generation FHE scheme – the GSW scheme**. The GSW scheme is again based on the LWE wicket crypto presumption ( but slenderly better ) and uses **bootstrapping** to make itself a in truth FHE scheme ( adequate to of evaluating any arbitrary-sized functionality \ ( F\ ) ) .

After 2013, there are a fortune more take after up works in the industry to further improve the BGV and the GSW schemes to make them more hardheaded. **IBM** worked on **the HElib project** which is an open-source FHE library that ’ s based on the BGV scheme. Another group developed **the TFHE project** which is derived from the GSW system. Both projects are actively maintained and optimized for performance and practicality .

There are besides a few attempts to accelerate FHE schemes using hardware. Projects such as **cuFHE** aim to **speed up FHE evaluations using CUDA-based GPU**. There are besides attempts to move this onto **FPGA** and **ASIC** chips to far boost its performance .

And here we are today – **standing on top of a well-paved road that are built by avant-gardes in this field.** The major focus today is placid about performance. With the state-of-the-art technologies, **we are still looking at the unit of seconds when evaluating useful functionalities on a moderately-rigged machine** .

### Worth-Mentioning Attempts at FHE

Before we continue explaining how Gentry ’ randomness FHE schemes work, I think it ’ ll be fun to go over some worth-mentioning attempts at build a FHE scheme .

#### RSA: Multiplicative HE

The identical inaugural campaigner that exhibits some HE properties is RSA .

If you know about RSA already, feel detached to skip this intro section ! But if not, allow me to briefly summarize this algorithm in a few sentences .

**RSA works by exponentiating a message in a cyclic finite field** ( or a group ). It can be broken down into a few steps :

- First, fix a large number \(N = p \cdot q\) where \(p, q\) are large primes.
- Then, find a pair of numbers \(e, d\) such that \(e \cdot d = 1 \text{ mod } \Phi(N)\). Here, \(\Phi(\cdot)\) is the Euler totient function and \(\Phi(N) = (p-1)(q-1)\).
- Set \((N, e)\) to be the public key, and \((N, d)\) to be the private key.
- When encrypting a message \(m\), simply compute \(Enc(pk, m) \rightarrow m^e \text{ mod } N\).
- When decrypting a ciphertext \(c\), simply compute \(Dec(pk, c) \rightarrow c^d \text{ mod } N\).

The **correctness** of this outline is assured by the fact that \ ( ( m^e ) ^d = m \text { mod } N\ ) .

Since the encoding of RSA is merely good exponentiation, we can immediate see some HE properties here. Assume that we have the encoding of message \ ( m_0, m_1\ ) which is \ ( c_0, c_1\ ). We can easily see that :

\[\hat{c} = c_0 \cdot c_1 = m_0^e \cdot m_1^e = (m_0 \cdot m_1)^e\]

\ [ \hat { deoxycytidine monophosphate } = c_0 \cdot c_1 = m_0^e \cdot m_1^e = ( m_0 \cdot m_1 ) ^e\ ] By merely multiplying two ciphertexts together, we equitable **obtained the encryption of the product of the original plaintexts**. indeed, we can tell that **RSA is Multiplicative HE** .

however, we couldn ’ thyroxine find linear HE properties within RSA. Therefore RSA is a **Partially HE** algorithm .

#### Cyclic Group ElGamal: Additive HE

The second candidate that people tried was the ElGamal encoding scheme over cyclic groups .

There are a few long-familiar cyclic groups such as the **Integer Finite Field** and the **Elliptical Curve Group**. however, we don ’ t need to understand these groups are actually implemented in detail .

All we need to know is that there ’ s a group \ ( \mathbb { G } \ ) that contains a fit of elements. Inside of that group there is a **generator** \ ( thousand \in \mathbb { G } \ ) where its exponentiation results in every single component of \ ( \mathbb { G } \ ). If that still sounds a bite fuzzy, precisely try to think that every component \ ( heat content \in \mathbb { G } \ ) can be expressed as the generator raised to some advocate \ ( x\ ) :

\[h = g^x \in \mathbb{G}\]

\ [ hydrogen = g^x \in \mathbb { G } \ ] **ElGamal Encryption** is an encoding scheme that works on top of **generic cyclic groups**. It works as the following :

- First, sample a random element integer \(\alpha\) that is less than the size of \(\mathbb{G}\), and set it to be the private key. We set \(g^\alpha \in \mathbb{G}\) to be the public key.
- When we want to encrypt a message \(m\), we will first sample a random integer \(\beta\), and then we will output ciphertext \(ct = (v = g^\beta, e = pk^\beta \cdot g^m)\).
- Later, when we want to decrypt this ciphertext \((v, e)\), we will first compute \(w \leftarrow v^\alpha = g^{\alpha \beta} = pk^\beta\). Finally, we can obtain the message \(m \leftarrow log_g(e/w)\).

For the sake of simplicity, I ’ ll omit the properties and the proof here .

If we look at this encoding dodge, it ’ s not hard to spot out its HE property. Let ’ s say we have an encoding of \ ( m_0, m_1\ ) which is \ ( ( v_0 = g^ { \beta_0 }, e_0 = pk^ { \beta_0 } \cdot g^m_0 ), ( v_1 = g^ { \beta_1 }, e_1 = pk^ { \beta_1 } \cdot g^m_1 ) \ ). Notice that we can multiply the ciphertexts together :

\[\hat{v} = v_0 \cdot v_1 = g^{\beta_0 + \beta_1}\\

\hat{e} = e_0 \cdot e_1 = pk^{\beta_0 + \beta_1} \cdot g^{m_0 + m_1}\]

\ [ \hat { five } = v_0 \cdot v_1 = g^ { \beta_0 + \beta_1 } \\ \hat { e } = e_0 \cdot e_1 = pk^ { \beta_0 + \beta_1 } \cdot g^ { m_0 + m_1 } \ ] then we can obtain a pair \ ( ( \hat { five }, \hat { e } ) \ ) which is the encoding of the of \ ( m_0 + m_1\ ). We can tell that **ElGamal is Additive HE** .

We haven ’ deoxythymidine monophosphate made much progress in finding the its multiplicative counterpart **just by using normal properties of a cyclic group**. therefore, this outline still lies in the **Partially HE** kingdom .

however, it is possible to get some multiplicative HE, if we assume some **non-standard properties**. Let ’ s take a search at it closely in the adjacent section .

#### Pairing-based Crypto: Somewhat HE

After people discovered how crypto based on groups ( particularly Elliptic Curve Crypto ) work, cryptographers went through an across-the-board research for plausible schemes in thie region. Around 20 years ago, **Pairings** became a fairly hot topic .

**So what is a pairing?** actually, pairing is good a special mathematical process that can be done between group elements. Consider we have two group elements \ ( g^a, g^b \in \mathbb { G } \ ). By applying the copulate operation \ ( einsteinium ( \cdot, \cdot ) \ ), we can obtain a modern group element \ ( g_T^ { ab } \in \mathbb { G } _T\ ) .

\[e(g^a \in \mathbb{G}, g^b \in \mathbb{G}) = g_T^{ab} \in \mathbb{G}_T\]

\ [ einsteinium ( g^a \in \mathbb { G }, g^b \in \mathbb { G } ) = g_T^ { ab } \in \mathbb { G } _T\ ] Notice that the solution of the pair operation is a group chemical element with advocate \ ( a \cdot b\ ) but in a fresh group \ ( \mathbb { G } _T\ ). This property allows us to “ calculate ” the merchandise of two obscure exponents \ ( a\ ) and \ ( b\ ) and can be utilitarian to do many things. For example, if we want to see whether \ ( r = a \cdot b\ ) given \ ( g^r, g^a, g^b\ ), then we can basically check this equality using pairings :

\[e(g^a, g^b) \stackrel{?}{=} e(g^r, g) \iff g_T^{ab} \stackrel{?}{=} g_T^r\]

\ [ vitamin e ( g^a, g^b ) \stackrel { ? } { = } east ( g^r, thousand ) \iff g_T^ { bachelor of arts } \stackrel { ? } { = } g_T^r\ ] There are many more mighty applications of the match operation, such as **the BLS Signature Scheme**. But hera we will focus on the **homomorphic properties** of groups that allows this coupling operation .

From the former section, we already know that ElGamal based on cyclic groups exhibits the **Additive HE** property. here, with the help of pairings, it takes us far – **allowing us to compute multiplications of group element exponents** .

With the avail of pairings, we are capable of computing both addition and multiplication of the exponents in the cyclic group. **However, this scheme is still not FHE**. In fact, it falls in the category of **Somewhat HE** .

The reason behind this is that **the pairing operation is very limited and will only work in some groups**. Let ’ s say that we find a group \ ( \mathbb { G } \ ) that we can do both ElGamal and pairings, it does not guarantee that the target group \ ( \mathbb { G } _T\ ) that the match process takes us to besides has a valid pairing operation .

therefore, the functionality \ ( F\ ) that this outline allows us to homomorphically compute consists of boolean circuits that can be represented by **arbitrary additions plus a few multiplications**. The number of multiplications allowed in the outline depends on the actual group \ ( \mathbb { G } \ ) that we select to begin with .

#### MPC-based HE

The survive worthy attack that I wanted to mention is MPC-based HE .

MPC, or **Secure Multi-Party Computation**, stands for a writing style of problems in Cryptography where we have a group of ( possibly malicious ) parties, each holding their own secret input \ ( x_i\ ), and together they wish to evaluate some functionality \ ( F\ ), and obtain \ ( F ( x_1, …, x_n ) \ ). The requirements of MPC is that all the parties do not want to reveal their private stimulation to anyone, consequently every party in the end should only obtain the evaluation leave of the functionality \ ( F\ ), and nothing else .

**MPC is actually a well-studies problem already**. Starting in the last hundred where **Andrew Yao** proposed his celebrated **Garbled Circuits** approach that leverages the herculean protocol called **Oblivious Transfer**. After that this field blossomed with a wide set of frameworks that allows multiple parties to compute arbitrary functionalities with a fairly virtual complexity .

therefore, we can **easily solve the FHE problem with any MPC protocol**. All we need to do is to have the user with private input be one party of the protocol, and the delegated server to be the early party. The drug user has its private remark \ ( pt_i\ ), and the waiter has its private functionality \ ( F\ ). Assume that the MPC protocol does what it says, then in the end **the user can receive its result, and the server receives nothing** .

Although the FHE problem sounds kind of trivial in the presence of MPC, but there ’ s a **critical issue** with this approach – Since MPC requires interaction between the participating parties, the exploiter has to remain on-line during the action of the protocol. **This kinds of defies the purpose of FHE, because we would want the user to offload computation to a third party, not participate in a computation with it.** consequently, solving the FHE problem while keeping the exploiter ’ s calculation low inactive remains as a valid and open problem !

## Up Next: The GSW FHE Scheme

I think we should all have a pretty firm understand of what FHE is at this moment .

In this series of posts, I ’ ll be going over the full details of **the GSW FHE scheme**, since it ’ s easiest to understand and makes the most commodious set of assumptions. ( besides this was the scheme they taught in class : P )

Read more: Ciphertext indistinguishability – Wikipedia

Since this mail is probably already long enough, I will stop write here. In the next post, I ’ ll start to go over **the fundamental concepts that help us understand how GSW works**. namely I ’ ll be talking about what **Learning With Errors** is and how **Lattice-based Crypto** works .

## Credits

Most message of this station were summarized from my notes for CS355. You can locate all the amazing lecture notes from CS355 here .

Thanks again to Dima, Florian, and Saba for teaching this perplex course !