New answers tagged

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