<p>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. </p>

CC BY-SA 3.0
2012-09-20T07:36:02.813Z
So you can guess the preimage of a 256 bit (N imput) boolean function ?
William Hird
CC BY-SA 3.0
2012-09-20T07:49:06.380Z
If you can guess the pre-image of the output with high probability then SAT would be in BPP.
Mohammad Alaggan
CC BY-SA 3.0
2012-09-20T11:13:29.040Z
@ William Hird, one-wayness is an asymptotic notion, so a function may be one way, but easily reversible at any concrete n.
Martin Berger
CC BY-SA 3.0
2012-09-20T13:05:54.340Z
@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).
Adam Smith
CC BY-SA 3.0
2012-09-20T13:49:40.420Z
@ Martin & Adam: Yes I am talking about a function hard to invert on random imputs, the output will of course be 1 half the time and zero half the time. Why the downvotes here, what is wrong or simple about my question?
William Hird
CC BY-SA 3.0
2012-09-20T14:40:45.600Z
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
CC BY-SA 3.0
2012-09-20T14:45:00.403Z
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](http://www.cs.berkeley.edu/~luca/pacc/lecture08.pdf)
Sasho Nikolov
CC BY-SA 3.0
2012-09-20T14:51:59.180Z
@ Sasho: OK , thank you. I will reformulate my question so that it meets the requirement of a research level question.
William Hird
CC BY-SA 3.0
2012-09-20T07:28:25.313Z
2012-09-20T07:28:25.313Z
Or Meir
<p>If one way functions exist, what would the truth table of a one way boolean function look like?</p>

CC BY-SA 3.0
2012-09-20T11:38:53.847Z
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
CC BY-SA 3.0
2012-09-20T13:42:05.607Z
@ Tsuyoshi: Yes, that is correct, {0,1}.
William Hird
CC BY-SA 3.0
2012-09-20T13:48:56.970Z
Then I do not think that this question is suitable on cstheory.stackexchange.com, which is a place for research-level questions.
Tsuyoshi Ito
<cr.crypto-security><one-way-function>
One Way Boolean Function
William Hird
# One Way Boolean Function

(Asked by: username_0 on 2012-09-20)

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

**Tags:** cr.crypto-security, one-way-function
> **Comments:**
> **username_1**: What do you mean by “Boolean function” in this question?  Clearly you do not mean a function which takes a value in {0,1}.  
> **username_0**: @ Tsuyoshi: Yes, that is correct, {0,1}.  
> **username_1**: Then I do not think that this question is suitable on cstheory.stackexchange.com, which is a place for research-level questions.  

---

## 1 answers

### Answer by username_2 on 2012-09-20. Score: 4

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.

> **Comments:**
> **username_0**: So you can guess the preimage of a 256 bit (N imput) boolean function ?  
> **username_3**: If you can guess the pre-image of the output with high probability then SAT would be in BPP.  
> **username_4**: @ William Hird, one-wayness is an asymptotic notion, so a function may be one way, but easily reversible at any concrete n.  
> **username_5**: @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).  
> **username_0**: @ Martin & Adam: Yes I am talking about a function hard to invert on random imputs, the output will of course be 1 half the time and zero half the time. Why the downvotes here, what is wrong or simple about my question?  
> **username_6**: 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$.  
> **username_6**: 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](http://www.cs.berkeley.edu/~luca/pacc/lecture08.pdf)  
> **username_0**: @ Sasho: OK , thank you. I will reformulate my question so that it meets the requirement of a research level question.  

---

