This paper presents a novel approach to optimizing the linear layer of block ciphers using the matrix decomposition framework. It is observed that the reduction properties proposed by Xiang et al. (in FSE 2020) need to be improved. To address these limitations, we propose a new reduction framework with a complete reduction algorithm and swapping algorithm. Our approach formulates matrix decomposition as a new framework with an adaptive objective function and converts the problem to a Graph Isomorphism problem (GI problem). Using the new reduction algorithm, we were able to achieve lower XOR counts and depths of quantum implementations under the s-XOR metric. Our results outperform previous works for many linear layers of block ciphers and hash functions; some of them are better than the current g-XOR implementation. For the AES MixColumn operation, we get two implementations with 91 XOR counts and depth 13 of in-place quantum implementation, respectively.
This paper presents a novel approach to optimizing the linear layer of block ciphers using the matrix decomposition framework. It is observed that the reduction properties proposed by Xiang et al. (in FSE 2020) need to be improved. To address these limitations, we propose a new reduction framework with a complete reduction algorithm and swapping algorithm. Our approach formulates matrix decomposition as a new framework with an adaptive objective function and converts the problem to a Graph Isomorphism problem (GI problem). Using the new reduction algorithm, we were able to achieve lower XOR counts and depths of quantum implementations under the s-XOR metric. Our results outperform previous works for many linear layers of block ciphers and hash functions; some of them are better than the current g-XOR implementation. For the AES MixColumn operation, we get two implementations with 91 XOR counts and depth 13 of in-place quantum implementation, respectively.
In this paper, we consider the problem of quantum implementation of the symmetric-key ciphers. The typical ciphers in this category have two main components, the linear and the non-linear layers, we consider both. The linear layer can be described as a non-singular matrix over binary operations. The in-place implementation is one of the main considerations for implementing such layer to minimize the number of qubits. We discuss the research works that have been done to this point on this subject matter and report the improved implementation of some of the matrices. Lists of our modifications include; making it more efficient (specially for the larger matrices), consideration for quantum depth (along with a randomized algorithm for optimization), etc. We report benchmarks for the ASCON and SHA-2 linear matrices. As for the non-linear layer, the constituent block is called an substitution box (an S-box, for short). Our “DORCIS” tool presented in this paper, finds a quantum circuit with an optimized depth for given S-boxes of size 3- and 4-bit. It is a follow-up work on LIGHTER-R (which is applicable for 4-bit S-boxes only) with multiple extensions. Unlike LIGHTER-R, our DORCIS takes a quantum decomposition based on Clifford and T gates. Also, both the full quantum depth and the T depth can be optimized by DORCIS. We compare our implementation with other optimized quantum circuits shown in the other research works and show that we find an implementation with the same cost metric, or find an implementation with lower cost metric, compared other tools proposed in the literature, apart from being simpler and more efficient.
In this paper, we propose a novel approach for optimizing the linear layer used in symmetric cryptography. It is observed that these matrices often have circulant structure. The basic idea of this work is to utilize the property to construct a sequence of transformation matrices, which allows subsequent heuristic algorithms to find more efficient implementations. Our results outperform previous works for various linear layers of block ciphers. For Whirlwind M0 , we obtain two implementations with 159 XOR counts (8% better than Yuan et al. at FSE 2025) and depth 17 (39% better than Shi et al. at AsiaCrypt 2024) respectively. For AES MixColumn, our automated method produces a quantum circuit with depth 10, which nearly matches the manually optimized state-of-the-art result by Zhang et al. at IEEE TC 2024, only with 2 extra CNOTs.
Abstract In this work we propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms formulated in the circuit model of computation onto specific quantum hardware. Our approach decomposes the routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. Extracting the allocation part from the qubit routing model of Nannicini et al. (Optimal qubit assignment and routing via integer programming, 2021, http://arxiv.org/abs/2106.06446 ), we formulate the allocation subproblem as a binary linear program. Herein, we employ a cost function that is a lower bound on the overall routing problem objective. We strengthen the linear relaxation by novel valid inequalities. For the token swapping part we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm which runs much faster than the exact approach and typically is able to determine solutions close to the optimum. We present numerical results for the fully integrated allocation and token swapping problem. Obtained solutions may not be globally optimal due to the decomposition and the usage of an approximation algorithm. However, the solutions are obtained fast and are typically close to optimal. In addition, there is a significant reduction in the number of artificial gates and output circuit depth when compared to various state-of-the-art heuristics. Reducing these figures is crucial for minimizing noise when running quantum algorithms on near-term hardware. As a consequence, using the novel decomposition approach leads to compiled algorithms with improved quality. Indeed, when compiled with the novel routing procedure and executed on real hardware, our experimental results for quantum approximate optimization algorithms show an significant increase in solution quality in comparison to standard routing methods.
We aim to advance the state-of-the-art in Quadratic Unconstrained Binary Optimization formulation with a focus on cryptography algorithms. As the minimal QUBO encoding of the linear constraints of optimization problems emerges as the solution of integer linear programming (ILP) problems, by solving special boolean logic formulas (like ANF and DNF) for their integer coefficients it is straightforward to handle any normal form, or any substitution for multi-input AND, OR or XOR operations in a QUBO form. To showcase the efficiency of the proposed approach we considered the most widespread cryptography algorithms including AES-128/192/256, MD5, SHA1 and SHA256. For each of these, we achieved QUBO instances reduced by thousands of logical variables compared to previously published results, while keeping the QUBO matrix sparse and the magnitude of the coefficients low. In the particular case of AES-256 cryptography function we obtained more than 8x reduction in variable count compared to previous results. The demonstrated reduction in QUBO sizes notably increases the vulnerability of cryptography algorithms against future quantum annealers, capable of embedding around 30 thousands of logical variables.
This paper introduces a novel approach to quantum algorithm design, focusing on the implementation of matrix multiplication through an adaptive linear matrix decomposition (ALM) framework. The core principle of this algorithm leverages quantum entanglement and superposition to achieve enhanced computational efficiency, specifically designed to optimize matrix multiplication operations. We demonstrate the effectiveness of this design through theoretical analysis and preliminary experiments, showcasing significant performance improvements over existing quantum algorithms for matrix multiplication. The study highlights the potential of ALM to unlock new capabilities in quantum computation, offering a pathway towards more robust and scalable quantum algorithms.
A quantum computer capable of running the Grover search algorithm, which reduces the complexity of brute-force attacks by a square root, has the potential to undermine the security strength of symmetric-key cryptography and hash functions. Recently, studies on quantum approaches have proposed analyzing potential quantum attacks using the Grover search algorithm in conjunction with optimized quantum circuit implementations for symmetric-key cryptography and hash functions. Analyzing quantum attacks on a cipher (i.e., quantum cryptanalysis) and estimating the necessary quantum resources are related to evaluating post-quantum security for the target cryptography algorithms. In this paper, we revisit quantum implementations of CHAM block cipher, an ultra lightweight cipher, with a focus on optimizing the linear operations in its key schedule. We optimized the linear equations of CHAM as matrices by applying novel optimized decomposition techniques. Using the improved CHAM quantum circuits, we estimate the cost of Grover’s key search and evaluate the post-quantum security strength with further reduced costs.