| 摘要: |
| 近年来,量子计算相关技术在不断的发展,其对传统密码算法体制产生了一定的冲击。例如,Shor算法使得基于大整数分解、求离散对数等数学问题设计的公钥密码算法不再安全。相较而言,量子计算对对称密码算法的冲击要小一些,能对对称密码算法产生威胁的攻击方法主要有两类。第一类是在经典询问的条件下,使用Grover算法进行密钥的搜索。第二类是在量子询问的条件下,使用Simon算法进行秘密信息的恢复。以上两类攻击方法,都需要用到被攻击算法所对应的量子预言机(quantumoracle)。其主要组成部分是基于Clifford+Toffoli等通用容错量子门集实现的对称密码算法的量子电路。因此密码算法量子电路的规模与攻击的复杂度密切相关。研究对称密码算法的量子电路有助于更好地量化对称密码算法抵抗量子攻击的能力。本文基于Clifford+Toffoli的量子电路模型将ZUC算法实现为量子电路,这是首次将流密码算法实现为量子电路。本文的主要目标是通过构造消耗量子比特数较少的量子电路模型,给出一个基于量子算法攻击ZUC算法的量子比特数的下界,从而说明当量子计算机能够支持的逻辑量子比特数达到何种规模时,可能会对ZUC算法产生实质性的威胁。针对此目标,本文的电路设计准则是,优先考虑减少量子比特的消耗,并在此基础上优化Toffoli门的消耗。本文针对ZUC算法的各个关键部件,如有限域GF (231-1)上的模加器,有限域GF (231-1)上的线性反馈移位寄存器以及S盒等,给出了详细的量子电路实现方案。基于这些关键组件的实现,本文给出了ZUC算法的整体量子电路实现方案。基于此方案,要实现ZUC算法的初始化过程并生成128比特的密钥流,我们需要752个量子比特,109770个Toffoli门,348117个CNOT门,以及26912个Pauli X门。 |
| 关键词: 量子密码分析 量子电路 流密码 ZUC |
| DOI：10.19363/J.cnki.cn10-1380/tn.2023.06.08 |
| 投稿时间：2020-11-17修订日期：2021-02-25 |
| 基金项目: |
|
| Implementing Quantum Circuit of ZUC Algorithm |
| SUN Zhuang,HUANG Zhenyu |
| State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China |
| Abstract: |
| In recent years, the development of quantum computing has had an impact on the classical cryptographic algorithms. Shor's algorithm makes some asymmetric cryptographic algorithms, which are based on factorization or discrete logarithm, no longer secure. On the other hand, the impact of quantum computing on symmetric cryptography algorithms is less. There are two main attck methods that can pose threats to symmetric cryptographic algorithms. The first method is using Grover's algorithm to search the key in the classical query condition. The second method is using Simon's algorithm to recover the secret information in the quantum query condition. Both of these methods need the corresponding quantum oracles of the attacked algorithm. Its main component is quantum circuits of symmetric cryptographic algorithms implemented with universal fault-tolerant quantum gate set. This makes the scales of such quantum circuits greatly influence the complexity of these attacks. Therefore, investigating the quantum circuits of symmetric cryptographic algorithms can help us quantify the resistance of symmetric cryptographic algorithms against these quantum attacks. In this paper, the stream cipher ZUC is implemented as a quantum circuit based on the “Clifford + Toffoli” quantum gate set. This is the first time that a stream cipher is implemented as a quantum circuit. By constructing this quantum circuit that consumes as few qubits as possible, we give a lower bound on the number of qubits that quantum algorithms can attack the ZUC algorithm. When the number of logical qubits that a quantum computer can support exceeds this lower bound, it may pose a substantial threat to the ZUC algorithm. According to this goal, our circuit design criterion is to consider reducing the consumption of qubits firstly, and on this basis to optimize the consumption of Toffoli gates. we give detailed quantum circuit design for each key component of ZUC, such as the modulo adder over the finite field GF(231-1), the linear feedback shift register over GF(231-1), and the S-boxes. Based on the quantum circuits of these components, we present the overall quantum circuit design of ZUC. According to the design in this paper, 752 qubits, 109770 Toffoli, 348117 CNOT, and 26912 Pauli X gates are needed for ZUC to complete its initialization process and generate 128-bit keystream. |
| Key words: quantum cryptanalysis quantum circuit stream cipher ZUC |
