Jump to content

Lai–Massey scheme

From Wikipedia, the free encyclopedia

The Lai–Massey scheme is a cryptographic structure used in the design of block ciphers,[1][2] an alternative to the Feistel network for converting a non-invertible keyed round function to an invertible keyed cipher. It is used in IDEA and IDEA NXT. The scheme was originally introduced by Xuejia Lai[3] with the assistance of James L. Massey, hence the scheme's name, Lai-Massey.

Design

[edit]

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.

Construction details

[edit]

Let be the round function, and a half-round function, and let be the sub-keys for the rounds respectively.

Then the basic operation is as follows:

Split the plaintext block into two equal pieces, (, ).

For each round , compute

where , and .

Then the ciphertext is .

Decryption of a ciphertext is accomplished by computing for

where , and .

Then 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 does not have to be invertible.

The half-round function is required to prevent a trivial distinguishing attack (). It commonly applies an orthomorphism on the left hand side, that is,

where both and 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 ), "almost orthomorphisms" are used instead.

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 " for a cipher that otherwise has rounds.

Literature

[edit]

References

[edit]
  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 Archived 2022-07-12 at the Wayback Machine. ASIACRYPT'99.
  3. ^ X. Lai. On the design and security of block ciphers. ETH Series in Information Processing, vol. 1, Hartung-Gorre, Konstanz, 1992