具有最小异或数的最大距离可分矩阵的构造

陈少真; 张怡帆; 任炯炯

doi:10.11999/JEIT181113

具有最小异或数的最大距离可分矩阵的构造

doi: 10.11999/JEIT181113

1.
解放军信息工程大学郑州 450001
2.
数学工程与先进计算国家重点实验室郑州 450001

基金项目: 信息保障技术重点实验室开放基金(KJ-17-002)，国家密码发展基金(MMJJ20180203)，数学工程与先进计算国家重点实验室开放基金(2018A03)

详细信息

作者简介:
陈少真：女，1967年生，教授，研究方向为密码学信息安全

张怡帆：女，1993年生，硕士生，研究方向为信息安全

任炯炯：男，1994年生，博士生，研究方向为信息安全

通讯作者:
张怡帆　zhangyifan_fan@163.com

中图分类号: TP309
计量
- 文章访问数: 2604
- HTML全文浏览量: 1184
- PDF下载量: 88
- 被引次数: 0
出版历程
- 收稿日期: 2018-12-03
- 修回日期: 2019-05-31
- 网络出版日期: 2019-06-12
- 刊出日期: 2019-10-01

Constructions of Maximal Distance Separable Matrices with Minimum XOR-counts

1.
PLA Information Engineering University, Zhengzhou 450001, china
2.
State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, china

Funds: The Foundation of Science and Technology on Information Assurance Laboratory (KJ-17-002), The National Cipher Development Foundation (MMJJ20180203), The State Key Laboratory of Mathematical Engineering and Advanced Computation Open Foundation (2018A03)

摘要

摘要: 随着物联网等普适计算的发展，传感器、射频识别(RFID)标签等被广泛使用，这些微型设备的计算能力有限，传统的密码算法难以实现，需要硬件效率高的轻量级分组密码来支撑。最大距离可分(MDS)矩阵扩散性能最好，通常被用于构造分组密码扩散层，异或操作次数(XORs)是用来衡量扩散层硬件应用效率的一个指标。该文利用一种能更准确评估硬件效率的XORs计算方法，结合一种特殊结构的矩阵—Toeplitz矩阵，构造XORs较少效率较高的MDS矩阵。利用Toeplitz矩阵的结构特点，改进矩阵元素的约束条件，降低矩阵搜索的计算复杂度，在有限域${\mathbb{F}_{{2^8}}}$上得到了已知XORs最少的4×4MDS矩阵和6×6MDS矩阵，同时还得到XORs等于已知最优结果的5×5MDS矩阵。该文构造的具有最小XORs的MDS Toeplitz矩阵，对轻量级密码算法的设计具有现实意义。
- 分组密码 /
- 轻量级扩散层 /
- 最大距离可分矩阵 /
- 异或数 /
- Toeplitz矩阵
Abstract: With the development of the internet of things, small-scale communication devices such as wireless sensors and the Radio Frequency IDentification(RFID) tags are widely used, these micro-devices have limited computing power, so that the traditional cryptographic algorithms are difficult to implement on these devices. How to construct a high-efficiency diffusion layer becomes an urgent problem. With the best diffusion property, the Maximal Distance Separable (MDS) matrix is often used to construct the diffusion layer of block ciphers. The number of XOR operations (XORs) is an indicator of the efficiency of hardware applications. Combined with the XORs calculation method which can evaluate hardware efficiency more accurately and a matrix with special structure——Toeplitz matrix, efficient MDS matrices with less XORs can be constructed. Using the structural characteristics of the Toeplitz matrix, the constraints of matrix elements are improved, and the complexity of matrices searching is reduced. The 4×4 MDS matrices and the 6×6 MDS matrices with the least XORs in the finite field ${\mathbb{F}_{{2^8}}}$ are obtained, and the 5×5 MDS matrices with the XORs which are equal to the known optimal results are obtained too. The proposed method of constructing MDS Toeplitz matrices with the least XORs has significance on the design of lightweight cryptographic algorithms.
- Block cipher /
- Lightweight diffusion layers /
- Maximal Distance Separable(MDS) matrices /
- XOR-counts /
- Toeplitz matrices

HTML全文

表 1 本文构造结果与已知结果对比

矩阵维度	不可约多项式	矩阵实例${\text{M}}$	$C\left( {\text{M}} \right)$	文献
$4 \times 4$	${x^8} + {x^6} + {x^5} + x + 1$	${\rm{Toep}}\left( {1,1,{x^2},1,{x^{ - 1}},x,{x^2}} \right)$	20	本文
$4 \times 4$	${x^8} + {x^6} + {x^5} + x + 1$	${\rm{Circ}}\left( {1,1,x,{x^{ - 2}}} \right)$	24	文献[12]
$4 \times 4$	${x^8} + {x^7} + {x^6} + x + 1$	${\rm{Toep}}\left( {1,1,x,{x^{ - 1}},{x^{ - 2}},1,{x^{ - 1}}} \right)$	27	文献[12]
$4 \times 4$	${x^8} + {x^7} + {x^6} + x + 1$	${\rm{Left - Circ}}\left( {1,1,x,{x^{ - 2}}} \right)$	32	文献[14]
$4 \times 4$	${x^8} + {x^7} + {x^6} + x + 1$	${\rm{Had}}\left( {1,x,{x^2},{x^{ - 2}}} \right)$	52	文献[12]
$5 \times 5$	${x^8} + {x^6} + {x^5} + x + 1$	${\rm{Toep}}\left( {1,{x^2},1,{x^{ - 1}},{x^{ - 1}},{x^{ - 1}},{x^{ - 1}},1,{x^2}} \right)$	40	本文
$5 \times 5$	${x^8} + {x^6} + {x^5} + x + 1$	${\rm{Circ}}\left( {1,1,x,{x^{ - 2}},x} \right)$	40	文献[12]
$5 \times 5$	${x^8} + {x^7} + {x^6} + x + 1$	${\rm{Left - Circ}}\left( {1,1,x,{x^{ - 2}},x} \right)$	55	文献[14]
$6 \times 6$	${x^8} + {x^6} + {x^5} + x + 1$	${\rm{Toep}}\left( {1,x,x,1,{x^{ - 2}},{x^2},{x^{ - 2}},{x^2},{x^{ - 2}},1,x} \right)$	80	本文
$6 \times 6$	${x^8} + {x^6} + {x^5} + x + 1$	${\rm{Circ}}\left( {1,x,{x^{ - 1}},{x^{ - 2}},1,{x^3}} \right)$	84	文献[12]
$6 \times 6$	${x^8} + {x^7} + {x^6} + x + 1$	${\rm{Left - Circ}}\left( {1,x,{x^{ - 1}},{x^{ - 2}},1,{x^3}} \right)$	108	文献[14]

下载: 导出CSV

参考文献(15)

BIHAM E and SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[J]. Journal of Cryptology, 1991, 4(1): 3–72. doi: 10.1007/BF00630563

MATSUI M. Linear cryptanalysis method for DES cipher[C]. Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, 1993: 386–397.

SHIRAI T, SHIBUTANI K, AKISHITA T, et al. The 128-bit blockcipher CLEFIA (extended abstract)[C]. The 14th International Workshop on Fast Software Encryption, Luxembourg, Luxembourg, 2007: 181–195.

BOGDANOV A, KNUDSEN L R, LEANDER G, et al. PRESENT: An ultra-lightweight block cipher[C]. The 9th International Workshop on Cryptographic Hardware and Embedded Systems, Vienna, Austria, 2007: 450–466.

GUO Jian, PEYRIN T, POSCHMANN A, et al. The LED block cipher[C]. The 13th International Workshop on Cryptographic Hardware and Embedded Systems, Nara, Japan, 2011: 326–341.

YANG Gangqiang, ZHU Bo, SUDER V, et al. The SIMECK family of lightweight block ciphers[C]. The 17th International Workshop on Cryptographic Hardware and Embedded Systems, Saint-Malo, France, 2015: 307–329.

SIM S M, KHOO K, OGGIER F, et al. Lightweight MDS involution matrices[C]. The 22nd International Workshop on Fast Software Encryption, Istanbul, Turkey, 2015: 471–493.

LIU Meicheng and SIM S M. Lightweight MDS generalized circulant matrices[C]. The 23rd International Conference on Fast Software Encryption, Bochum, Germany, 2016: 101–120.

LI Yongqiang and WANG Mingsheng. On the construction of lightweight circulant involutory MDS matrices[C]. The 23rd International Conference on Fast Software Encryption, Bochum, Germany, 2016: 121–139.

SARKAR S and SYED H. Lightweight diffusion layer: Importance of Toeplitz matrices[J]. IACR Transactions on Symmetric Cryptology, 2016, 2016(1): 95–113. doi: 10.13154/tosc.v2016.i1.95-113

JEAN J, PEYRIN T, SIM S M, et al. Optimizing implementations of lightweight building blocks[J]. IACR Transactions on Symmetric Cryptology, 2017, 2017(4): 130–168. doi: 10.13154/tosc.v2017.i4.130-168

BEIERLE C, KRANZ T, and LEANDER G. Lightweight multiplication in GF(2ⁿ) with applications to MDS matrices[C]. The 36th Annual International Cryptology Conference, Santa Barbara, USA, 2016: 625–653.

SARKAR S and SYED H. Analysis of Toeplitz MDS matrices[C]. The 22nd Australasian Conference on Information Security and Privacy, Auckland, New Zealand, 2017: 3–18.

KHOO K, PEYRIN T, POSCHMANN A Y, et al. FOAM: Searching for hardware-optimal SPN structures and components with a fair comparison[C]. The 16th International Workshop on Cryptographic Hardware and Embedded Systems, Busan, South Korea, 2014: 433–450.

JUNOD P and VAUDENAY S. Perfect diffusion primitives for block ciphers[C]. The 11th International Workshop on Selected Areas in Cryptography, Waterloo, Canada, 2004: 84–99.

施引文献

资源附件(0)

访问统计