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.

Published in:
Selected Areas in Cryptography, 10th Annual International Workshop, SAC 2003, 3006, 234-247
Presented at:
Selected Areas in Cryptography, Ottawa, Canada, August 14-15

 Record created 2007-01-19, last modified 2018-01-27

External link:
Download fulltext
Rate this document:

Rate this document:
(Not yet reviewed)