-3
$\begingroup$

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

$\endgroup$
3
  • 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$ Sep 20, 2012 at 11:38
  • $\begingroup$ @ Tsuyoshi: Yes, that is correct, {0,1}. $\endgroup$ Sep 20, 2012 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$ Sep 20, 2012 at 13:48

1 Answer 1

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$
8
  • 1
    $\begingroup$ So you can guess the preimage of a 256 bit (N imput) boolean function ? $\endgroup$ Sep 20, 2012 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$ Sep 20, 2012 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, 2012 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$ Sep 20, 2012 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$ Sep 20, 2012 at 14:45

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