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 ...
user avatar
  • 992
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 ...
user avatar
  • 8,677
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 $...
user avatar
  • 11.7k
13 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 ...
user avatar
  • 11.7k
11 votes

Why is lattice-based cryptography believed to be hard against quantum computer?

I'm unaware of a great answer to this problem. There are "partial answers", but they are not great. Still, they are what I use to (vaguely) explain things, being someone interested in ...
user avatar
  • 8,677
11 votes

What does the modulo plus minus mean?

From the NIST Post-Quantum Cryptography Round 3 submission for Crystals-Kyber: Modular reductions. For an even (resp. odd) positive integer α, we define $r' = r\bmod^± α$ to be the unique element $r'...
user avatar
  • 1,480
10 votes

Why did NIST select Kyber and Dilithium?

NIST did consider the MATZOV attacks. If we read their Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, we see in section 4.1.1 on page 29: During the ...
user avatar
  • 11.7k
8 votes
Accepted

Difference signature / asymmetric encryption (PQC)

The question's statement The signature algorithms are based on public-key encryption algorithms goes straight against accepted wisdom. Which is that signature and public-key encryption are separate ...
user avatar
  • 125k
6 votes
Accepted

NSA removed EC-256 and SHA-256 from CNSA recently--should we be alarmed by this?

NSA removed EC-256 and SHA-256 from CNSA recently--should we be alarmed by this? No. There is one overwhelming reason why, as stated in the document: The cryptographic systems that NSA produces, ...
user avatar
  • 12.7k
6 votes
Accepted

Post-quantum algorithms and side channel attacks

Why are classical cryptanalysis methods -algebraic, mathematical attacks etc.- more effective on classical algorithms than post-quantum algorithms? I feel that this is a little unfair on some ...
user avatar
  • 11.7k
6 votes

The XOR operation, is it a quantum resistant operation and why is that? if not, what is the most lightweight alternatives?

You are making a category error. The XOR operation is not a trapdoor function or hardness problem. For an algorithm to be weakened by quantum computers, it has to be easy in one direction and tough in ...
user avatar
  • 13.5k
5 votes

Post-quantum algorithms and side channel attacks

I noticed that almost all third party cryptanalysis papers consist of side-channel attacks. Well, there certainly are papers examining the strength of these postquantum algorithms and the hardness of ...
user avatar
  • 133k
5 votes
Accepted

Why are public keys derived from elliptic curve cryptography (ECC) and not from hashing?

…Public keys are derived from private keys using ECDSA … using secp256k1. Not quite. The transformation of private key to public key is not using ECDSA. It's per the parameters of secp256k1, using an ...
user avatar
  • 125k
5 votes
Accepted

Is password hashing post-quantum secure?

Does Grover's algorithm (or any other applicable quantum algorithm) only apply to weakening the hash function itself or can it also search only plausible inputs (a-z, A-Z, 0-9 <=14 characters) to ...
user avatar
  • 133k
5 votes

In multivariate public key cryptography, why can not we use the same public key for both signature and encryption?

For a signature scheme, the function $P$ needs to be surjective i.e. for every element of the output space there exists at least one input that produces that output. This is so that the signer is able ...
user avatar
  • 11.7k
4 votes
Accepted

CSIDH - l ideal generators

To answer your first question: it's as simple as that. Restating what you wrote, it's enough to check that $l$ divides all the four generators: $l^2$, $l(π-1)$, $l(π+1)$ and $π^2-1$. It's obvious for ...
user avatar
4 votes

Why RLWE is hard or even has a solution?

There are two key points that you are mentioning (one mentioned by Poncho in the comments --- I repeat here for exposition purposes). The RLWE errors $e_i(x)$ are small, and the secret $s(x)$ is ...
user avatar
  • 8,677
4 votes
Accepted

Post quantum security experiment

Cryptanalysis with adversaries capable of submitting superpositions of inputs and interpreting superpositions of outputs does exist, but is still relatively new with relatively little work. The ...
user avatar
  • 11.7k
4 votes
Accepted

Is there a quantum algorithm to find SHA256 collisions?

In 2009, D J Bernstein wrote one of the early papers on this topic available here: The abstract states: Current proposals for special-purpose factorization hardware will become obsolete if large ...
user avatar
  • 16.6k
4 votes
Accepted

Is the combination of X25519 ECDH and NTRU in OpenSSH 9.X secure against quantum attacks?

Can the combination of X25519 ECDH and NTRU in OpenSSH 9.X defend me against quantum attacks? Actually, that version of OpenSSH uses NTRU Prime, rather than NTRU. However, that does not change the ...
user avatar
  • 133k
4 votes
Accepted

RLWE Explanation

The cyclotomic polynomials are used in the proofs that worst-case lattice problems reduce to the RLWE. If you try to instantiate RLWE with other polynomials, then you don't have such formal guarantees ...
user avatar
4 votes

Is Argon2 Quantum safe?

Simply put, it should be because it's based on BLAKE2b, it's memory hard, and symmetric cryptography is relatively unaffected by quantum computing since attacks can't be carried out efficiently ...
user avatar
3 votes

Testing of PQC NIST round3 submissions

How does NIST do a comparison that a particular algorithm is efficient and its security can not be broken by future quantum attacks? How efficient an algorithm to implement is easy - these algorithms ...
user avatar
  • 133k
3 votes
Accepted

What is the security strength of XMSS according to NIST PQC categories?

In which category does XMSS fall when instantiated with SHA256 or SHAKE256? Well, XMSS is as strong as the second preimage resistance of the underlying hash function - with either SHA256 or SHAKE256, ...
user avatar
  • 133k
3 votes

Natural resistance to side channel attacks of XMSS/LMS/SPHINCS+

All these post quantum signature schemes are claimed by the authors to be naturally resistant to side channel attacks. My question is, why or how? Well, lets break this down: In terms of timing and ...
user avatar
  • 133k
3 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. ...
user avatar
  • 43.5k
3 votes
Accepted

Are PKI PQC algorithms slower than their nonPQ counterparts? (e.g. NTRU vs RSA)

Computation wise, there are schemes faster in some functions (e.g. KEM, sign, verify). Commnication cost wise, generally PQC schemes have larger communication cost than current public key ...
user avatar
  • 325
3 votes
Accepted

Difference between FFT and NTT

TL;DR You need NTTs for exact arithmetic in crypto applications. FFT is just an algorithm for evaluating the traditional DFT, for complex valued (note reals and integers are subsets of the complex ...
user avatar
  • 16.6k
3 votes

Difference between FFT and NTT

Disclaimer: Comp-Sci math ahead, proper mathematicians beware. ;) Fast Fourier Transform (FFT) and Discrete Fourier Transform (DFT) The FFT is an algorithm which allows to calculate the DFT, as well ...
user avatar
  • 578
3 votes

Tree Parity Machines (neural cryptography) advantages

After like an hour of search on the subject of Tree Parity Machines as an alternative to Diffie-Hellman key exchange, I found that: It started with this article: Ido Kanter, Wolfgang Kinzel and Eran ...
user avatar
  • 125k

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