Sage Notebook Demonstrating Ring-BKW
Version 1.3, May 10, 2019
Katherine E. Stange
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
This notebook has been prepared as an accompaniment to the paper Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm. See the website http://math.colorado.edu/~kstange/ring-bkw.html. Usage is demonstrated below.
The purpose of this worksheet is only to demonstrate/verify mathematical correctness of the algorithms, not to determine runtimes or parameter boundaries.
Limitations: In this version, the code has the following limitations (compared to the generality of the paper):
1) the error width x means error coefficients are drawn uniformly from integers in the window [-x,x]
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)
Evaluate the following cell to load all the code.
{{{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. = 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
}}}