Stange-Ring-BKW-v1.3
system:sage


<p><span style="font-size: xx-large;"><strong>Sage Notebook Demonstrating Ring-BKW</strong></span></p>
<p><span style="font-size: x-large;">Version 1.3, May 10, 2019</span></p>
<p><span style="font-size: x-large;">Katherine E. Stange</span></p>
<p><span style="font-size: x-large;"><span class="cc-license-identifier">This work is licensed under a <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="license">Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License</a>.</span><br /></span></p>
<p><span style="font-size: x-large;"><br /></span></p>
<p><span style="font-size: x-large;">This notebook has been prepared as an accompaniment to the paper <strong><em>Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm</em></strong>.&nbsp; See the website <a href="Algebraic%20aspects%20of%20solving%20Ring-LWE,%20including%20ring-based%20improvements%20in%20the%20Blum-Kalai-Wasserman%20algorithm">http://math.colorado.edu/~kstange/ring-bkw.html</a><span style="font-size: x-large;"><span style="font-size: x-large;">.</span></span>&nbsp; Usage is demonstrated below.</span></p>
<p><span style="font-size: x-large;"><br /></span></p>
<p><span style="font-size: x-large;">The purpose of this worksheet is only to demonstrate/verify mathematical correctness of the algorithms, not to determine runtimes or parameter boundaries.<br /></span></p>
<p><span style="font-size: x-large;"><br /></span></p>
<p><span style="font-size: x-large;"><strong>Limitations:&nbsp;</strong> In this version, the code has the following limitations (compared to the generality of the paper):</span></p>
<p><span style="font-size: x-large;">1) the e<span style="font-size: x-large;">rror width x means <strong>error coefficients are drawn uniformly</strong> from integers in the window [-x,x]</span></span></p>
<p><span style="font-size: x-large;"><span style="font-size: x-large;">2) the prime must be 1 mod 4 (to avoid a "not-implemented" error in Sage v7.3 associated to a tower of polynomial extensions)<br /></span></span></p>
<p><span style="font-size: x-large;"><br /></span></p>
<p><span style="font-size: x-large;">Evaluate the following cell to load all the code.<br /></span></p>

{{{id=114|
from sage.modules.free_module_integer import IntegerLattice
import random
import itertools
from sortedcontainers import SortedList, SortedDict
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic


#####################################################
#### Auxiliary Tools for Choosing Instance Parameters
#####################################################

### give various info about factorization of q^k-1
def investigate( k, q ):
    for d in divisors(k):
        print "factor q^", k/d, "-1: ", factor( q^(k/d)-1 )
    
### list primes in a range with a certain power of two in base field
def find_primes( lowbound, upbound, power_of_two ):
    return [ _ for _ in primes(lowbound, upbound) if Mod(_,power_of_two)==1 ]

### compute embedding degree
def emb_degree( n, q ): # n = dim, i.e. 2n roots of unity, q=prime
    emb_degree_flag = 0
    emb_degree = 1
    while emb_degree_flag == 0:
        if Mod(q^emb_degree-1,2*n) <> 0:
            emb_degree += 1
        else:
            emb_degree_flag = 1
    return emb_degree
    

################################################    
#### Rq = R/qR class
################################################
#### this class generates the ring Rq and its tower of subrings
#### this class guarantees that the generator of a subring is the square of the generator of the next larger ring in the tower
#### it allows for tracing into the subfield and for embedding subring back into big ring
################################################

class Rq:
    
    def __init__(self, dim, prime):  
        
        ## Notes:
        ## dim -> 2*dim th roots appear, 
        ## dim = dimension of this ring over Fq, must be power of two
        ## q = prime; modpoly = polynomial
    
        ### Dimension of big ring, must be power of two
        self.n = dim
        
        ### log base 2 of dimension
        self.logn = ZZ(log(self.n,2)) # exponent such that dimension = 2^exponent
        
        ### prime field we work over
        self.q = prime
        
        ### Generate the underlying prime field 
        self.F = GF(self.q)
        
        ### Generate the tower of rings
        ###############################
        
        ### rings stores a list of [ring,generator] in increasing order
        ### rings[0] is the finite field with generator -1
        self.rings = [ [self.F, self.F(-1)] ]
        
        ### the largest ring is index self.logn
        for i in range(1,self.logn+1):
            lastring = self.rings[i-1]
            S.<x> = PolynomialRing(lastring[0], 'x')
            zetaname = 'z' + str(i); # z0 = -1, z1 = i, etc.
            R = S.quotient( x^2 - lastring[1], zetaname ) # take square root of last generator
            self.rings.append( [R, R.gen()] )
            
        ### bigring is the largest ring, used most often
        self.bigring = self.rings[self.logn][0]
        
        ### Report on the ring created
        print "Ring: ", self.bigring
        print "Size of ring in bits: ", log( self.q^self.n, 2 ).n()
        
        ### Store ring generator (zeta) and report
        self.r = self.rings[self.logn][1]
        print "Ring generator (2n-th root): ", self.r 

        ### store powers of r for later use
        r_pows = [ self.r^i for i in range(self.n) ]
        
    def iterator(self, i):  # iterator for the subring of index 2^i
        ring = self.rings[self.logn-i][0]
        gen = self.rings[self.logn-i][1]
        repeatrange = self.n/(2^i)
        gen_pows = [ gen^_ for _ in range(repeatrange) ]
        print gen_pows
        for tuple in itertools.product(self.F,repeat=repeatrange):
            elt = ring(0)
            for i in range(repeatrange):
                elt += gen_pows[i]*tuple[i]
            yield elt
            
    def subring(self, i ):  # return index 2^i subring
        return self.rings[self.logn-1-i][0]
        
    def subgen(self, i ):  # return generator of index 2^i subring
        return self.subrings[self.logn-1-i][1]
        
    def coefficient_list_onestep(self, elt ):  # return the coefficient list in terms of subring of index 2
        return elt.list()
        
    def coefficient_list(self, elt):  # return the coefficient list in terms of powers of zeta (self.r)
        if elt.parent() == self.rings[0][0]:
            return elt
        else:
            returnlist = []
            coeffs_lower = self.coefficient_list_onestep(elt);
            if coeffs_lower[0].parent() == self.rings[0][0]:
                return coeffs_lower
            list1 = self.coefficient_list(coeffs_lower[0])
            list2 = self.coefficient_list(coeffs_lower[1])
            for i in range(len(list1)):
                returnlist.append(list1[i])
                returnlist.append(list2[i])
            return returnlist            
        
    def trace_red_1(self, ringindex, elt):   # return trace to index 2 subring
        return self.rings[ringindex][0](elt).list()[0]
            
    def trace_red(self, elt, i ):   # return the trace to the index 2^i subring (i=1 is subfield of index 2)
        myelt = elt
        for j in range(i):
            myelt = self.trace_red_1(self.logn - j, myelt)
        return myelt
        
        
################################################
#### Two-Power Cyclotomic Ring-LWE Class
################################################
#### this class generates a Ring-LWE instance
#### this means 
####       1) ring Rq object
####       2) error generator, check if something is an error
####       3) fake (i.e. uniform) sample generator
#### it doesn't include or know about a secret (that's what an oracle class is for)
################################################

class RingLWE:
    
    def __init__(self, dim, prime, error_sigma ): # dim must be a power of two, indicating x^dim+1 (2dim-th roots)

        ### Set up and report basic parameters
        self.n = dim
        self.m = 2*dim
        self.q = prime
        self.sigma = error_sigma
        print "Initializing a Ring-LWE with dimension ", dim, " (meaning ", 2*dim, "-th roots), prime ", prime, " and error width ", error_sigma
        
        ### Compute embedding degree and report
        self.k = emb_degree( self.n, self.q )
        print "embedding degree self.k: ", self.k
        
        ### Create the ring Rq
        self.Rq = Rq(self.n, self.q);
        self.r = self.Rq.bigring.gen();
        
        print "Primitive 2n-th root of unity r = ", self.r
        print "Primitive n-th root of unity t = r^2 = ", self.r^2
            
        ### save powers of primitive root
        self.r_pows = [ self.r^_ for _ in range(self.n) ]
        
        ### compute error coefficient range and save
        self.error_coeffs_range = range(-self.sigma,self.sigma+1)

    def get_error(self):  # return a random error
        coeffs = [ random.choice(self.error_coeffs_range) for _ in range(self.n) ] # for m-th roots, choose coefficients
        eg = 0
        for jj in range(len(coeffs)):
            eg += coeffs[jj]*self.r_pows[jj]
        return eg
    
    def get_fake_sample(self):  # return a uniform (non-valid) sample
        aa = self.Rq.bigring.random_element()
        bb = self.Rq.bigring.random_element()
        return [aa,bb]
        
    def trace_red(self, elt, i ):   # return the trace to the index 2^i subfield (i=1 is subfield of index 2)
        return self.Rq.trace_red(elt, i)
        
    def coset_rep(self, elt ):   # return a representative of the mult. coset of the index 2 subfield
        my_trace = self.trace_red(self.Rq(elt))
        if my_trace == 0:
            return self.r
        else:
            return self.Rq(elt)/my_trace
    
    def is_error(self, elt):  # check if elt in Rq is an error
        eltlist = self.Rq.coefficient_list(elt)
        error_flag = True
        for i in range( self.k ):
            if eltlist[i] not in self.error_coeffs_range:
                error_flag = False
                break
        return error_flag
        
    def secretanought_recreation(self, downdim, anought, clist):  # given a list of c's, uses Main Theorem to reconstruct secret
        anought_trace = self.trace_red(anought,downdim)
        zcoeffs = [0 for _ in range(self.n)]
        for j in range( 2^downdim ):
            vcoeffs = self.Rq.coefficient_list(self.Rq.bigring(clist[j]*anought_trace))
            print "v coeffs:", vcoeffs
            for i in range( self.n/(2^downdim) ):
                zcoeffs[i*(2^downdim) - j] = vcoeffs[i*2^downdim]
                if i*(2^downdim) - j < 0 :
                    zcoeffs[i*(2^downdim)-j] = -vcoeffs[i*2^downdim]
        print "z coeffs:", zcoeffs
        print self.r_pows
        z = 0
        for jj in range(len(zcoeffs)):
            z += zcoeffs[jj]*self.r_pows[jj]
        print "z: ", z
        return z
        
        
        
################################################
#### Oracle class
################################################    
#### The Oracle is the secret keeper
#### It is created on an rlwe instance and gives out valid samples
#### This has a cheat_sample function where you can generate samples with desired 'a' value
################################################

class Oracle:
    
    def __init__(self, rlwe ): # using some Ring-LWE instance, create an oracle that keeps a secret and offers samples
               
        ### Set the secret
        self.secret = rlwe.Rq.bigring.random_element()
        self.rlwe = rlwe
        
    def get_valid_sample(self):  # return a valid sample, random a
        aa = self.rlwe.Rq.bigring.random_element()
        bb = aa*self.secret + self.rlwe.get_error()
        return [aa,bb]
    
    def create_samps(self, numsamps): # create a list of valid samples of requested length
        samples = [] 
        for i in range(numsamps):   # first numsamps-1 elements of avals are the auxiliary samples
            mysamp = self.get_valid_sample()
            samples.append(mysamp)
        return samples
        
    def cheat_sample(self, aa):  # create a sample with given aa value (cheating!)
        bb = aa*self.secret + self.rlwe.get_error()
        return [aa,bb]
        

        
############################################
#### Simple exhaustive search
############################################
#### Given a Ring-LWE instance and a sample list,
#### perform exhaustive search to find secret
############################################

class Exhaust:
    
    def __init__(self, rlwe, samplist ):  # using the rlwe instance
        
        #### set up 
        self.rlwe = rlwe
        self.samps_list = samplist
         
    def find_c(self):  # look for possible secret "c", given samps, a list of reduced samples
        poss_c = []
        for c in self.rlwe.Rq.iterator(0):
            possible_flag = True
            for samp in self.samps_list:
                putative = samp[1] - samp[0]*c
                if not self.rlwe.is_error(putative):
                    possible_flag = False
                    break
            if possible_flag:
                poss_c.append(c)
                print "possible c:", c
        return poss_c
        
    def find_secret(self):   # try to find a possible secret and report on outcome
        poss_c = self.find_c()
        if len(poss_c) > 1:
            print "please try more samples"
            return False
        elif len(poss_c) == 0:
            print "error, no solutions"
            return False
        else:
            print "guessed secret:", poss_c[0]
            return poss_c[0]
    
############################################
#### Reduction Theorem
############################################
#### This takes in a ring-lwe object and sample list from one (specified) multiplicative coset
#### It gives out sample lists for an RLWE of reduced dimension
############################################

class Reduction:
    
    def __init__(self, rlwe, samplist, downdim, anought ):
        
        #### set up 
        self.rlwe = rlwe
        self.samplist = samplist
        self.downdim = downdim # downdim is the exponent (number of 2s) we move down; 1 -> index 2 subfield
        self.anought = anought
        
        #### Create the reduced sample lists
        self.samplists = [0 for _ in range(2^self.downdim)]
        for i in range(2^self.downdim):
            self.create_reduced_samplist(i)
        
    def create_reduced_samplist(self, j ):
        
        #### Create the trace-reduced samples
        newsamplist = []
        for samp in self.samplist:
            trace = self.rlwe.Rq.trace_red(samp[0], self.downdim)
            ring = self.rlwe.Rq.rings[self.rlwe.Rq.logn - self.downdim][0]
            newa = ring(self.rlwe.Rq.trace_red(samp[0], self.downdim))
            newb = ring(self.rlwe.Rq.trace_red(samp[1]*self.rlwe.r_pows[j], self.downdim))
            newsamplist.append([newa,newb])
            
        self.samplists[j] = newsamplist
///
}}}

{{{id=326|
### q = prime, n = 2 power dimension
n = 16
q = 13
### Choose how many dimensions to trace down (to index 2^downdim subring)
downdim = 2
### Build RingLWE instance object, and oracle with random secret
myRLWE = RingLWE(n,q,1)
myOracle = Oracle(myRLWE)
### Choose a particular multiplicative coset
anought = myRLWE.Rq.bigring.random_element(); anought
### Generate a sample list from the oracle, which cheats and uses a's drawn from the specified multiplicative coset
samplist = []
for i in range(200):
    samplist.append(myOracle.cheat_sample(anought*myRLWE.Rq.rings[downdim][0].random_element()))
### Produce an instance of the Reduction Theorem object
myRed = Reduction( myRLWE, samplist, downdim, anought)
### Produce an instance of the smaller Ring-LWE object
smallRLWE = RingLWE( ZZ(myRLWE.n/2^downdim), myRLWE.q, 2)
### Run exhaustive search on the smaller Ring-LWE instances and collect results
clist = []
for i in range( 2^downdim ):
    ex = Exhaust( smallRLWE, myRed.samplists[i] )
    clist.append(ex.find_secret())
### Do the linear algebra to recombine the secret*anought
guessedSecret = myRLWE.secretanought_recreation(downdim, anought, clist)
realSecret = myOracle.secret*anought
print "*************************"
print "My guessed secret*anought:", guessedSecret
print "My real secret*anought:   ", realSecret
///
Initializing a Ring-LWE with dimension  16  (meaning  32 -th roots), prime  13  and error width  1
embedding degree self.k:  8
Ring:  Univariate Quotient Polynomial Ring in z4 over Univariate Quotient Polynomial Ring in z3 over Univariate Quotient Polynomial Ring in z2 over Univariate Quotient Polynomial Ring in z1 over Finite Field of size 13 with modulus x^2 + 1 with modulus x^2 + 12*z1 with modulus x^2 + 12*z2 with modulus x^2 + 12*z3
Size of ring in bits:  59.2070354902575
Ring generator (2n-th root):  z4
Primitive 2n-th root of unity r =  z4
Primitive n-th root of unity t = r^2 =  z3
Initializing a Ring-LWE with dimension  4  (meaning  8 -th roots), prime  13  and error width  2
embedding degree self.k:  2
Ring:  Univariate Quotient Polynomial Ring in z2 over Univariate Quotient Polynomial Ring in z1 over Finite Field of size 13 with modulus x^2 + 1 with modulus x^2 + 12*z1
Size of ring in bits:  14.8017588725644
Ring generator (2n-th root):  z2
Primitive 2n-th root of unity r =  z2
Primitive n-th root of unity t = r^2 =  z1
[1, z2, z1, z1*z2]
possible c: (9*z1 + 9)*z2 + 10*z1
guessed secret: (9*z1 + 9)*z2 + 10*z1
[1, z2, z1, z1*z2]
possible c: (4*z1 + 10)*z2 + 8*z1 + 1
guessed secret: (4*z1 + 10)*z2 + 8*z1 + 1
[1, z2, z1, z1*z2]
possible c: 3*z1*z2 + 4
guessed secret: 3*z1*z2 + 4
[1, z2, z1, z1*z2]
possible c: (6*z1 + 10)*z2 + 5*z1 + 7
guessed secret: (6*z1 + 10)*z2 + 5*z1 + 7
v coeffs: [1, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 6, 0, 0, 0]
v coeffs: [6, 0, 0, 0, 7, 0, 0, 0, 4, 0, 0, 0, 12, 0, 0, 0]
v coeffs: [0, 0, 0, 0, 7, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
v coeffs: [12, 0, 0, 0, 10, 0, 0, 0, 12, 0, 0, 0, 12, 0, 0, 0]
z coeffs: [1, 10, 7, 7, 4, 12, 1, 4, 4, 12, 0, 12, 6, 1, 0, 7]
[1, z4, z3, z3*z4, z2, z2*z4, z2*z3, z2*z3*z4, z1, z1*z4, z1*z3, z1*z3*z4, z1*z2, z1*z2*z4, z1*z2*z3, z1*z2*z3*z4]
z:  (((7*z1 + 4)*z2 + 12*z1 + 7)*z3 + (z1 + 12)*z2 + 12*z1 + 10)*z4 + (z2 + 7)*z3 + (6*z1 + 4)*z2 + 4*z1 + 1
*************************
My guessed secret*anought: (((7*z1 + 4)*z2 + 12*z1 + 7)*z3 + (z1 + 12)*z2 + 12*z1 + 10)*z4 + (z2 + 7)*z3 + (6*z1 + 4)*z2 + 4*z1 + 1
My real secret*anought:    (((7*z1 + 4)*z2 + 12*z1 + 7)*z3 + (z1 + 12)*z2 + 12*z1 + 10)*z4 + (z2 + 7)*z3 + (6*z1 + 4)*z2 + 4*z1 + 1
}}}