On Unbiased Linear Approximations

Jonathan Etrog, Matt J. B. Robshaw

Abstract

In this paper we explore the recovery of key information from a block cipher when using unbiased linear approximations of a certain form. In particular we develop a theoretical framework for their treatment and we confirm their behaviour with experiments on reduced round variants of DES. As an application we show a novel form of linear cryptanalysis using multiple linear approximations which can be used to extract key information when all pre-existing techniques would fail.