Selected Publications

Authors: Kento Oonishi and Noboru Kunihiro Abstract: Shor’s algorithm is a quantum algorithm that can efficiently solve the problems of integer factorization and discrete logarithms, which potentially break currently used public-key cryptosystems such as RSA and elliptic curve cryptography. However, a significant challenge in solving these problems is the noise inherent in quantum computers. Previous research advanced fault-tolerant techniques such as surface codes to mitigate this noise in quantum computers. Analyzing the security of currently used public-key cryptosystems on fault-tolerant quantum computers is essential. In this paper, we estimate the computational cost required to solve integer factorization using Shor’s algorithm on surface codes. We evaluated computational resources required for surface codes and magic state distillation and derived the computational cost of Shor’s algorithm based on these evaluations. Our computational complexity analysis indicates that there is no significant difference in the order of complexity. However, it underscores the paramount importance of optimizing the coefficient part for future efficiency improvements. ...

Authors: Kaito Kishi, Junpei Yamaguchi, Tetsuya Izu, and Noboru Kunihiro Abstract: The discrete logarithm problem (DLP) over finite fields, commonly used in classical cryptography, has no known polynomial-time algorithm on classical computers. However, Shor has provided its polynomial-time algorithm on quantum computers. Nevertheless, there are only few examples simulating quantum circuits that operate on general pairs of modulo $p$ and order $q$. In this article, we constructed such quantum circuits and solved DLPs for all 1860 possible pairs of $p$ and $q$ up to 32 qubits using a quantum simulator with PRIMEHPC FX700. From this, we obtained and verified values of the success probabilities, which had previously been heuristically analyzed by Ekerå (2019). As a result, the detailed waveform shape of the success probability of Shor’s algorithm for solving the DLP, known as a periodic function of order $q$, was clarified. In addition, we generated 1015 quantum circuits for larger pairs of $p$ and $q$, extrapolated the circuit sizes obtained, and compared them for $p =2048$ bits between safe-prime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same if $p$ is equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length of $p$ in the former when using Shor’s quantum algorithm. In particular, it was experimentally and theoretically shown that when a basic adder is used in the addition circuit, the cryptographic strength of a Schnorr group with $p =2048$ bits under Shor’s algorithm is almost equivalent to that of a safe-prime group with $p = 1024$ bits. ...

Authors: Kenta Tani and Noboru Kunihiro Abstract: The secure implementation of the Greatest Common Divisor (GCD) algorithm is fundamental for many cryptographic schemes. The binary GCD algorithm has a highly input-dependent behavior. Therefore, we must carefully implement the binary GCD used in cryptographic systems. However, it has been noted that the binary GCD algorithm implemented in OpenSSL 1.1.0-1.1.0h and 1.0.2b-1.0.2o is not secure. Aldaya et al. presented this vulnerability at CHES2019. They also proposed a side-channel attack to collect sequences of operations performed by the binary GCD algorithm and an error correction algorithm (AGTB algorithm) to recover the LSBs of secret keys from the noisy sequences. In this paper, we propose an error correction algorithm that, like the AGTB algorithm, focuses on only a single type of error. We evaluate our algorithm using numerical experiments that reveal that our algorithm achieves a higher recovery rate than the AGTB algorithm. ...

Authors: Kento Oonishi, Tomoki Tanaka, Shumpei Uno, Takahiko Satoh, Rodney Van Meter, Noboru Kunihiro Abstract Control modular addition is a core arithmetic function, and we must consider the computational cost for actual quantum computers to realize efficient implementation. To achieve a low computational cost in a control modular adder, we focus on minimizing KQ, defined by the product of the number of qubits and the depth of the circuit. In this paper, we construct an efficient control modular adder with small KQ by using relative-phase Toffoli gates in two major types of quantum computers: Fault-Tolerant Quantum Computers (FTQ) on the Logical layer and Noisy Intermediate-Scale Quantum Computers (NISQ). We give a more efficient construction compared to Van Meter and Itoh’s, based on a carry-lookahead adder. In FTQ, T gates incur heavy cost due to distillation, which fabricates ancilla for running T gates with high accuracy but consumes a lot of specially prepared ancilla qubits and a lot of time. Thus, we must reduce the number of T gates. We propose a new control modular adder that uses only 20% of the number of T gates of the original. Moreover, when we take distillation into consideration, we find that we minimize KQT (the product of the number of qubits and T-depth) by running (n / log n) T gates simultaneously. In NISQ, CNOT gates are the major error source. We propose a new control modular adder that uses only 35% of the number of CNOT gates of the original. Moreover, we show that the KQCX (the product of the number of qubits and CNOT-depth) of our circuit is 38% of the original. Thus, we realize an efficient control modular adder, improving prospects for the efficient execution of arithmetic in quantum computers." ...

Authors Mengce Zheng, Noboru Kunihiro, Yuanzhi Yao Abstract RSA (Rivest-Shamir-Adleman) cryptosystem is the most popular asymmetric key cryptographic algorithm used in computer science and information security. Recently, an RSA-like cryptosystem was proposed using a novel product that arises from a cubic field connected to the cubic Pell equation. The relevant key equation is $ed = 1 \bmod (p^2+p+1)(q^2+q+1)$ with $N=pq$. This RSA variant is claimed to be robust against the Wiener’s attack and hence the bit-size of the private key could be shorter, namely $d < N^{1/4}$. In this paper, we explore the further security analysis and investigate the potential small private exponent attack. We show that such RSA variant is particularly vulnerable to the lattice-based method. To be specific, we can carry out the lattice-based small private exponent attack if $d < N^{2-√2}}$, which is less secure than the standard RSA. Furthermore, we conduct numerical experiments to verify the validity of the proposed attack." ...