# Tagged Questions

Complexity describes - in simple words - how hard (complex) it is to reach a specific goal; and under which conditions. In cryptography, this mostly ends up in using the complexity theory to analyze things. One of the main goals of complexity theory is to prove lower bounds on the resources (e.g. ...

33 views

### Can a low density subset sum problem be intractable?

Hardness of a subset sum problem depends on it's density. Is it possible for a subset sum problem to be intractable even if it's density is less than 0.9408?
1k views

### Complexity of arithmetic in a finite field?

I am wondering what the complexities are of adding/subtracting and muliplying/dividing numbers in a finite field $\mathbb{F}_q$. I need it to understand an article I am reading.
66 views

### PRNG output with truly random noise

I am considering a situation where an adversary does not have access to the $n$-bit output string of a PRNG, but instead receives a noisy version of it, where each bit of the string is flipped with ...
23 views

37 views

237 views

### Are post-quantum cryptographic ciphers *also* secure if the P=NP conjecture holds true?

First of all, I only understand the P versus NP debate on a rather shallow level as I am not a computer scientist. So perhaps the answer to the question is straightforward but if not, I would be ...
124 views

143 views

### DES-X , computation load and storage

The passage said that the computational load to attack DES-X can be reduced to approximately $2^{(56+64)}=2^{120}$ steps,and the storage of data sets should be $2^{64}$. But I can't figure why it is ...
166 views

### Complexity of verifying OTP secret

What is the minimum number of unique pairs of digests and inputs to a one-time pass needed to verify that a secret is equal to a ...
259 views

### Solution with high decryption cost and low encryption cost

I am looking for any cryptographic solution that will meet those requirements : Only known method to get the encrypted string need to be brute force. Decrypting on modern computer not more than ...
245 views

### Computational Complexity - When is it really exponential time?

I'm currently working on the discrete logarithm problem and the relevant attacks. I'm fine on the mathematical side of things, but when it comes to estimation of running times I run into problems. ...