31
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 ...
- 49.5k
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 ...
- 5,883
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 ...
- 26.4k
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-...
- 336
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) ...
- 5,883
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 ...
- 28.2k
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,933
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,261
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
11
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 ...
- 111
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
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; ...
- 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 ...
- 23.7k
9
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 ...
- 146k
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 ...
- 146k
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 ...
- 528
8
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 ...
- 191
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 ...
- 151k
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.
...
- 14.6k
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 ...
- 26.4k
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.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 ...
- 1,584
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 ...
- 96
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 ...
- 94.5k
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 ...
- 151k
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....
- 94.5k
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,584
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 > ...
- 399
6
votes
Accepted
Is quantum randomness different to conventional randomness?
Statistically, yes, random is random (read: entropy). It's also worth stating that you can really only approximate how random something is based on samples. This means that you can't measure ...
- 214
Only top scored, non community-wiki answers of a minimum length are eligible