# [Resource Topic] 2019/960: Another Look at Key Randomisation Hypotheses

Welcome to the resource topic for 2019/960

Title:
Another Look at Key Randomisation Hypotheses

Authors: Subhabrata Samajder, 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.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.