Skip to main content
53 votes
Accepted

Largest integer factored by Shor's algorithm?

wondering what the largest integer is which they were able to factor with a small quantum computer This answer starts with stunt records. See final paragraph for the the largest meaningful record. ...
37 votes

Applicability of IBM's projected 50-qubit quantum computer Q to cryptanalysis?

What would be the applicability of that to cryptanalysis? It wouldn't appear to have any direct applicability to cryptanalysis, for two reasons: 50 Qbits is just not enough to attack any ...
poncho's user avatar
  • 148k
32 votes
Accepted

Applicability of IBM's projected 50-qubit quantum computer Q to cryptanalysis?

TL;DR: Not much. If the qubits were very high quality, some very tricky algorithms could use them to do some algorithm subprocesses more quickly, but we actually have more quantity than quality. So it'...
Charles's user avatar
  • 528
31 votes

What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?

There is no public paper available yet, so this answer is preliminary and based on what was presented in the talk and the follow-up discussion. A full understanding cannot be reached until there is a ...
Chris Peikert's user avatar
30 votes
Accepted

How does IBM's 53-bit quantum computer compare to classical ones for cryptanalytic tasks?

How does it compare to classical computers, performance-wise, for cryptanalytic tasks? Not at all - IBM's quantum computer cannot perform any nontrivial cryptanalytic task. For one, 53 physical ...
poncho's user avatar
  • 148k
26 votes
Accepted

Polynomial-time Quantum Algorithms for Lattice Problems

Current status regarding the correctness TL;DR: the attack is not working. Update: Since April 18 a bug has been found in the paper and the author retracted their claim: Further details are listed ...
Léo Colisson's user avatar
21 votes
Accepted

Can or can not D-Wave's quantum computers use Shor's and Grover's Algorithm to find encryption keys? Why?

D-Wave's "Quantum computers" are NOT general purpose quantum computers. They can only do quantum annealing, which allows a small subset of problems to be solved. They can't run Shor's or Grover's ...
SAI Peregrinus's user avatar
18 votes
Accepted

Factoring 2048-bit integer with quantum computer?

The 20,000,000 is the number of physical qubits of a certain quality required and corresponds most closely to the number of qubits quoted by those engineering teams current developing quantum devices. ...
Daniel S's user avatar
  • 24.1k
17 votes
Accepted

Quantum Computing Used to Break RSA by "fixing" Schnorr's Recent Factorization Claim?

TL;DR This appears unlikely to work at scale, at least with current parameter choices. There's a classical post-processing step which is worse than the quadratic sieve in complexity unless the quantum ...
Daniel S's user avatar
  • 24.1k
16 votes
Accepted

Can quantum computers put computer security in jeopardy?

can they (quantum computers) do such complicated computing (cryptanalysis)? Not currently. Current quantum computers (including the adiabatic variants specialized in quantum annealing) do not perform ...
fgrieu's user avatar
  • 142k
16 votes

New paper claims quantum polylog time attack on AES

There is an answer on the PQC mailing list by Xavier Bonnetain (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/orySwdhmjH8/m/ScE8G_ajBgAJ) which I will copy below: The algorithm begins but ...
lamba's user avatar
  • 1,365
15 votes
Accepted

Is this paper's technique for factoring RSA 2048 with noisy qubits realistic?

I'm one of the authors of the paper. In order to make the paper more approachable, we factored each major optimizations out into its own paper. There are three of these sub-papers, and they each ...
Craig Gidney's user avatar
13 votes
Accepted

New paper claims quantum polylog time attack on AES

I concur with Xavier Bonnetain per lamba's answer, but can add a bit more flesh to what is going on. Working through the proposed algorithm with an $n$-bit search space, looking for a solution $x$ to $...
Daniel S's user avatar
  • 24.1k
11 votes

Polynomial-time Quantum Algorithms for Lattice Problems

Probably it will take some time for the experts in this community to carefully review the paper to see whether it works or not, since it is quite long and technical. Meanwhile, I feel members of this ...
Wenzhe's user avatar
  • 227
11 votes

Polynomial-time Quantum Algorithms for Lattice Problems

A new paper on ePrint (A Note on Quantum Algorithms for Lattice Problems) claims to have found an error on that paper. Quoting: "Our observation is very simple and can be summed up as that the ...
swineone's user avatar
  • 880
10 votes

What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?

I created a website to crowdsource what is known about algorithms for lattice problems in NP intersect CoNP: https://latticealgorithms.xyz Our paper is up: https://arxiv.org/abs/2201.13450 For the ...
SeanH's user avatar
  • 101
9 votes

Can quantum computers put computer security in jeopardy?

If quantum computers are physically feasible, then there are some algorithmic problems that they should be able to solve faster than classical computers. It happens that brute-force search and ...
zwol's user avatar
  • 785
8 votes

What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?

One could give a much longer answer to this question (and I would be quite interested in seeing someone like Chris's perspective), but the following two points probably suffice for a non-specialist. ...
Mark Schultz-Wu's user avatar
  • 13.5k
8 votes

Polynomial-time Quantum Algorithms for Lattice Problems

Yilei Chen published an update on his website yesterday saying that "Step 9 of the algorithm contains a bug", and that he does not yet know if it will be possible to fix it. TLDR: As of ...
ProfCornDog's user avatar
7 votes
Accepted

Are there post-quantum cryptosystems with a gap between classical and quantum security?

Here's an example where the best known quantum attack is, in a sense, just "halfway" between the best known classical attack on one side, and a complete break on the other: Inverting a cryptographic ...
yyyyyyy's user avatar
  • 12.1k
7 votes

Can or can not D-Wave's quantum computers use Shor's and Grover's Algorithm to find encryption keys? Why?

Even though the D-Wave machines can not be labelled as "general purpose", they are certainly research objects with new applications everyday. The capabilities of what they can do is only limited by ...
not2qubit's user avatar
  • 205
7 votes

Quantum Computing Used to Break RSA by "fixing" Schnorr's Recent Factorization Claim?

The consensus among experts seems to be that this does not constitute a break, simply because the classical part of the algorithm still requires exponential time. I don't know whether this could yield ...
Geoffroy Couteau's user avatar
6 votes

What telltale signs would indicate that quantum computers are about to become dangerous to classical cryptography?

There are three main standard quantum threats to traditional cryptography: Shor's algorithm. Spend $O(\log \ell \cdot \log \log \ell)$ quantum gates and $O(\log \ell)$ additional qubits in a quantum ...
Squeamish Ossifrage's user avatar
6 votes

Does the block size of a symmetric cipher impact the security of the cipher itself?

Does the block size of a symmetric cipher impact the security of the cipher itself? Yes, absolutely. A small block size limits the amount of data that can be encrypted with a given key, and some ...
forest's user avatar
  • 15.4k
6 votes

Can Shor's algorithm factor multi-prime numbers?

Shor's algorithm works by using quantum magic to compute a period of $f\colon x \mapsto a^x \bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} \equiv 1 \pmod n$, and if $a^t \not\equiv -1 \pmod ...
Squeamish Ossifrage's user avatar
6 votes
Accepted

Can Shor's algorithm factor multi-prime numbers?

Yes, it can. Quoting the document of DJB: "Post-quantum RSA" by Daniel J. Bernstein, Nadia Heninger, Paul Lou and Luke Valenta, which forest has linked to: If $n$ is a product of more primes, say $...
Maarten Bodewes's user avatar
  • 93.4k
6 votes

Can Shor's algorithm factor multi-prime numbers?

Shor's algorithm finds the prime factors of any integer, regardless of the number of primes. This is explained in this Wikipedia article which describes how the algorithm takes an odd integer and ...
forest's user avatar
  • 15.4k
6 votes
Accepted

Breaking ciphertext using a quantum computer when the public key is not available

You asked: Is it possible to crack RSA / ECC on a quantum computer if we only have ciphertext and don't have the public key used to encrypt itself? Typically not, with a few exceptions; here are ...
poncho's user avatar
  • 148k
5 votes
Accepted

How Will Quantum Computing Change Cryptography's Future?

It depends on the kind of quantum computer and how many logical qubits it has. Not all quantum computer designs are capable of breaking cryptographic systems. The popular adiabatic quantum computers, ...
forest's user avatar
  • 15.4k
5 votes

Does a thermodynamic limit on key search apply to quantum computers?

From this Thermodynamic Analysis of Classical and Quantum Search Algorithms, Sep 29, 2017; For the problem of collision finding, previous work suggested that quantum algorithms were unlikely to ...
kelalaka's user avatar
  • 49.1k

Only top scored, non community-wiki answers of a minimum length are eligible