SM4密码算法S盒的量子电路优化  

Quantum Circuit Optimization for SM4 Cryptographic Algorithm S-Box

作　　者：李强 罗庆斌 吕轶 郑圆梦 沈济南 LI Qiang;LUO Qing-Bin;LYU Yi;ZHENG Yuan-Meng;SHEN Ji-Nan(College of Intelligent Systems Science and Engineering,Hubei Minzu University,Enshi 445000,China;School of Information and Software Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China)

机构地区：[1]湖北民族大学智能科学与工程学院,恩施445000 [2]电子科技大学信息与软件工程学院,成都611731

出　　处：《密码学报（中英文）》2024年第2期455-465,共11页Journal of Cryptologic Research

基　　金：国家自然科学基金(62262020,12164037);湖北省自然科学基金(2020CFB326);湖北民族大学研究生科研创新资助项目(MYK2023074)。

摘　　要：S盒是SM4密码算法中的重要非线性组件.首先基于复合域理论,将S盒代数表达式中有限域GF(2^(8))中的运算同构到复合域GF((2^(4))2)中的运算,然后使用NCT门库逐步构建并优化各个运算的量子电路,最后综合出完整的S盒量子电路.为降低Toffoli门的使用量,根据GF(24)中乘法计算的代数表达式,选取使用Toffoli门最少的量子电路.为了降低CNOT门的使用量,主要从三方面优化:一是使用最优的CNOT电路综合出4阶矩阵的量子电路;二是采用置换矩阵法以及优化子电路的方式综合出8阶矩阵的量子电路;三是通过先合并计算再综合的思路优化整个S盒中CNOT门的数量.该S盒量子电路使用Qiskit Aer量子模拟器实现,并验证了其正确性.经量子资源分析,该优化的S盒量子电路一共使用了21个量子比特、10个NOT门、152个CNOT门和34个Toffoli门,电路深度为97.Toffoli门数量、总量子逻辑门数量、电路深度等相比已有结果都有较大减少.The S-box is an important nonlinear component in the SM4 cryptographic algorithm.The quantum circuit for SM4 can be designed by the following steps:Firstly,based on the composite field theory, the operations of the S-box over the finite field GF(28) are mapped to that over the compositefield GF((24)2) with an isomorphic mapping, and then the quantum circuits of the individual operationsare gradually constructed and optimized using the NCT gate library, finally, a complete S-box quantumcircuit is designed. To reduce the usage of Toffoli gates, the quantum circuit that uses the least numberof Toffoli gates is selected according to the algebraic expression of multiplicative operation over GF(24).In order to reduce the amount of CNOT gates, this paper focuses on three aspects of optimization: first,to synthesize the quantum circuit of the 4th order matrix using the optimal CNOT circuit. Second,to synthesize the quantum circuit of the 8th order matrix by using the substitution matrix and theoptimized subcircuit. Third, to optimize the number of CNOT gates of the whole S-box by the idea ofcombining the calculations and then synthesizing. This S-box quantum circuit is implemented usingthe Qiskit Aer quantum simulator and its correctness is verified. After quantum resource analysis, theoptimized S-box quantum circuit uses a total of 21 qubits, 10 NOT gates, 152 CNOT gates and 34Toffoli gates, and the circuit depth is 97. Compared with the existing results, both the number ofToffoli gates, the total number of sub-logic gates and the circuit depth are greatly reduced.

关 键 词：量子电路 SM4 S盒 复合域 优化 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]