×

A new class of invertible mappings. (English) Zbl 1020.94522

Kaliski, Burton S. jun. (ed.) et al., Cryptographic hardware and embedded systems - CHES 2002. 4th international workshop, Redwood Shores, CA, USA, August 13-15, 2002. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 2523, 470-483 (2002).
Summary: Invertible transformations over \(n\)-bit words are essential ingredients in many cryptographic constructions. When \(n\) is small (e.g., \(n=8\)) we can compactly represent any such transformation as a lookup table, but when \(n\) is large (e.g., \(n=64\)) we usually have to represent it as a composition of simpler operations such as linear mappings, S-P networks, Feistel structures, etc. Since these cryptographic constructions are often implemented in software on standard microprocessors, we are particularly interested in invertible univariate or multivariate transformations which can be implemented as small compositions of basic machine instructions on 32 or 64 bit words. In this paper we introduce a new class of provably invertible mappings which can mix arithmetic operations (negation, addition, subtraction, multiplication) and Boolean operations (not, xor, and, or), are highly efficient, and have desirable cryptographic properties. In particular, we show that for any \(n\) the mapping \(x \to x+(x^2 \vee C) \pmod{2^n}\) is a permutation with a single cycle of length \(2^n\) iff both the least significant bit and the third least significant bit in the constant \(C\) are 1.
For the entire collection see [Zbl 1007.00053].

MSC:

94A60 Cryptography
06E30 Boolean functions
PDFBibTeX XMLCite
Full Text: Link