-3
$\begingroup$

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

$\endgroup$

closed as off topic by Dave Clarke Sep 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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ So you can guess the preimage of a 256 bit (N imput) boolean function ? $\endgroup$ – William Hird Sep 20 '12 at 7:36
  • 1
    $\begingroup$ @ William Hird, one-wayness is an asymptotic notion, so a function may be one way, but easily reversible at any concrete n. $\endgroup$ – Martin Berger Sep 20 '12 at 11:13
  • 2
    $\begingroup$ @M.Alaggan One way ness requires that the function be hard to invert on random inputs. SAT is hard only. When the fraction of satisfying assignments is small. But such a formula is not one way since on a random input, the function value will almost certainly be 0. So Or Meir's solution is correct (it is a standard textbook answer). $\endgroup$ – Adam Smith Sep 20 '12 at 13:05
  • 1
    $\begingroup$ 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$. $\endgroup$ – Sasho Nikolov Sep 20 '12 at 14:40
  • 2
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov Sep 20 '12 at 14:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.