# [Resource Topic] 2016/1118: Designing Optimal Implementations of Linear Layers (Full Version)

Welcome to the resource topic for 2016/1118

Title:
Designing Optimal Implementations of Linear Layers (Full Version)

Authors: Ruoxin Zhao, Baofeng Wu, Rui Zhang, 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 co-ordinates 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 graph-theoretical 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 double-directionâ€™â€™ 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.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.