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
54 votes
Accepted

Is AES-128 quantum safe?

All of the above sources are correct; there is not a realistic threat to AES from Grover's algorithm. The headline statement of $2^{64}$ quantum operations is often misinterpreted because people think ...
Daniel S's user avatar
  • 23.9k
47 votes
Accepted

Are cryptographic hash functions quantum secure?

It is a bit dubious to claim that hash functions "are not based on any hard problem": inverting a standard hash function, or finding a collision, is itself a very hard problem. The point of ...
Geoffroy Couteau's user avatar
45 votes
Accepted

Does Terra Quantum AG break AES and Hash Algorithms?

The onus is on the company to prove their claims, especially when they are extreme. There is also no financial motivation to not prove their claims. I can understand if they say that they want to keep ...
Yehuda Lindell's user avatar
30 votes

Kyber and Dilithium explained to primary school students?

I'll take that challenge for Kyber, but I fear that a simplification of Dilithium could more easily lead to a dangerous understanding. I'm going to describe a cryptographic design, mini-Kyber, that is ...
Daniel S's user avatar
  • 23.9k
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
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
25 votes

Which elliptic curves are quantum resistant?

Post-quantum crypto is a very young field and is still changing quite rapidly. If you just want a reading list to introduce you to the topics, I would recommend the March 2015 report released by the ...
Mike Ounsworth's user avatar
25 votes
Accepted

Are hash functions strong against quantum cryptanalysis and/or independent enough of mathematics?

This depends on what kind of hash function you mean and what kind of security you want. Poly1305 is an almost-universal hash family, which, when used with a uniform random key for a single message, ...
Squeamish Ossifrage's user avatar
23 votes
Accepted

How many qubits are required to break RSA 2048 or 4096 with a universal quantum computer?

How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer? Like the answer you linked to shows, about $\log_2(N^2) = 2 \log_2(N)$ or just $2n$ where $n$ ...
otus's user avatar
  • 32.1k
22 votes

Why are only lattice problems used in cryptography?

What makes a problem suitable for cryptography is slightly different than what makes a problem NP-hard. What is required for cryptography is average-case hardness --- i.e., a randomly selected ...
ckamath's user avatar
  • 5,268
21 votes
Accepted

Is lattice-based cryptography practical?

Yes, it is feasible. In fact, the NIST post-quantum submissions include a number of lattice-based cryptographic key exchange and signature protocols. As you can see from a summary of the different ...
forest's user avatar
  • 15.3k
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
20 votes
Accepted

Why is pqRSA in the NIST PQC submissions?

[source of information: my interpretation of multiple hallway chats I've had with DJB and Tanja Lange at conferences] The actual NIST PQC submission was for two reasons: A joke. Evidence1: DJB ...
Mike Ounsworth's user avatar
20 votes

Why NIST insists on post-quantum standardization procedure rather than post-quantum competition?

Is there any functional difference on how this process is conducted? One likely difference is the intended end goal. The intended result of the AES process was to approve exactly one proposal, and ...
poncho's user avatar
  • 148k
19 votes

How will the world learn that Q-Day has arrived?

How will the world learn that scalable, fully fault-tolerant quantum computers capable of running Shor's algorithm have arrived? Well, one thing to note is that cryptanalysis is not the only thing a ...
poncho's user avatar
  • 148k
17 votes

Assuming a 1024qb quantum computer, how long to brute force 1024bit RSA, 256bit AES and 512bit SHA512

With a 1024 qubit quantum computer you cannot break any of the algorithm you mentioned. Current estimations for an impelmentation of Grover's algorithm for AES requires much more qubits. According to ...
Ruggero's user avatar
  • 7,104
17 votes
Accepted

Relation between Key-exchange and Public-Key encryption schemes

First, some definitions. A public key encryption scheme (PKE) is a scheme with public and private keys, where we can encrypt a message using the public key and decrypt using the private key. A key ...
K.G.'s user avatar
  • 4,742
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

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
16 votes

The death of isogeny-based cryptography?

It's early days to assess the full implications yet, but there is an excellent blog by Stephen Galbraith that seems to indicate that this does not currently apply to all isogeny-based schemes (in ...
Daniel S's user avatar
  • 23.9k
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
15 votes

Does Terra Quantum AG break AES and Hash Algorithms?

Edit 2021-02-10: covering now their latest press release Red flags While the details of their work/claims are yet to be published, this article is containing a lot of conspicuous statements. Vinokur ...
Lery's user avatar
  • 7,699
15 votes

Does Grover's algorithm really threaten symmetric security proofs?

Yes, but also no. Grover's algorithm is actually quadratically faster than classical algorithms. However there are a few catches. Quantum computers are slow and expensive. This means that in the near ...
Oscar Smith's user avatar
14 votes
Accepted

Does perfect forward secrecy (using DH or ECDH) imply quantum resistance?

No it does not. Perfect forward secrecy implies that even if you retrieve the private key of the asymmetric key pair that you cannot read any of the past or future messages within a connection. It is ...
Maarten Bodewes's user avatar
14 votes
Accepted

Post Quantum Symmetric Cryptography

AES-256 is still considered the strongest (and is considered secure) as related key attacks are not particular to analysis with quantum computers. Related key attacks could happen when AES is used ...
Maarten Bodewes's user avatar
14 votes
Accepted

Is this variant of Diffie-Hellman viable and quantum resilient?

Is this actually a viable method of key exchange? No. An eavesdropper can find the integer $b$ chosen by Bob from $x$ (as sent by Alice) and $b'$ (as sent by Bob), and the equation $b'\,=\,b\,x\bmod ...
fgrieu's user avatar
  • 142k
14 votes
Accepted

Impact of Ryan and Heninger's CRYPTO 2023 paper on post quantum cryptosystems

The following is mostly known to lattices people (and mentioned at the end of the Quanta article), but I also reached out to Keegan to clarify some questions I had. There are (roughly) two main types ...
Mark Schultz-Wu's user avatar
  • 13.3k
13 votes

Which elliptic curves are quantum resistant?

What we traditionally call Elliptic Curve Cryptography (working in the group of points on an elliptic curve over a finite field) is vulnerable to an attack by a quantum computer running Shor's ...
luiz carvalho's user avatar
13 votes

Why is pqRSA in the NIST PQC submissions?

The pqRSA proposal technically complies with the NIST rules for the competition, and, as all governmental organizations, NIST tends to be stickler for rules. Now of course it's a sort of joke (...
Thomas Pornin's user avatar
13 votes

Current Consensus on Security of Lattice Based Cryptography?

The claimed attack does not "break" lattice-based cryptography, merely further improves known attacks. I'll try to briefly describe the situation. Asymptotics: Asymptotically, our best ...
Mark Schultz-Wu's user avatar
  • 13.3k

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