New answers tagged complexity
0
Problems for post-quantum algorithms do not need to be NP-hard.
The goal of post-quantum cryptography is for the cryptographic scheme to be secure against quantum computers.
For example, a cryptographic scheme in which the hardest part of the decryption algorithm is the factoring of integers is not post-quantum secure because Shor's algorithm for factoring ...
3
I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why lattices are solely "adjacent" to an $NP$-hard problem.
The story is rather simple, but also technical.
Let $\mathsf{LWE}[n, \sigma, q]$ be the average-case ...
2
They don't need to be: isogeny-based cryptography has no connection to any NP-complete problems, as far as I am aware.
Generally you want the underlying mathematical problem to be hard, and you can't get "harder" than NP, since (to be very imprecise) the secret key of a public-key cryptosystem acts like a "witness" for any hard problem ...
4
What I don’t get is why the complexity became quadratic in linear case?
Well, in linear cryptanalysis, for each input, we get a bit with a bias of $0.5 \pm \epsilon$, and we need to determine if that bias is $0.5 + \epsilon$ or whether it is $0.5 - \epsilon$
If we were to query a random bit (that is, one with no bias) $n$ times and sum the results, we're ...
4
You are right. A hash function applied to $n$ bits of input will typically take $O(n)$ work to evaluate. It is important for a hash function to use every single bit of input as part of the calculation or collisions become very, very easy.
The "hashing takes time $O(1)$" is true for fixed/bounded length inputs, but as you say this is misleading.
Top 50 recent answers are included
