# A Parallel Quantum Circuit Implementations of LSH Hash Function for Use with [PERSON]'s Algorithm
## 3 Proposed Method
### Parallel Quantum Circuit for LSH  
In LSH, the addition is used for message expansion (MsgExp) and message mix (Mix), and it has a characteristic that can be processed as a parallel adder. Each addition operation unit in MsgExp and the mix does not affect the results of each other. Due to this characteristic, the depth of the circuit can be significantly reduced using the parallel adder. In LSH-256-\(n\), 32 bits are processed in units of 1 word. In the LSH-256-\(n\) quantum circuit, 1024 qubits are used in the padded plaintext M, 512 qubits for the connection variable (CV), and 16 carry qubits are used in the parallel adder. In LSH-512-\(m\), 64 bits are processed in units of 1 word. In the LSH-512-\(m\) quantum circuit, 2048 qubits for the padded plaintext M, 1024 qubits for the connection variable (CV), and 15 carry qubits are used in the parallel adder. The overall operation process of LSH-256-\(n\) and LSH-512-\(m\) is the same, but the output of each operation bit unit, step constant, and the final hash value is different. Source codes of the proposed parallel structure LSH quantum circuit are available in [[https://github.com/kyungzzu/Grover-on-SM3-and-LSH](https://github.com/kyungzzu/Grover-on-SM3-and-LSH)]([https://github.com/kyungzzu/Grover-on-SM3-and-LSH](https://github.com/kyungzzu/Grover-on-SM3-and-LSH)) (accessed on 18 September 2022). Figure 2 shows the progress of the MsgExp function and _step_ function of the original LSH hash function. That is, after expanding all messages through the MsgExp function, the expanded message is used in the _step_ function. This method is very inefficient in terms of quantum resources because it requires qubits to store the entire expanded message. Therefore, in the quantum circuit, the MsgExp function and _step_ functions are iteratively performed, as shown in Figure 7 to reduce the temporary qubits used for message expansion. For example, by the message expansion equation \(M_{j}^{(i)}[l]\gets M_{j-1}^{(i)}[l]\boxplus M_{j-2}^{(i)}[\tau(l)]\) in Equation (4), the third message block \(M_{2}\) is expanded by the addition operation of \(M_{1}\) and \(M_{0}\). \(\tau(l)\) is the value substituted by the permutation in Table 4. If the MsgExp and _step_ functions are performed in units of one message block when the \(M_{2}\) message block is used, \(M_{0}\) and \(M_{1}\) have already been used, so the result of the expansion of \(M_{2}\) can be calculated in \(M_{0}\). In LSH-256-\(n\), a 1024 bit message is divided into \(M_{k-1}^{i},M_{k-2}^{i}(0\leq i\leq 15)\) of 1 word(1 word=32 bit) each to perform the _step_ function. In LSH-512-\(m\), a 2048-bit message is divided into \(M_{k-1}^{i},M_{k-2}^{i}(0\leq i\leq 15)\) of 1 word(1 word=64 bits) each to perform _step_ function. In summary, the proposed technique does not allocate qubits to store the updated \(M\). Instead, it saves qubits by generating new values for \(M\) used in the previous round. The connection variable \(T[i],T[i+8],(0\leq i\leq 7)\) updates the value by performing the MsgExp, Mix, and WordPerm functions, and finally obtains a hash value through the Final function with the updated value. MsgExp generates 16 word message block \(M_{j}^{(i)}(0\leq j\leq N_{s})\) for message block \(M^{(i)}=M^{(i)}[0],\,\ldots,\,M^{(i)}[31]\) (32 bits) by using Equation (4). The adder used to generate the next message is performed after bit permutation, where the bit permutation \(\tau(l)\) is shown in Table 4.  
Figure 7: LSH quantum circuit for MsgExp and _step_ function. \[ \begin{array}{l}M_{0}^{(i)}\gets M^{(i)}[0],M^{(i)}[1],\cdots,M^{(i)}[15]\,\\ M_{1}^{(i)}\gets M^{(i)}[16],M^{(i)}[17],\cdots,M^{(i)}[31]\,\\ M_{j}^{(i)}[l]\gets M_{j-1}^{(i)}[l]\boxplus M_{j-2}^{(i)}[\tau(l)]\,\ (0\leq l\leq 15)\end{array}  \tag{4}\]  
In MsgExp, the addition operations of message block pairs (i.e., \(M_{j-1},M_{j-2},\ 2\leq j\leq N_{s}\)) are all independent, so the adders can be designed in parallel. Algorithm 1 shows the computation for parallel addition in MsgExp.