Paper 2016/1118
Designing Optimal Implementations of Linear Layers (Full Version)
Ruoxin Zhao, Baofeng Wu, Rui Zhang, and Qian Zhang
Abstract
Linear layer is a fundamental primitive for computer science, electronic engineering, and telecommunication. The performance of a linear layer depends on two aspects: diffusion ability and implementation cost, where the latter is usually measured by the number of XORs needed to implement it. For many years, linear layers have been implemented by computing coordinates of the output independently. With this method, costs are determined only by the matrices representing linear layers. However, we note that the implementation cost of a given linear layer depends not only on its matrix but also on the ways with which we implement it. So, in this paper, we focus on another implementation method: modifying input vectors to output step by step (MIOSS). This method uses fewer XORs than previous methods do and needs no extra temporary register. Besides, this method makes the implementation cost of a linear layer same as that of its inverse. With the new implementation method, we first clarify the measurement of implementation cost and the optimal implementation procedure of linear layers. Here, ``optimal'' means using fewest XORs. Then, to find the optimal implementation procedure of a given linear layer, we construct a graphtheoretical model and transfer the problem to the shortest path problem in graph theory. Although there has been several algorithms for the shortest path problem, they do not perform best for the graph that we construct in this paper because of its regularity. Therefore, we adopt a new ``doubledirection'' algorithm that uses less storage and makes the search for a shortest path more efficient in a regular graph. Unfortunately, this algorithm is not practical for large size linear layers because of its high space/time complexity. So, we finally construct another algorithm for finding efficient implementations of linear layers. An important advantage of this last algorithm is its extremely low complexity. We conduct it to the linear layer of AES and get very efficient implementations.
Note: We correct some mistakes of the last version and put a new section into it.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint. MINOR revision.
 Keywords
 Linear LayerXOR CountEquivalence RelationRegular GraphThe Shortest Path
 Contact author(s)
 zhaoruoxin @ iie ac cn
 History
 20170208: last of 2 revisions
 20161201: received
 See all versions
 Short URL
 https://ia.cr/2016/1118
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/1118, author = {Ruoxin Zhao and Baofeng Wu and Rui Zhang and Qian Zhang}, title = {Designing Optimal Implementations of Linear Layers (Full Version)}, howpublished = {Cryptology ePrint Archive, Paper 2016/1118}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/1118}}, url = {https://eprint.iacr.org/2016/1118} }