Linked Questions

25 votes
4 answers
4k views

Arguments for existence of one-way functions

I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-...
Anonymous's user avatar
  • 4,041
11 votes
5 answers
1k views

Complexity Classes for Cases Other Than "Worst Case"

Do we have complexity classes with respect to, say, average-case complexity? For instance, is there a (named) complexity class for problems which take expected polynomial time to decide? Another ...
Sadeq Dousti's user avatar
  • 16.5k
7 votes
2 answers
2k views

P vs. NP and Pseudorandom Bit Generators

According to an article on pseudorandom number generators (PRNG) by Jeff Lagarias, he states that trying to prove that a PRNG is unpredictable (secure) is just "as hard" as trying to prove ...
user avatar
16 votes
3 answers
372 views

Are there any classes of functions which require provably different resources to compute versus computing their inverse?

Apologies in advance if this question is too simple. Basically, what I want to know is if there are any functions $f(x)$ with the following properties: Take $f_n(x)$ to be $f(x)$ when the domain and ...
Joe Fitzsimons's user avatar
13 votes
3 answers
1k views

Why do computer scientists on the whole work under the assumption that P ≠ NP?

Coming from a math background, it seems interesting to me that on the whole computer scientists tend to work under the assumption that $P \neq NP$. While there is no proof either way, generally, ...
Eli Sadoff's user avatar
16 votes
1 answer
1k views

Password hashing using NP complete problems

Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is ...
Cyker's user avatar
  • 779
8 votes
3 answers
604 views

Candidates for One-Way Function

Why are the candidates for one-way functions so few? Today, almost all candidates are based on elementary mathematics, except Goldreich's candidate 2000 and ... (?!). Why one can not generate ...
Arash Ahadi's user avatar
7 votes
1 answer
771 views

Public-key encryption without the assumption that $P \neq NP$

I'm not talking about the RSA, El-gamal, nor any specific encryption scheme. Rather, my question, as related to this and this threads, is why the idea of Public-Key encryption scheme cannot be secure ...
Bush's user avatar
  • 241
10 votes
1 answer
320 views

Worlds Relative to Which "Invulnerable Generators" Do Not Exist

Invulnerable generators are defined as follows: Let $R$ be an NP relation, and $M$ be a machine which accepts $L(R)$. Informally, a program is an invulnerable generator if, on input $1^n$, it produces ...
Sadeq Dousti's user avatar
  • 16.5k
17 votes
0 answers
959 views

Deeper look at Algorithmica?

Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995. He presented five possible worlds we could be living in, depending on how P and NP were related. The ...
András Salamon's user avatar
8 votes
0 answers
637 views

A generalisation of one-wayness

$\mathbf{NP}$-complete problems are worst-case hard. Their average-case counterpart are one-way functions. Is there an analogous one-wayness notion for $\mathbf{coNP}$-complete problems? More ...
Pooya Farshim's user avatar