Quantum-inspired Hash Function Based on Parity-dependent Quantum Walks with Memory (August 2023)

Cryptographic hash function acts as a key component of identification, message authentication, digital signatures, and pseudorandom number generation. From a security perspective, cryptographic hash functions can be divided into two broad categories: provably secure hash functions based on hard mathematical problems and dedicated hash functions based on ad-hoc constructions, especially iterative constructions of one-way compression functions. The former only satisfy computational security and are inefficient to be used in practice; the latter are efficiently computable, but the security of which is not built on a firm foundation.

To develop a secure and efficient hash function, more and more researchers have shown interests in hash functions based on quantum computing [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], especially on discrete quantum walks [1, 2, 5, 6, 7, 8, 9, 10, 11, 12] (hereafter, simply DQW-based hash functions). The security of this kind of hash functions is based on quantum mechanics; more precisely, it is ensured by the theoretically infinite possibilities of the initial state and the irreversibility of modulo operation [7]. The output results of DQW-based hash functions are more attainable by classical simulation of the quantum walk process, where the final amplitudes can be calculated with linear overhead with respect to the number of steps. For this reason, a DQW-based hash function can be considered as a “quantum inspired” algorithm, where everything is calculated classically using some desired properties of a quantum system and its dynamics. In what follows, hash schemes constructed by simulating discrete quantum walks and then calculating hash values from the resulting probability distributions are called DQW-based hash functions or quantum inspired hash functions interchangeably.

Quantum inspired hash functions was first explored by Li et al. in [12], and further intensively discussed by Cao et al. in [10], Yang et al. in [5, 6, 7, 8, 11], and zhou et al. in [1]. Until Zhou et al.’s scheme (called QHFM) [1], all quantum inspired hash functions simply use quantum walks with different coin parameters, where only the coin operator is controlled by the message bit. QHFM is based on quantum walks with memory, where an additional changeable transform—the direction-determine operator is also controlled by the message bit. More recently, Hou et al. [2] has proposed a hash function QHFL based on lively quantum walks, where the shift operator contains a liveliness parameter, whose value (one out of two) is determined by the message bit. The good statistical performance of QHFM and QHFL suggests that combining quantum walks differing in component operators other than coin transform is a promising way to construct good hash functions.

Quantum walks with memory (QWM) [13, 14, 15, 16, 17, 18, 19, 20, 21, 22] are types of modified quantum walks where the next direction of the walking particle is governed by the direction-determine operator, which specifies how the latest path together with the coin state affects the movement direction of the particle; different QWM models have different direction-determine operators. Unlike usual quantum walks without memory [23] or lively quantum walks [2], where the changeable operator (the coin or shift operator) can be characterized by a single parameter, the direction-determine operator of QWM is highly flexible. It is influenced by two factors: the memory length and the movement rule, the latter can be an arbitrary relation between the movement direction and the recorded shifts of the walker, which cannot simply be dictated by a few parameters. Hence, QWM have great potential to be used to construct various quantum-inspired hash functions.

Here, we present an alternative QWM-based hash function QHFM-P, which is inspired by quantum walks with memory provided by parity of memory [15]. The proposed hash function is on a par with the state-of-the-art DQW-based hash functions in terms of sensitivity of hash value to message, diffusion and confusion properties, uniform distribution property, collision resistance property, and computational complexity. Furthermore, it can preserve near-ideal statistical performance when changing the values of its coin parameters, indicating that QHFM-P has nice stability with respect to different coin angles.

One-dimensional quantum walks with $m$-step memory depending on the parity of memory (QWM-P), or parity-dependent quantum walks with $m$-step memory on the line [15], is a quantum system living in a Hilbert space $\mathcal{H}_{p}\otimes\mathcal{H}_{d_{m}}\otimes\cdots\otimes\mathcal{H}_{d_{2}}\otimes\mathcal{H}_{d_{1}}\otimes\mathcal{H}_{c}$ spanned by orthogonal basis states $\{\Ket{x,d_{m},\dots,d_{2},d_{1},c}|d_{m},\dots,d_{1},c\in\mathbb{Z}_{2};x\in\mathbb{Z}\}$, where $c$ is the coin state, $d_{j}$ (0 stands for left and 1 stands for right) records the shift of the walker $j$ steps before ($d_{1}$ is the direction of the most recent step, and $d_{m}$ is the earliest direction that is memorized), and $x$ is the current position of the walker. If the walker moves on a cycle with $n$ nodes, then $x\in\mathbb{Z}_{n}$. The one-step evolution of QWM-P may be decomposed into three parts: the first is a $2\times 2$ coin operator $C$ on subspace $\mathcal{H}_{c}$, here $C$ is parameterized by an angle $\theta$, i.e.,

the second is the direction-determine transform $D$ on $\mathcal{H}_{d_{m}}\otimes\cdots\otimes\mathcal{H}_{d_{2}}\otimes\mathcal{H}_{d_{1}}\otimes\mathcal{H}_{c}$, whose action can be written as

where $ifeven(d_{m},\dots,d_{1})$ equals 1 (respectively, 0) if the number of zeros in the memorized directions $d_{m},\dots,d_{1}$ is even (respectively, odd); and the third is the shift operator $S$ on $\mathcal{H}_{p}\otimes\mathcal{H}_{d_{1}}$, whose action can be expressed as

If the walker moves on a cycle with $n$ nodes, then the shift operator becomes $\Ket{x,d_{1}}\rightarrow\Ket{x+2d_{1}-1(\bmod n),d_{1}}$.

A controlled one-dimensional quantum walks with memory depending on the parity of memory (CQWM-P) can be obtained by alternately applying QWM-P with different memory lengths (as well as different coin parameters). More precisely, CQWM-P evolves according to a $t$-bit binary string $msg=(m_{1},m_{2},\dots,m_{t})\in\{0,1\}^{t}$: at the $j$th time step, if $m_{j}=0$ ($j\in\{1,2,\dots,t$), then the walker performs QWM-P with $s_{0}$ step memory (denoted by QW$s_{0}$M-P) and with coin parameter $\theta_{0}$; if $m_{j}=1$, then the walker performs QWM-P with $s_{1}$ ($s_{1}\neq s_{0}$) step memory (denoted by QW$s_{1}$M-P) and with coin parameter $\theta_{1}$.

To enable QW$s_{0}$M-P and QW$s_{1}$M-P to be performed alternately, $|s_{0}-s_{1}|$ redundant qubits can be added to the walk process with less memory length, so that two walks live in the same Hilbert space. For instance, if $0<s_{0}<s_{1}$, then $s_{1}-s_{0}$ redundant qubits are added to QWM$s_{0}$P. In this case, the basis states of QWM$s_{0}$P becomes $\{\Ket{x,d_{s_{1}},\dots,d_{2},d_{1},c}|d_{s_{1}},\dots,d_{1},d\in\mathbb{Z}_{2};x\in\mathbb{Z}\}$, wherein the first $s_{1}-s_{0}$ qubits are invariant under the transforms of QWM$s_{0}$P, and the $D$ transform becomes

In this work ,we focus on CQWM-P with one- and two-step memory, whose evolution operator controlled by $msg$ is the product of $t$ unitary transforms

where $U^{(m_{j})}$ is the one-step transform defined as

In Eq. (6), $C^{(0)}$ and $C^{(1)}$ are coin operators parameterized by $\theta_{0}$ and $\theta_{1}$, respectively; $I_{4n}$ and $I_{n}$ are $4n\times 4n$ and $n\times n$ identity operators, respectively; $S$ is the conditional shift operator controlled by the next direction $d_{1}$, such a direction is determined by an $8\times 8$ unitary operator $D^{(m_{j})}$. If $m_{j}=0$, then $D^{(m_{j})}$ is the direction-determine transform of QW1M-P, i.e., $\hat{D}^{(0)}:\Ket{d_{1},c}\rightarrow\Ket{c\oplus 1\oplus d_{1},c}$; and if $m_{j}=1$, then $D^{(m_{j})}$ is the direction-determine transform of QW2M-P, i.e., $D^{(1)}:\Ket{d_{2},d_{1},c}\rightarrow\Ket{d_{1},c\oplus(d_{1}\oplus d_{2}),c}$. By appending a redundant qubit $d_{2}$ to the state of QW1M-P and letting $D^{(0)}:\Ket{d_{2},d_{1},c}\rightarrow\Ket{d_{2},c\oplus 1\oplus d_{1},c}$ determines the next direction if the controlling bit equals 0, the walk process can switch freely between QW1M-P and QW2M-P.

The proposed hash function is constructed by numerically simulating CQWM-P with one- and two-step memory on cycles under the control of the input message, and then calculating the hash value from the resulting probability distribution of this walk.

Specifically, our hashing algorithm is parameterized by three positive integers $\{n,m,l|n\bmod 2=1,10^{l}\gg 2^{m}\}$ and three angles $\{\theta_{0},\theta_{1},\alpha|\theta_{0},\theta_{1},\alpha\in(0,\pi/2)\}$, where $n$ specifies the total number of nodes in the cycle that the walker moves along, $m$ is the number of hash bits that are contributed by each node, $l$ is the number of digits in the probability value (associated with each node) that are used to calculate the hash result, $\theta_{0}$ (respectively, $\theta_{1}$) is the coin parameter of QW1M-P (respectively, QW2M-P), and $\alpha$ is the parameter of the initial state of the walker. Given the input message $msg$, the $m\times n$-bit hash value $H(msg)$ is calculated as follows.

1. 1)

   Initialize the walker in the state $\Ket{\psi_{0}}\!=\!\text{cos}\alpha\Ket{0,\!1,\!0,\!0}+\text{sin}\alpha\Ket{0,1,0,1}$;

2. 2)

   Apply $U_{msg}$ to $\Ket{\psi_{0}}$ and generate the resulting probability distribution $prob=(p_{0},p_{1},\dots,p_{n-1})$, where $p_{x}$ is the probability that the walker locates at node $x$ when the walk is finished.

3. 3)

   The hash value of $msg$ is a sequence of $n$ blocks $H(msg)=B_{0}\lVert B_{1}\lVert\dots\lVert B_{n-1}$, where each block $B_{x}$ is the $m$-bit binary representation of $\lfloor p_{x}\cdot 10^{l}\rfloor\bmod 2^{m}$ ($\lfloor\cdot\rfloor$ denotes the floor of a number), and $B_{x}\lVert B_{x+1}$ denotes the concatenation of $B_{x}$ and $B_{x+1}$.

The proposed scheme is a kind of dedicated hash function, the security of which is hard to prove, and it is commonly evaluated by means of statistical analysis. To facilitate comparison and discussion, we consider two typical instances QHFM-P-264 and QHFM-P-296 of the proposed scheme, where QHFM-P-$L$ produces $L$-bit hash values and will be compared with the existing DQW-based hash functions with $L$-bit output length. The values of $m,l,\theta_{0},\theta_{1}$, and $\alpha$ for the two instances are the same, which are taken to be $8,8,\pi/4,\pi/3$, and $\pi/4$, respectively; the only distinction between QHFM-P-296 and QHFM-P-264 lies in the value of $n$, which are taken to be 37 for the 296-bit output length and 33 for the 26-bit output length.

Our statistical tests considers four kinds of properties: sensitivity of hash value to message, diffusion and confusion properties, uniform distribution property, and collision resistance property, the latter three are assessed by analyzing the same collection of hash values, whose input messages come from the public arXiv dataset (see https://www.kaggle.com/Cornell-University/arxiv).

Recall from section III that the proposed hash function is parameterized by three integers and three angles, among which the two coin angles are crucial components of the underlying controlled alternate quantum walks and may affect the four statistical properties considered in section IV.

To explore how robust the hashing properties of QHFM-P are with respect to different coin angles, we uniformly divide $(0,\pi/2)$ into $c=30$ subintervals, take the endpoints (except 0 and $\pi/2$) of those subintervals as the candidate values of each coin parameter, and then conduct $N=2048$ experiments for each pair of values. During the experiments for each angle pair, primary indicators of each type of statistical property are calculated. Specifically, we take $P$ together with $\Delta P$, $\overline{T}$ together with $\Delta T$, and $D_{KL}(P^{e}\|P^{t})$ together with $\left\lvert\overline{d}_{byte}^{\,e}-\overline{d}_{byte}^{\,t}\right\rvert$ to be the primary indicators of the diffusion and confusion properties, the uniform distribution property, and the collision resistance property, respectively. Following Ref. [2], we take the mean Jensen-Shannon divergence [24] (over $N$ random experiments) between the resulting probability distributions corresponding to the original and modified messages to be the quantitative indicator of the sensitivity of hash value to message. Suppose, in an experiment, the probability distribution produced by the underlying controlled alternate quantum walks controlled by $msg_{j}$ ($j=0,1,2,3$) is $P_{j}$, the Jensen-Shannon divergence (referred to as JS divergence for short) between $P_{0}$ and $P_{1}$ is

where $M=(P_{0}+P_{1})/2$, and $D_{KL}(P_{0}\|M)$ is the KL divergence of $P_{0}$ from $M$ (see Eq. (8)).

The results of the stability test for the four kinds of properties of QHFM-P-296 are illustrated in Figs. 2 to 5, where $\overline{D}_{JS}(P_{0},P_{j})$ ($j=1,2,3$) in Fig. 2 denotes the average value of $D_{JS}(P_{0},P_{j})$ over $N$ experiments. One may notice that the shape of Fig. 3(a) is identical to that of Fig. 4(a), this is because $\overline{T}$ is directly proportional to $P$ when the $N$ pairs of original and modified messages used in the diffusion and confusion test are re-used in the uniform distribution test.

It can be seen from Fig. 2(a) that the average JS divergences between $P_{0}$ and $P_{1}$ for different values of coin parameters fall within a narrow range, indicating that the value of $\overline{D}_{JS}(P_{0},P_{1})$ is quite stable with respect to $\theta_{0}$ and $\theta_{1}$. Similarly, the maximum and minimum values of $\overline{D}_{JS}(P_{0},P_{2})$ (or $\overline{D}_{JS}(P_{0},P_{3})$) are very close to each other, suggesting that the sensitivity of hash value to message of the proposed hash function is stable with respect to the coin parameters. In Fig. 3, the mean changed probability $P$ fluctuates around $50\%$; meanwhile, the value of the standard deviation $\Delta P$ is small and does not vary significantly for different values of $\theta_{0}$ and $\theta_{1}$. Hence, the diffusion and confusion properties of QHFM-P is robust with regard to different coin angles. Likewise, the experimental values of $\overline{T}$ for different coin angles are close to the theoretical value $N/2$, and the results of $\Delta T$, $D_{KL}(P^{e}\|P^{t})$, and $\left\lvert\overline{d}_{byte}^{\,e}-\overline{d}_{byte}^{\,t}\right\rvert$ displayed in Figs. 4 and 5 are relatively small, which suggests that the uniform distribution property and the collision resistance property of the proposed hash function are also stable with respect to coin parameters.

Similar to existing DQW-based hash schemes, the proposed hash algorithm can be efficiently computed using classical computer. Thus, it is more appropriate to consider QHFM-P as a classical algorithm and to concentrate on classical complexity.

By rewriting the 4-term basis state $\Ket{x,d_{2},d_{1},c}$ of QWHF-P in $\mathcal{H}_{p}\otimes\mathcal{H}_{d_{2}}\otimes\mathcal{H}_{d_{1}}\otimes\mathcal{H}_{c}$ as a 2-term basis state $\Ket{x,j}=\Ket{x,2^{2}d_{2}+2^{1}d_{1}+2^{0}c}$ in $\mathcal{H}_{p}\otimes\mathcal{H}^{8}$, where $\mathcal{H}^{8}$ is the 8-dimensional Hilbert space, the quantum state of the walker performing parity-dependent quantum walks with one- and two-step memory on a cycle of length $n$ after $t$ time steps can be expressed as

The results of sequentially performing the coin operator, the direction-determine transform, and the shift operator of QW2M-P on the computational states $\Ket{x,j}$ are tabularized in Table 4. For ease of notation, we denote $C^{(1)}$ by $\bigl{(}\begin{smallmatrix}a_{1}&b_{1}\\ c_{1}&d_{1}\end{smallmatrix}\bigr{)}$ and write $(x\pm 1)\bmod n$ shortly as $x\pm 1$. In the first three columns of Table IV, the second terms $j$ of the basis states and the transformed results are written in binary format, for the binary representation $j_{2}j_{1}j_{0}$ of $j$ indicates the values of $d_{2}$, $d_{1}$, and $c$ in a natural way.

Combining Eq. (11) with the first and last columns of Table IV, one can obtain the relation between $\{A_{t+1}^{x,j}|x\in\mathbb{Z}_{n},j\in\mathbb{Z}_{8}\}$ and $\{A_{t}^{x,j}|x\in\mathbb{Z}_{n},j\in\mathbb{Z}_{8}\}$ (hereafter, simply $\{A_{t+1}^{x,j}\}$ and $\{A_{t}^{x,j}\}$, respectively) after one step of QW2M-P as follows:

Relation (12) shows that the eight amplitudes of being at position $x$ at time $t+1$ can be calculated from the amplitudes of being at positions $x\pm 1$ at time $t$ using 16 multiplications and 8 additions, meaning that the $8n$ amplitudes of being at $n$ locations can be calculated using $O(n)$ basic arithmetic operations. Similarly, one can obtain the relation between $\{A_{t+1}^{x,j}\}$ and $\{A_{t}^{x,j}\}$ for QW1M-P, where the amplitudes can also be updated using $O(n)$ basic operations at each time step.

If one wants to obtain an $L$-bit hash value ($L$ is a multiple of $m$) of an $M$-bit message, then the walker moves $M$ steps on a cycle with $L/m=O(L)$ nodes, here $m$ is constant with respect to $M$. The assignment of the initial amplitudes $\{A_{0}^{x,j}\}$ can be carried out with $O(L)$ time and $O(L)$ memory space, the values of $\{A_{M}^{x,j}\}$ can be calculated from $\{A_{0}^{x,j}\}$ using $O(ML)$ basic operations with $O(L)$ space, and the hash value can be computed from $\{A_{M}^{x,j}\}$ using $O(L)$ multiplications and $O(L)$ modulo operations with $O(L)$ space. As a result, the time and space complexity of QHFM-$L$ are $O(ML)$ and $O(L)$, respectively, which are the same as those of the state-of-the-art hash functions [1, 2, 5, 6, 7] based on discrete quantum walks.

In this article, a new QWM-based hash function QHFM-P is proposed and analyzed. Similar to the existing QWM-based hash function [1], the proposed scheme is also constructed by using quantum walks with one- and two-step memory; the major distinction lies in that the underlying walks with two-step memory of QHFM and QHFM-P are different extensions of Mc Gettrick’s QW1M model [13]. The proposed hash function has the same time and space complexity as those of QHFM, and it also has near-ideal statistical properties. It is noteworthy that the four kinds of statistical properties of QHFM-P are quite stable with respect to the coin angles, which suggests the robustness of the hashing properties of the proposed scheme.

In the future, we will try to identify the region of stability in the plane of coin and other parameters, examine the stability with respect to various direction-determine transforms, and establish the conditions for constructing good QWM-based hash functions.