On the Use of GF-Inversion as a Cryptographic Primitive

Inversion in Galois Fields is a famous primitive permutation for designing cryptographic algorithms e.g. for Rijndael because it has suitable differential and linear properties. Inputs and outputs are usually transformed by addition (e.g. XOR) to key bits. We call this construction the APA (Add-Permute-Add) scheme. In this paper we study its pseudorandomness in terms of k-wise independence. We show that the pairwise independence of the APA construction is related to the impossible differentials properties. We notice that inversion has many impossible differentials, so x --> 1/(x+a)+b is not pairwise independent. In 1998, Vaudenay proposed the random harmonic permutation h:x --> a/(x-b)+c. Although it is not perfectly 3-wise independent (despite what was originally claimed), we demonstrate in this paper that it is almost 3-wise independent. In particular we show that any distinguisher limited to three queries between this permutation and a perfect one has an advantage limited to 3/q where q is the field order. This holds even if the distinguisher has access to h-1. Finally, we investigate 4-wise independence and we suggest the cross-ratio as a new tool for cryptanalysis of designs involving inversion.