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.

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

    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           

    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

        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

    print("private key")
    print("the matrix of variables ")
    print("the matrix of signs")

I have tried to do something regarding 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")

        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

            for j in xrange(0,beta):
                block[j]=pub[nr[j]]              #store clauses according to their position                   
                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)}      

                R=f.subs(dict)                                       #generate R 

                g_beta+= c_j*R

    print("the encrypted bit is",g)


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

def decrypt(priv,g):


    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)

1 Answer 1


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. 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
    Jun 29, 2016 at 18:57
  • I gave it a try. I would appreciate a constructive critic. Jun 30, 2016 at 18:55
  • 1
    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
    Jun 30, 2016 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.