Paper 2016/1036

Direct Construction of Lightweight Rotational-XOR MDS Diffusion Layers

Zhiyuan Guo, Renzhang Liu, Wenling Wu, and Dongdai Lin

Abstract

As a core component of Substitution-Permutation Networks, diffusion layer is mainly introduced by matrices from maximum distance separable (MDS) codes. Surprisingly, up to now, most constructions of MDS matrices require to perform an equivalent or even exhaustive search. Especially, not many MDS proposals are known that obtain an excellent hardware efficiency and simultaneously guarantee a remarkable software implementation. In this paper, we study the cyclic structure of rotational-XOR diffusion layer, one of the commonly used linear layers over ${(\mathbb{F}_{\rm{2}}^b)^n}$, which consists of only rotation and XOR operations. First, we provide novel properties on this class of matrices, and prove the a lower bound on the number of rotations for $n \ge 4$ and show the tightness of the bound for $n=4$. Next, by precisely characterizing the relation among sub-matrices for each possible form, we can eliminate all the other non-optimal cases. Finally, we present a direct construction of such MDS matrices, which allows to generate $4 \times 4$ perfect instances for arbitrary $b \ge 4$. Every example contains the fewest possible rotations, so under this construction strategy, our proposal costs the minimum gate equivalents (resp. cyclic shift instructions) in the hardware (resp. software) implementation. To the best of our knowledge, it is the first time that rotational-XOR MDS diffusion layers have been constructed without any auxiliary search.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Lightweight CryptographyMDS Diffusion LayersBit-wise Circulant MatricesMultiple Platforms
Contact author(s)
liurenzhang @ iie ac cn
History
2016-11-02: received
Short URL
https://ia.cr/2016/1036
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1036,
      author = {Zhiyuan Guo and Renzhang Liu and Wenling Wu and Dongdai Lin},
      title = {Direct Construction of Lightweight Rotational-XOR MDS Diffusion Layers},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1036},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1036}},
      url = {https://eprint.iacr.org/2016/1036}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.