one wayness of boolean functions

cam875

I was learning about boolean functions and the boolean satisfiability problem when I thought about what if we constructed a problem where you had two things: the domain and the range of a particular boolean function b. And the problem was that you had to solve for the boolean function which creates the appropriate mapping from the domain to the range.

So unlike the boolean satisfiability problem where you have to find appropriate values of either 1 or 0 to substitute into the function to make the function true you have the values but not the function. An example would be:

{0,0,0} -> 1
{0,1,0} -> 1
{0,1,1} -> 0

From this set of data you can conclude that b(0,00) = 1, b(0,1,0) = 1, and b(0,1,1) = 0
obviously this is a short example but the point would be to construct the function which creates this mapping. It seems that the only way to do so would be to perform an exhaustive search. As you can see this seems to be a one way type problem due to the fact that given a boolean function it is simple to compute all outputs for every possible input(2^n where n is the number of variables to the function) but take away the function and it seems to be become a computationally hard problem to solve for the function, hence the one wayness.

I am not sure though if it actually is one way and if this problem already exists.
I am working on this for my cs project so any help is greatly appreciated. Thanks in advance.

Office_Shredder

You can use conjunctive normal form to, given any truth table, construct a function that has that truth table as its output. If your truth table isn't complete then you have more than one choice as to your function

http://en.wikipedia.org/wiki/Conjunctive_normal_form

The basic idea is to notice that: You want b(a,b,c) to be true when (a,b,c) fulfills any of the rows in which you want it to be true.

So B(a,b,c) = (-a^-b^-c)V(-a^b^-c)

where -a means not a and ^ means and. So B(a,b,c) is true only if one of the two expressions in the or is true, but the first expression is true only for the values (0,0,0) and the second only for the values (0,1,0). Since you specified b(0,1,1)=0 I can't include that as an or term but for everything not specified I can choose whether or not to include it

cam875

I am thinking about it from a hash function perspective. So its like if you typed your password in, it would be converted to a boolean function and then all possible inputs would be sent in and the results would be the only thing recorded and therefore if the results from the boolean function entered match the results stored then access is granted otherwise it is considered an invalid password. Therefore a hacker only has access to the domain and range and the mapping but does not know the function which models the mapping exactly. That is the part which appears to me to be one way and I am trying to figure out whether or not it is.

Office_Shredder

So your password is a boolean function. The computer stores only the results from all possible inputs. I could then enter any boolean function that has the same set of outputs and be successful at breaking this right? I'm a bit confused here as to what your definition of 'different boolean functions' is, if two give the same truth table most mathematicians would call them the same, but if you want the exact same symbols then obviously it's impossible to guess which symbols were used precisely (but then again those symbols are not recorded anywhere). Can you elaborate?

cam875

If I were to use B(x,y,z,q) = ((x and y) xor z)nand q as the password
and I generated all 16 possible inputs to the function and there outputs then in order for someone to match the data they would have to know the equation i just typed but if they guessed it wrong they would end up with different data tables, would they not?