How to generate random Boolean functions in Algebraic Normal Form in Python?

Question

I am looking at A SAT-based Public Key Cryptography Scheme and got inspired to challenge myself to write an implementation of this Cryptography Scheme on Python.

A part of the cipher encoding would be to generate random Boolean functions in Algebraic Normal Form in a certain set of binary variables. I am new to coding and I can not figure out how to generate the required random functions.

EDIT
I have already written some code in sage (and made several runs in Python as well) for the key generation. Since I can't put the code in a comment I am putting it here. While I am conscious that the code might be naive I have checked with small examples and it looks okay to me.

#n-number of binary variables
#m-number of clauses
#k-number of literals in each clause


def key_gen(n,m,k):

    print("the list of variables")

    print([var('x'+str(n)) for n in range(n+1)])   #listing the variables
    print("")

    priv=[randint(0,1) for x in range(n)]          #choose randomly the private key 

    pub=matrix(m,k,0)                           #store the variables used as a m*k matrix
    signs=matrix(m,k,0)                         #store the signs as a m*k matrix           

    i=0
    j=0
    while j<m:

        clause=sorted((sample(xrange(0,n),k)))     #choose k variables at random 
        sgn=[randint(0,1) for x in range(k)]       #choose their signs at random

        value=0
        for i in xrange(0,k):                     
            value += (mod(sgn[i]+priv[clause[i]],2))  #check the truth value of the clause

        if value!=0:                                  #the clause is accepted iff there is
            pub[j]=clause                             #at least one literal with truth value one
            signs[j]=sgn
            j=j+1


        i=i+1                           
    print("")
    print("private key")
    print(priv)
    print("")
    print("the matrix of variables ")
    print(pub)
    print("")
    print("the matrix of signs")
    print(signs)

I have tried to do something regarding encryption.

#encryption
#n-number of variables
#pub is a m*k-matrix, where in its rows are stored the clauses
#signs-a m*k matrix where are stored the signs of literals
#y-bit to be encrypted
#alpha, beta encryption parameters


def encrypt(n,pub,signs,alpha,beta,y):

    if ((beta > len(pub.rows())) or (beta >= alpha)):     
        print("Encryption  is not possible")
    else:
        m=len(pub.rows())
        k=len(pub.columns())

        g_alpha=0
        for i in xrange(0,alpha):              

            block=matrix(beta,k,0)          #store the tuples of clauses as beta*k matrix
            nr=sorted((sample(xrange(0,m),beta)))       #choose at random beta clauses

            g_beta=0
            for j in xrange(0,beta):
                block[j]=pub[nr[j]]              #store clauses according to their position                   
                B=BooleanPolynomialRing(n,'x')
                used_var=[B.gens()[pub[nr[j]][i]] for i in xrange(k)]   #store the 
                c_j=0                                                   #used variables
                for i in xrange(0,k):  
                    c_j+=(B.gen(pub[nr[j]][i]) + signs[nr[j]][i]+1) #calculate the negation 

                zero_list=[0 for x in xrange(k)]                        
                dict={key:value for key,value in zip(used_var,zero_list)}      

                f=B.random_element()
                R=f.subs(dict)                                       #generate R 

                g_beta+= c_j*R
        g_alpha+=g_beta      

    g=y+g_alpha
    print("the encrypted bit is",g)

Decryption:

#priv- a list of numbers
#g-a symbolic expression-the cipher

def decrypt(priv,g):

    n=len(priv)
    B=BooleanPolynomialRing(n,'x')

    A=[B.gen(i) for i in xrange(n)]

    f=B(g)                          #get a Boolean Polynomial from symbolic expression

    dict={key:value for key,value in zip(A,priv)}

    s=f.subs(dict)    #evaluate g(priv)
    print('decrypted bit is',s)

Andrew · Accepted Answer · 2016-06-29 18:15:33Z

I'm basing this off of the Algorithms section of the paper, which is kind of hard to understand, so I would appreciate someone else checking this. Also, I hope you're doing this for fun and not planning on using this for real cryptography without thorough analysis by professionals and academics,

The public Boolean function (13) is a series of clauses ANDed together, x -> ^ c_j(x). Each clause is a series of subclauses ORed together, x -> V(...). And each subclause is an element of the input x_[I(i, j)] XORed with some sign s(i, j).

The signs come from a matrix of Booleans and are chosen randomly as 1 or 0, which is pretty straightforward, but picking the elements out of the input is trickier. The input is a vector of Booleans, and we want a random way to choose which one to put in each subclause. So, we make a matrix of integers size m, k and call it I. For each row in this matrix, c_j(x) has to be true for the private key (since they will be ANDed together). So, generate a row of random integers (from 1 to n so we don't go out of bounds of the input) and a row of random signs. Each of these should be k items, since they will be rows of their matrices.

Once we've come up with candidate rows, we need to make sure they satisfy the private key. So, for each index in the row, we derive a subclause for the function c_j and make sure at least one is true (since they will be ORed together). For example, the first elements might be 5 and 1, so we XOR the 5th element of the private key with 1 and see if it is true. Continue down the rows until at least one is true, and if it is, add the rows to your matrices.

Thinking in the other direction, if you have the matrices I and s, you can check a candidate key pretty easily. For each row of the matrices, make sure that with the integer from I indexing the key, you get a value that can be XORed with the Boolean from s.

Let's take the rows [1, 3, 2] and [1, 0, 0], and a candidate key [1, 1, 0]. First, take the first element from the key (1) and XOR it with 1. This gives you 0, so continue on. Take the third element from the key (0) and XOR it with 0. This gives 0, so keep going. Finally, we XOR the second element (1) and the third sign (0) to get 1. Since we got a 1, these rows work with this key.

I am a Math major student and I want to do this just to improve my coding skills. Author of the paper provides an implemenation already. Your idea seems to obey the algorithm which I struggle to understand completely. I will try to implement it and let you know if I succeed or not. — Kristina
– Kristina, Commented Jun 29, 2016 at 18:55
Just wanted the standard "don't roll your own crypto" disclaimer. Even if 99% of people know better, it's safest to remind everyone. — Andrew
– Andrew, Commented Jun 29, 2016 at 18:57
Looks like it should work, but you might want to take it to CodeReview for critique. One thing I notice is that you're doing mutation when you don't need to. When you define priv, just use [randint(0,1) for x in range(n)] instead of first giving it zeros and then initializing it. Also, your id function could build and return ind instead of mutating the reference to it. — Andrew
– Andrew, Commented Jun 30, 2016 at 19:02

Stack Exchange Network

How to generate random Boolean functions in Algebraic Normal Form in Python?

1 Answer 1

Your Answer

Hot Network Questions

How to generate random Boolean functions in Algebraic Normal Form in Python?

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions