-3
$\begingroup$

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

| cite | improve this question | | | | |
$\endgroup$
  • 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.

| cite | improve this answer | | | | |
$\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.