Ask Your Question

What can i do about this large boolean function?

asked 2019-04-29 06:56:28 -0600

athulan gravatar image

updated 2019-04-30 16:08:23 -0600

slelievre gravatar image

If i have a large boolean function like this:

FUN() = (
    (( ~g&(f^i^0))|(g&(1^f^h^0)))^(( ~x&(w^z^0))|(x&(1^w^y^0)))
    ^((d&(1^a^b^e))|( ~d&(1^a^c^e)))^((m&(1^j^k^n))|( ~m&(1^j^l^n)))

can anyone explain how can i code to obtain the non-linearity of this boolean formula?

I didn't really understand the BooleanFunction() function in Sage.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2019-04-30 10:04:16 -0600

rburing gravatar image

Let's first convert this to a BooleanPolynomial. We define a BooleanPolynomialRing:

R.<a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z> = BooleanPolynomialRing(26)

We define a small wrapper class that helps to make the given formula into valid Python code:

class BooleanWrapper:
    _expr = None
    def __init__(self, arg):
        self._expr = arg
    def __pow__(self, exponent):
        return BooleanWrapper(self._expr + exponent._expr)
    def __repr__(self):
        return self._expr.__repr__()
    def __invert__(self):
        return BooleanWrapper(1 - self._expr)
    def __and__(self, other):
        return BooleanWrapper(self._expr * other._expr)
    def __or__(self, other):
        return BooleanWrapper(1 - (1-self._expr)*(1-other._expr))

We also need to preprocess the string a little bit because 0 and 1 are not wrapped:

boolean_str = '(( ~g&(f^i^0))|(g&(1^f^h^0)))^(( ~x&(w^z^0))|(x&(1^w^y^0)))^((d&(1^a^b^e))|( ~d&(1^a^c^e)))^((m&(1^j^k^n))|( ~m&(1^j^l^n)))^o^p^q^0^r^s^t^u^v'
wrapper_vars = {'BooleanWrapper' : BooleanWrapper}
wrapper_vars.update({str(g) : BooleanWrapper(g) for g in R.gens()})
boolean_poly = sage_eval(boolean_str.replace('0', 'BooleanWrapper(0)').replace('1', 'BooleanWrapper(1)'), locals=wrapper_vars)._expr

This gives boolean_poly as

a + b*d + c*d + c + e + f + g*h + g*i + g + i + j + k*m + l*m + l + n + o + p + q + r + s + t + u + v + w + x*y + x*z + x + z

Now we can make this into a boolean function:

from sage.crypto.boolean_function import BooleanFunction
boolean_function = BooleanFunction(boolean_poly)

and finally boolean_function.nonlinearity() gives $31457280$.

edit flag offensive delete link more


Hi. Is there some way to make reverse transformation? I mean, from boolean polynomial to formula written with '&', '|' and '~'. Thanks.

baumanets7 gravatar imagebaumanets7 ( 2019-09-22 08:48:41 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2019-04-29 06:56:28 -0600

Seen: 70 times

Last updated: Apr 30