Friday, May 22, 2015

52 Things: Number 33: How does the Bellcore attack work against RSA with CRT?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this blog post we discuss a possible attack on RSA-CRT. 

Note: This follows the paper by Dan Boneh, Richard A. DeMillo, Richard J. Lipton: On the importance of Eliminating Errors in Cryptographic Computations.

In the 52 Things: Number 21 blog post, it discusses how the Chinese Remainder theorem method can improve the performance of RSA. Here we show that if the hardware (or software) used to implement RSA produces errors or faults from time to time, then an attack can be used to break RSA with high probability. 

RSA[1] was one of the first practical public key cryptosystems used for secure data transmission. Developed by Rivest, Shamir and Adleman in 1977, it is based on the difficulty of factoring the product of two large prime numbers. Direct attacks on RSA involve trying to factorise the modulus. Boneh, DeMillo and Lipton wanted to find an attack on RSA that avoids directly factoring the modulus. They show that erroneous cryptographic values jeopardise security by enabling an attacker to expose secret information. We are going to look specifically at the attack on RSA-CRT.

First, a brief description of RSA. Formally, let $N=pq$ be the product of two large prime numbers each $\frac{n}{2}$ bits long. If we have a message $x \in \mathbb{Z}_N$, we encrypt the message using a secret signing exponent $d$ by $S=x^d \textrm{ mod } N$. The modular exponentiation of $x$ is computationally expensive. For a more efficient implementation we can first compute $S_1 = x^d \textrm{ mod } p$ and $S_2 = x^d \textrm{ mod } q$, then use the Chinese Remainder Theorem (CRT)[2] to construct the signature $S = x^d \textrm{ mod } N$. 

It can be shown that this RSA with CRT scheme is particularly susceptible to software or hardware errors. If we contain two signatures of the same message. One signature being the correct one, the other the faulty signature. Once again, letting $x \in \mathbb{Z}_N$ be the message and $S = x^d \textrm{ mod } N$ being the correct signature. Then $\hat{S}$ be a faulty signature. From above, $S$ is computed by first finding $S_1$ and $S_2$. Similarly, $\hat{S}$ is computed by first finding $\hat{S}_1$ and $\hat{S}_2$, suppose that the error occurred while computing only one of $\hat{S_1}, \hat{S_2}$. If we assume the fault occurred while computing $\hat{S}_1$ but no error occurred during the computation of $\hat{S}_2$, i.e. $S_1 \neq \hat{S}_1 \textrm{ mod } p$ and $\hat{S}_2 = S_2$ This means that $S = \hat{S} \textrm{ mod } q$ but $S \neq \hat{S} \textrm{ mod }p$. Therefore, $$ \textrm{gcd}(S - \hat{S}, N) = q $$ so N can be factored easily. This shows that with one faulty signature, the modulus N can be easily factored.

[1] -
[2] -

One-Round Cat Exchange

Suppose two parties have generated public/private keypairs and published their public keys. Non-interactive key exchange (NIKE) allows them to agree on a shared secret key without interaction.

This is the internet, so let's demonstrate with cats. The private key is represented by a male cat, and the corresponding public key by a female cat of the same colour. Alice generates a keypair and publishes her public key, and Bob does the same.

Now Alice can obtain Bob's public key, and combine it with her private key to generate a shared secret key. Alice's private key is a male cat, and Bob's public key is a female cat, so they make a shared secret kitten. As anyone with basic knowledge of feline genetics knows, two cats of different colours will have offspring in the colour of the parent whose colour has the largest hex value, with spots in the colour of the parent with the smaller hex value.

Bob used his private key and Alice's public key to generate the shared key. These kittens look the same, so Alice and Bob now have a shared secret key. Great! However this process always generates the same key, which is a problem if the key is compromised. One-round key exchange (ORKE) can help. At the cost of one round of interaction, Alice and Bob can have a whole litter of kittens.

In this week's study group Bin presented a generic construction of ORKE from NIKE published by Bergsma, Jager and Schwenk at PKC this year. The construction makes use of a deterministic strong signature scheme and a PRF.

The users generate NIKE keypairs as before, but now also generate signing keys.

To generate a shared session key, they generate temporary NIKE keypairs, and sign the temporary public key.

After receiving the other party's signed temporary public key, they can compute a shared secret key. First they check the signature is valid, and then they begin computing four NIKE keys using each possible permutation of temporary and long-term NIKE keys available.

Though Alice and Bob compute the second and third keys in a different order, this doesn't matter since the final key is computed through the commutative XOR operation. In fact the session key isn't just the XOR of the four NIKE keys - the NIKE keys are used as keys for a PRF evaluated at a common point derived from the long-term public keys, and the outputs XORed - but why let details clutter cartoon cats. The scheme is secure in a version of the enhanced CK security model for key exchange, and is standard model secure if instantiated with standard model secure components. The proof is quite straightfoward, ignoring the complexities of the security model itself, and you can check it out on eprint.

Friday, May 15, 2015

52 Things: Number 32: difference between game-based and simulation-based security definitions

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know to do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this post we outline the difference between a game-based and a simulation-based security definition.

In a game-based security definition the security is defined, unsurprisingly, by a game. This game revolves around some generic primitive and is usually played by a challenger and an adversary, where the challenger poses a challenge to the adversary with a certain 'goal' in mind. The adversary may further have access to some number of oracles and it is said to 'win' if it achieves its goal, which usually means it needs to provide some 'correct' output depending on the challenge. The advantage of an adversary is defined as a number that roughly corresponds to how much 'better' the adversary can do at the game than a trivial adversary that just guesses its output. E.g., if the adversary needs to output the value of an uniformly random bit, its advantage corresponds to how much better it can do than a success probability of one half. Now, a cryptographic scheme is said to satisfy this security definition if and only if all 'efficient' adversaries cannot achieve a substantial advantage when the generic primitive is instantiated by the scheme.

Informally, one may think of the challenger as a legitimate user that wants to use a cryptographic scheme and of the adversary as the bad guy that wants to achieve something against the wishes of the legitimate user, where this 'achievement' corresponds to the goal of the adversary. Generally, the challenger will have access to all secret parameters (think secret or signing key), whereas the adversary only has access to some oracles (think public hash functions or public key encryption) plus whatever it is given by the challenger during the game (think public parameters and the challenge).

Security proofs in this paradigm include two important concepts. To link security to computationally hard problems they use reductions, which lead to a statement of the following form: 'if an adversary wins the game with non-negligible advantage, it is possible to construct an algorithm that uses the adversary as a subroutine to solve some hard problem efficiently.' The other concept is game hopping through a sequence of games. Here, one takes the event of an adversary winning the game and relates it to events in a sequence of different games. Each subsequent game is close to the previous one in the sense that the adversary cannot tell the difference between two subsequent games unless it can solve some hard problem or alternatively something happens that has a negligible probability of happening.

The previous five blog posts in this series contain four game-based security definitions and one example of a game-based proof with a sequence of games, so we will not consider any specific examples here.

In a simulation-based security definition, security is defined by the existence of a simulator and some ideal 'functionality'. Consider a cryptographic scheme in the real world and now imagine how you would like this scheme to behave in an ideal world. E.g., in a voting scheme, it would be nice to have a trusted third party that has secure channels to all voters, takes in all the votes via these secure channels, and publishes the result and nothing else. A cryptographic scheme is now secure if, for any adversary against this scheme in the real world, there exists a simulator that provides the same output as the adversary in the real world, while interacting with the ideal 'functionality' in the ideal world. This means that any 'attack' possible in the real world can also be applied to the ideal functionality in the ideal world. Conversely, if the ideal functionality resists attacks in the ideal world, the real scheme resists these attacks in the real world as well.

The notion first appears in a paper by Goldreich, Micali, and Widgerson, who show that you can play any game (which is some joint computation by multiple parties) such that at any step of the game, any group of less than half the players know nothing more than they would in an ideal execution of the game with a trusted party. More recently, the notion of simulation-based security appeared in the paper introducing Universal Composability by Ran Canetti. It is mostly used in settings of multi-party computation.

So what is the difference? In the game-based approach, each notion of security has its own game. If this notion correctly captures or models the real world attributes you would like your system to have, then you are done. If your scheme needs to satisfy various notions, you will need to play games for each one. However, there is a known hierarchy in some cases, e.g., IND-CCA security implying IND-CPA security.

Conversely, in the simulation-based approach, the security is modeled by the ideal functionality. Conceptually, your schemes will be secure from attacks that do not break the ideal functionality. This means that different security notions are captured by this model.

For more reading, you can find good discussions on the crypto StackExchange here and here.

Friday, May 8, 2015

52 Things: Number 31: Game Hopping Proof

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this post we give an example of a proof that uses the 'game hopping' technique.

Note, this blog post is based on Section 3.3 of 'An Introduction to Provable Security' by Douglas Stebila, downloadable via this link.

Recall the definition of IND-CCA security for a public key encryption scheme, described by Ana here. If one removes the decryption oracle from the adversary, we obtain the IND-CPA (indistinguishability under chosen-plaintext attacks) security notion. Note that removing the encryption oracle does not change the adversary's view since it holds the public key and can therefore produce its own encryptions.

In an earlier blog post, we described the Decisional Diffie-Hellman (DDH) problem. In this post, we are going to use a technique called 'game hopping' to show that the ElGamal encryption scheme is IND-CPA secure if DDH is hard. Loosely speaking, we will transform the IND-CPA game against ElGamal into a game against DDH and show that an adversary's advantage in the first game cannot be more than their advantage in the second. So if their advantage in the second game is negligible (which is the assumption that DDH is hard), the advantage in the first game must also be negligible (showing that the encryption scheme is IND-CPA secure).

Firstly, let's describe the ElGamal scheme. We work in a cyclic group $G$ of prime order $q$ with generator $g$. (Implicitly the selection of the group depends on a security parameter $\lambda$ and when we say that a quantity is negligible, we mean a negligible function of $\lambda$, but we'll omit those details here.) Plaintexts and ciphertexts are group elements. The private key is a secret exponent $x \in \mathbb{Z}_q$ and the public key is $X = g^x$. To encrypt a message $M \in G$, one selects an exponent $y \in \mathbb{Z}_q$ uniformly at random, computes $c_1 = g^y$, $c_2 = MX^y$ and the ciphertext is the pair $(c_1, c_2)$. To decrypt, notice that $c_2 = MX^y = M(g^x)^y = M(g^y)^x = Mc_1^x$ so, with the private key $x$ we just compute $M = c_2c_1^{-x}$.

Now consider the following game $\mathrm{Game}_0$ played by a PPT adversary $\mathcal{A}$.
  1. $x \overset{\$}{\leftarrow} \mathbb{Z}_q, X \leftarrow g^x$ (generate the public, private key pair)
  2. $(M_0, M_1) \overset{\$}{\leftarrow} \mathcal{A}(X)$ (the adversary, in possession of the public key, produces a pair of challenge messages, possibly using a randomised process)
  3. $b \overset{\$}{\leftarrow} \{0,1\}$ (a random bit is chosen)
  4. $y \overset{\$}{\leftarrow} \mathbb{Z}_q, c_1 \leftarrow g^y, Z \leftarrow X^y, c_2 \leftarrow M_bZ $ (an encryption of message $b$ is produced)
  5. $b' \overset{\$}{\leftarrow} \mathcal{A}(c_1, c_2)$ (the adversary, in possession of the ciphertext, produces a bit, possibly using a randomised process)
  6. if $b = b'$ then return 1, else return 0.
We say $\mathcal{A}$ wins $\mathrm{Game}_0$ if the game returns 1. From the definition in Ana's blog, it should be clear that the advantage of $\mathcal{A}$ against the IND-CPA security of ElGamal (with parameters $G$, $q$ and $g$) is $2|\mathrm{Pr}[\mathcal{A} \: \mathrm{wins \: Game}_0] - 1/2|$ (1).

Next, consider a new game $\mathrm{Game}_1$. This game is exactly as above, except that in Step 4, we replace the command 
$Z \leftarrow X^y$
$z \overset{\$}{\leftarrow} \mathbb{Z}_q, Z \leftarrow g^z$.
So the new ciphertext is $(c_1, c_2) = (g^y, M_bg^z)$ instead of $(c_1, c_2) = (g^y, M_bg^{xy})$. 

Again we say $\mathcal{A}$ wins this game if it returns 1. What is the probability that this happens? Note that $Z$ is now a totally random group element by the randomness of $z \in \mathbb{Z}_q$. So $c_2$ is also a random group element, independent of $X$, $c_1$ and $b$. So the adversary gains no information about $b$ from $(c_1, c_2)$, meaning it outputs the correct bit and wins the game with probability exactly 1/2 (2).

Now we bound the difference in probability for an adversary to win each of the games. Since the only difference in the two games is that the group element $g^{xy}$ is replaced by a random group element $g^z$, it is easy to see how this relates to the DDH problem, where an adversary must distinguish between the triples $(g^x, g^y, g^{xy})$ and $(g^x, g^y, g^z)$ for a random exponent $z \in \mathbb{Z}_q$. To make the link between the games precise, we use the adversary $\mathcal{A}$ to build an adversary $\mathcal{B}$ against DDH as follows:
  1. On input $(X, Y, Z)$, run $\mathcal{A}$ on input $X$ to receive a challenge pair $(M_0, M_1)$
  2. Select a bit $b$ uniformly at random and compute $m_bZ$
  3. Give the 'ciphertext' $(Y, m_bZ)$ to the $\mathcal{A}$ and receive a bit $b'$
  4. If $b = b'$, guess that $Z = g^{xy}$ and return 1, else guess $Z$ is random so return 0.
If $\mathcal{B}$ is given a real Diffie-Hellman triple $(g^x, g^y, g^{xy})$ then the above is a perfect simulation of $\mathcal{A}$ playing $\mathrm{Game}_0$, and if $\mathcal{B}$ is given a fake triple $(g^x, g^y, g^z)$ then it is a perfect simulation of $\mathcal{A}$ playing $\mathrm{Game}_1$. Therefore, the difference between the probability of $\mathcal{A}$ winning $\mathrm{Game}_0$ and $\mathcal{A}$ winning $\mathrm{Game}_1$ is precisely the difference between the probability that $\mathcal{B}$ outputs 1 on input $(g^x, g^y, g^{xy})$ and outputs 1 on input $(g^x, g^y, g^z)$, which is exactly the advantage of $\mathcal{B}$ against DDH.

Combining the above with facts (1) and (2) (and using the triangle inequality to take care of the modulus signs), we can easily obtain that the advantage of $\mathcal{A}$ against the IND-CPA security of ElGamal is no greater than the advantage of $\mathcal{B}$ against DDH. So if DDH is hard for all polynomial time adversaries (meaning their advantage is negligible), ElGamal must be IND-CPA secure.

Tuesday, May 5, 2015

Eurocrypt 2015: Threshold Implementations

On Thursday morning, Vincent Rijman gave an invited talk on Threshold Implementations designed to be more secure against side-channel attacks. He started off discussing Shannon's Product Cipher[1](like a modern SP network). From a cryptanalysis point of view, this can be very difficult to break due to high diffusion. What this means is that if one character of plaintext is changed then several characters of ciphertext will be changed. Similarly, changing a character of the ciphertext will change several characters of plaintext. However, if we introduce side-channel attacks[2], attacks based on gaining information from the physical implementation of a cryptosystem such as timing information, power consumption, or the example given by Vincent, electromagnetic radiation. 

Changing the value of a logic cell from `0' to `1' consumes energy. The amount of energy the hardware consumes can depend on many things, such as transister design, process variations, length of connection line, crosstalk between lines and many more. In order to counter these attacks a few methods have been devised; 
  • The first is to try to balance the power consumption equally, this means it limits the amount of information gained from the power consumption. 
  • The next is Leakage-Resilient Cryptography such as Ephemeral Keys[3]. 
  • Finally, the method of masking. This splits the sensitive information into $d+1$ shares where $d$ is called the masking order. 
This talk concentrated on the latter technique. In the 2003 paper by Ishai et. al [4] they use masking in private circuits. In 2003 Trichina [5] wrote a paper on a masked multplier. But on its own this is not enough, since there are transient effects in hardware. What this means is that changing values takes time. We call this a transition period. These delays depend on the circuit lay-out. Transient effects account for almost all the power consumption of CMOS[6] circuits. The propogation of these transient effects depends on the input of the combinational circuit, and these dependencies are non-linear. Thus, we have a security breakdown.

Vincent then introduced a threshold implementation that doesn't rely on the behaviour of hardware implementations of combinational logic. The setup assumes that combinational logic leaks information on all its inputs. They do this by the method of secret sharing. An example of this is if we have a function $f$ and an input $x$ giving the output $y$. I.e. $y = f(x)$. We can split the function and hence the input into 3 seperate parts $f_1, f_2, f_3$ and $x_1, x_2,x_3$, respectively. We then create the setup such that the inputs of each split function has only 2 of the split inputs. So that we have
f_1(x_2, x_3) = y_1, \\
f_2(x_1, x_3) = y_2, \\
f_3(x_1, x_2) = y_3.

y_1+y_2+y_3 = y, \\
x_1+x_2+x_3 = x.
This looks extremely similar to multi-party computation. The main theorem that follows from this is: $\textit{The average power consumption of the circuit is independent of x.}$ An extremely informal proof of this is as follows. For each $i$, $f_i$ is independent of the input $x_i$, the power consumption of $f_i$ is independent of $x_i$. If $(x_{i-1}, x_{i+1})$ is independent of $x$, then the power consumption of $f_i$ is independent of $x$. The average power consumption of the circuit is equal to the sum of the average power consumptions of $f_i$. Hence, the power consumption of the circuit is independent of $x$. A few assumptions were necessary for this. The $x_i$'s need to be uniformally random. The implementation of the $f_i$'s depend only on $(x_1, \ldots, x_{i+1}, x_{i-1}, \ldots, x_n)$ and finally we obviously need suitable $f_i$ to exist! For linear $f$ it's easy to have the property
f_1(x_2, x_3, \ldots, x_n) +  \ldots + f_n(x_1, x_2, \ldots, x_{n-1}) = f(x_1, x_2, \ldots, x_n)
however for most interesting $f$ this is a research problem. A simple example of this is the multiplier. We have
z = f(x,y) = x \cdot y \\
z_1 = f_1(x_2,x_3,y_2,y_3) = x_2 y_2 + x_2 y_3 + x_3 y_2, \\
z_2 = f_1(x_1,x_3,y_1,y_3) = x_3 y_3 + x_1 y_3 + x_3 y_1, \\
z_3 = f_1(x_1,x_2,y_1,y_2) = x_1 y_1+ x_1 y_2 + x_1 y_3.
This is secure, even with transient effects. If we consider some facts we can gain about arbitrary functions. The size of the hardware increases with the number of shares. Functions with algebraic degree $n$ requires $n+1$ shares and strong ciphers have high algebraic degree. What this means is that the stronger the cipher, the higher the algebraic degree and hence the amount of shares required increases; meaning the larger the hardware required. 

A potential solution to this is using registers. The combinational logic between registers has lower algebraic degree and registers limit the propagation of transient effects. For this to work we need a few more assumptions. The inputs of each stage need to be uniformly distributed. The input of the second step must equal the output of the first step and the outputs of the first step need to be uniformly distributed. This can be done by remasking, or an extra property for $f_i$ is needed. This property is as follows; every $y_i$-tuple for the same $y$ must get an equal amount of "hits". The original multiplier does not fit this extra assumption, some binary representations of $y$ are actually "hit" more often. Changing the definition of the multiplier to what follows solves this.

z_1 = (x_3 + x_4)(y_2 + y_3) + x_2 + x_4, \\
z_2 = (x_1+ x_3)(y_1 + y_4) + y_1 + x_4, \\
z_3 = (x_2 + x_4)(y_1 + y_4) + x_2, \\
z_4 = (x_1 + x_2)(y_2 + y_3)  + y_1.
Further work suggested by Vincent is security against fault attacks, which induce hardware failure while measuring signals. Other suggested future work is security against attacks using non-linear combinations of signals measured at different times.

[1] -
[2] -
[3] -
[4] -
[5] -
[6] -

Saturday, May 2, 2015

52 Things: Number 30: Roughly outline the BR security definition for key agreement

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this week we look at a security definition for authenticated key exchange.

Establishing a shared key between two parties is one of the oldest problems in cryptography, and turns out to be much harder than standard encryption, even when just considering definitions. Although the classic Diffie-Hellman protocol from 1976 seems to solve the problem, it provides no authenticity guarantee - i.e. that a key has been agreed with the right person - since a man-in-the-middle attack can easily be performed.

To model this kind of attack, and others, we need a security definition. There are two main approaches when defining the security of a key exchange protocol, namely those based on a symbolic model and those using a computational model. In the symbolic model, which become popular in the '90s after the classic paper on BAN logic, techniques from formal methods are used to model and analyse a protocol. The symbolic model is good for identifying attacks, but it is difficult for the underlying logic to capture all classes of attacks, so analysis in this model does not provide great security guarantees, but can be semi-automated using theorem provers.

In their seminal 1993 paper, Bellare and Rogaway instead created a game-based security definition for authenticated key exchange in a computational model, similar to the IND-CPA and IND-CCA definitions for encryption. In this model, cryptographic primitives are not assumed to be unbreakable, but instead we attempt to quantify the success probability of an adversary by computing their 'advantage' in a security game. The main feature of an adversary that we wish to encompass is that all communication is under the adversary's control: they can read, modify, delay and replay messages. They can also run any number of instances of the protocol simultaneously with other parties. The intuition behind the AKA security game is that the only way an adversary can get a party to accept an agreed key is by forwarding honest messages from a genuine protocol run, in which case they cannot possibly learn anything new.

The security game consists of a number of different oracles that an adversary can query. The three main oracles are the corruption oracle, which allows the adversary to take control of a chosen party, the key registration oracle, which registers a public key for any chosen user, and the message oracle, which is the main oracle used for passing messages. Note that messages are not sent directly between the participants, instead the adversary does this using the message oracle.

The message oracle is the main oracle allowing the adversary to create protocol sessions with parties (where they aim to establish a short-term, or ephemeral, shared key) and send messages. When querying the oracle, they can take one of the following actions:
  • Start a new session between two users
  • Learn the secret key of any terminated session
  • Send a message in an existing session and receive the response
The security game follows the real-or-random paradigm, similarly to standard definitions of encryption, by choosing a secret bit $b$; if $b=0$ then the adversary is given a random key for its challenge, otherwise it gets the real key. After interacting with the oracles, the adversary chooses a single session that has terminated, in which both parties are not corrupted and there is no 'matching' conversation where the key has been revealed (to prevent a trivial break), and receives a challenge key for this session. They win the game if they correctly guess $b$.

A protocol is said to be a secure authenticated key exchange protocol if it is correct, and any adversary's strategy is the above game is no better than random guessing. The above outline is only a rough sketch, of course, and there are many further details in the paper.

Thursday, April 30, 2015

Eurocrypt 2015: When life gives you Fully Homomorphic Encryption...

On Wednesday morning, Kristin Lauter gave an invited talk about the Practical Applications of Homomorphic Encryption. She started by talking about a recent competition on Secure Genome Analysis sponsored by the (American) National Institutes of Health at the iDASH Privacy & Security Workshop, which received a substantial amount of media coverage.

Kristin reasoned that this excitement was caused in part by the fact that with the rise of relatively inexpensive genome sequencing, privacy is becoming a fundamental problem. A person's genome can give information on genetic diseases that the person has, as well as partial information on the genetic make-up of close family members. Leaking this information can lead to genetic discrimination, for example from health insurance providers. Still, this kind of data can be put to good use as well, such as personalized medicine, biomedical research and ancestry or paternity tests, so we would like to give researchers access to this data without breaking the privacy of the data donors.

Therefore, the aim of the competition was to devise ways of performing analysis on genomic data in a secure manner, which was implemented with two different tracks. The first track considered the scenario where one party owns all the data, like a hospital that wants to protect the privacy of its patients, which is an ideal scenario for Homomorphic Encryption. The second track considered the scenario where there are multiple data owners that mutually distrust one another, which is an ideal scenario for Multi-Party Computation. There were teams from both industry and academia. The used data was part real data from donors and part simulated data.

Kristin described a few different tasks: counting the frequency of minor alleles, and computing the Hamming and Edit distances for the alignment of genomes. The frequency count can be performed by purely additive homomorphic solutions, but schemes based on RLWE allowing for more homomorphism were still competitive. On the other end of the spectrum was the Edit distance, which consists of a relatively deep circuit. However, in practice it is often good enough to have an approximation, as it allows for a shallower circuit such that even existing schemes can provide a practical solution. Each task had a different winner, indicating that there is currently no best solution for all applications.

This competition spurred fundamental progress in the field of secure genome analysis through the interaction between computer scientists, mathematicians, bio-informaticians and policy-makers. Kristin therefore also highlighted the importance of communicating the concept and possibilities of Homomorphic Encryption to the general public, in order to find more good applications. One major point of the invited talk was that there are applications out there right now that can be implemented using relatively shallow circuits, such as the aforementioned secure genome analysis, but also the evaluation of private models in the cloud and machine learning. These applications can be solved by the schemes we have today, even with their inefficiency drawbacks.

That is not to say there are no more challenges to be solved. Storage costs are a problem as Fully Homomorphic Encryption schemes suffer from substantial ciphertext expansion. The security is not always as well understood as we would like. The efficiency does not scale very well to deep circuits and large amounts of data. These are but some of the challenges that Kristin outlined at the end of her talk. So let us work together and make some lemonade!