Abstract It is assumed that the attacker obtains an error-containing noisy key through side-channel attacks, and the probability distribution of the key space follows a \((n)\)-fold Bernoulli distribution. We investigate the key search problem of cryptographic algorithms in the scenario of side-channel attacks. The main contributions of this study are summarized as follows: First, the computational complexity of the classical key search algorithm in the scenario of side-channel attacks is derived. Second, a quantum key search algorithm is designed based on Grover’s algorithm and Montanaro's algorithm. By leveraging the \((n)\)-fold Bernoulli distribution, the key space partition strategy is determined, different from Montanaro's algorithm, thus developing an improved quantum key search algorithm; the computational complexity of this improved algorithm is further analyzed. Simulation results show that the proposed quantum key search algorithm can achieve a super-quadratic speedup over the classical counterpart under side-channel attack conditions. Taking a 256-bit cryptographic key as an example (1% BER), the query complexity decreases from \((2^{256})\) for the conventional classical algorithm to \((2^{62.29})\) with side-channel attacks, and is further reduced from Glaser's \((2^{21.59})\) to \((2^{19.77})\) by our quantum algorithm. Correspondingly, the speedup factor of the proposed quantum algorithm relative to the classical algorithm under side-channel attack conditions reaches 3.15, while the speedup factor reported by Glaser is only 2.73 under the same conditions. Third, to address the difficulty of input state preparation in the our quantum algorithm, we transform the problem of input state preparation into the preparation of the Dicke state. The Dicke state can be implemented by \((O(nd))\) CNOT gates with \((O\left(d \log \frac{n}{d}\right))\) circuit depth for ion trap topology (or \((O\left(\sqrt{nd}\right))\) circuit depth for superconducting topology) in short-depth quantum circuits, and the input state of our algorithm only need to add \((O(d))\) \((X)\)-gates based on the Dicke state.
Abstract It is assumed that the attacker obtains an error-containing noisy key through side-channel attacks, and the probability distribution of the key space follows a ((n))-fold Bernoulli distribution. We investigate the key search problem of cryptographic algorithms in the scenario of side-channel attacks. The main contributions of this study are summarized as follows: First, the computational complexity of the classical key search algorithm in the scenario of side-channel attacks is derived. Second, a quantum key search algorithm is designed based on Grover’s algorithm and Montanaro's algorithm. By leveraging the ((n))-fold Bernoulli distribution, the key space partition strategy is determined, different from Montanaro's algorithm, thus developing an improved quantum key search algorithm; the computational complexity of this improved algorithm is further analyzed. Simulation results show that the proposed quantum key search algorithm can achieve a super-quadratic speedup over the classical counterpart under side-channel attack conditions. Taking a 256-bit cryptographic key as an example (1% BER), the query complexity decreases from ((2^{256})) for the conventional classical algorithm to ((2^{62.29})) with side-channel attacks, and is further reduced from Glaser's ((2^{21.59})) to ((2^{19.77})) by our quantum algorithm. Correspondingly, the speedup factor of the proposed quantum algorithm relative to the classical algorithm under side-channel attack conditions reaches 3.15, while the speedup factor reported by Glaser is only 2.73 under the same conditions. Third, to address the difficulty of input state preparation in the our quantum algorithm, we transform the problem of input state preparation into the preparation of the Dicke state. The Dicke state can be implemented by ((O(nd))) CNOT gates with ((O\left(d \log \frac{n}{d}\right))) circuit depth for ion trap topology (or ((O\left(\sqrt{nd}\right))) circuit depth for superconducting topology) in short-depth quantum circuits, and the input state of our algorithm only need to add ((O(d))) ((X))-gates based on the Dicke state.
Side-channel attacks on block ciphers rarely recover the key outright: they leave a residual key space ordered by subkey posteriors, and evaluation laboratories report the key rank of the true key against thresholds near 2^48 and 2^60. No evaluation framework models an adversary who collects traces classically and finishes the search on a quantum computer, although quantum search with advice provides exactly that. We give such an adversary a cost model and a metric. For a device whose key has rank r, any quantum algorithm with classical access to the posteriors needs Omega(sqrt(r)) cipher evaluations, and block search achieves O(sqrt(r)); the per-instance advantage is exactly quadratic, and the super-quadratic exponents reported for search with advice are averages over the prior that apply to no single device. Under the NIST MAXDEPTH budget D and a Grover iteration of g gates and depth d, the quadratic advantage holds only for ranks up to (4D/(pi d))^2 and collapses to a constant factor beyond; with the best published AES-128 oracle and D = 2^40 the window closes near rank 2^58.6. We define the quantum-aware key rank, the classical rank of equal cost, computable from the rank estimators laboratories already run, and derive the classical rank a device must retain to keep a given threshold against each depth budget. Block search and amplitude amplification from the product-form posterior state are within a factor of two to four of each other on Hamming-weight posteriors, so the cost of coherent indexing decides between them. Experiments on simulated leakage and a toy cipher confirm the predicted window: at SNR 0.125 a depth-limited quantum adversary is worth about 22 traces to a classical one, however large its gate budget.
Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.
Compared with electronic computers, quantum parallelism has led to a significant increase in the computing power of quantum computers.However, the computing power of quantum computers will also be limited by the laws of physics, and hence there is no doubt that the computing power of quantum computers is not unlimited.For an algorithm, we need to consider both its space complexity and time complexity.This not only requires quantum computers to achieve large-scale integration, but also requires the quantum coherence time to be sufficiently long.If either of the above two conditions is not met, the task cannot be completed.Shor's algorithm [1] reduced the computational complexity of large integer factorization to the polynomial level.This complexity is of the same order as that of the encryption and decryption for the RSA public key cryptography protocol, which leads to the insecurity of the RSA in universal quantum computing.In addition, some other quantum algorithms show different kinds of enhanced speeds for solving different problems, such as the Grover's search algorithm [2] and its improved works [ 3 , 4 ], and the HHL algorithm [5] .With the remarkable computational power of these quantum algorithms, physicists have begun to seek suitable physical systems for the implementation of quantum computing.The implementation of quantum computing includes several basic technologies, such as preparation, precise control, measurement of the physical qubits, and construction of logical qubits.At present, there are many experimental candidate quantum computing platforms, including the superconducting system [6] , trapped ions system [7] , nitrogenvacancy centers in diamonds [8] , and ultra-cold atoms [9] .Recently, Google experimentally demonstrated quantum supremacy with a superconducting quantum computer [10] , thus placing the research on quantum computing at the forefront.With the booming development of quantum computing technology, the public key cryptosystem also needs to be updated periodically.Thus, cryptographers have to constantly look for public key protocols to resist quantum computing attacks, which leads to the emergence of postquantum cryptography.It is worth noting that although the name of post-quantum cryptography contains the word 'quantum', it essentially consists of protocols of classical cryptography.The current research on post-quantum cryptography mainly includes protocols based on the following four frameworks: the protocols based on Hash function, the pro- * Corresponding author.
Grover's quantum search algorithm provides a quadratic speedup over the classical one. The computational complexity is based on the number of queries to the oracle. However, depth is a more modern metric for noisy intermediate-scale quantum computers. We propose a depth optimization method for the quantum search algorithm. We show that Grover's algorithm is not optimal in depth. We propose a quantum search algorithm, which can be divided into several stages. Each stage has a new initialization, which is a rescaling of the database. This decreases errors. The multistage design is natural for parallel running of the quantum search algorithm.
We study the fundamental problem of guessing cryptographic keys, drawn from some non-uniform probability distribution D, as e.g. in LPN, LWE or for passwords. The optimal classical algorithm enumerates keys in decreasing order of likelihood. The optimal quantum algorithm, due to Montanaro (2011), is a sophisticated Grover search. We give the first tight analysis for Montanaro's algorithm, showing that its runtime is 2H2/3(D)/2, where Hα(⋅) denotes Renyi entropy with parameter α. Interestingly, this is a direct consequence of an information theoretic result called Arikan's Inequality (1996) -- which has so far been missed in the cryptographic community -- that tightly bounds the runtime of classical key guessing by 2H1/2(D). Since H2/3(D)<H1/2(D) for every non-uniform distribution D, we thus obtain a super-quadratic quantum speed-up s>2 over classical key guessing. As another main result, we provide the first thorough analysis of guessing in a multi-key setting. Specifically, we consider the task of attacking many keys sampled independently from some distribution D, and aim to guess a fraction of them. For product distributions D=χn, we show that any constant fraction of keys can be guessed within 2H(D) classically and 2H(D)/2 quantumly per key, where H(χ) denotes Shannon entropy. In contrast, Arikan's Inequality implies that guessing a single key costs 2H1/2(D) classically and 2H2/3(D)/2 quantumly. Since H(D)<H2/3(D)<H1/2(D), this shows that in a multi-key setting the guessing cost per key is substantially smaller than in a single-key setting, both classically and quantumly.
In this work we first examine the hardness of solving various search problems by hybrid quantum-classical strategies, namely, by algorithms that have both quantum and classical capabilities. We then construct a hybrid quantum-classical search algorithm and analyze its success probability. Regarding the former, for search problems that are allowed to have multiple solutions and in which the input is sampled according to arbitrary distributions we establish their hybrid quantum-classical query complexities -- i.e., given a fixed number of classical and quantum queries, determine what is the probability of solving the search task. At a technical level, our results generalize the framework for hybrid quantum-classical search algorithms proposed by Rosmanis. Namely, for an arbitrary distribution D on Boolean functions, the probability an algorithm equipped with τc classical and τq quantum queries succeeds in finding a preimage of 1 for a function sampled from D is at most νD⋅(2τc+2τq+1)2, where νD captures the average (over D) fraction of preimages of 1. As applications of our hardness results, we first revisit and generalize the security of the Bitcoin protocol called the Bitcoin backbone, to a setting where the adversary has both quantum and classical capabilities, presenting a new hybrid honest majority condition necessary for the protocol to properly operate. Secondly, we examine the generic security of hash functions against hybrid adversaries. Regarding our second contribution, we design a hybrid algorithm which first spends all of its classical queries and in the second stage runs a ``modified Grover'' where the initial state depends on the distribution D. We show how to analyze its success probability for arbitrary target distributions and, importantly, its optimality for the uniform and the Bernoulli distribution cases.