1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

One wayness of boolean functions

  1. Nov 6, 2009 #1
    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.
     
  2. jcsd
  3. Nov 6, 2009 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  4. Nov 6, 2009 #3
    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.
     
  5. Nov 6, 2009 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  6. Nov 6, 2009 #5
    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: One wayness of boolean functions
  1. Boolean Functions (Replies: 8)

  2. Boolean functions (Replies: 13)

  3. Function one to one (Replies: 9)

Loading...