The Shor’s algorithm can find solutions to the discrete logarithm problem on binary elliptic curves in polynomial time. A major challenge in implementing Shor’s algorithm is the overhead of representing and performing arithmetic on binary elliptic curves using quantum circuits. Multiplication of binary fields is one of the critical operations in the context of elliptic curve arithmetic, and it is especially costly in the quantum setting. Our goal in this paper is to optimize quantum multiplication in the binary field. In the past, efforts to optimize quantum multiplication have centred on reducing the Toffoli gate count or qubits required. However, despite the fact that circuit depth is an important metric for indicating the performance of a quantum circuit, previous studies have lacked sufficient consideration for reducing circuit depth. Our approach to optimizing quantum multiplication differs from previous work in that we aim at reducing the Toffoli depth and full depth. To optimize quantum multiplication, we adopt the Karatsuba multiplication method which is based on the divide-and-conquer approach. In summary, we present an optimized quantum multiplication that has a Toffoli depth of one. Additionally, the full depth of the quantum circuit is also reduced thanks to our Toffoli depth optimization strategy. To demonstrate the effectiveness of our proposed method, we evaluate its performance using various metrics such as the qubit count, quantum gates, and circuit depth, as well as the qubits-depth product. These metrics provide insight into the resource requirements and complexity of the method. Our work achieves the lowest Toffoli depth, full depth, and the best trade-off performance for quantum multiplication. Further, our multiplication is more effective when not used in stand-alone cases. We show this effectiveness by using our multiplication to the Itoh–Tsujii algorithm-based inversion of .
As Mobile Communication and Internet Systems (MCIS) have rapidly developed, security issues related to MCIS have become increasingly important. Therefore, the development and research of security technologies for mobile communication and internet systems are actively being conducted. Hash-Based Signature (HBS) uses a hash function to construct a digital signature scheme, where its security is guaranteed by the collision resistance of the hash function used. To provide sufficient security in the post-quantum environment, the length of hash should be satisfied for the security requirement. Modern HBS can be classified into stateful and stateless schemes. Two representative stateful and stateless HBS are eXtended Merkle Signature Scheme(XMSS) and SPHINCS, respectively. In this paper, we propose two HBS schemes: K-XMSS and K-SPHINCS, which replace internal hash functions of XMSS and SPHINCS with Korean cryptography algorithms. K-XMSS is a stateful signature, while K-SPHINCS is its stateless counterpart. We showcase the reference implementation of K-XMSS and K-SPHINCS employing Lightweight Secure Hash (LSH) and two hash functions based on block ciphers (i.e., CHAM and LEA) as the internal hash function. In addition, K-XMSS and K-SPHINCS using Advanced Vector Extensions 2 (AVX2) have been provided, demonstrating that they can be optimized for better performance using advanced implementation techniques than previous approaches.
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.