2004 | OriginalPaper | Chapter
On the Use of GF-Inversion as a Cryptographic Primitive
Authors : Kazumaro Aoki, Serge Vaudenay
Published in: Selected Areas in Cryptography
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.