# Tag Info

15

We cannot hope to prove a general impossibility result since if one-way functions exist (and we believe they do), then in particular it follows that the statement "If $P \ne NP$ then one-way functions exist" is true. However, we can prove that certain proof techniques are too weak to prove that statement. In particular, the following paper of Akavia, ...

11

Yes, such a function was found by Levin himself, published somewhat recently: The tale of one-way functions. Problems of Information Transmission (= Problemy Peredachi Informatsii), 39(1):92-103, 2003.

11

Regarding log-space: Several candidate one-way functions are computable in log-space or below (and are supposedly secure even against poly-time adversaries). You can find several pointers for example in the Cryptography in NC$^0$ paper. Two specific examples include: Integer multiplication (there are some subtleties for standard OWF, but if you only care ...

10

If you mean the cryptographic kind of one-way function (i.e. average-case hard to invert), then Or Meir's answer is great. But for the slightly easier notion of worst-case one-way function - that is, an injective function $f$ that is computable in polynomial time, but where there is no deterministic polynomial-time algorithm $g$ such that $f(g(y)) = y$ for ...

8

The application you mention is called "proof of useful work" in the literature, see for instance this article. You can use a fully homomorphic encryption scheme (where the plaintext is the CNF instance) to delegate the computation to an untrusted party without disclosing the input. This doesn't answer exactly your question, since such scheme doesn't map a ...

8

Here is a "canned" answer that might be useful, but has no cryptographic depth (hopefully we get answers with depth as well). What makes for a good candidate OWF? The naive answer tends to boil down to "something that looks hard to invert to me", but the expert's response is usually more like "something that many smart people have tried to invert but failed"...

6

In a recent work with Rafael Pass, it is shown that without those extra complexity assumptions of Barak-Ong-Vadhan, noninteractive commitments can not be based on one-way functions in a black-box way. In fact even with these extra assumptions (when formalized as some kind of hitting property assumed in addition to one-way-ness) still a black-box separation ...

5

Feigenbaum in, Encrypting Problem Instances, proposes a definition (Def. 1) of encryption function for NP-complete problems which satisfies your requirements. She proves that the NP-complete problem Comparative Vector Inequalities admits such encryption function. She concludes with the main theorem that all NP-complete problems that are p-isomorphic to CNF-...

4

You don't need to know whether it is quadratic on all $x$, only on the particular $x$ that is given as input. And it's easy to decide whether a machine runs in a given time bound on a fixed input $x$. Just simulate it for that many steps and check whether it stops before the time bound runs out. Here, "at most quadratic" is a little sloppy. It should be ...

4

As for your last question, the are several candidates for combinatorial one-way functions. This paper by Kojevnikov and Nikolenko lists three combinatorial complete one-way functions that are based on the tiling problem of Levin, semi- Thue systems, and Post Correspondence problem ( complete means those functions are one-way if one-way functions do exist). ...

4

There exist no boolean one way functions, since for a boolean function, you can always guess a preimage of the output, and with high probability, you'll be right.

3

This is a late response. First, to correct what you wrote: Cryptographic pseudorandomness (the one obtained from OWFs) doesn't have enough stretch to derandomize "naturally defined" computational complexity classes. In an old paper (beginning of 80s) Andrew Yao shows some subexponential time derandomization for RP etc using these objects (btw, this is ...

2

Integer factorization is widely considered the best candidate for one way functions and it is in TFNP. From the abstract of this paper, Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?, it gives a relativized negative result by constructing an oracle under which TFNP functions are efficiently computable but the polynomial-time ...

Only top voted, non community-wiki answers of a minimum length are eligible