Efficient quantum circuit research and implementation for 16-bit S-boxes based on composite field
摘要
With the development of quantum computing technology, efficiently implementing the core component S-box of block ciphers in quantum environments has become an important research direction in the field of cryptographic engineering. Due to the limitations of the no-cloning theorem of quantum states, the implementation of S-boxes in quantum circuits faces the dual challenges of exponential growth in space complexity and excessive consumption of quantum resources, especially in 16-bit and larger S-boxes. To address these problems, this paper proposes a construction framework for 16-bit S-box quantum circuits based on composite fields. This method relies on normal bases representation to construct composite field structures, decomposing high-dimensional multiplicative inverse into low-dimensional subdomain operations through isomorphic mapping, thereby significantly reducing the quantum cost of nonlinear component. In the linear component, a dynamic optimal pivot selection strategy is proposed to effectively optimize the Gaussian elimination process while maintaining the row echelon form of the matrix, thereby reducing the number of CNOT gates. Taking the 16-bit S-box in the MK-3 algorithm as an example, experimental results show that the proposed method maintains correct circuit structure while reducing CNOT gate consumption in the linear component by more than 32.8%, and the utilization of quantum resources in the nonlinear component is more advantageous. This study provides theoretical support and an implementation path for the high-performance implementation of block ciphers in practical quantum computing environments.