One wayness of boolean functions

  • Thread starter Thread starter cam875
  • Start date Start date
  • Tags Tags
    Functions
AI Thread Summary
The discussion centers on the concept of one-wayness in boolean functions, particularly in the context of constructing a boolean function from a given domain and range. The challenge lies in deriving the function that maps specific inputs to outputs, which is computationally difficult compared to evaluating a function when it is known. An example illustrates how to create a boolean function using conjunctive normal form based on a truth table, emphasizing that multiple functions can yield the same output for incomplete truth tables. The conversation also draws parallels to password security, suggesting that if only output data is stored, a hacker could potentially guess the function that generates those outputs, complicating the notion of uniqueness in boolean functions. The participants express uncertainty about the one-way nature of this problem and seek clarification on the definitions of different boolean functions.
cam875
Messages
227
Reaction score
0
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.
 
Mathematics news on Phys.org
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
 
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.
 
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?
 
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?
 
Thread 'Video on imaginary numbers and some queries'
Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Thread 'Unit Circle Double Angle Derivations'
Here I made a terrible mistake of assuming this to be an equilateral triangle and set 2sinx=1 => x=pi/6. Although this did derive the double angle formulas it also led into a terrible mess trying to find all the combinations of sides. I must have been tired and just assumed 6x=180 and 2sinx=1. By that time, I was so mindset that I nearly scolded a person for even saying 90-x. I wonder if this is a case of biased observation that seeks to dis credit me like Jesus of Nazareth since in reality...
Back
Top