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

Abstract

S 盒是 SM4 密码算法中的重要非线性组件. 首先基于复合域理论, 将 S 盒代数表达式中有限域 GF(28) 中的运算同构到复合域 GF((24)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 门数量、总量子逻辑门数量、电路深度等相比已有结果都有较大减少.

Alternate abstract:

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 composite field GF((24)2) with an isomorphic mapping, and then the quantum circuits of the individual operations are gradually constructed and optimized using the NCT gate library, finally, a complete S-box quantum circuit is designed. To reduce the usage of Toffoli gates, the quantum circuit that uses the least number of 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 the optimized subcircuit. Third, to optimize the number of CNOT gates of the whole S-box by the idea of combining the calculations and then synthesizing. This S-box quantum circuit is implemented using the Qiskit Aer quantum simulator and its correctness is verified. After quantum resource analysis, the optimized S-box quantum circuit uses a total of 21 qubits, 10 NOT gates, 152 CNOT gates and 34 Toffoli gates, and the circuit depth is 97. Compared with the existing results, both the number of Toffoli gates, the total number of sub-logic gates and the circuit depth are greatly reduced.