Skip to main content
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, ...
Bjørn Kjos-Hanssen's user avatar
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 ...
didest's user avatar
  • 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 ...
Mohammad Al-Turkistany's user avatar
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 ...
D.W.'s user avatar
  • 12.2k
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 ...
user17164's user avatar
  • 351

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