**Another Look at Key Randomisation Hypotheses**

*Subhabrata Samajder and Palash Sarkar*

**Abstract: **In the context of linear cryptanalysis of block ciphers, let $p_0$ (resp. $p_1$) be the probability that a particular linear approximation
holds for the right (resp. a wrong) key choice. The standard right key randomisation hypothesis states that $p_0$
is a constant $p\neq 1/2$ and the standard wrong key randomisation hypothesis states that $p_1=1/2$. Using these hypotheses,
the success probability $P_S$ of the attack can be expressed in terms of the data complexity $N$. The resulting expression for $P_S$
is a monotone increasing function of $N$.

Building on earlier work by Daemen and Rijmen (2007), Bogdanov and Tischhauser (2014) argued that $p_1$ should be considered to be a random variable. They postulated the adjusted wrong key randomisation hypothesis which states that $p_1$ follows a normal distribution. A non-intuitive consequence was that the resulting expression for $P_S$ is no longer a monotone increasing function of $N$. A later work by Blondeau and Nyberg (2017) argued that $p_0$ should also be considered to be a random variable and they postulated the adjusted right key randomisation hypothesis which states that $p_0$ follows a normal distribution.

In this work, we revisit the key randomisation hypotheses. While the argument that $p_0$ and $p_1$ should be considered to be random variables is indeed valid, we consider the modelling of their distributions by normal to be inappropriate. Being probabilities, the support of the distributions of $p_0$ and $p_1$ should be subsets of $[0,1]$ which does not hold for normal distributions. We show that if $p_0$ and $p_1$ follow any distributions with supports which are subsets of $[0,1]$, and $E[p_0]=p$ and $E[p_1]=1/2$, then the expression for $P_S$ that is obtained is exactly the same as the one obtained using the standard key randomisation hypotheses. Consequently, $P_S$ is a monotone increasing function of $N$ even when $p_0$ and $p_1$ are considered to be random variables.

**Category / Keywords: **secret-key cryptography / linear cryptanalysis, key randomisation hypotheses

**Date: **received 23 Aug 2019

**Contact author: **subhabrata samajder at gmail com, palash@isical ac in

**Available format(s): **PDF | BibTeX Citation

**Version: **20190823:161219 (All versions of this report)

**Short URL: **ia.cr/2019/960

[ Cryptology ePrint archive ]