Lai-Massey scheme

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Lai Massey scheme diagram en.svg

The Lai-Massey scheme is a cryptographic structure used in the design of block ciphers.[1][2] It is used in IDEA and IDEA NXT.

Construction details[edit]

Let \mathrm F be the round function and \mathrm H a half-round function and let K_0,K_1,\ldots,K_n be the sub-keys for the rounds 0,1,\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,\dots,n, compute

(L_{i+1}',R_{i+1}') = \mathrm H(L_i' + T_i,R_i' + T_i)

where T_i = \mathrm F(L_i' - R_i', K_i) and (L_0',R_0') = \mathrm H(L_0,R_0)

Then the ciphertext is (L_{n+1}, R_{n+1}) = (L_{n+1}',R_{n+1}').

Decryption of a ciphertext (L_{n+1}, R_{n+1}) is accomplished by computing for i=n,n-1,\ldots,0

(L_i',R_i') = \mathrm H^{-1}(L_{i+1}' - T_i, R_{i+1}' - T_i)

where T_i = \mathrm F(L_{i+1}' - R_{i+1}',K_i) and (L_{n+1}',R_{n+1}')=\mathrm H^{-1}(L_{n+1},R_{n+1})

Then (L_0,R_0) = (L_0',R_0') 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 \mathrm F does not have to be invertible.

The half-round function is required to prevent a trivial distinguishing attack (L_0-R_0 = L_{n+1}-R_{n+1}). It commonly applies an orthomorphism \sigma on the left hand side, that is,

\mathrm H(L, R) = (\sigma(L),R)

where both \sigma and x\mapsto \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.

\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.



  1. ^ Aaram Yun, Je Hong Park, Jooyoung Lee: Lai-Massey Scheme and Quasi-Feistel Networks. IACR Cryptology
  2. ^ Serge Vaudenay: On the Lai-Massey Scheme. ASIACRYPT'99