An efficient quantum implementation of the advanced encryption standard (AES) is crucial for reducing the complexity of implementing an exhaustive key search through Grover’s algorithm. In this paper, we study how to construct resource-efficient quantum circuits for AES. We consider the product of T-gates depth and width (TDW) and the product of full depth and width (FDW) as optimization targets. We propose a generic method, called the controlled control qubit cascade (CCQC) technique, to construct quantum circuits for nonlinear components with reduced TDW and FDW. Using this, we construct a quantum circuit for the AES S-box. Compared with recent work presented at ASIACRYPT 2023, our S-box quantum circuit achieves reductions of 2.3% in TDW and 45.2% in FDW. Additionally, we propose a new key schedule strategy to reduce the full depth of the AES quantum circuit. Finally, the trade-offs between T-gates depth and width and the parallel numbers of S-box and TDW are analyzed.
Between NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation, we propose a scheme to achieve a provable superpolynomial quantum advantage (under some widely accepted complexity conjectures) that is robust to noise with minimal error correction requirements. We choose a class of sampling problems with commuting gates known as sparse IQP (Instantaneous Quantum Polynomial-time) circuits and we ensure its fault-tolerant implementation by introducing the tetrahelix code. This new code is obtained by merging several tetrahedral codes (3D color codes) and has the following properties: each sparse IQP gate admits a transversal implementation, and the depth of the logical circuit can be traded for its width. Combining those, we obtain a depth-1 implementation of any sparse IQP circuit up to the preparation of encoded states. This comes at the cost of a space overhead which is only polylogarithmic in the width of the original circuit. We furthermore show that the state preparation can also be performed in constant depth with a single step of feed-forward from classical computation. Our construction thus exhibits a robust superpolynomial quantum advantage for a sampling problem implemented on a constant depth circuit with a single round of measurement and feed-forward.
A lot of work in the field of quantum cryptanalysis is currently devoted to finding applications of Grover-meets-Simon algorithm and its complexity is given in the form ofO, but research on how to implement the attack efficiently is still insufficient. After all, it is crucial to study quantum attacks in resource-limited situations, according to NIST’s guidance on circuit depth. This work first evaluates the parallelization of Grover-meets-Simon by drawing on the Grover’s parallel approach and shows that as the width increases by2t(t>0), the depth decreases by a factor of2t. Further, the first dedicated quantum attack on a class of functions that appear in cryptographic scheme applications (so-called XOR-type function) is proposed. The depth, width, and the number of gates required for the attack are greatly reduced compared to the general parallelization. Then we apply the attack to various Beyond-Birthday-Bound (BBB) MACs, where the XOR function can be constructed, includingSUM-ECBCand its variants (2K-SUM-ECBC,2K-ECBC_Plus), andGCM-SIV2. In the typical case whereSUM-ECBCis based on AES-128, our attack saves at least 62.3% in depth, 19.5% in width and 22.2% in gate count simultaneously. The impact on some lightweight ciphers is further explored, and it is interesting to note that the lighter the quantum circuit implementation of the cipher is, the greater the possible impact of an attack will be. This observation may provide new insights into quantum cryptanalysis.