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

Thomas Attema, Nicole Gervasoni, Michiel 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 Beyond Computational Security

T. Attema, Nicole Gervasoni, M.J.H. 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

A Survey on Security Reductions in Post-Quantum Cryptography

Thomas Attema, Ronald Cramer, Serge Fehr +3 more

It is obviously necessary that the security of post-quantum cryptographic schemes is based on computational problems that are hard to solve even with a quantum computer (unlike, e.g., factoring). Examples of such computational problems appear in the theory of lattices or in coding theory. However, this is not sufficient: also the security proof, which comes in the form of an algorithmic reduction that turns any hypothetical attacker into an algorithm that solves the considered hard computational problem, needs to be valid when considering quantum computing as the model of computation. In this work, we provide an overview of the hurdles one typically encounters when proving the security of post-quantum cryptographic schemes, and we elaborate on some of the mathematical techniques that have been developed in order to overcome these hurdles (to some extent). We also analyze the caveat that even when a security proof can be established (by reducing the security to a quantum-hard computational problem), the reduction often suffers from a larger reduction loss, compared to when proving classical security, which negatively affects the concrete security. In the second part of this work, we offer a survey of the respective reduction losses in (1) generic transformations that are often used in the design of cryptographic schemes (like the Fiat-Shamir and Fujisaki-Okamoto transformations), and (2) some concrete cryptographic schemes (with a focus on those standardized by NIST), when considering classical and when considering post-quantum security. Finally, we investigate how these reduction losses translate into bit security, the standard measure of the concrete security of a cryptographic scheme (or of the hardness of an underlying computational problem). A natural question is how the bit security is affected by the different reduction losses we encountered. Surprisingly, we observe that a better or worse reduction (in terms of the reduction loss) is not always reflected as such in the bit security. We explain this phenomenon by the fact that the bit security is oblivious to the actual advantage–time function, and instead considers a worst-case behavior of that function. Thus, by exploiting the actual advantage–time function there is potential to get more accurate (i.e., less conservative) estimates for the concrete security.

IACR Communications in CryptologyOct 26, 20260 citations

Post-Quantum Cryptography Using Lattices

Patchigulla Pooja, Jakka Ramya, Paras Nath Singh +4 more

The need and emergence of quantum computing under National Quantum Mission threatens the cyber-security of existing cryptographic protocols, especially public-key schemes built on integer factorization and discrete logarithms. Lattice-based cryptography has gained prominence as a robust candidate for post-quantum cryptography—offering security against quantum attacks while enabling efficient operations, parallelization, and novel functionalities. This paper analyzes the mathematical foundations of lattices, explores hardness assumptions underlying widely studied lattice problems, highlights prominent cryptographic constructions, analyzes performance trade-offs, and reviews standardization efforts. This paper concludes by identifying ongoing issues and future directions for lattice-based cryptographic systems in a quantum-secure digital world. The algorithm has been implemented in Python.

IEEE Global Conference for Advancement in Technology (GCAT)Oct 24, 20250 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

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