30 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 ...
26 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 ...
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-...
19 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) ...
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 ...
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 ...
  • 4,721
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 ...
  • 1,126
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 ...
  • 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 ...
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 ...
  • 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 ...
  • 134k
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 ...
9 votes
Accepted

Is full Homomorphic encryption quantum resistant?

Actually, most of the primitives that are currently believed to be secure FHE methods would appear to be quantum resistant; a partial list would include Craig Gentry's original scheme based on ideal ...
  • 134k
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; ...
  • 716
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 ...
  • 16.9k
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 ...
  • 126k
9 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 ...
  • 91
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 ...
  • 508
8 votes
Accepted

Small Quantum Signatures - Reality check needed

I see two problems with this idea. The first problem is Shor's algorithm; that's a quantum algorithm that is able to find the cycle length of a group (and if you can solve that problem, it is easy to ...
  • 134k
8 votes

What does "a 15360-bit RSA key is the equivalent to a 256-bit symmetric key" mean?

The statement a 15360-bit RSA key is the equivalent to a 256-bit symmetric key does not take into account quantum algorithms. In fact, it is based on a specific computation model. It is just ...
  • 124
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 ...
  • 134k
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. ...
  • 8,742
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 ...
  • 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 ...
  • 19.3k
7 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 ...
  • 126k
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 ...
  • 86.4k
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 ...
  • 134k
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....
  • 86.4k
6 votes

What role plays Quantum Fourier Transformation in Shor's integer factorization algorithm?

To do factoring, Shor's algorithm presents a way of finding the the following problem. If I know some natural numbers $g$ and $N$, with $g < N$, where $\gcd(g, N) = 1$, what is the smallest $r > ...
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 ...
  • 1,554

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