# Questions tagged [complexity]

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. time and/or space) needed to solve a certain computational problem. Cryptography can therefore be seen as the complexity theory's main field of use.

269 questions
Filter by
Sorted by
Tagged with
167 views

### Question about P and NP problem

There is a definition for NP shown below. Could anyone please explain why "By restricting the definition of NP to witness strings of length zero, we capture the same problems as those in P."?...
1 vote
74 views

### Why doesn't the existence of the Quadratic Sieve algorithm imply that integer factorization is in the class SUBEXP?

SUBEXP is defined as the intersection of DTIME(2^n^c) over all c>0. The order of the Quadratic Sieve algorithm is O(exp((k+o(1))(logN)^1/2(loglogN)^1/2)). Doesn't this imply that the decision ...
66 views

### Difficulty of factoring large semiprime N if given a second value y = (p-1)*r, where r is a random large prime?

Lets say we have 2 public values: N and y $$N = pq$$ $$y = r(p-1)$$ Where p, q, and r are large primes, are different, have a large distance between them and are kept secret. I have three ...
2k views

4k views

### Cryptography based on uncomputable problems?

A lot of cryptography is based on the assumption that ${\sf P} \neq {\sf NP}$. Is it conceivable to construct a cryptography system based on a class of much harder problems than ${\sf NP}$-problems, ...
7k views

### How reassuring is 64-bit (in)security?

In Feb 2017, CWI and Google announced SHAttered hash collision attack on SHA1, which took $2^{63.1}$ work estimated 6500 CPU years, to achieve. Therefore, 64-bit should be considered now an insecurity....
1 vote
36 views

1 vote
93 views

### How does the security of AES change if we allow multiple uses in a row? How does it change if we limit the key space? And introduce a filter function?

$$f_0 = A$$ $$f_{n+1}=AES(f_n,k_n)$$ $$f_i = B$$ For given 128-bit values $A, B$ we want to find a chain of suitable 128-bit keys $k_1$ to $k_i$. The total length $i$ is undetermined. Every valid key ...