Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD)

Design and Analysis of a Scalable and Efficient Quantum Circuit for LWE Matrix Arithmetic

Chao Lu, Utsav Banerjee, Kanad Basu

Published Oct 1, 2022• 3 citations
Publisher

Abstract

Quantum computing furnishes exponential speed up over classical computing in specific areas. For example, Shor’s algorithm can factor two numbers in a polynomial time complexity. Thus, many encryption algorithms that rely on large number factorization are potentially vulnerable to quantum computers. In order to address this, the National Institute of Standard and Test (NIST) has organized a competition to evaluate several post quantum cryptography (PQC) algorithms, that are secure from the attacks from quantum computers. Several of these lattice-based PQC encryption algorithms are based on Learning With Errors (LWE) computation. Conversely, LWE is the heaviest computation in a classical computer, which incurs significant portion of the latency overhead for the entire encryption algorithm. In this paper, we design an optimized quantum circuit for LWE computation. The proposed quantum circuit does not need any ancillary qubits and scales efficiently and easily if there are more qubits available on a higher qubit quantum computer.

DOI
10.1109/iccd56317.2022.00026

Related papers

A COMPARATIVE ANALYSIS OF LWE BASED POST QUANTUM CRYPTOGRAPHIC SCHEMES: BALANCING CRYPTOGRAPHIC SECURITY, EFFICIENCY METRICS, AND IMPLEMENTATION FEASIBILITY IN THE POST QUANTUM TRANSITION ERA

Kainat Mubarik, Malik Aazaz Abbasi

The imminent threat posed by the realization of large-scale, fault-tolerant quantum computers (QCs), capable of leveraging Shor's algorithm to break foundational classical public-key cryptosystems like RSA and ECC, necessitates an immediate and comprehensive shift to Post-Quantum Cryptography (PQC). This urgency is intensified by the "Harvest Now, Decrypt Later" (HNDL) threat, which compromises long-term data confidentiality. The NIST PQC Standardization process has established Lattice-Based Cryptography as the leading family for new standards. This paper presents a comprehensive comparative analysis of major PQC schemes built upon the foundational mathematical problem, Learning with Errors (LWE). We systematically evaluate these LWE-based schemes (CRYSTALS-Kyber, CRYSTALS-Dilithium) by balancing three critical dimensions: cryptographic security (against classical and quantum attacks), efficiency metrics (key size, signature size, and operational speed), and implementation feasibility across diverse hardware environments. Our findings provide essential insights and a structured framework to guide engineers, policy-makers, and organizations in making informed decisions for the strategic and secure migration to quantum-resistant standards in the post-quantum transition era.

Policy Research Journal•Nov 29, 2025•0 citations

Cryptography with Ring Algorithm – LWE

Paramita Lumban Gaol, Stephen Buulolo, Aritmen Andreas L. Manurung +1 more

Ring Learning With Errors (Ring-LWE) is one of the basic schemes used to develop cryptographic algorithms that are resistant to quantum attacks, offering better computational efficiency compared to standard Learning With Errors (LWE). Ring-LWE uses the algebraic characteristics of polynomial rings to create a robust and fast encryption system. This study implements and evaluates the Ring-LWE algorithm in the context of public key exchange and encryption. Simulations are performed with various security parameters, including modulus size and error rate, to test the resistance to brute force attacks and lattice-based attacks. The experimental results show that the Ring-LWE algorithm can achieve a balance between security and computational efficiency, with shorter processing time than conventional LWE while maintaining a high level of security even in the face of quantum computers. From this study, it can be concluded that Ring-LWE is an excellent choice for application in post-quantum security systems, especially in encrypted communication and digital authentication applications. The next step can be directed at optimizing resource utilization and testing against various types of attacks.

Login Jurnal Teknologi Komputer•Jun 25, 2024•0 citations

Quantum Arithmetic Circuits in Public-Key Cryptography

Siyi Wang, Kyungbae Jang, Hyunji Kim +4 more

Quantum computing has advanced rapidly in recent decades, driven by developments across the technology stack, including quantum error-correcting codes and efficient quantum algorithms. Among these, quantum arithmetic circuits serve as fundamental building blocks for various promising algorithms. Despite their crucial role, the design of quantum arithmetic circuits faces challenges arising from the no-cloning theorem, qubit limitations, and circuit depth constraints, which significantly impact the efficiency of large-scale quantum computing. We provide an overview of quantum arithmetic circuits in the context of public-key cryptanalysis, with particular emphasis on optimization strategies such as measurement-based uncomputation and conditionally clean ancilla. We review state-of-the-art designs for essential arithmetic operations in public-key cryptanalysis such as addition, multiplication, and modular exponentiation. We also present an overview of the techniques used for fault-tolerant runtime and resource estimation in quantum cryptanalysis. In brief, this chapter emphasizes strategies for designing resource-efficient quantum arithmetic circuits, providing a basis for realistic evaluations of quantum cryptanalytic capabilities.

quant-pharXiv:2607.11713•Jul 14, 2026•0 citations

The Impact of Quantum Noise on Shor's Algorithm and Its Cryptographic Applications

Wael M. F. Abdel-Rehim

Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.

•May 12, 2025•2 citations

EFFICIENT QUANTUM CIRCUITS FOR ARITHMETIC OPERATIONS AND THEIR APPLICATIONS

Yasuhiro Takahashi

This thesis focuses on constructing efficient quantum circuits for arithmetic operationsand applying them to Shor’s factoring algorithm to answer the question: Whatwould be sufficient computational resources for a quantum computer to be able toperform Shor’s factoring algorithm for a large input number? The answers to theproblem would contribute to our understanding of the computational power of smallquantum circuits such as logarithmic-depth quantum circuits. Moreover, the answerswould be useful for analyzing the detailed relationships between the computationalpower of a quantum computer and the security of cryptosystems and for designinga new cryptosystem that is secure against a quantum computer. First, I constructa linear-size quantum circuit for addition with no ancillary qubits. This is an affirmativeanswer to Cuccaro et al.’s question. Then, using the circuit, I construct alogarithmic-depth quantum circuit for addition with few qubits and apply it to constructingan O(n2 log n)-depth O(n3 log n)-size quantum circuit for Shor’s algorithmwith 2n+O(n/ log n) qubits, where n is the length of the number to be factored. Thenumber of qubits is less than that in any other O(n2 log n)-depth quantum circuit everconstructed for Shor’s algorithm. Then, I construct a quantum circuit for comparisonwith uninitialized ancillary qubits and apply it to constructing an O(n3)-depthO(n3 log n)-size quantum circuit for Shor’s algorithm with 2n+2 qubits. The numberof qubits is less than that in any other quantum circuit ever constructed for Shor’salgorithm. Lastly, on a linear nearest neighbor architecture, I construct a small-sizequantum circuit for the quantum Fourier transform and apply it to constructing anO(n3)-depth O(n3 log n)-size quantum circuit for Shor’s algorithm with 2n+4 qubits.The size is less than that of any other quantum circuit ever constructed for Shor’salgorithm on a linear nearest neighbor architecture.

•Mar 24, 2008•0 citations

Survey on Quantum-Safe Cryptography for PostQuantum Internet Security

MURALI KRISHNA DARA

The threats are existential to the traditional cryptosystems of public keys, including RSA, Diffie-Hellman, and elliptic curve cryptography (ECC), due to the rapid progress in quantum computing. Such algorithms as the Shor and Grover algorithms prove that as soon as large scale quantum computers are achieved, these classical cryptographic protocols will not provide any privacy and integrity to online communication. This has created an emergency to find post-quantum cryptography (PQC), or quantum-safe cryptography, which will resist attacks by both classical and quantum attackers. The paper is a review of the latest research and development in post-quantum cryptographic algorithms and their implementation in current security systems. We organize quantum-safe methods into significant organizations such as lattice-based, hash-based, multivariate polynomial-based and code-based encrypted communications. Each type has been evaluated critically based on computational efficiency, key sizes, speed of encryption/decryption and security proofs. The survey also examines the current standardization activities happening in the world and especially the U.S. National Institute of Standards and Technology (NIST) PQC competition, which lists candidate algorithms that have advanced to standard adoption. Besides this, the paper addresses hybrid cryptographic designs that use both classical and post-quantum bases in ensuring a seamless migration in the transition phase. Internet security protocols like TLS, VPNs and blockchain consensus as applications of PQC are examined in detail. Lastly, we pinpoint open research issues, which include creating lightweight PQC to support resource-constrained IoT devices, balancing performance and strong security assurances, and interoperability between the new PQC algorithms and existing infrastructures. Through detailed survey we inform the future of researchers, practitioners, and policymakers on the preparation of the post-quantum era of secure digital communications.

International Journal of Engineering Research and Science & Technology•Feb 6, 2024•0 citations
Quantum computing furnishes exponential speed up over classical computing in specific areas. For example, Shor’s algorithm can factor two numbers in a polynomial time complexity. Thus, many encryption algorithms that rely on large number factorization are potentially vulnerable to quantum computers. In order to address this, the National Institute of Standard and Test (NIST) has organized a competition to evaluate several post quantum cryptography (PQC) algorithms, that are secure from the attacks from quantum computers. Several of these lattice-based PQC encryption algorithms are based on Learning With Errors (LWE) computation. Conversely, LWE is the heaviest computation in a classical computer, which incurs significant portion of the latency overhead for the entire encryption algorithm. In this paper, we design an optimized quantum circuit for LWE computation. The proposed quantum circuit does not need any ancillary qubits and scales efficiently and easily if there are more qubits available on a higher qubit quantum computer.
The imminent threat posed by the realization of large-scale, fault-tolerant quantum computers (QCs), capable of leveraging Shor's algorithm to break foundational classical public-key cryptosystems like RSA and ECC, necessitates an immediate and comprehensive shift to Post-Quantum Cryptography (PQC). This urgency is intensified by the "Harvest Now, Decrypt Later" (HNDL) threat, which compromises long-term data confidentiality. The NIST PQC Standardization process has established Lattice-Based Cryptography as the leading family for new standards. This paper presents a comprehensive comparative analysis of major PQC schemes built upon the foundational mathematical problem, Learning with Errors (LWE). We systematically evaluate these LWE-based schemes (CRYSTALS-Kyber, CRYSTALS-Dilithium) by balancing three critical dimensions: cryptographic security (against classical and quantum attacks), efficiency metrics (key size, signature size, and operational speed), and implementation feasibility across diverse hardware environments. Our findings provide essential insights and a structured framework to guide engineers, policy-makers, and organizations in making informed decisions for the strategic and secure migration to quantum-resistant standards in the post-quantum transition era.
Ring Learning With Errors (Ring-LWE) is one of the basic schemes used to develop cryptographic algorithms that are resistant to quantum attacks, offering better computational efficiency compared to standard Learning With Errors (LWE). Ring-LWE uses the algebraic characteristics of polynomial rings to create a robust and fast encryption system. This study implements and evaluates the Ring-LWE algorithm in the context of public key exchange and encryption. Simulations are performed with various security parameters, including modulus size and error rate, to test the resistance to brute force attacks and lattice-based attacks. The experimental results show that the Ring-LWE algorithm can achieve a balance between security and computational efficiency, with shorter processing time than conventional LWE while maintaining a high level of security even in the face of quantum computers. From this study, it can be concluded that Ring-LWE is an excellent choice for application in post-quantum security systems, especially in encrypted communication and digital authentication applications. The next step can be directed at optimizing resource utilization and testing against various types of attacks.
Quantum computing has advanced rapidly in recent decades, driven by developments across the technology stack, including quantum error-correcting codes and efficient quantum algorithms. Among these, quantum arithmetic circuits serve as fundamental building blocks for various promising algorithms. Despite their crucial role, the design of quantum arithmetic circuits faces challenges arising from the no-cloning theorem, qubit limitations, and circuit depth constraints, which significantly impact the efficiency of large-scale quantum computing. We provide an overview of quantum arithmetic circuits in the context of public-key cryptanalysis, with particular emphasis on optimization strategies such as measurement-based uncomputation and conditionally clean ancilla. We review state-of-the-art designs for essential arithmetic operations in public-key cryptanalysis such as addition, multiplication, and modular exponentiation. We also present an overview of the techniques used for fault-tolerant runtime and resource estimation in quantum cryptanalysis. In brief, this chapter emphasizes strategies for designing resource-efficient quantum arithmetic circuits, providing a basis for realistic evaluations of quantum cryptanalytic capabilities.
Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.
This thesis focuses on constructing efficient quantum circuits for arithmetic operationsand applying them to Shor’s factoring algorithm to answer the question: Whatwould be sufficient computational resources for a quantum computer to be able toperform Shor’s factoring algorithm for a large input number? The answers to theproblem would contribute to our understanding of the computational power of smallquantum circuits such as logarithmic-depth quantum circuits. Moreover, the answerswould be useful for analyzing the detailed relationships between the computationalpower of a quantum computer and the security of cryptosystems and for designinga new cryptosystem that is secure against a quantum computer. First, I constructa linear-size quantum circuit for addition with no ancillary qubits. This is an affirmativeanswer to Cuccaro et al.’s question. Then, using the circuit, I construct alogarithmic-depth quantum circuit for addition with few qubits and apply it to constructingan O(n2 log n)-depth O(n3 log n)-size quantum circuit for Shor’s algorithmwith 2n+O(n/ log n) qubits, where n is the length of the number to be factored. Thenumber of qubits is less than that in any other O(n2 log n)-depth quantum circuit everconstructed for Shor’s algorithm. Then, I construct a quantum circuit for comparisonwith uninitialized ancillary qubits and apply it to constructing an O(n3)-depthO(n3 log n)-size quantum circuit for Shor’s algorithm with 2n+2 qubits. The numberof qubits is less than that in any other quantum circuit ever constructed for Shor’salgorithm. Lastly, on a linear nearest neighbor architecture, I construct a small-sizequantum circuit for the quantum Fourier transform and apply it to constructing anO(n3)-depth O(n3 log n)-size quantum circuit for Shor’s algorithm with 2n+4 qubits.The size is less than that of any other quantum circuit ever constructed for Shor’salgorithm on a linear nearest neighbor architecture.
The threats are existential to the traditional cryptosystems of public keys, including RSA, Diffie-Hellman, and elliptic curve cryptography (ECC), due to the rapid progress in quantum computing. Such algorithms as the Shor and Grover algorithms prove that as soon as large scale quantum computers are achieved, these classical cryptographic protocols will not provide any privacy and integrity to online communication. This has created an emergency to find post-quantum cryptography (PQC), or quantum-safe cryptography, which will resist attacks by both classical and quantum attackers. The paper is a review of the latest research and development in post-quantum cryptographic algorithms and their implementation in current security systems. We organize quantum-safe methods into significant organizations such as lattice-based, hash-based, multivariate polynomial-based and code-based encrypted communications. Each type has been evaluated critically based on computational efficiency, key sizes, speed of encryption/decryption and security proofs. The survey also examines the current standardization activities happening in the world and especially the U.S. National Institute of Standards and Technology (NIST) PQC competition, which lists candidate algorithms that have advanced to standard adoption. Besides this, the paper addresses hybrid cryptographic designs that use both classical and post-quantum bases in ensuring a seamless migration in the transition phase. Internet security protocols like TLS, VPNs and blockchain consensus as applications of PQC are examined in detail. Lastly, we pinpoint open research issues, which include creating lightweight PQC to support resource-constrained IoT devices, balancing performance and strong security assurances, and interoperability between the new PQC algorithms and existing infrastructures. Through detailed survey we inform the future of researchers, practitioners, and policymakers on the preparation of the post-quantum era of secure digital communications.