Post-Quantum Cryptography Beyond Computational Security

T. Attema, Nicole Gervasoni, M.J.H. Marcus, Gabriele Spini

Published Jan 1, 2021• 0 citations

Abstract

The advent of a full-scale quantum computer will severely impact most currently-used cryptographic systems.The most well-known aspect of this impact lies in the computational-hardness assumptions that underpin the security of most current public-key cryptographic systems: a quantum computer can factor integers and compute discrete logarithms in polynomial time, thereby breaking systems based on these problems.However, simply replacing these problems by other which are (believed to be) impervious even to a quantum computer does not completely solve the issue.Indeed, many security proofs of cryptographic systems are no longer valid in the presence of a quantum-capable attacker; while this does not automatically implies that the affected systems would be broken by a quantum computer, it does raises questions on the exact security guarantees that they can provide.This overview document aims to analyze all aspects of the impact of quantum computers on cryptographic, by providing an overview of current quantum-hard computational problems (and cryptographic systems based on them), and by presenting the security proofs that are affected by quantum-attackers, detailing what is the current status of research on the topic and what the expected effects on security are.

Related papers

Post-Quantum Cryptography: Computational-Hardness Assumptions and Beyond.

Thomas Attema, Nicole Gervasoni, Michiel Marcus +1 more

The advent of a full-scale quantum computer will severely impact most currently-used cryptographic systems. The most well-known aspect of this impact lies in the computational-hardness assumptions that underpin the security of most current public-key cryptographic systems: a quantum computer can factor integers and compute discrete logarithms in polynomial time, thereby breaking systems based on these problems. However, simply replacing these problems by other which are (believed to be) impervious even to a quantum computer does not completely solve the issue. Indeed, many security proofs of cryptographic systems are no longer valid in the presence of a quantum-capable attacker; while this does not automatically implies that the affected systems would be broken by a quantum computer, it does raises questions on the exact security guarantees that they can provide. This overview document aims to analyze all aspects of the impact of quantum computers on cryptographic, by providing an overview of current quantum-hard computational problems (and cryptographic systems based on them), and by presenting the security proofs that are affected by quantum-attackers, detailing what is the current status of research on the topic and what the expected effects on security are.

Jan 1, 20210 citations

Post Quantum Cryptography

Kirandeep Kaur, Arwinderjit Kaur, Manmeet Kaur

The increasing advancement in quantum computing threatens the security of traditional cryptographic systems that underpin much of the modern world’s data protection. These systems rely heavily on the computational difficulty of problems like integer factorization (RSA) and elliptic curve discrete logarithms (ECC), which quantum computers could solve in polynomial time. As a result, there is an urgent need for cryptographic systems that remain secure even in the presence of quantum capabilities. Post-Quantum Cryptography (PQC) is the emerging field that aims to develop cryptographic protocols resistant to quantum-based attacks. This paper discusses the need for PQC, explores various candidate algorithms, reviews standardization efforts, and looks at the current challenges and future directions in the field.

Jan 1, 20260 citations

Post-Quantum Cryptography for Navigating Challenges and Exploring Opportunities

Tejinder Sharma, Shivangi, Rishab Sharma

The rise of quantum computing poses a significant threat to the security of such classical cryptographic systems, as they inherently depend on the computational difficulty of problems such as integer factorization and discrete logarithm. Examining Theoretical Foundations of Post-Quantum Cryptography: Challenges and Opportunities for Building Secure Cryptographic Protocols in the PostQuantum World This paper aims to explore how quantum computers will affect the current state of cryptography, contributing towards the ongoing discussion to upgrade our cryptographic systems' foundations in the face of potential quantum attacks and assessing the efforts for developing quantum-resilient algorithms. Quantum computers promise unprecedented computation power by harnessing the strange properties of quantum mechanics. While quantum algorithms still pose a significant threat to conventional cryptography, the emergence of post-quantum algorithms offer hope to secure our data in the quantum era

International Journal of Research and Review in Applied Science Humanities and TechnologyJan 30, 20253 citations

Recent Developments in Post-Quantum Cryptography

Tsuyoshi Takagi

The security of current public-key cryptosystems relies on the hardness of factoring large integers or solving discrete logarithm problems. However, these mathematical problems can be solved in polynomial time using a quantum computer. This vulnerability has prompted research into post-quantum cryptography using alternative mathematical problems that are secure in the era of quantum computers. In this regard, the National Institute of Standards and Technology (NIST) began to standardize post-quantum cryptography in 2016. In this expository article, we give an overview of recent research on post-quantum cryptography. In particular, we describe the construction and security of multivariate polynomial cryptosystems and lattice-based cryptosystems, which are the main candidates of post-quantum cryptography.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesDec 31, 20173 citations

Quantum Resistant Cryptography and Cyberwarfare

William Easttom

Quantum computing poses a significant threat to conventional cryptographic systems that rely on the difficulty of mathematical problems such as integer factorization and discrete logarithms. These systems underpin much of the current security infrastructure, including public key cryptography and digital signatures. As quantum computers approach practical viability, there is an urgent need to transition to quantum-resistant cryptographic solutions that can secure digital communications against adversaries equipped with quantum capabilities. This paper explores the landscape of quantum-resistant cryptography, focusing on those algorithms that have emerged either as standards or as leading algorithm. Furthermore, the paper examines the progress of standardization efforts, such as the National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) initiative, and the implications of deploying these algorithms in existing systems. By addressing the practical considerations for adoption, this study aims to provide a comprehensive overview of the current state and future directions of quantum-resistant cryptography, ensuring robust security in a post-quantum world.

International Conference on Cyber Warfare and SecurityMar 24, 20251 citation

Review of Quantum Computing Advances and their Impact on Modern Cryptographic Security

Niravkumar Prajapati

Quantum computing is poised to revolutionize numerous sectors, with cryptographic security identified as one of the most critically affected domains. For instance, Elliptic Curve Cryptography (ECC) and RSA, two traditional encryption techniques, rely on the computational difficulty of integer factorization and discrete logarithms. Nevertheless, quantum algorithms, particularly Shor's algorithm, which jeopardizes the security of existing cryptographic systems, may be able to address these problems successfully. This discovery necessitates the development of cryptographic techniques that are impervious to quantum attacks. The study of post-quantum cryptography (PQC), which includes hash-based, lattice-based, and other quantum-resistant algorithms, is becoming essential to ensuring the long-term confidentiality and integrity of data. This paper explores the basic concepts of quantum computing, their relationship to cryptographic privacy, and potential solutions for the associated security problems in the quantum age.

May 29, 20252 citations