50 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
  • 21.9k
46 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
29 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
  • 21.9k
26 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
  • 21.9k
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
24 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
  • 32k
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,133
20 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.1k
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
  • 145k
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) ...
Chris Peikert's user avatar
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
  • 6,904
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,607
17 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
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
  • 21.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,136
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,629
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
  • 91.9k
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
  • 91.9k
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
  • 138k
14 votes

Kyber and Dilithium explained to primary school students?

Despite Daniel's valiant effort I think the correct answer is no, you can not with reasonable effort explain the inner workings of post quantum cryptography to most primary school students. You should ...
Meir Maor's user avatar
  • 11.7k
14 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
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's user avatar
  • 11.7k
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
  • 21.9k
12 votes

Is AES-256 a post-quantum secure cipher or not?

We know Grover's algorithm speedup brute-force attacks two times faster in block ciphers (e.g brute-forcing 128-bit keys take 264 operations, not $2^{128}$). This is the advertisement of the Lov K. ...
kelalaka's user avatar
  • 47.6k

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