Quantum walk based hash functions have attracted a lot of attention in recent years because of its faster execution time and robust resistance against attacks compared to classical hash functions. It has been observed that the underlying graph and the way message controls the quantum walk iteration steps play a crucial role for the robustness of the hash function. We propose a quantum hash function based on the discrete-time quantum walk on a Hanoi network--a one dimensional periodic lattice with extra long-range edges of a specific form--which is highly collision resistant. The message bits of our scheme control the flow of probability amplitude through the extra long-range edges and the conditional shift operators. Our method even works for messages with small bit-lengths, contrary to most of the quantum walk based hash functions defined on a cycle, which usually work for messages with bit-lengths more than the length of the cycle.
Quantum walk based hash functions have attracted a lot of attention in recent years because of its faster execution time and robust resistance against attacks compared to classical hash functions. It has been observed that the underlying graph and the way message controls the quantum walk iteration steps play a crucial role for the robustness of the hash function. We propose a quantum hash function based on the discrete-time quantum walk on a Hanoi network--a one dimensional periodic lattice with extra long-range edges of a specific form--which is highly collision resistant. The message bits of our scheme control the flow of probability amplitude through the extra long-range edges and the conditional shift operators. Our method even works for messages with small bit-lengths, contrary to most of the quantum walk based hash functions defined on a cycle, which usually work for messages with bit-lengths more than the length of the cycle.
Quantum hash function is an important area of interest in the field of quantum cryptography. Quantum hash function based on controlled alternate quantum walk is a mainstream branch of quantum hash functions by virtue of high efficiency and flexibility. In recent development of this kind of schemes, evolution operators determined by an input message depend on not only coin operators, but also direction-determine transforms, which usually are hard to extend. Moreover, the existing works ignore the fact that improper choice of initial parameters may cause some periodic quantum walks, and further collisions. In this paper, we propose a new quantum hash function scheme based on controlled alternate lively quantum walks with variable hash size and provide the selection criteria for coin operators. Specifically, each bit of an input message determines the magnitude of an additional long-range hop for the lively quantum walks. Statistical analysis results show excellent performance in the aspect of collision resistance, message sensitivity, diffusion and confusion property, and uniform distribution property. Our study demonstrates that a fixed coin operator, along with different shift operators, can effectively work on the design of a quantum hash function based on controlled alternate quantum walks, and shed new light on this field of quantum cryptography.
A method of constructing a quantum hash function (QHF) based on continuous-time quantum walk is proposed, in which the time of quantum walk is controlled by the binary string message, namely, a binary string message as the input of the constructed QHF and the probability value of finally walking to the nodes on the cycle is used as the output of the QHF. Numerical simulation and performance analysis show that our QHF has obvious advantages in the efficiency of the QHF compared with the existing QHF based on the discrete-time quantum walk, that is, the efficiency of our scheme is nearly 4 times faster in computing the hash value of the same size file compared with the most efficient scheme. Besides, the QHF has also better collision resistance compared with the existing QHF based on the discrete-time quantum walk.
The proposed quantum hash function (QHF) based on the discrete-time quantum walk (DTQW) structure requires enlarging the coin state space and the preparation of continuous quantum states is less difficult. Hence, a new construction method of QHF is proposed based on the continuous-time quantum walk (CTQW) of the one-dimensional (1D) lattice with boundary constraints and without additional coin space. In the scheme, the input of the QHF is an arbitrary binary string message which is used to control the selected Hamiltonian of CTQW at each time interval, and the output of the QHF is the final probability distribution of CTQW. Under the same computing environment, simulation and analysis indicate that our QHF can satisfy the same security requirements such as sensitivity, diffusion and confusion, collision, birthday attack, but the collision rate is reduced by 40% without reducing effectiveness.
We propose a new hash function QHFM based on controlled alternate quantum walks with memory on cycles, where the jth message bit decides whether to run quantum walk with one-step memory or to run quantum walk with two-step memory at the jth time step, and the hash value is calculated from the resulting probability distribution of the walker. Numerical simulation shows that the proposed hash function has near-ideal statistical performance and is at least on a par with the state-of-the-art hash functions based on quantum walks in terms of sensitivity of hash value to message, diffusion and confusion properties, uniform distribution property, and collision resistance property; and theoretical analysis indicates that the time and space complexity of the new scheme are not greater than those of its peers. The good performance of QHFM suggests that quantum walks that differ not only in coin operators but also in memory lengths can be combined to build good hash functions, which, in turn, enriches the construction of controlled alternate quantum walks.
We propose a Quantum inspired Hash Function using controlled alternate quantum walks with Memory on cycles (QHFM), where thejth message bit decides whether to run quantum walk with one-step memory or to run quantum walk with two-step memory at thejth time step, and the hash value is calculated from the resulting probability distribution of the walker. Numerical simulation shows that the proposed hash function has near-ideal statistical performance and is at least on a par with the state-of-the-art hash functions based on quantum walks in terms of sensitivity of hash value to message, diffusion and confusion properties, uniform distribution property, and collision resistance property; and theoretical analysis indicates that the time and space complexity of the new scheme are not greater than those of its peers. The good performance of QHFM suggests that quantum walks that differ not only in coin operators but also in memory lengths can be combined to build good hash functions, which, in turn, enriches the construction of controlled alternate quantum walks.
We investigate quantum walk-based hash functions, which are generated from the count distribution generated by a quantum walker on graphs. The method is expected to be one of the promising approaches for generating robust hash functions; however, the quantum computation in small systems is susceptible to spoofing via classical imitation. To address this issue, it is necessary to perform calculations in a quantum space size that classical algorithms are difficult to simulate. In such cases, simply increasing the quantum space size leads to an increase in the number of quantum circuit measurements, thereby increasing the time required to generate the ideal measurement distribution. Based on these facts, we propose a quantum hybrid algorithm combining a quantum walk with a shot-based random projection architecture. This method compresses the output into a fixed-length 256-bit hash by weighting and binarizing the measurement counts of each node. We investigate the proposed method through the numerical simulations of quantum walks on the Hanoi Network (HN4) withN=4096. The results demonstrate no hash collisions and an avalanche effect of approximately 49%, which is close to the ideal value of 50%. Additionally, we achieved the consensus robustness of up to 94%, compared to the ideal value of 100%. These results suggest the feasibility of a scalable quantum hash function for Proof of Quantum Work (PoQ) on quantum devices.