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

American Scientist

Turning Hard Problems into Post-quantum Solutions

Gretchen L. Matthews

Published Jan 1, 2024• 0 citations
Publisher
DOI
10.1511/2024.112.2.82

Related papers

Quantum Reductions from Hard problems

Nai-Hui Chia

•Apr 2, 2018•0 citations

Cryptanalysis of Post-Quantum Security Schemes Based on the Hardness of the Inhomogeneous Small Integer Solution (ISIS) Problem

An Braeken, Awaneesh Kumar Yadav

With the rise of new advancements in quantum computing, more attention is given to the development of post-quantum security primitives and protocols. Recently, several authentication, key agreement and signature schemes relying on the hardness of the Inhomogeneous Small Inter Solution (ISIS) and its variants have been defined in literature. The advantage of these schemes is that they are simple, easy to implement and possess a reasonable communication and computation cost, compared to other post-quantum alternatives. Unfortunately, we show serious attacks on six different categories of these schemes, corresponding with more than ten publications in recent highly reputed journals. These vulnerabilities pose serious risks to consumer electronics, including IoT devices, smart home systems, and wearable technologies, where secure communication and authentication are vital. Exploitation of these vulnerabilities could lead to unauthorized access, device tampering, and data breaches, significantly impacting user trust and device functionality. Finally, we discuss the feasibility of defining post-quantum secure key exchange protocols, based on the ISIS problem and propose a high level approach to derive secure post-quantum protocols.

IEEE Transactions on Consumer Electronics•Nov 17, 2025•2 citations

Advancing stable set problem solutions through quantum annealers

Janez Povh, Dunja Pucher

We assess the performance of D-wave quantum solvers for solving the stable set problem in a graph, one of the most studied NP-hard problems. We perform computations on some instances from the literature with up to 125 vertices and compare the quality of the obtained solutions with known optimum solutions. It turns out that the hybrid solver gives very good results, while the Quantum Processing Unit solver shows rather modest performance overall.

arXiv:2308.13041•Aug 23, 2023•2 citations

Quantum Solutions to Difficult Problems

Science•Apr 20, 2001•0 citations

Making Hard Problems for Quantum Computers

Anonymous

Physics•Jul 14, 2016•0 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 Cryptology•Oct 26, 2026•0 citations
With the rise of new advancements in quantum computing, more attention is given to the development of post-quantum security primitives and protocols. Recently, several authentication, key agreement and signature schemes relying on the hardness of the Inhomogeneous Small Inter Solution (ISIS) and its variants have been defined in literature. The advantage of these schemes is that they are simple, easy to implement and possess a reasonable communication and computation cost, compared to other post-quantum alternatives. Unfortunately, we show serious attacks on six different categories of these schemes, corresponding with more than ten publications in recent highly reputed journals. These vulnerabilities pose serious risks to consumer electronics, including IoT devices, smart home systems, and wearable technologies, where secure communication and authentication are vital. Exploitation of these vulnerabilities could lead to unauthorized access, device tampering, and data breaches, significantly impacting user trust and device functionality. Finally, we discuss the feasibility of defining post-quantum secure key exchange protocols, based on the ISIS problem and propose a high level approach to derive secure post-quantum protocols.
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.