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 ...
- 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 ...
- 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 $...
- 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 ...
- 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 ...
- 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'...
- 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 ...
- 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 ...
- 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, ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 853
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
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 ...
- 449
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 ...
- 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, ...
- 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 ...
- 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. ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 125k
Only top scored, non community-wiki answers of a minimum length are eligible