Lightweight Iterative MDS Matrices: How Small Can We Go?
Lightweight Iterative MDS Matrices: How Small Can We Go?
复制标题
轻量级迭代 MDS 矩阵：我们能做到多小？
DOI：
10.13154/tosc.v2019.i4.147-170
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Lei Hu
中科院分区：
文献类型：
--
作者：
Shun Li;Siwei Sun;Danping Shi;Chaoyun Li;Lei Hu
作为许多密钥原语的扩散层的完美构建块，具有轻量级电路的MDS矩阵的构造受到了密钥社区的广泛关注。实现低成本MDS矩阵的一种有前途的方法是基于迭代构造：低成本矩阵在提升到一定幂后成为MDS。更具体地说，如果At是MDS，那么可以实现A而不是At来实现MDS属性，但代价是t个时钟周期的延迟增加。在这项工作中，我们确定了一个4 × 4块矩阵的非零块的数目的确切下界是潜在的迭代MDS。随后，我们证明了理论上最轻的4 × 4迭代MDS分块矩阵（其元素或分块是4 × 4二元矩阵）具有最少的非零分块，至少需要3个异或门，并提供了一个实现3-异或界的具体例子。此外，我们证明了以前的结构（GFS，LFS，DSI和备件DSI）没有希望击败这个界限。由于电路延迟是另一个重要因素，我们还考虑了某些迭代MDS矩阵的迭代次数的下界。在这些界限的指导下，并根据用于识别它们的思想，我们探索了轻量级迭代MDS矩阵与其他维度的设计空间，并报告了改进的结果。当我们无法找到更好的结果时，我们试图确定最优解的范围。结果证明了已有结果的最优性。
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.
登录
查看更多内容
影响因子：
3.5
作者：
Avanzi, Roberto
通讯作者：
Avanzi, Roberto
影响因子：
--
作者：
Siang Meng Sim;Khoongming Khoo;F. Oggier;Thomas Peyrin
通讯作者：
Siang Meng Sim;Khoongming Khoo;F. Oggier;Thomas Peyrin
DOI：
10.1109/18.746771
发表时间：
1999
期刊：
IEEE Trans. Inf. Theory
影响因子：
--
作者：
M. Blaum;R. Roth
通讯作者：
M. Blaum;R. Roth
DOI：
10.1007/978-3-540-85238-4_13
发表时间：
2008-08
期刊：
--
影响因子：
--
作者：
J. Boyar;Philip Matthews;R. Peralta
通讯作者：
J. Boyar;Philip Matthews;R. Peralta
DOI：
10.1007/978-3-319-03515-4_18
发表时间：
2013-12
期刊：
--
影响因子：
--
作者：
T. Berger
通讯作者：
T. Berger