# 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
165 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 ...
• 13
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 ...
1 vote
102 views

### Discrete log problem - does luck exist?

Assume the discrete log problem: $g^x mod (p) = h$ For sure, $p$ is a prime number and $g$ is its primitive root or generator and assume that Alice sent $h$ to Bob and middle man caught it. So ...
55 views

### What do we mean when we say we need more than polynomial time many cipher texts

What does it mean when we say something like „we need more than polynomial time many cipher texts“? I understand it as „an adversarial can run for polynomial time and try as many messages as possible ...
55 views

### Inefficient double-lengthening PRG

I'm trying to prove that an inefficient double-lengthening PRG exists, i.e. construct a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$ My current approach is to bound the number of poly-time non-uniform ...
• 123
194 views

### Testing whether the Euler Totient of a number equals to certain value

I have solved a problem in Project Euler. My solution was based on the finding the all numbers whose Euler Totient value equals to $13!$ However, while I was working on the problem, I thought that: &...
• 640
35 views

### Can the runtime of a reduction help an adversary distinguish the reduction from the adversary's challenger?

Generally, in cryptography, the security of a scheme/protocol $\Pi$ relying on a hard problem $P$ is demonstrated by constructing a reduction $\mathcal{B}$ that takes as input an instance of the ...
• 467
187 views

### Speed comparison of encryption algorithms

I am trying to compare various encryption algorithms in terms of encryption duration, decryption duration, information entropy, NPCR, UACI, and correlation coefficients. I used a Lena 256x256 ...
1 vote
123 views

### Decision LWE vs Search LWE: Which one is harder?

Sometimes if we have an attacker who's able to solve decision-LWE problem then we can use them (as a sub-routine) to solve (search) LWE problem, i.e., $\mathsf{sLWE} \leq \mathsf{dLWE}$. Conversely, ...
• 450
53 views

### Learning the LWE secret with advice

I am trying to argue about the hardness of LWE, but in a setting that is different from the standard one. Consider the task of learning the LWE secret $s$ from noisy samples. The specifications of the ...
• 387
1 vote
86 views

### How to prove that an algorithm is the time optimal algorithm for implementing a problem?

Given an objective function, we can give many programming implementations based on existing computers. Can we prove that the algorithm given is time optimal? For example, if we give a recursive solver ...
• 21
1 vote
70 views

### What exactly is the RAM program runtime?

In my previous understanding, if a RAM program requires $T$ read/write operations to memory during its execution, then the runtime of this RAM program is $T$. However, as I have read some literature, ...
• 112
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, ...
1 vote
85 views

• 41
318 views

### Time Complexity Of Solving DLog When g and P are known

This (https://en.m.wikipedia.org/wiki/Discrete_logarithm) Wikipedia article confuses me. If you have the equation a = g^n (mod P), and g, P and a are all known, then how does a brute force solving for ...
• 300
1 vote
86 views

### Comparing complexity of RSA decryption with/without CRT

(Cross-listed on math stackexchange, received no replies) For context, this is a homework question from an assignment already turned in. I am looking for better understanding of the concepts involved, ...
• 111
1 vote
695 views

### Berlekamp–Massey input sequence length

For a given periodic sequence of length $N$ for which minimal polynomial is being constructed. Does the Berlekamp-Massey algorithm take the input of $2N$, i.e., the repeated input sequence or just the ...
608 views

### Why Zero-Knowledge protocols are used for NP problems if IP is the class of interactive proof systems where they come from?

As stated in the title, I'm studying ZKPs and I see they are just interactive proof systems that respect the zero-knowledge property. Now, if that's true, why aren't they used for IP problems, the ...
572 views

### Rabin-Miller primality test complexity

I was thinking about the complexity of the Rabin-Miller primality test. On wikipedia I find O(k log3n), but there is no explanation. My idea was too simple. To see if n is prime, we have k attempts ...
• 299