One Way Boolean Function [closed]

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

closed as off topic by Dave ClarkeSep 26 '12 at 7:23

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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