# 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.

164 questions
540 views

### Quantum complexity of LWE

As per my understanding, LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al., if there is any algorithm that ...
553 views

### Practical differences between circuits and turing machines for cryptography

In formal cryptography, we model algorithms (mostly our adversaries) as (Probabilistic) Turing Machines or as boolean circuits. In our lecture on formal cryptography, we learned that circuits are more ...
3k views

### What happens for factoring algorithms if P=NP?

If someone ever demonstrates that P=NP, will it give us a polynomial factoring algorithm, or will it only tell us that such an algorithm exists, but we still have to find it?
575 views

### Why are only lattice problems used in cryptography?

There are thousands of NP-hard problems out there. Why have only lattice problems been applied to cryptography?
4k views

### uniform vs. non-uniform PPT

I'm trying to understand PPT and in particular what the differences are in uniform and non-uniform PPT's. First, this is how I see it: A probabilistic polynomial-time (PPT) algorithm $A$ is an ...
2k views

### What does “running in polynomial time” really mean?

I'm currently learning private-key cryptography. I've been able to see that perfect secrecy is achievable if no assumption is made about the computational power of the attacker. However, perfect ...
367 views

### Is it possible to construct an encryption scheme for which breaking is NP complete but there nearly always exists an efficient breaking algorithm

The question stems from the fact that foundations of crypto states: suppose breaking an encryption scheme is NP-complete, then P != NP implies that this encryption is hard to break in the worst case, ...
2k 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....
2k views

### What's the difference between polylogarithmic and logarithmic? [closed]

I can't imagine one that is not polylogarithmic but logarithmic. $O(\log N)$ satisfies both. What about $O(\log^{3}N)$, $O(\log^{100}N)$, and $O(\log^{10000}N)$ ? Let's say $N=10^{10}$
5k views

### What is the largest performed/possible bruteforce attack to date?

I've read that cracking 128-bit key is currently out of reach of all humanity. However, I can't seem to find any information on what scope of brute force attacks have been performed or are possible at ...
297 views

### how to understand the universal hash and the leftover hash lemma [closed]

I always meet the leftover hash lemma when I read some papers.But I only know the defination of universal hash and the leftover hash lemma.How to understand them and how to use them?
2k 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.
2k views

168 views

### Are there lower bounds to how efficient one can make obfuscated code?

I am wondering if there are any theoretical reasons why obfuscated programs cannot be nearly as efficient as the plaintext programs and whether there is any necessary computational overhead from ...
141 views

### Making attacks on password hashes less economical

Perhaps an abstract question on complexity given the trade offs between memory vs runtime, I was wondering if it's possible to constrain only either extremes approaches to be optimally efficient, thus ...
95 views

### P-Complete hashes, hashing to a larger set

Historically hashes have been from a large set (say 256 characters) to a smaller set (256 bits). Also, hash functions that are P-complete have no known parallel algorithm; they must be computed ...
3k views

### Why do look up tables speed things up compared to brute force?

I'm currently reading up on lookup tables and efficiency. In my uni script it says the following: For Brute Force: Preparation time: $O(1)$ Disk space requirement: $O(1)$ Time required to crack the ...
648 views

### What is meant by $\tilde\Omega(\lambda^4)$?

I'm currently reading the paper (Leveled) fully homomorphic encryption without bootstrapping , and the following paragraph was near the start: What is meant by the symbol used? Is it merely to ...
898 views

### Solve a Modular Exponentiation

It might be common, but if we had to solve an equation like this $m=s^{e}$ mod $n$ where $m,e,n$ are known. How can we find $s$. What optimisations could be applied? And what would the complexity of ...
246 views

### How was this Mersenne Twister seed for a 20-character string known a priori found?

Someone generated a seed for the Mersenne Twister, with the intent of that seed producing this string: "9!dlroW ,olleH"ck,@ Which is 20 characters long. Why he ...
462 views

### What is the difference between Argon2d and Argon2i?

I know that Argon2d accesses the memory array in a password dependent order and Argon2i accesses the memory array in a password independent order. What is the difference in computational complexity?
201 views

### Polynomials and efficient computability

In public key crypto, the popular definitions of security (CPA, CCA1,2) depend on PPT adversaries. I'm trying to understand why adversaries should be PPT. It's clear that adversaries should be at ...
Suppose integer $m$ has $\phi(m)=2pq^5r^2$ where $p,q,r$ are primes. Hellman-Pohlig says that finding discrete log $z\bmod p$, $z\bmod q^5$, $z\bmod r^2$ and $z\bmod 2$ suffices to find \$z\bmod\phi(m)...