Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
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
29 votes

How effective is quantum computing against elliptic curve cryptography?

Elliptic curve cryptography is not presently vulnerable to quantum computing because there are no quantum computers big and reliable enough to matter. But it would be vulnerable to quantum computers ...
Squeamish Ossifrage's user avatar
27 votes
Accepted

Will IBM's Condor quantum processor run Shor's Algorithm to crack a 256-bit Elliptic Curve key?

No. The issue here is the distinction between physical qubits and logical qubits. The back of the envelope estimate for Shor's algorithm for a 256-bit elliptic curve is 512 logical qubits, but a more ...
Daniel S's user avatar
  • 23.9k
22 votes
Accepted

What does a "real" quantum computer need for cryptanalysis and/or cryptographic attack purposes?

For example: the 5-qubit quantum computer created at MIT by using the technique of ion traps succeeded in prime-factorizing 15. Does that mean that since it succesfully managed that, that it is a all-...
DanielSank's user avatar
20 votes
Accepted

New quantum attack on lattices (or Shor strikes again)?

As mentioned in the comments, there is a serious flaw in the paper, and it has been withdrawn: see https://groups.google.com/forum/#!msg/cryptanalytic-algorithms/WNMuTfJuSRc/OtQMLRXgBwAJ and part (3) ...
Chris Peikert's user avatar
16 votes

New quantum attack on lattices (or Shor strikes again)?

The authors themselves point out that this doesn't break lattice-based assumptions used in crypto. To quote: Lattice problems have received enormous attention in recent years, mainly because of ...
Yehuda Lindell's user avatar
16 votes
Accepted

Dice vs quantum random number generator

From the manufacturer's website: Quantis uses Quantum Physics to create truly random numbers Existing randomness sources can be grouped in two classes: software solutions, which can only ...
Elias's user avatar
  • 4,913
15 votes

New quantum attack on lattices (or Shor strikes again)?

Unless I misunderstood the definitions, an algorithm for the problem in Definition 1 (i.e. their main result) is in fact enough to attack decision-LWE if the noise is small. The fact that they need a ...
Vadim L.'s user avatar
  • 1,146
13 votes
Accepted

Qubit / Qutrit - Is there a theoretical limit on how many orthogonal states a quantum bit has?

There is, in principle, no limit to the dimension of the state space of a quantum system. This includes infinite dimension (usually countable, i.e. a separable Hilbert space) and any large but finite ...
E.P.'s user avatar
  • 246
12 votes
Accepted

Are there any applications of Quantum Computation to Cryptography? (besides Cryptanalysis)

As noted by kodlu, you are basically asking about the existence of the whole field of quantum cryptography (which is different from post-quantum cryptography). All the field was arguably started by ...
Frédéric Grosshans's user avatar
11 votes
Accepted

How does quantum encryption work?

There are a few key distinctions to make Quantum cryptanalysis This is what you hear all the buzzing about. Specifically, there is something called Shor's algorithm, that when used to break modern ...
J.A.K.'s user avatar
  • 433
10 votes
Accepted

Can Shor's algorithm compromise RSA when both the public and private key are secret?

Actually, if RSA is being used in a deterministic way (and the public exponent $e$ is relatively small), someone could recover the value $N$. We know that $P^e = C \bmod N$; that's equivalent to $P^e ...
poncho's user avatar
  • 148k
10 votes

In quantum cryptography, why can a qubit can be both 0 and 1 at the same?

“Both 0 and 1 simultaneously” is a lie-to-children: it's a simplification intended to be comprehensible and not fully accurate. It's not a very good one. A better way to present it is that a qubit is ...
Gilles 'SO- stop being evil''s user avatar
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
Accepted

Generating a random number using a quantum computer

Yes, it is possible to use quantum computer as a true random number generator, by applying Hadamard gates to all available qubits in initial $|0\rangle$ state and measuring them in the standard basis; ...
kludg's user avatar
  • 736
9 votes

Are there any applications of Quantum Computation to Cryptography? (besides Cryptanalysis)

Quantum Key Distribution as a concept dates back to the BB84 (Bennett, Brassard) protocol, and has been implemented for countering passive attacks, such as Man in the Middle. In theory it is ...
kodlu's user avatar
  • 22.6k
9 votes
Accepted

Quantum Cryptography Used in a messaging application

NO, if "messaging application" is software running on an stock consumer-grade computer or variant (including mobile phone, tablet): in any of its standard meanings, Quantum Cryptography ...
fgrieu's user avatar
  • 142k
8 votes

How does quantum encryption work?

Quantum key distribution takes advantage of physics to create a communication channel that can't be cleanly intercepted without corrupting part of the message. This can be used to create a shared ...
Macil's user avatar
  • 528
8 votes

How effective is quantum computing against elliptic curve cryptography?

Some ECC cryptosystems in wide use, including ECDSA and Ed25519, ECDH.. are theoretically vulnerable to quantum computing, should that ever become usable for cryptanalysis (Cryptographically Relevant ...
fgrieu's user avatar
  • 142k
8 votes
Accepted

Can AES be broken by factorization (using Quantum Period Finding)?

Two things: Firstly, the paper is not talking about factorization at all; instead, it is using the Quantum Computer as a "constant-that-doesn't-change-the-output" algorithm (that is, find an $s$ such ...
poncho's user avatar
  • 148k
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.3k
8 votes

How could ECDSA be broken with prime factorization through Shor's Algorithm?

I'm going to give a more detailed version of @poncho's answer. Let me know if you'd like more detail on any point and I can make it still longer. Ideas that you might need to read additional ...
Daniel S's user avatar
  • 23.9k
7 votes
Accepted

Advantages of RSA / EC against QC attacks

This is by no means a comprehensive answer on this subject, but perhaps it's a good start. Shor's algorithm for (specific) ECC This paper by Proos and Zalka compares implementations of Shor's ...
bkjvbx's user avatar
  • 1,554
7 votes
Accepted

How could consumer level OTP + QKD over the internet ever be practical?

There are many questions here; I am not answering the question in the title, but rather addressing the final questions in the body. One-time pad encryption nevertheless has a bright future. It is ...
Ella Rose's user avatar
  • 19.6k
7 votes

How can Shor's Algorithm be applied to ECC?

Section 2.2 of the following paper details how to apply Shor's algorithm to ECDLP: https://eprint.iacr.org/2017/598.pdf The process is similar to DLP, except that we need different circuits to ...
user44248's user avatar
7 votes

How effective is quantum computing against elliptic curve cryptography?

Most of public key algorithms used today are based on two mathematical problems, the factorization of large numbers (e.g., RSA) and the calculation of discrete logarithms (e.g., DSA signatures and ...
user_58972's user avatar
7 votes

Practical quantum attacks on AES - Is AES-128 used in a block mode vulnerable to attack using quantum algorithms

Sure, you can use Grover's algorithm to attack AES-128 in CTR mode. Assume the attacker knows a few plaintext blocks and the counter. The AES ciphertext blocks that are generated by encrypting this ...
Maarten Bodewes's user avatar
  • 92.9k
7 votes
Accepted

Can we break RSA with an optical Fourier transform?

The horsepower underlying this algorithm is the Fourier transform Not quite; the algorithm is to generate a superposition of states, compute the modular exponentiation of those states (generating the ...
poncho's user avatar
  • 148k
7 votes
Accepted

What are the misconceptions of IBM's CEO Arvind Krishna talk on the "Axios on HBO" about the quantum computing

IBM says its new Eagle processor can handle 127 qubits, a measure of quantum computing power. I have no doubt that they have 127 physical qubits. I'm not sure how stable it is or anything else though....
Maarten Bodewes's user avatar
  • 92.9k
6 votes
Accepted

Mathematically/Theoretically calculating time to brute-force RSA encryption keys for a quantum computer vs a Classical computer?

Is there any way to theoretically, by the use of mathematics, to calculate the time taken to brute-force RSA keys? Even classically, this is not so easy as you seem to imply. RSA is based on the ...
bkjvbx's user avatar
  • 1,554

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