Noboru Kunihiro
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Noboru Kunihiro has a total of 114 co-authors. Here are the top co-authors by number of shared publications:
Kazuo Ohta
The University of Electro‐Communications Chofu Japan
28 shared publicationsYu Sasaki
NTT Corporation
13 shared publications- Atsushi Takayasu
The University of Tokyo
12 shared publications Tetsuya Izu
Data and Security Laboratory, Fujitsu Research, Fujitsu Ltd., Kawasaki, Japan
12 shared publicationsLei Wang
University of Electro-Communications
11 shared publications- Goichiro Hanaoka
National Institute of Advanced Industrial Science and Technology, Tokyo, Japan
9 shared publications
Latest Publications
- Open Access
- 18 February 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 14, 27264-27289
An Evaluation of Computational Complexity of Shor’s Algorithm on Surface Codes for Factorization
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.
- 18 February 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 14, 27264-27289
Open AccessAn Evaluation of Computational Complexity of Shor’s Algorithm on Surface Codes for Factorization
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.
- Open Access
- 28 October 2025
- Published by Springer Nature
- p. 163-181
Full Key Recovery on RSA from Noisy Binary GCD Operation Sequences
In CHES2019, Aldaya et al. reported a vulnerability of the binary GCD algorithm used in RSA key generation in OpenSSL. Furthermore, they proposed an attack that exploits this vulnerability. The attack consists roughly of (1) collecting the sequences of operations performed in the binary GCD algorithm using a side-channel attack, (2) error correction to generate candidate solutions for the LSBs of the secret key, and (3) full key recovery using the Coppersmith algorithm. Tani and Kunihiro proposed novel error correction algorithms in ACNS2023. In ACNS2023, they presented no experimental results about the overall attack, concretely the full key recovery phase. In this paper, we first optimize the parameters of the Coppersmith algorithm. Using the optimized parameters, we apply the Coppersmith algorithm to the candidate solutions and evaluate the success rate and execution time. This allows for a more rigorous evaluation of the success rate and execution time of the overall attack.
- 28 October 2025
- Published by Springer Nature
- p. 163-181
Open AccessFull Key Recovery on RSA from Noisy Binary GCD Operation Sequences
In CHES2019, Aldaya et al. reported a vulnerability of the binary GCD algorithm used in RSA key generation in OpenSSL. Furthermore, they proposed an attack that exploits this vulnerability. The attack consists roughly of (1) collecting the sequences of operations performed in the binary GCD algorithm using a side-channel attack, (2) error correction to generate candidate solutions for the LSBs of the secret key, and (3) full key recovery using the Coppersmith algorithm. Tani and Kunihiro proposed novel error correction algorithms in ACNS2023. In ACNS2023, they presented no experimental results about the overall attack, concretely the full key recovery phase. In this paper, we first optimize the parameters of the Coppersmith algorithm. Using the optimized parameters, we apply the Coppersmith algorithm to the candidate solutions and evaluate the success rate and execution time. This allows for a more rigorous evaluation of the success rate and execution time of the overall attack.
- Open Access
- 21 July 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 6, 1-12
Simulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo $p$ and Order $q$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 paper, we constructed such quantum circuits and solved DLPs for all 1,860 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å, arXiv:1905.09084 (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. Additionally, we generated 1,015 quantum circuits for larger pairs of $p$ and $q$, extrapolated the circuit sizes obtained, and compared them for $p = 2048$ bits between safeprime 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.
- 21 July 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 6, 1-12
Open AccessSimulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo $p$ and Order $q$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 paper, we constructed such quantum circuits and solved DLPs for all 1,860 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å, arXiv:1905.09084 (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. Additionally, we generated 1,015 quantum circuits for larger pairs of $p$ and $q$, extrapolated the circuit sizes obtained, and compared them for $p = 2048$ bits between safeprime 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.
- 7 July 2025
- Published by Springer Nature
- p. 319-339
Solving Generalized Approximate Divisor Multiples Problems
- 7 July 2025
- Published by Springer Nature
- p. 319-339
Solving Generalized Approximate Divisor Multiples Problems
- 13 March 2025
- Published by Springer Nature
- p. 205-229
Bias from Uniform Nonce: Revised Fourier Analysis-Based Attack on ECDSA
- 13 March 2025
- Published by Springer Nature
- p. 205-229
Bias from Uniform Nonce: Revised Fourier Analysis-Based Attack on ECDSA
- 8 March 2024
- Published by Springer Nature
- p. 163-184
Extended Attacks on ECDSA with Noisy Multiple Bit Nonce Leakages
- 8 March 2024
- Published by Springer Nature
- p. 163-184
Extended Attacks on ECDSA with Noisy Multiple Bit Nonce Leakages
- Open Access
- 25 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 4, 1-16
Shor's Algorithm Using Efficient Approximate Quantum Fourier Transform
Shor's algorithm solves the integer factoring and discrete logarithm problems in polynomial time. Therefore, the evaluation of Shor's algorithm is essential for evaluating the security of currently used public-key cryptosystems because the integer factoring and discrete logarithm problems are crucial for the security of these cryptosystems. In this article, a new approximate quantum Fourier transform is proposed, and it is applied to Rines and Chuang's implementation. The proposed implementation requires one-third the number of $T$ gates of the original. Moreover, it requires one-fourth the $T$ -depth of the original. Finally, a $T$ -scheduling method for running the circuit with the smallest KQ is presented.
- 25 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 4, 1-16
Open AccessShor's Algorithm Using Efficient Approximate Quantum Fourier Transform
Shor's algorithm solves the integer factoring and discrete logarithm problems in polynomial time. Therefore, the evaluation of Shor's algorithm is essential for evaluating the security of currently used public-key cryptosystems because the integer factoring and discrete logarithm problems are crucial for the security of these cryptosystems. In this article, a new approximate quantum Fourier transform is proposed, and it is applied to Rines and Chuang's implementation. The proposed implementation requires one-third the number of $T$ gates of the original. Moreover, it requires one-fourth the $T$ -depth of the original. Finally, a $T$ -scheduling method for running the circuit with the smallest KQ is presented.
- 29 May 2023
- Published by Springer Nature
- p. 59-88
HS-Based Error Correction Algorithm for Noisy Binary GCD Side-Channel Sequences
- 29 May 2023
- Published by Springer Nature
- p. 59-88
HS-Based Error Correction Algorithm for Noisy Binary GCD Side-Channel Sequences
- 8 December 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Dependable and Secure Computing
- Vol. 20 (6) , 4486-4501
Efficient Noise Generation Protocols for Differentially Private Multiparty Computation
To bound information leakage in outputs of protocols, it is important to construct secure multiparty computation protocols which output differentially private values perturbed by the addition of noise. However, previous noise generation protocols have round and communication complexity growing with differential privacy budgets, or require parties to locally generate non-uniform noise, which makes it difficult to guarantee differential privacy against active adversaries. We propose three kinds of protocols for generating noise drawn from certain distributions providing differential privacy. The two of them generate noise from finite-range variants of the discrete Laplace distribution. For $(\epsilon ,\delta )$ -differential privacy, they only need constant numbers of rounds independent of $\epsilon ,\delta$ while the previous protocol needs the number of rounds depending on $\delta$ . The two protocols are incomparable as they make a trade-off between round and communication complexity. Our third protocol non-interactively generate shares of noise from the binomial distribution by predistributing keys for a pseudorandom function. It achieves communication complexity independent of $\epsilon$ or $\delta$ for the computational analogue of $(\epsilon ,\delta )$ -differential privacy while the previous protocols require communication complexity depending on $\epsilon$ . We also prove that our protocols can be extended so that they provide differential privacy in the active setting.
- 8 December 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Dependable and Secure Computing
- Vol. 20 (6) , 4486-4501
Efficient Noise Generation Protocols for Differentially Private Multiparty Computation
To bound information leakage in outputs of protocols, it is important to construct secure multiparty computation protocols which output differentially private values perturbed by the addition of noise. However, previous noise generation protocols have round and communication complexity growing with differential privacy budgets, or require parties to locally generate non-uniform noise, which makes it difficult to guarantee differential privacy against active adversaries. We propose three kinds of protocols for generating noise drawn from certain distributions providing differential privacy. The two of them generate noise from finite-range variants of the discrete Laplace distribution. For $(\epsilon ,\delta )$ -differential privacy, they only need constant numbers of rounds independent of $\epsilon ,\delta$ while the previous protocol needs the number of rounds depending on $\delta$ . The two protocols are incomparable as they make a trade-off between round and communication complexity. Our third protocol non-interactively generate shares of noise from the binomial distribution by predistributing keys for a pseudorandom function. It achieves communication complexity independent of $\epsilon$ or $\delta$ for the computational analogue of $(\epsilon ,\delta )$ -differential privacy while the previous protocols require communication complexity depending on $\epsilon$ . We also prove that our protocols can be extended so that they provide differential privacy in the active setting.