Linked Questions

25
votes
4answers
3k 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-...
10
votes
5answers
773 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 ...
7
votes
2answers
1k 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 that P!=NP. ...
16
votes
1answer
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 ...
15
votes
3answers
303 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 ...
12
votes
3answers
857 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, ...
7
votes
3answers
489 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 ...
7
votes
1answer
553 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 ...
10
votes
1answer
229 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 ...
16
votes
0answers
644 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 ...
8
votes
0answers
628 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 ...