SOLILOQUY: a New Primitive and a Quantum Attack

This week, Ana gave a study group talk based on the paper Soliloquy: a Cautionary Tale by Campbell, Groves and Shepherd of CESG (the Information Security arm of GCHQ).

The paper describes a new primitive, SOLILOQUY, a Key Encapsulation Mechanism, which was proposed secretly in 2007, found to resist classical cryptanalysis (for reasons omitted by the authors), but then abandoned due to the development of "a reasonably efficient quantum attack on the primitive". The paper is very complicated and appears to skip over a number of technical details, so we will present here a very high level view of SOLILOQUY and the attack, before mentioning some of the discussion about this result that has taken place, both in our study group and elsewhere in the academic community.

Construction of SOLILOQUY

Let $n$ be a prime, about 10 bits in size, and $\zeta$ a primitive $n$th root of unity. Let $K$ be the number field $\mathbb{Q}(\zeta)$ and $\mathcal{O}=\mathbb{Z}[\zeta]$ the ring of integers in $K$. One selects a candidate private key $\alpha = \sum_{i = 1}^{n}a_i\zeta^i \in \mathcal{O}$ where the coefficients $a_i$ are sampled from a discrete Gaussian distribution of mean 0 (so they are small). Let $p$ be the norm of $\alpha$. The pair $(\alpha, p)$ can be used as a SOLILOQUY key pair if

1. $p$ is prime
2. $c = 2^{\frac{(p-1)}{n}} \not\equiv 1 \: (\mathrm{mod}\: p)$

where condition 2 occurs with probability $1 - \frac{1}{n}$.

We check these conditions because, for a prime $p \equiv 1 \: (\mathrm{mod} \: n)$, the principal ideal $p\mathcal{O}$ decomposes into a product of prime ideals $\mathcal{P}_i$, each with a representation of the form $\mathcal{P}_i = p\mathcal{O} + (\zeta - c_i)\mathcal{O}$ where the $c_i$ are the non-trivial $n$th roots of unity mod $p$. The conditions above ensure that $\alpha\mathcal{O}$ is one of these $\mathcal{P}_i$ and that one of these $\mathcal{P}_i$ has the form $\mathcal{P} = p\mathcal{O} + (\zeta - c)\mathcal{O}$ for the particular choice $c = 2^{\frac{(p-1)}{n}}$. Then, since the Galois group $\mathrm{Gal}(K/\mathbb{Q})$ permutes the prime ideals $\mathcal{P}_i$, we can make sure that $\alpha\mathcal{O} = \mathcal{P}$ by taking some Galois conjugate of $\alpha$ (which will just reorder the coefficients $a_i$).

Now there is a natural homomorphism $\psi : \mathcal{O} \to \mathcal{O}/\mathcal{P} \simeq \mathbb{F}_p$ given by \[\psi(\epsilon) = \psi \left ( \sum_{i = 1}^{n}e_i \zeta^i \right) = \sum_{i = 1}^{n}e_i c^i \: (\mathrm{mod} \: p) = z\] and this is the encryption function in SOLILOQUY. One samples an ephemeral key $\epsilon$ from $\mathcal{O}$ as above, (whose coefficients must again be sampled with a mean of 0) and encapsulates it as $z$, viewed as a (rational) integer $0 \leq z < p$.

To decrypt, one computes $\epsilon = z - \lceil z\alpha^{-1} \rfloor \cdot \alpha$ where $\lceil - \rfloor$ is coordinate-wise rounding. That this is correct is not proved in the paper, but roughly corresponds to $\epsilon$ being small enough that $\lceil \epsilon \cdot \alpha^{-1} \rfloor = 0$. 

The Quantum Attack
Key recovery is an example of the small principal ideal problem: we have a representation $p\mathcal{O} + (\zeta - c)\mathcal{O}$ of the principal ideal $\mathcal{P} = \alpha\mathcal{O}$ of $\mathcal{O}$ and wish to compute the small generator $\alpha$. There are classical sub-exponential attacks for such a problem but the authors claim to provide the first 'practical' quantum algorithm for it. First, they make some simplifications, citing a 2004 result in Algebraic Number Theory that shows it suffices to look at the real subfield $\mathbb{Q}\left( \zeta + \zeta^{-1} \right)$ of $K$ and find $\alpha' = \alpha \cdot (\alpha)^*$ in the ring of integers $\mathcal{O}' = \mathbb{Z}\left [ \zeta + \zeta^{-1} \right ]$. Furthermore, they claim that in this setting it is easy to find a short generator of a principal ideal given any generator. So, to find $\alpha'$ (and hence find $\alpha$), it suffices to find any generator of $\alpha' \mathcal{O}'$.

The attack itself uses complicated ideas, but essentially amounts to using a logarithm function to transform the group of units $\mathcal{O}'^{\times}$ (with multiplicative structure) into a lattice $\Lambda$ (with additive structure). Then we consider an encoding of $\alpha'$ as a hidden, high-dimensional lattice $\Lambda_{\alpha'}$ with known sublattice $\Lambda$ of co-dimension 1. Then, using a "quantum fingerprint" of the hidden lattice, one can approximate the dual lattice $\Lambda_{\alpha'}^*$ (and iterate this procedure to produce many samples close to the true dual lattice). Then, with $\Lambda_{\alpha'}^*$, one can find a basis for $\Lambda_{\alpha'}$, determine the value of $\alpha'$ and hence find the secret key $\alpha$.

Discussion
While we were unable to examine the algorithm closely during the study group, some felt it was unclear how efficient the proposed attack is (even with quantum computers). Indeed, there has been a fair bit of discussion about the meaning of this paper in the academic community: see, for example, this thread.

While it is welcome that the researchers at GCHQ are sharing some of their work with the wider community, the paper is slightly unclear in places. It was felt that greater clarification was needed for the new attack to have impact beyond SOLILOQUY itself. 

52 Things: Number 34: Describe the Baby-Step/Giant-Step method for breaking DLPs

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, we discuss the Baby-Step/Giant-Step attack against DLPs. 

Baby-Step/Giant-Step is an algorithm developed by Daniel Shanks that solves Discrete Logarithm Problem (DLP), of which its hardness founded many of our mordern security protocols.

First, let's just briefly recall DLP.

Given a cyclic group $G$ of order $n$, a generator $g$ and an element of the group $h$, the DLP is to find $x$, such that 
\begin{equation}
h=g^x
\end{equation}

Now let's come back to Baby-Step/Giant-Step.

Since $n$ is the group order, so we have $0 \leq x \leq n$. Therefore we can write $x$ as
\begin{equation}
x = i\lceil \sqrt{n} \rceil + j
\end{equation}
where $ 0 \leq i,j \leq \sqrt{n}$.

So the DLP equation can be rewritten as
\begin{eqnarray}
h = g^{i\lceil \sqrt{n} \rceil + j}\\
h(g^{-j}) = g^{i\lceil \sqrt{n} \rceil}
\end{eqnarray}
The problem is transformed into finding a pair of $(i,j)$ that satisfies the new equation.

One way to do this is to precompute a table of $\{g^{i\lceil \sqrt{n} \rceil}\}$ over $0 \leq i \leq \sqrt{n}$ and $g^{-1}$. For any given $h$, we iterate $j$ for $h(g^{-1})^j$ until we find a match in our precomputed table, which essentially means
\begin{equation}

g^{i\lceil \sqrt{n} \rceil} = h(g^{-1})^j = h(g^{-j})
\end{equation}

Once a match is found, we can simply reconstruct $x$ using
\begin{equation}
x = i\lceil \sqrt{n} \rceil + j
\end{equation}

The algorithem has both time and space complexity of $O(\sqrt{n})$. Fortunate for us, this is just not good enough to tear our cryptographic life apart.

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] - http://en.wikipedia.org/wiki/RSA_(cryptosystem)

[2] - http://en.wikipedia.org/wiki/Chinese_remainder_theorem

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.

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.

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$

by 

$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.

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.
$$

Where
$$
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] - http://en.wikipedia.org/wiki/Product_cipher
[2] - http://en.wikipedia.org/wiki/Side-channel_attack
[3] - http://en.wikipedia.org/wiki/Ephemeral_key
[4] - http://www.cs.berkeley.edu/~daw/papers/privcirc-crypto03.pdf
[5] - https://eprint.iacr.org/2003/236.pdf
[6] - http://en.wikipedia.org/wiki/CMOS

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.