International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Lightweight Iterative MDS Matrices: How Small Can We Go?

Authors:
Shun Li , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China; Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
Siwei Sun , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China; Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing 100093, China; School o
Danping Shi , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China; Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing 100093, China; School o
Chaoyun Li , Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China; imec-COSIC, Dept. Electrical Engineering (ESAT), KU Leuven, Leuven 3001, Belgium
Lei Hu , Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing 100093, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
Download:
DOI: 10.13154/tosc.v2019.i4.147-170
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8460
Search ePrint
Search Google
Abstract: As perfect building blocks for the diffusion layers of many symmetric-key primitives, the construction of MDS matrices with lightweight circuits has received much attention from the symmetric-key community. One promising way of realizing low-cost MDS matrices is based on the iterative construction: a low-cost matrix becomes MDS after rising it to a certain power. To be more specific, if At is MDS, then one can implement A instead of At to achieve the MDS property at the expense of an increased latency with t clock cycles. In this work, we identify the exact lower bound of the number of nonzero blocks for a 4 × 4 block matrix to be potentially iterative-MDS. Subsequently, we show that the theoretically lightest 4 × 4 iterative MDS block matrix (whose entries or blocks are 4 × 4 binary matrices) with minimal nonzero blocks costs at least 3 XOR gates, and a concrete example achieving the 3-XOR bound is provided. Moreover, we prove that there is no hope for previous constructions (GFS, LFS, DSI, and spares DSI) to beat this bound. Since the circuit latency is another important factor, we also consider the lower bound of the number of iterations for certain iterative MDS matrices. Guided by these bounds and based on the ideas employed to identify them, we explore the design space of lightweight iterative MDS matrices with other dimensions and report on improved results. Whenever we are unable to find better results, we try to determine the bound of the optimal solution. As a result, the optimality of some previous results is proved.
Video from TOSC 2020
BibTeX
@article{tosc-2020-30090,
  title={Lightweight Iterative MDS Matrices: How Small Can We Go?},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2019, Issue 4},
  pages={147-170},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8460},
  doi={10.13154/tosc.v2019.i4.147-170},
  author={Shun Li and Siwei Sun and Danping Shi and Chaoyun Li and Lei Hu},
  year=2020
}