# One Way Boolean Function [closed]

If one way functions exist, what would the truth table of a one way boolean function look like?

• What do you mean by “Boolean function” in this question? Clearly you do not mean a function which takes a value in {0,1}. – Tsuyoshi Ito Sep 20 '12 at 11:38
• @ Tsuyoshi: Yes, that is correct, {0,1}. – William Hird Sep 20 '12 at 13:42
• Then I do not think that this question is suitable on cstheory.stackexchange.com, which is a place for research-level questions. – Tsuyoshi Ito Sep 20 '12 at 13:48

• William, one-wayness requires that given the image of a random input a polytime TM cannot guess a preimage with probability greater than $1-\delta(n)$ where $\delta(n)$ goes to 0 superpolynomially fast. But with a boolean function you can guess an input from the larger of the two preimages and you'll be right with probability $\geq 1/2$. – Sasho Nikolov Sep 20 '12 at 14:40
• Maybe you're asking for boolean functions which are hard to invert with probability $(1+\epsilon(n))/2$ where $\epsilon(n)$ is inverse polynomial. The Goldreich-Levin theorem constructs such a "hard-core predicate" from any one-way permutation: Luca's notes – Sasho Nikolov Sep 20 '12 at 14:45