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 ...
post-quantum-cryptography lattice-crypto complexity multivariate-cryptography code-based-cryptography
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 ...
post-quantum-cryptography lattice-crypto complexity multivariate-cryptography code-based-cryptography
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 ...
post-quantum-cryptography lattice-crypto complexity multivariate-cryptography code-based-cryptography
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
Related Tags
complexity × 217encryption × 27
hash × 19
public-key × 15
rsa × 14
factoring × 13
discrete-logarithm × 12
cryptanalysis × 11
algorithm-design × 11
brute-force-attack × 11
one-way-function × 10
provable-security × 9
aes × 8
post-quantum-cryptography × 8
hardness-assumptions × 8
elliptic-curves × 7
symmetric × 7
number-theory × 7
des × 6
lattice-crypto × 6
finite-field × 6
zero-knowledge-proofs × 5
garbled-circuits × 5
block-cipher × 4
collision-resistance × 4