12
votes
Accepted
Function that is guaranteed to be one-way if one-way functions exist?
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, ...
- 4,495
8
votes
Is it possible to encrypt a CNF?
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 ...
- 1,551
6
votes
Accepted
Is it possible to encrypt a CNF?
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 ...
- 21.1k
3
votes
Accepted
What is the simplest one-way function (in terms of boolean circuit complexity)?
A reasonable approach is probably to take a lightweight block cipher, $E_\cdot(\cdot)$, fix a constant $c$, and use the function $f(k) = E_k(c)$ as the function. While we have no proof that $f$ is a ...
- 12.4k
3
votes
Consequences of OWFs for Complexity
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 ...
- 351
Only top scored, non community-wiki answers of a minimum length are eligible