{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

Sage Notebook Demonstrating Ring-BKW

\n", "

Version 1.3, May 10, 2019

\n", "

Katherine E. Stange

\n", "

\n", "

\n", "

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.

\n", "

\n", "

The purpose of this worksheet is only to demonstrate/verify mathematical correctness of the algorithms, not to determine runtimes or parameter boundaries.

\n", "

\n", "

Limitations:  In this version, the code has the following limitations (compared to the generality of the paper):

\n", "

1) the error width x means error coefficients are drawn uniformly from integers in the window [-x,x]

\n", "

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)

\n", "

\n", "

Evaluate the following cell to load all the code.

" ] }, { "cell_type": "code", "execution_count": 114, "metadata": {}, "outputs": [ { "data": { "text/plain": [] }, "execution_count": 114, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sage.modules.free_module_integer import IntegerLattice\n", "import random\n", "import itertools\n", "from sortedcontainers import SortedList, SortedDict\n", "from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic\n", "\n", "\n", "#####################################################\n", "#### Auxiliary Tools for Choosing Instance Parameters\n", "#####################################################\n", "\n", "### give various info about factorization of q^k-1\n", "def investigate( k, q ):\n", " for d in divisors(k):\n", " print \"factor q^\", k/d, \"-1: \", factor( q^(k/d)-1 )\n", " \n", "### list primes in a range with a certain power of two in base field\n", "def find_primes( lowbound, upbound, power_of_two ):\n", " return [ _ for _ in primes(lowbound, upbound) if Mod(_,power_of_two)==1 ]\n", "\n", "### compute embedding degree\n", "def emb_degree( n, q ): # n = dim, i.e. 2n roots of unity, q=prime\n", " emb_degree_flag = 0\n", " emb_degree = 1\n", " while emb_degree_flag == 0:\n", " if Mod(q^emb_degree-1,2*n) <> 0:\n", " emb_degree += 1\n", " else:\n", " emb_degree_flag = 1\n", " return emb_degree\n", " \n", "\n", "################################################ \n", "#### Rq = R/qR class\n", "################################################\n", "#### this class generates the ring Rq and its tower of subrings\n", "#### this class guarantees that the generator of a subring is the square of the generator of the next larger ring in the tower\n", "#### it allows for tracing into the subfield and for embedding subring back into big ring\n", "################################################\n", "\n", "class Rq:\n", " \n", " def __init__(self, dim, prime): \n", " \n", " ## Notes:\n", " ## dim -> 2*dim th roots appear, \n", " ## dim = dimension of this ring over Fq, must be power of two\n", " ## q = prime; modpoly = polynomial\n", " \n", " ### Dimension of big ring, must be power of two\n", " self.n = dim\n", " \n", " ### log base 2 of dimension\n", " self.logn = ZZ(log(self.n,2)) # exponent such that dimension = 2^exponent\n", " \n", " ### prime field we work over\n", " self.q = prime\n", " \n", " ### Generate the underlying prime field \n", " self.F = GF(self.q)\n", " \n", " ### Generate the tower of rings\n", " ###############################\n", " \n", " ### rings stores a list of [ring,generator] in increasing order\n", " ### rings[0] is the finite field with generator -1\n", " self.rings = [ [self.F, self.F(-1)] ]\n", " \n", " ### the largest ring is index self.logn\n", " for i in range(1,self.logn+1):\n", " lastring = self.rings[i-1]\n", " S. = PolynomialRing(lastring[0], 'x')\n", " zetaname = 'z' + str(i); # z0 = -1, z1 = i, etc.\n", " R = S.quotient( x^2 - lastring[1], zetaname ) # take square root of last generator\n", " self.rings.append( [R, R.gen()] )\n", " \n", " ### bigring is the largest ring, used most often\n", " self.bigring = self.rings[self.logn][0]\n", " \n", " ### Report on the ring created\n", " print \"Ring: \", self.bigring\n", " print \"Size of ring in bits: \", log( self.q^self.n, 2 ).n()\n", " \n", " ### Store ring generator (zeta) and report\n", " self.r = self.rings[self.logn][1]\n", " print \"Ring generator (2n-th root): \", self.r \n", "\n", " ### store powers of r for later use\n", " r_pows = [ self.r^i for i in range(self.n) ]\n", " \n", " def iterator(self, i): # iterator for the subring of index 2^i\n", " ring = self.rings[self.logn-i][0]\n", " gen = self.rings[self.logn-i][1]\n", " repeatrange = self.n/(2^i)\n", " gen_pows = [ gen^_ for _ in range(repeatrange) ]\n", " print gen_pows\n", " for tuple in itertools.product(self.F,repeat=repeatrange):\n", " elt = ring(0)\n", " for i in range(repeatrange):\n", " elt += gen_pows[i]*tuple[i]\n", " yield elt\n", " \n", " def subring(self, i ): # return index 2^i subring\n", " return self.rings[self.logn-1-i][0]\n", " \n", " def subgen(self, i ): # return generator of index 2^i subring\n", " return self.subrings[self.logn-1-i][1]\n", " \n", " def coefficient_list_onestep(self, elt ): # return the coefficient list in terms of subring of index 2\n", " return elt.list()\n", " \n", " def coefficient_list(self, elt): # return the coefficient list in terms of powers of zeta (self.r)\n", " if elt.parent() == self.rings[0][0]:\n", " return elt\n", " else:\n", " returnlist = []\n", " coeffs_lower = self.coefficient_list_onestep(elt);\n", " if coeffs_lower[0].parent() == self.rings[0][0]:\n", " return coeffs_lower\n", " list1 = self.coefficient_list(coeffs_lower[0])\n", " list2 = self.coefficient_list(coeffs_lower[1])\n", " for i in range(len(list1)):\n", " returnlist.append(list1[i])\n", " returnlist.append(list2[i])\n", " return returnlist \n", " \n", " def trace_red_1(self, ringindex, elt): # return trace to index 2 subring\n", " return self.rings[ringindex][0](elt).list()[0]\n", " \n", " def trace_red(self, elt, i ): # return the trace to the index 2^i subring (i=1 is subfield of index 2)\n", " myelt = elt\n", " for j in range(i):\n", " myelt = self.trace_red_1(self.logn - j, myelt)\n", " return myelt\n", " \n", " \n", "################################################\n", "#### Two-Power Cyclotomic Ring-LWE Class\n", "################################################\n", "#### this class generates a Ring-LWE instance\n", "#### this means \n", "#### 1) ring Rq object\n", "#### 2) error generator, check if something is an error\n", "#### 3) fake (i.e. uniform) sample generator\n", "#### it doesn't include or know about a secret (that's what an oracle class is for)\n", "################################################\n", "\n", "class RingLWE:\n", " \n", " def __init__(self, dim, prime, error_sigma ): # dim must be a power of two, indicating x^dim+1 (2dim-th roots)\n", "\n", " ### Set up and report basic parameters\n", " self.n = dim\n", " self.m = 2*dim\n", " self.q = prime\n", " self.sigma = error_sigma\n", " print \"Initializing a Ring-LWE with dimension \", dim, \" (meaning \", 2*dim, \"-th roots), prime \", prime, \" and error width \", error_sigma\n", " \n", " ### Compute embedding degree and report\n", " self.k = emb_degree( self.n, self.q )\n", " print \"embedding degree self.k: \", self.k\n", " \n", " ### Create the ring Rq\n", " self.Rq = Rq(self.n, self.q);\n", " self.r = self.Rq.bigring.gen();\n", " \n", " print \"Primitive 2n-th root of unity r = \", self.r\n", " print \"Primitive n-th root of unity t = r^2 = \", self.r^2\n", " \n", " ### save powers of primitive root\n", " self.r_pows = [ self.r^_ for _ in range(self.n) ]\n", " \n", " ### compute error coefficient range and save\n", " self.error_coeffs_range = range(-self.sigma,self.sigma+1)\n", "\n", " def get_error(self): # return a random error\n", " coeffs = [ random.choice(self.error_coeffs_range) for _ in range(self.n) ] # for m-th roots, choose coefficients\n", " eg = 0\n", " for jj in range(len(coeffs)):\n", " eg += coeffs[jj]*self.r_pows[jj]\n", " return eg\n", " \n", " def get_fake_sample(self): # return a uniform (non-valid) sample\n", " aa = self.Rq.bigring.random_element()\n", " bb = self.Rq.bigring.random_element()\n", " return [aa,bb]\n", " \n", " def trace_red(self, elt, i ): # return the trace to the index 2^i subfield (i=1 is subfield of index 2)\n", " return self.Rq.trace_red(elt, i)\n", " \n", " def coset_rep(self, elt ): # return a representative of the mult. coset of the index 2 subfield\n", " my_trace = self.trace_red(self.Rq(elt))\n", " if my_trace == 0:\n", " return self.r\n", " else:\n", " return self.Rq(elt)/my_trace\n", " \n", " def is_error(self, elt): # check if elt in Rq is an error\n", " eltlist = self.Rq.coefficient_list(elt)\n", " error_flag = True\n", " for i in range( self.k ):\n", " if eltlist[i] not in self.error_coeffs_range:\n", " error_flag = False\n", " break\n", " return error_flag\n", " \n", " def secretanought_recreation(self, downdim, anought, clist): # given a list of c's, uses Main Theorem to reconstruct secret\n", " anought_trace = self.trace_red(anought,downdim)\n", " zcoeffs = [0 for _ in range(self.n)]\n", " for j in range( 2^downdim ):\n", " vcoeffs = self.Rq.coefficient_list(self.Rq.bigring(clist[j]*anought_trace))\n", " print \"v coeffs:\", vcoeffs\n", " for i in range( self.n/(2^downdim) ):\n", " zcoeffs[i*(2^downdim) - j] = vcoeffs[i*2^downdim]\n", " if i*(2^downdim) - j < 0 :\n", " zcoeffs[i*(2^downdim)-j] = -vcoeffs[i*2^downdim]\n", " print \"z coeffs:\", zcoeffs\n", " print self.r_pows\n", " z = 0\n", " for jj in range(len(zcoeffs)):\n", " z += zcoeffs[jj]*self.r_pows[jj]\n", " print \"z: \", z\n", " return z\n", " \n", " \n", " \n", "################################################\n", "#### Oracle class\n", "################################################ \n", "#### The Oracle is the secret keeper\n", "#### It is created on an rlwe instance and gives out valid samples\n", "#### This has a cheat_sample function where you can generate samples with desired 'a' value\n", "################################################\n", "\n", "class Oracle:\n", " \n", " def __init__(self, rlwe ): # using some Ring-LWE instance, create an oracle that keeps a secret and offers samples\n", " \n", " ### Set the secret\n", " self.secret = rlwe.Rq.bigring.random_element()\n", " self.rlwe = rlwe\n", " \n", " def get_valid_sample(self): # return a valid sample, random a\n", " aa = self.rlwe.Rq.bigring.random_element()\n", " bb = aa*self.secret + self.rlwe.get_error()\n", " return [aa,bb]\n", " \n", " def create_samps(self, numsamps): # create a list of valid samples of requested length\n", " samples = [] \n", " for i in range(numsamps): # first numsamps-1 elements of avals are the auxiliary samples\n", " mysamp = self.get_valid_sample()\n", " samples.append(mysamp)\n", " return samples\n", " \n", " def cheat_sample(self, aa): # create a sample with given aa value (cheating!)\n", " bb = aa*self.secret + self.rlwe.get_error()\n", " return [aa,bb]\n", " \n", "\n", " \n", "############################################\n", "#### Simple exhaustive search\n", "############################################\n", "#### Given a Ring-LWE instance and a sample list,\n", "#### perform exhaustive search to find secret\n", "############################################\n", "\n", "class Exhaust:\n", " \n", " def __init__(self, rlwe, samplist ): # using the rlwe instance\n", " \n", " #### set up \n", " self.rlwe = rlwe\n", " self.samps_list = samplist\n", " \n", " def find_c(self): # look for possible secret \"c\", given samps, a list of reduced samples\n", " poss_c = []\n", " for c in self.rlwe.Rq.iterator(0):\n", " possible_flag = True\n", " for samp in self.samps_list:\n", " putative = samp[1] - samp[0]*c\n", " if not self.rlwe.is_error(putative):\n", " possible_flag = False\n", " break\n", " if possible_flag:\n", " poss_c.append(c)\n", " print \"possible c:\", c\n", " return poss_c\n", " \n", " def find_secret(self): # try to find a possible secret and report on outcome\n", " poss_c = self.find_c()\n", " if len(poss_c) > 1:\n", " print \"please try more samples\"\n", " return False\n", " elif len(poss_c) == 0:\n", " print \"error, no solutions\"\n", " return False\n", " else:\n", " print \"guessed secret:\", poss_c[0]\n", " return poss_c[0]\n", " \n", "############################################\n", "#### Reduction Theorem\n", "############################################\n", "#### This takes in a ring-lwe object and sample list from one (specified) multiplicative coset\n", "#### It gives out sample lists for an RLWE of reduced dimension\n", "############################################\n", "\n", "class Reduction:\n", " \n", " def __init__(self, rlwe, samplist, downdim, anought ):\n", " \n", " #### set up \n", " self.rlwe = rlwe\n", " self.samplist = samplist\n", " self.downdim = downdim # downdim is the exponent (number of 2s) we move down; 1 -> index 2 subfield\n", " self.anought = anought\n", " \n", " #### Create the reduced sample lists\n", " self.samplists = [0 for _ in range(2^self.downdim)]\n", " for i in range(2^self.downdim):\n", " self.create_reduced_samplist(i)\n", " \n", " def create_reduced_samplist(self, j ):\n", " \n", " #### Create the trace-reduced samples\n", " newsamplist = []\n", " for samp in self.samplist:\n", " trace = self.rlwe.Rq.trace_red(samp[0], self.downdim)\n", " ring = self.rlwe.Rq.rings[self.rlwe.Rq.logn - self.downdim][0]\n", " newa = ring(self.rlwe.Rq.trace_red(samp[0], self.downdim))\n", " newb = ring(self.rlwe.Rq.trace_red(samp[1]*self.rlwe.r_pows[j], self.downdim))\n", " newsamplist.append([newa,newb])\n", " \n", " self.samplists[j] = newsamplist" ] }, { "cell_type": "code", "execution_count": 326, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Initializing a Ring-LWE with dimension 16 (meaning 32 -th roots), prime 13 and error width 1\n", "embedding degree self.k: 8\n", "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\n", "Size of ring in bits: 59.2070354902575\n", "Ring generator (2n-th root): z4\n", "Primitive 2n-th root of unity r = z4\n", "Primitive n-th root of unity t = r^2 = z3\n", "Initializing a Ring-LWE with dimension 4 (meaning 8 -th roots), prime 13 and error width 2\n", "embedding degree self.k: 2\n", "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\n", "Size of ring in bits: 14.8017588725644\n", "Ring generator (2n-th root): z2\n", "Primitive 2n-th root of unity r = z2\n", "Primitive n-th root of unity t = r^2 = z1\n", "[1, z2, z1, z1*z2]\n", "possible c: (9*z1 + 9)*z2 + 10*z1\n", "guessed secret: (9*z1 + 9)*z2 + 10*z1\n", "[1, z2, z1, z1*z2]\n", "possible c: (4*z1 + 10)*z2 + 8*z1 + 1\n", "guessed secret: (4*z1 + 10)*z2 + 8*z1 + 1\n", "[1, z2, z1, z1*z2]\n", "possible c: 3*z1*z2 + 4\n", "guessed secret: 3*z1*z2 + 4\n", "[1, z2, z1, z1*z2]\n", "possible c: (6*z1 + 10)*z2 + 5*z1 + 7\n", "guessed secret: (6*z1 + 10)*z2 + 5*z1 + 7\n", "v coeffs: [1, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0, 6, 0, 0, 0]\n", "v coeffs: [6, 0, 0, 0, 7, 0, 0, 0, 4, 0, 0, 0, 12, 0, 0, 0]\n", "v coeffs: [0, 0, 0, 0, 7, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]\n", "v coeffs: [12, 0, 0, 0, 10, 0, 0, 0, 12, 0, 0, 0, 12, 0, 0, 0]\n", "z coeffs: [1, 10, 7, 7, 4, 12, 1, 4, 4, 12, 0, 12, 6, 1, 0, 7]\n", "[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]\n", "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\n", "*************************\n", "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\n", "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" ] }, "execution_count": 326, "metadata": {}, "output_type": "execute_result" } ], "source": [ "### q = prime, n = 2 power dimension\n", "n = 16\n", "q = 13\n", "### Choose how many dimensions to trace down (to index 2^downdim subring)\n", "downdim = 2\n", "### Build RingLWE instance object, and oracle with random secret\n", "myRLWE = RingLWE(n,q,1)\n", "myOracle = Oracle(myRLWE)\n", "### Choose a particular multiplicative coset\n", "anought = myRLWE.Rq.bigring.random_element(); anought\n", "### Generate a sample list from the oracle, which cheats and uses a's drawn from the specified multiplicative coset\n", "samplist = []\n", "for i in range(200):\n", " samplist.append(myOracle.cheat_sample(anought*myRLWE.Rq.rings[downdim][0].random_element()))\n", "### Produce an instance of the Reduction Theorem object\n", "myRed = Reduction( myRLWE, samplist, downdim, anought)\n", "### Produce an instance of the smaller Ring-LWE object\n", "smallRLWE = RingLWE( ZZ(myRLWE.n/2^downdim), myRLWE.q, 2)\n", "### Run exhaustive search on the smaller Ring-LWE instances and collect results\n", "clist = []\n", "for i in range( 2^downdim ):\n", " ex = Exhaust( smallRLWE, myRed.samplists[i] )\n", " clist.append(ex.find_secret())\n", "### Do the linear algebra to recombine the secret*anought\n", "guessedSecret = myRLWE.secretanought_recreation(downdim, anought, clist)\n", "realSecret = myOracle.secret*anought\n", "print \"*************************\"\n", "print \"My guessed secret*anought:\", guessedSecret\n", "print \"My real secret*anought: \", realSecret" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.1", "language": "sage", "name": "sagemath" }, "language": "python", "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.5" } }, "nbformat": 4, "nbformat_minor": 1 }