Study Group: Towards Sound Fresh Re-keying with Hard (Physical) Learning Problems

The first study group on side-channel analysis in the academic year 2016/2017 is "Towards Sound Fresh Re-keying with Hard (Physical) Learning Problems" from Stefan Dziembowski, Sebastian Faust, Gottfried Herold, Anthony Journault, Daniel Masny and Francois-Xavier Standaert, and recently published at Crypto this year. There are mainly two reasons why I chose to present it: it is somehow close to my personal research and, generally speaking, I like to read of different areas influencing each other. In this particular case, learning problems which are usually associated to post-quantum cryptography (more specifically to lattice-based cryptography) have been used to prove a security result in leakage-resilient cryptography.

In one sentence and very loosely speaking, the content of the paper which has been covered in the study group can be summarised as: the authors construct a fresh re-keying scheme and show it is secure under the LPN assumption. The remaining of this blog post is structured as a number of questions and answers on the previous statement that will hopefully clarify and detail its meaning.

Q: what is a fresh re-keying scheme?

A: intuitively, a fresh re-keying scheme is a set of cryptographic algorithms which allows the generation of session keys from a master secret key and some publicly known randomness. A session key is used to encrypt a message and then discarded. The following diagram nicely represents what is going on.

Protecting block ciphers (or other cryptographic primitives) against DPA is an expensive procedure that introduces overhead in the design and whose security is often based on heuristic arguments. Such attacks exploit the dependence of multiple power traces with the same secret key to retrieve it. Hence, fresh re-keying schemes represent a solution that try to structurally avoid the threat by using each session key only once. Both the receiver and the sender can compute the same session key by means of the shared master secret key and some randomness associated with the ciphertext. At that point, the underlying block cipher should retain security only against SPA, while the algorithm the session key is computed by should resist DPA to prevent the adversary to gain information about the master secret key thanks to leakage. The overall scheme is designed to be more efficient than a one which applies DPA countermeasures directly to the block cipher because the GenSK algorithm is built to be easier to protect.

Q: what is the LPN assumption?

A: the Learning Parity with Noise (LPN) problem asks to find a vector $\mathbf{k}\in\mathbb{Z}_2^n$ given query access to an oracle that outputs $$ (\mathbf{r},<\mathbf{r},\mathbf{k}>\oplus e) \in \mathbb{Z}_2^n\times\mathbb{Z}_2 $$ where $\mathbf{r}\in\mathbb{Z}_2^n$ is a uniformly random vector and $e\leftarrow \mathcal{B}_\tau$ is an error bit drawn from the Bernoulli distribution of a fixed parameter $0<\tau<1/2$, i.e. $\mathbb{P}(e=1)=\tau$. The decisional version, instead, asks to distinguish the above distribution from the uniform one on $\mathbb{Z}_2^n\times\mathbb{Z}_2$. The first step in the overall proof is to define a similar version of such a problem, what the author call the Learning Parity with Leakage (LPL) problem, in which everything is the same bar the distribution of the noise, which is now taken to be the Gaussian distribution over the reals. Note that the second component of the LPL distribution is then a real number. It is shown that: $$ \text{LPN is hard} \Rightarrow \text{LPL is hard}. $$

Q: what does it mean for a fresh re-keying scheme to be secure?

A: since we deal with an environment where leakage exists, we should specify both what kind of security model the proof follows and what kind of leakage the adversary is allowed to query.

Security can be stated as the indistinguishability game in the above picture. In the real part on the left, the adversary plays with and queries a real oracle, that is to say an oracle that generates all keys and randomness according to the scheme to be secured. Hence also the leakage is computed on the sensitive variables. Instead, the right-hand side depicts the random game: an ideal oracle generates keys at random, which are then passed to a simulator which computes leakage on them. For the security claim to be valid, the (computational) adversary shouldn't distinguish the oracles she is playing with.
The leakage model is the $t$-noisy probing model. If you imagine a circuit, such a model can be depicted as the adversary being allowed to put probes on up to $t$ wires and to read a noisy version of the values being carried on them. In the specific case of their construction, since there isn't a circuit from which the adversary can get leakage from, the authors specify a set of variables on which noisy bit-selector functions are applied.

Q: which is their fresh re-keying scheme?

A: even if the scheme, called $\Pi_{noisy}$ in the paper, is composed of a set of algorithms, I only specify the core of GenSK, which is responsible for generating the session key. I assume the inputs are some randomness $R$ and a set of shares of the master secret key $\{msk_i\}_{i\leq d}$, which are needed in order to secure the algorithm against DPA. $$ \begin{align*} 1.\ & u_i \leftarrow R\cdot msk_i \\ 2.\ & u \leftarrow \sum_{i\leq d} u_i \\ 3.\ & sk \leftarrow H(u) \\ \end{align*} $$ The sum in the second line is computed iteratively as $((\dots (u_1 +u_2)+u_3)+\dots )+u_d$ for security reasons, while the $H$ in the third line is an hash function modelled as a random oracle. In the game, the adversary is given $sk$ and $R$ and can query leakage on a certain amount of bits of: $msk_i$, $R\cdot msk_i$ and $\sum u_i$. A further step not specified in the previous list is the application of a refreshing algorithm to the shares of the master secret key, in such a way that they look like new shares when the next session key is generated. Finally, the author prove the following: $$ \text{LPL is hard} \Rightarrow \Pi_{noisy} \text{ is secure}. $$

For many other details, the paper is available on ePrint.