Lai–Massey scheme

File:Lai Massey scheme diagram en.svg

The Lai-Massey Scheme is similar to a Feistel network in design, but in addition to using a using a non-invertible round function whose input and output is half the data block size, each round uses a full-width invertible half-round function. Either, or preferably both of the functions may take a key input as well.

Initially, the inputs are passed through the half-round function. In each round, the difference between the inputs is passed to the round function along with a sub-key, and the result from the round function is then added to each input. The inputs are then passed through the half-round function. This is then repeated a fixed number of times, and the final output is the encrypted data. Due to its design, it has an advantage over a Substitution-permutation network since the round-function does not need to be inverted - just the half-round - enabling it to be more easily inverted, and enabling the round-function to be arbitrarily complex. The encryption and decryption processes are fairly similar, decryption instead requiring a reversal of the key schedule, an inverted half-round function, and that the round function's output be subtracted instead of added.

Let $\backslash mathrm\; F$ be the round function, and $\backslash mathrm\; H$ a half-round function, and let $K\_0,K\_1,\backslash ldots,K\_n$ be the sub-keys for the rounds $0,1,\backslash ldots,n$ respectively.

Then the basic operation is as follows:

Split the plaintext block into two equal pieces, ($L\_0$, $R\_0$).

For each round $i\; =0,1,\backslash dots,n$, compute

:$(L\_\{i+1\}\text{'},R\_\{i+1\}\text{'})\; =\; \backslash mathrm\; H(L\_i\text{'}\; +\; T\_i,R\_i\text{'}\; +\; T\_i),$

where $T\_i\; =\; \backslash mathrm\; F(L\_i\text{'}\; -\; R\_i\text{'},\; K\_i)$, and $(L\_0\text{'},R\_0\text{'})\; =\; \backslash mathrm\; H(L\_0,R\_0)$.

Then the ciphertext is $(L\_\{n+1\},\; R\_\{n+1\})\; =\; (L\_\{n+1\}\text{'},R\_\{n+1\}\text{'})$.

Decryption of a ciphertext $(L\_\{n+1\},\; R\_\{n+1\})$ is accomplished by computing for $i=n,n-1,\backslash ldots,0$

:$(L\_i\text{'},R\_i\text{'})\; =\; \backslash mathrm\; H^\{-1\}(L\_\{i+1\}\text{'}\; -\; T\_i,\; R\_\{i+1\}\text{'}\; -\; T\_i),$

where $T\_i\; =\; \backslash mathrm\; F(L\_\{i+1\}\text{'}\; -\; R\_\{i+1\}\text{'},K\_i)$, and $(L\_\{n+1\}\text{'},R\_\{n+1\}\text{'})=\backslash mathrm\; H^\{-1\}(L\_\{n+1\},R\_\{n+1\})$.

Then $(L\_0,R\_0)\; =\; (L\_0\text{'},R\_0\text{'})$ is the plaintext again.

The Lai–Massey scheme offers security properties similar to those of the Feistel structure. It also shares its advantage over a substitution–permutation network that the round function $\backslash mathrm\; F$ does not have to be invertible.

The half-round function is required to prevent a trivial distinguishing attack {{nobr|($L\_0\; -\; R\_0\; =\; L\_\{n+1\}\; -\; R\_\{n+1\}$)}}. It commonly applies an orthomorphism $\backslash sigma$ on the left hand side, that is,

:$\backslash mathrm\; H(L,\; R)\; =\; (\backslash sigma(L),\; R),$

where both $\backslash sigma$ and $x\; \backslash mapsto\; \backslash sigma(x)\; -\; x$ are permutations (in the mathematical sense, that is, a bijection – not a permutation box). Since there are no orthomorphisms for bit blocks (groups of size $2^n$), "almost orthomorphisms" are used instead.

$\backslash mathrm\; H$ may depend on the key. If it doesn't, the last application can be omitted, since its inverse is known anyway. The last application is commonly called "round $n.5$" for a cipher that otherwise has $n$ rounds.

• X. Lai. [http://e-collection.library.ethz.ch/eserv/eth:38650/eth-38650-02.pdf On the design and security of block ciphers]. ETH Series in Information Processing, vol. 1, Hartung-Gorre, Konstanz, 1992
• X. Lai, J. L. Massey. [http://www.isiweb.ee.ethz.ch/archive/massey_pub/pdf/BI319.pdf A proposal for a new block encryption standard]. Advances in Cryptology EUROCRYPT'90, Aarhus, Denmark, LNCS 473, p. 389–404, Springer, 1991
• Serge Vaudenay: A Classical Introduction to Cryptography, [https://books.google.com/books?id=DVLEql738mwC&pg=PA33 p. 33]

{{Cryptography block}}

{{DEFAULTSORT:Lai-Massey scheme}}

Category:Block ciphers