extfieldsofstudy:
Mathematics
Computer Science

text:
Learning With Errors and Extrapolated Dihedral Cosets

The hardness of the learning with errors (LWE) problem is one of the most fruitful resources of modern cryptography. In particular, it is one of the most prominent candidates for secure post-quantum cryptography. Understanding its quantum complexity is therefore an important goal. We show that under quantum polynomial time reductions, LWE is equivalent to a relaxed version of the dihedral coset problem (DCP), which we call extrapolated DCP (eDCP). The extent of extrapolation varies with the LWE noise rate. By considering different extents of extrapolation, our result generalizes Regev's famous proof that if DCP is in BQP (quantum poly-time) then so is LWE (FOCS'02). We also discuss a connection between eDCP and Childs and Van Dam's algorithm for generalized hidden shift problems (SODA'07). Our result implies that a BQP solution for LWE might not require the full power of solving DCP, but rather only a solution for its relaxed version, eDCP, which could be easier.

Introduction
The Learning With Errors problem LWE n,q,α with parameters n, q ∈ Z and α ∈ (0, 1) consists in finding a vector s ∈ Z n q from arbitrarily many samples (a i , a i , s + e i ) ∈ Z n q × Z q , where a i is uniformly sampled in Z n q and e i is sampled from D Z,αq , the discrete Gaussian distribution of standard deviation parameter αq (i.e., the distribution such that D Z,αq (k) ∼ exp(−πk 2 /(αq) 2 ) for all k ∈ Z). Since its introduction by Regev [27,28], LWE has served as a security foundation for numerous cryptographic primitives (see e.g. an overview in [23]). The cryptographic attractiveness of LWE stems from two particularly desirable properties. First, its algebraic simplicity enables the design of primitives with advanced functionalities, such as fully homomorphic encryption [7], attribute-based encryption for all circuits [13] and (single key) functional encryption [12]. Second, LWE is conjectured hard even in the context of quantum computations, making it one of the most appealing candidate security foundations for post-quantum cryptography [5]. Current quantum algorithms for LWE do not outperform classical ones, but it is not clear whether this is inherent (for example, it is known that LWE is easier than the Dihedral Coset Problem under polynomial-time reductions, see below). In this work, we characterize the quantum hardness of LWE under polynomial-time reductions and show that it is computationally equivalent (up to small parameter losses) to a quantum problem closely related to the aforementioned Dihedral Coset Problem.
LWE, Lattices and the Dihedral Coset Problem. LWE is tightly connected to worst-case approximation problems over Euclidean lattices. In particular, LWE is an (average-case) instance of the Bounded Distance Decoding problem (BDD) (see, e.g., [20,Section 5.4]), but is also known to be as hard as worst-case BDD (with some polynomial loss in parameters) [28]. BDD is the problem of finding the closest lattice vector to a given target point which is promised to be very close to the lattice (formally, closer than λ 1 /γ where λ 1 is the length of the shortest non-zero vector). Classical and quantum connections between BDD and other problems such as SIVP, GapSVP, uSVP are also known [6,19,22,28].
Regev [24,26] showed that uSVP, and therefore also BDD and LWE, are no harder to solve than the quantumly-defined Dihedral Coset Problem (DCP). An instance of DCP N,ℓ , for integer parameters N and ℓ, consists of ℓ quantum registers in superposition |0, x k + |1, x k + s , with a common s ∈ Z N and random and independent x k ∈ Z N for k ∈ [ℓ]. The goal is to find s (information theoretically ℓ = O(log N ) is sufficient for this task [9]). We note that Regev considered a variant with unbounded number of registers, but where a fraction of them is faulty (a faulty state is of the form |b, x k for arbitrary b ∈ {0, 1}, x k ∈ Z N ). In our work, we assume a non-faulty formulation of DCP. Still, it is quite possible that DCP is in fact much harder to solve than LWE. The best known algorithm for DCP, due to Kuperberg [16], runs in time 2 O(log ℓ+log N/ log ℓ) which does not improve upon classical methods for solving LWE. Other variants of the problem were explored in [9,10], and of particular relevance to this work is a "vector" variant of the problem where Z N is replaced with Z n q (i.e. s and x k are now vectors). These problems behave similarly to DCP with N = q n .
Finally, Regev showed that DCP can be solved given efficient algorithms for the subset-sum problem (which is classically defined), however in a regime of parameters that appears harder to solve than LWE itself.
Extrapolated DCP. The focus of this work is a generalization of the DCP problem, i.e. rather than considering registers containing |0, x k +|1, x k + s , we allow (1) x i 's and s be n-dimensional vectors, and (2) other than non-uniform distribution for amplitudes. We name this problem Extrapolated DCP (EDCP) as its in-put registers has more extrapolated states. To be more precise, EDCP ℓ n,N,f , with parameters three integers n, N, ℓ and a function f : Z → C with j∈Z j·|f (j)| 2 < +∞, consists in recovering s ∈ Z n N from the following ℓ states over Z × Z n N : where the x k 's are arbitrary in Z n N . 1 Note that DCP is the special case of EDCP for n = 1 and f being the indicator function of {0, 1}.
In [8], Childs and van Dam consider a special case of EDCP where f is the indicator function of {0, . . . , M − 1} for some integer M , which we will refer to as uniform EDCP (or, U-EDCP ℓ n,N,M ).
Our Main Result. We show that up to polynomial loss in parameters, U-EDCP is equivalent to LWE. Thus we provide a formulation of the hardness assumption underlying lattice-based cryptography in terms of the (generalized) Dihedral Coset Problem.
Theorem 1 (Informal). There exists a quantum polynomial-time reduction from LWE n,q,α to U-EDCP ℓ n,N,M , with N = q, ℓ = poly(n log q) and M = poly(n log q) α . Conversely, there exists a polynomial-time reduction from U-EDCP to LWE with the same parameter relationships, up to poly(n log q) factors.
Our proof crucially relies on a special case of EDCP where f is a Gaussian weight function with standard deviation parameter r. We call this problem Gaussian EDCP (G-EDCP). We show that G-EDCP and U-EDCP are equivalent up to small parameter losses.
EDCP is analogous to LWE in many aspects. The decisional version of LWE (dLWE) asks to distinguish between LWE samples and random samples of the form (a, b) ∈ Z n q × Z q where both components are chosen uniformly at random. Similarly, we also consider the decisional version of EDCP, denoted by dEDCP. In dEDCP n,N,f , we are asked to distinguish between an EDCP state and a state of the form |j |x mod N , where j is distributed according to the function |f | 2 , and x ∈ Z n N is uniformly chosen. EDCP enjoys a reduction between its search and decisional variants via LWE.
Related work. In [8], Childs and van Dam show that U-EDCP ℓ 1,N,M reduces to the problem of finding all the solutions b ∈ {0, . . . , M − 1} k to the equation b, x = w mod N , where x and w are given and uniformly random modulo N . They interpret this as an integer linear program and use lattice reduction, within Lenstra's algorithm [18], to solve it. This leads to a polynomial-time algorithm for U-EDCP ℓ 1,N,M when M = ⌊N 1/k ⌋ and ℓ ≥ k, for any k ≥ 3. Interestingly, finding small solutions to the equation b, x = w mod N is a special case of the Inhomogeneous Small Integer Solution problem [11] (ISIS), which consists in finding a small-norm x such that Bx = w mod q, with B ∈ Z n×m q and w ∈ Z n q uniform (where q, n, m are integer parameters). A reduction from the homogeneous SIS (i.e., with w = 0 and x = 0) to LWE was provided in [30]. It does not seem possible to derive from it a reduction from EDCP to LWE via the Childs and van Dam variant of ISIS, most notably because the reduction from [30] does not provide a way to compute all ISIS solutions within a box {0, 1, . . . , M − 1} k .
It is not hard to see that, at least so long as M is polynomial, a solution to DCP implies a solution to EDCP ℓ n,N,M . Therefore our result implies [24] as a special case. On the other extreme, our result also subsumes [8] since the LLL algorithm [17] can be used to solve LWE n,q,α in polynomial time when 1/α and q are 2 Θ(n) , which implies a polynomial-time algorithm for EDCP for M = 2 Θ( √ n log N ) , significantly improving Childs and van Dam's M = 2 εn log N . Finally, we observe that the LWE to U-EDCP reduction (and the uSVP to DCP reduction from [26]) can be adapted to a uSVP to U-EDCP reduction, as explained below. Combining this adaptation with the reduction from U-EDCP to LWE (via G-EDCP) provides a novel quantum reduction from worst-case lattice problems to LWE. However, it does not seem to have advantages compared to [28].

Technical overview
As mentioned above, the hardness of LWE is essentially invariant so long as n log q is preserved, and therefore we restrict our attention in this overview to the one-dimensional setting. A crucial ingredient in our reduction is a weighted version of EDCP, denoted by G-EDCP and quantified by a Gaussian weight function f r (j) =ρ r (j) = exp(−πj 2 /r 2 ), for some standard deviation parameter r. We refer to this problem as Gaussian EDCP (G-EDCP).
Reducing G-EDCP to LWE. Given an G-EDCP state as input, our reduction efficiently transforms it into a classical LWE sample with constant success probability. Thus, making only one query to the LWE oracle, we are able to solve G-EDCP. More precisely, the reduction input consists of a normalized state corresponding to j∈ZN ρ r (j) |j |x + j · s mod N , for some integers r ≪ N . One can think of N as the LWE modulus and of r as the standard deviation parameter of the LWE error.
Our first step is to apply a quantum Fourier transform over Z N to the second register. This gives us a quantum superposition of the form:  where ω N = exp(2iπ/N ). We then measure the second register and obtain a value a ∈ Z N . This leaves us with the state: Note that a is uniformly random over Z N , which at the end serves as the first component of LWE sample. The exponent of relative phase in current state has a form similar to the second component of LWE sample but without noise. Now we can benefit from the first register, which stores a superposition corresponding to a Gaussian distribution over Z N with standard deviation r. Applying a second quantum Fourier transform over Z N to the first register gives us a quantum superposition of the form: Now the second component of the LWE sample a · s + b is stored in the phase (up to a factor j). Omitting the exponentially small Gaussian tail, we assume the summation for j is taken over the integers. An application of the Poisson summation formula transfers a · s + b into a shift of the Gaussian distribution defined over Z. In other words, the received state is exponentially close to the superposition: Once we measure the state above, we obtain a value − a·s+e, where e ←֓ D Z,N/r . Together with already known a, this gives us an LWE sample: (− a, − a · s + e) .
In case the input state is of the form |j |x mod N , where j is distributed according to the function ρ 2 r , and x ∈ Z N is uniformly chosen (the decisional case), the reduction outlined above outputs a uniform random pair (a, b) from Z N ×Z N . This gives a reduction from decisional version of G-EDCP to decisional version of LWE.
Reducing LWE to G-EDCP. Our reduction from LWE to G-EDCP follows the general design of Regev's reduction from uSVP to DCP [26], with several twists that enable simplifications and improvements. We note that this reduction is folklore, 2 although we could not find it described explicitly.
First, the use of LWE rather than uSVP allows us to avoid Regev's initial subreduction from uSVP to BDD, as LWE is a randomized variant of BDD. Indeed, if we consider m samples (a i , a i · s + e i ) from LWE n,q,α , then we have a BDD instance for the lattice Λ = AZ q + qZ m and the target vector t = b + e ∈ Z m with b ∈ Λ satisfying b = A · s mod q.
As Regev's, our reduction proceeds by subdividing the ambient space R m with a coarse grid, setting the cell width between e and λ 1 (Λ). We map each point y ∈ R m to a cell φ(y). By choice of the cell width, we have φ(c 1 ) = φ(c 2 ) for any c 1 = c 2 in Λ. Also for any c ∈ R m , the vectors c and c + e are most likely mapped to the same cell, as e is short. This intuition fails if a border between two cells falls close to c. This (rare but non-negligibly so) event is the source of the limitation on the number ℓ of DCP/EDCP states produced by the reduction. The space subdivision by a grid is illustrated in Figure 2. Regev's reduction and ours differ in the way the grid is used to create the DCP/EDCP states. Let us first briefly recall the core of Regev's reduction. Let B = (b 1 , . . . , b m ) be a basis of Λ and subtract an appropriate combination of the b i 's from t to get t ′ so that the coordinates x ′ of the closest vector b ′ ∈ Λ to t ′ with respect to the b i 's are ≤ 2 m (this may be achieved using LLL [17] and Babai's nearest plane algorithm [1]). The first step is the creation of a superposition where the equality holds by a change of variable. By measuring the last register, with overwhelming probability this collapses to |0 |x k + |1 |x k + x ′ , which corresponds to an m-dimensional DCP input state with modulus 2 O(m) . The whole process can be repeated multiple times using the same input vector t, and results in different x k 's but a common x ′ . Each iteration may fail because of an illplaced cell delimitation, or if x k + x ′ has a coordinate whose magnitude is larger than 2 2m . This leads to a bounded number of correct DCP input states. Finally, m-dimensional DCP can be reduced to 1-dimensional DCP, with a significant modulus increase: the resulting modulus N is 2 O(m 2 ) . Instead of using a superposition based on the coordinates with respect to a basis, we exploit the special form of Λ = aZ q + qZ m (w.l.o.g., assume 1dimensional LWE, [6]). We start with the following superposition: We then measure the last register (classically known and omitted) and hopefully obtain a superposition |0 |x + |1 |x + s . This approach has several notable advantages. First, by using a grid over the torus R m /qR m , the only source of failure is the position of the cell delimitation (coordinates cannot spill over, they wrap around). Second, we directly end up with a DCP state, not a vectorial variant thereof. Third, and most importantly, the DCP modulus N is only q and not 2 O(m 2 ) . Note that m should be set as Ω(log q) for s to be uniquely determined by the LWE samples. This improvement results in a much tighter reduction.
The improvement stems from the use of a small modulus q rather than large integer coordinates. It is possible to obtain such a small DCP modulus while starting from BDD (rather than LWE), by modifying Regev's reduction as follows. One may first reduce BDD to a variant thereof that asks to find the coordinates of the BDD solution modulo a small modulus q rather than over the integers. Such a reduction is presented in [28,Lemma 3.5]. One may then reduce this BDD variant to DCP as we proceed for LWE. Note that this transformation makes the BDD to DCP reduction from [26] iterative: the DCP oracle is called several times, and the input of an oracle call depends on the output of the previous oracle calls. This is akin to the phenomenon described in the open questions paragraph from [6].
A further difference between our reduction and the one from [26] is that we consider larger multiples of s in the input superposition to obtain a state of the form j ρ r (j) |j |x + js , with r ≈ 1/α (up to polynomial factors). This does not lead to any extra complication, but leads us to G-EDCP rather than DCP, which we crucially need to allow for a converse reduction. We conjecture that G-EDCP is strictly easier than DCP.
As Regev [25], we can also improve the resulting deviation parameter r of G-EDCP by a factor of √ m using balls' intersections rather than cube separation. We consider intersections of balls drawn around a · s and its noisy shifts. The radius R of each ball is set to be the largest value such that the balls arising from different s (and their shifts) do not intersect. We are interested in the intersection area the balls drawn around ±s, ±2s, etc. Following Regev [25], this area is large enough to guarantee that once we measure, we hit a point from the intersection of all the balls (see grey areas in Figure 3). Fig. 3: A visualization of the balls' intersections. The lattice points (black dots) are of distance first minimum of lattice aZ q + qZ to each other. The distance between the two furtherst shifts je (red dots) has an upper bound, denoted by d. Each ball has a radius R chosen to be (approximately) λ 1 (Λ q (a))/2, where Λ q (a) = aZ q + qZ. Note that once the shaded gray area is measured, the reduction succeeds in outputting an G-EDCP sample. For the reduction to work with a constant success probability, the shaded area has to have a large enough proportion compared to the volume of the balls.
The same algorithm provides a reduction from dLWE to dG-EDCP. Given a random sample (a, b) ∈ Z m q × Z m q , it suffices to show that all the balls centered at as + jb for s ∈ Z q and j ∈ Z, do not intersect with each other. All the points considered above form the lattice (a|b)Z q + qZ, We argue analogously using the upper-bound on the minima of this lattice. As a result, the superposition collapses exactly to one of the balls, which gives a random sample of dG-EDCP.

Open problems
Towards an alternative reduction from EDCP to LWE. In [8], Childs and van Dam obtain a state of the form for some uniform y ∈ Z ℓ N . Note the uniform distribution of weights for j. To recover s, the authors use the Pretty Good Measurement technique from [15] as was done in [2,3] for similar problems. Implementing this general technique to this particular setup requires the construction of a POVM with operators corresponding to superpositions of all the j's in {0, . . . , M −1} ℓ such that j, y = a mod N . As we already mentioned, a unitary operator that realizes such a POVM, uses a lattice-reduction technique as its main subroutine and, hence, works efficiently only for large values of M .
The question we do not address here is the interpretation of the POVM technique (and, possibly, a different reduction to LWE) for Gaussian-weighted superpositions. It might be simpler to obtain Gaussian j's rather than uniform from a cube, and hence it is possible that such a technique may lead to an improved reduction to LWE.
Hardness of EDCP with more input states. We show in this work that LWE and U-EDCP are computationally equivalent up to small parameter losses, when the number of U-EDCP states ℓ is polynomial. In these reductions, the U-EDCP bound M is within a polynomial factor of the LWE noise rate 1/α. When more states are available, U-EDCP is likely to become easier. For instance, with M = 2, the best known algorithms when ℓ is polynomially bounded are exponential. Oppositely, Kuperberg's algorithm [16] . This suggests that there may be a U-EDCP self-reduction allowing to trade ℓ for M : Is it possible to reduce EDCP N,ℓ,M to EDCP N,ℓ ′ ,M ′ with ℓ ′ ≤ ℓ, while allowing for M ′ ≥ M ?

Prerequisites
Notations. We use lower case bold letters to denote vectors and upper case bold to denote matrices. For a vector x, we let x ∞ denote its ℓ ∞ norm and x denote its ℓ 2 norm. We let Z N denote the cyclic group {0, 1, · · · , N − 1} with addition modulo N . We assume we can compute with real numbers. All the arguments are valid if a sufficiently accurate approximation is used instead. For a distribution D, the notation x ←֓ D means that x is sampled from D. For a set S, we let x ←֓ S denote that x is a uniformly random element from S.
For any r > 0, we let ρ r (x) denote exp(−π x 2 /r 2 ), where x ∈ R n for a positive integer n. We let D Z,r denote a Gaussian distribution over the integers with density function proportional to ρ r (·). We let D Λ,r,c denote the Gaussian distribution over the n-dimensional lattice Λ (for a positive integer n), with standard deviation parameter r ∈ R and center c ∈ R n . If c = 0, we omit it. We let B n (c, R) denote the n-dimensional Euclidean ball of radius R centered at c ∈ R n and B n denotes the n-dimensional Euclidean unit ball centered at 0. We use ω N as a short-hand for exp(2πi/N ).
For a lattice Λ with a basis B, the parallelepiped P(B) = {Bx : 0 ≤ x i ≤ 1} is a fundamental domain of Λ. We let λ 1 (Λ) (resp. λ ∞ 1 (Λ)) denote the ℓ 2 -norm (ℓ ∞ -norm) of a shortest vector of Λ. We let Λ ⋆ = {y ∈ R n : ∀x ∈ Λ, x, y ∈ Z} denote the dual of a lattice Λ. We define the smoothing parameter η ε (Λ) as be . We assume all the parameters n (the dimension), q (the modulus) and r are functions of a common parameter κ. The most relevant choice of such a relation one can keep in mind is when n, ℓ, q and r are poly(κ). One can trace the losses in the parameters (with respect to the number of samples ℓ and to r) once we move from one problem to another. Notice that some reductions may be performed in two ways. For example, using the self-reducibility property of EDCP (Lemma 10), we can bypass Gaussian EDCP and have a more sampleefficient reduction from EDCP with large r to an EDCP with smaller r. Similarly, Gaussian EDCP can be reduced to DCP either directly (Lemma 11) or via uniform EDCP.
The two central reductions that show equivalence between LWE and EDCP problems are on the vertical line. As for EDCP, the LWE parameters n, q, and α are functions of κ. We present two reductions from LWE to EDCP, the stronger one gives a tighter result for the error-parameter by a factor of √ m.
We introduce a variable κ to relate all the parameters involved in the definitions below. Namely, n, q, etc. are actually functions in κ: n(κ), q(κ). We omit the variable κ for clarity.
Definition 1 (Search LWE). Given a parameter κ, the input to the search LWE m n,q,χ with dimension n ≥ 1, modulus q ≥ 2 and distribution χ over Z, consists of m ≥ n many samples of the form (a, b) ∈ Z n q × Z q , with a ←֓ Z n q , b = a, s +e and e ←֓ χ, where s ∈ Z n q is uniformly chosen. We say that an algorithm solves the search LWE m n,q,χ if it outputs s with probability poly(1/(n log q)) in time poly(n log q).
Definition 2 (Decision LWE). Given a parameter κ, the decisional LWE m n,q,χ with dimension n ≥ 1, modulus q ≥ 2 and distribution χ over Z, asks to distinguish between m ≥ n many LWE samples and random samples of the form (a, b) ∈ Z n q ×Z q , with a ←֓ Z n q , b ←֓ Z q . We say that an algorithm solves the decisional LWE m n,q,χ if it succeeds in distinguishing with probability poly(1/(n log q)) in time poly(n log q).
We let LWE m n,q,α (resp. dLWE m n,q,α ) denote search (resp. decisional) LWE problem with m samples of dimension n, modulus q, error distributed as D Z,αq .
Definition 3 (Dihedral Coset Problem). Given a parameter κ, the input to the DCP ℓ N with modulus N consists of ℓ states. Each state is of the form (normalization is omitted) stored on 1 + ⌈log 2 N ⌉ qubits, where x ∈ Z N is arbitrary and s ∈ Z N is fixed throughout all the states. We say that an algorithm solves DCP ℓ N if it outputs s with probability poly(1/ log N ) in time poly(log N ).
Note that Regev in [24] defines the Dihedral Coset problem slightly differently. Namely, he introduces a failure parameter f (κ), and with probability ≤ 1/(log N (κ) f (κ) ), we have a state of the form |b |x for arbitrary b ∈ {0, 1} n and x ∈ Z N . Such a state does not contain any information on s. Our definition takes 0 for the failure parameter. Conversely, Regev's definition is our Def. 3 with a reduced number of input states. Now we define the problem which can be viewed as an extension of DCP. Analogous to LWE, it has two versions: search and decisional.
Definition 4 (Search Extrapolated Dihedral Coset Problem). Given a parameter κ, the input to the search Extrapolated Dihedral Coset Problem (EDCP ℓ n,N,D ) with dimension n, modulus N and a discrete distribution D, consists of ℓ input states of the form (normalization is omitted) where x ∈ Z n N is arbitrary and s ∈ Z n N is fixed for all ℓ states. We say that an algorithm solves search EDCP ℓ n,N,D if it outputs s with probability poly(1/(n log N )) in time poly(n log N ).
Definition 5 (Decisional Extrapolated Dihedral Coset Problem). Given a parameter κ, the decisional Extrapolated Dihedral Coset Problem (dEDCP ℓ n,N,D ) with modulus N and a discrete distribution D, asks to distinguish between ℓ many EDCP samples and ℓ many random samples of the form where j k ←֓ D 2 and x k ∈ Z n N is uniformly chosen for 1 ≤ k ≤ ℓ. We say that an algorithm solves dEDCP ℓ n,N,D if it distinguishes the two cases with probability poly(1/(n log N )) in time poly(n log N ).
Different choices of D give rise to different instantiations of EDCP. The two interesting ones are: (1) D is uniform over Z M for some M ∈ Z, which we further denote as U-EDCP ℓ n,N,M and (2) D is Gaussian D Z,r , which we further denote as G-EDCP ℓ n,N,r . The former, named the generalized hidden shift problem, was already considered in [8]. The latter is central in our reductions. Correspondingly, we call the decisional version of G-EDCP by dG-EDCP.
Gaussian distribution on lattices. In the following, we recall some important properties of discrete Gaussian distribution. For the sake of completeness, we include the proof in Appendix A.1. From Lemma 1, we can see that the tail of Gaussian distribution has only negligible proportion compared to the whole sum. We use this fact within a quantum superposition state. For a quantum superposition state with Gaussian amplitudes, the superposition corresponding to Gaussian distribution over full lattice and the one without Gaussian tail have exponentially small ℓ 2 distance.

Lemma 3 (Poisson Summation Formula).
For any n-dimensional lattice Λ and vector u ∈ R n , it holds that The following Lemma is originally due to Grover-Rudolph [14] and was adapted to Gaussian distribution in [28].
Lemma 4 (Adapted from [28,Lemma 3.12]). Given a parameter κ and an integer r, there exists an efficient quantum algorithm that outputs a state that is within ℓ 2 distance 2 −Ω(κ) of the normalized state corresponding to x∈Z ρ r (x) |x .
The following two lemmata are well-known facts about lower-bounds on minimum of q-ary lattices.
Lemma 5. Given a uniformly chosen matrix A ∈ Z m×n q for some positive integers q, m and n such that m ≥ n, then we have λ ∞ 1 (Λ q (A)) ≥ q (m−n)/m /2 and λ ∞ 1 (Λ ⊥ q (A)) ≥ q n/m /2 both with probability 1 − 2 −m . Lemma 6. Given a uniformly chosen matrix A ∈ Z m×n q for some positive integer q, m and n such that m ≥ n, then we have λ 1 (Λ q (A)) ≥ min{q, Reductions between EDCP variants. In the following, we show that the EDCP problem is analogue to the LWE problem in many aspects: (1) Gaussian-EDCP (G-EDCP ℓ ′ n,N,r ) and uniform-EDCP (U-EDCP ℓ n,N,M ) are equivalent, up to small parameter losses; (2) EDCP enjoys the self-reduction property as we show in Lemma 10. The main ingredient in both proofs is quantum rejection sampling due to Ozols et al. [21].
for some p k ≤ π k , with probability p 2 = n k=1 p 2 k . Lemma 8 (G-EDCP ≤ U-EDCP). Let N, n and ℓ be integers greater than 1, r be any real number, and let M = c · r for some constant c such that M is an integer. Then there is a probabilistic reduction with run-time polynomial in κ, from G-EDCP ℓ n,N,r to U-EDCP Proof. We are given as input G-EDCP ℓ n,N,r states: Our aim is to find s, given access to a U-EDCP O(ℓ/κ) n,N,cr oracle for some constant c. For each G-EDCP n,N,r sample, we proceed as follows. We let sign(x) to denote the sign of x, its output is either 1 (for ' + ') or 0 (for ' − '). We first compute the sign of the first register and store it in a new register: Second, we measure the third register. Note that we observe 1 with probability at least 1/2, independently over all k's. If the observed value is 0, we discard the state. From states with the observed value 1, we obtain (up to normalization): |j |(x + j · s) mod N with probability Ω(M ρ 2 r (c · r)/r) = Ω(1). We repeat the above procedure until we obtain O(ℓ/κ) many U-EDCP n,N,M states, which happens with probability ≥ 1 − 2 −Ω(κ) . We call the U-EDCP O(ℓ/κ) n,N,M oracle to recover the secret s as the solution for the input G-EDCP ℓ n,N,r instance. Proof. We are given as input ℓ many U-EDCP ℓ n,N,M states: Our aim is to find s, given access to a G-EDCP Using rejection sampling (Lemma 7), with probability Ω(r/M ) = Ω(1/ √ κ) we transform each U-EDCP n,N,⌈ M −1 2 ⌉ state into a G-EDCP n,N,r state: According to Lemma 1, the latter is within the ℓ 2 distance of 2 −Ω(κ) away from the state We repeat the above procedure until we obtain O(ℓ/κ 1.5 ) many G-EDCP n,N,r states, which happens with probability ≥ 1 − 2 −Ω(κ) . Then we can use the G-EDCP O(ℓ/κ 1.5 ) n,N,r oracle to recover the secret s as the solution to U-EDCP ℓ n,N,M . Next, we show the self-reducibility property for EDCP. We refer the reader to Appendix A.2 for the proof.
Lemma 10 (EDCP self-reduction). Let N, n, and ℓ be integers greater than 1, r 1 and r 2 be such that r 1 > r 2 and r 1 /r 2 = O(κ c ) for any constant c. Then there is a probabilistic reduction with run-time polynomial in κ, from G-EDCP ℓ n,N,r1 ).
In the following, we give a reduction from Gaussian-EDCP to DCP. Thus uniform-EDCP can also be reduced to DCP in two ways: either via self-reduction, or via Gaussian-EDCP as the next lemma shows. This result is especially interesting when the parameter r (or M for the uniform-EDCP) is super-polynomially large, as in this case, Lemma 10 cannot be applied. Lemma below works with 1-dimensional EDCP. This is without loss of generality as we can combine our main result (equivalence of LWE and EDCP) with the result of Brakerski et al. [6] (equivalence of LWE n,q,α and LWE 1,q n ,α ). Proof. We are given as input ℓ many G-EDCP 1,N,r states: We show how to find s if we are given access to a DCP wherex k = x k − M · s. We measure the third register and denote the observed value by v k . We make use of the two well-known facts from number theory. For proofs, the reader may consult [29,Chapter 5]. First, there exist more than M/ log M many primes that are smaller than M . Second, N has at most 2 log N/ log log N prime factors. Thus there are at least M/ log M − 2 log N/ log log N many numbers smaller than M that are co-prime with all prime factors of N .
From the above, with probability Ω(1/ log M ) = Ω(1/ log r), the observed value v k is non-zero and co-prime with N . If this is not the case, we discard the state. Otherwise, we obtain (up to normalization): We multiply the value in the second register by v −1 k mod N : Rewrite the above state as: |−v k |x k + |v k |(x k +s) mod N .
As we know v k classically, we uncompute the first register and obtain a DCP state: |0 |x k + |1 |(x k +s) mod N .
• Case that r < 3 log N .
The first steps are identical to the proof for the case r ≥ 3 log N : Compute the absolute value of the first register to get a state as in (4) and measure the third register. Denote the observed value by v k . Now we keep only those states, for which v k = 1 was observed. Otherwise, we do not use the state. In case v k = 1, we can easily transform the result to the state given in (5) analogously to the proof for r ≥ 3 log N . Now we show that v k = 1 occurs with probability Ω(1/r) independently over all k's. Indeed, We repeat the above procedure until we obtain O(ℓ/(r · κ)) many DCP N states, which happens with probability ≥ 1 − 2 −Ω(κ) . In both cases considered in this lemma, we can use the DCP O(ℓ/(r·κ)) N oracle and get the secrets. There are at most 2 possible values s such thats = 2s mod N : if there are 2 possibilities, we uniformly choose either, which decreases the success probability by at most a factor of 2.

Reduction from LWE to EDCP
In this section, we reduce LWE m n,q,α to G-EDCP ℓ n,q,r , where r ≈ 1/α up to a factor of poly(n log q). Analogous to Regev's reductions from uSVP to DCP, we present two versions of the reduction from LWE to G-EDCP. The second one is tighter with respect to the parameter losses. At the end of the section we show that using the same algorithm, one can reduce the decisional version of LWE to the decisional version of EDCP (see Def. 5).

First reduction: using cube separation
The main result of this section is the following theorem.
Theorem 2 (LWE ≤ EDCP). Let (n, q, α) be LWE parameters and (n, q, r) be EDCP parameters. Given m = n log q = Ω(κ) many LWE n,q,α samples, there exists a probabilistic quantum reduction, with run-time polynomial in κ, from LWE m n,q,α to G-EDCP ℓ n,q,r , where r < 1/(32mκαℓq n/m ). The main step of our reduction is to partition the ambient space R m with an appropriately chosen grid (cubes). This is analogous to Regev's reduction from uSVP to DCP [24]. Lemma 12 shows how we choose the width of the cell in our grid. Figure 2 gives a 2-dimensional example of such a grid.
Proof. • Proof for the first claim. Write u = Ax + e 1 mod q and v = Ax + e 2 mod q for some x ∈ Z n q and e 1 ∞ , e 2 ∞ ≤ λ ∞ 1 (Λ q (A))/(2ck). Fig. 5: Quantum circuit for our reduction LWE ≤ EDCP. All the global phases are omitted. The input registers are assumed to have the required number of qubits. Function f is defined as U f |j |s |0 → |j |s |As − jb mod q . Function U g is the embedding of function g described in Lemma 12, i.e. U g |x |0 → |x |⌊x/z − w modq⌋ for appropriately chosen z, w,q.
We use Lemma 4 to obtain a state within ℓ 2 distance of 2 −Ω(κ) away from s∈Z n q j∈Z ρ r (j) |j |s |0 .
We evaluate the function f (j, s) → As − j · b mod q and store the result in the third register. The next equality follows from a change of variable on s ρ r (j) |j |s + js 0 |As − je 0 .
For x ∈ Z m q , we define whereq = q/z = c. We evaluate the function g on the third register and store the result on a new register. We obtain ρ r (j) |j |s + j · s 0 |As − j · e 0 |g(As − j · e 0 ) .
Finally, we evaluate the function (j, s, b) → b − As + j · b 0 on the first three registers, which gives 0. Discarding this 0-register, the state is of the form According to Lemma 1, the above state is within ℓ 2 distance of 2 −Ω(κ) away from j∈Z ρ r (j) |j |s + j · s 0 .
We repeat the above procedure ℓ times, and with probability (1 − 1 k ) mℓ , we obtain ℓ many G-EDCP ℓ n,q,r states   where x k ∈ Z n q . Now we can call the G-EDCP ℓ n,q,r oracle with the above states as input and obtain s 0 as output of the oracle.

An improved reduction: using balls' intersection
Here we give an improved reduction from LWE to EDCP. Following the idea of Regev ([24][Section 3.3]), instead of separating the ambient space Z m by cubes, we consider intersections of balls drawn around the points As and its shifts. Note that with this reduction we improve the upper-bound on r essentially by the factor of √ m.
We give an intuitive idea of how the reduction works. All the necessary lemmata and the full proof are given in Appendix B.
Informally, the reduction works as follows. Given an LWE instance (A, b = As 0 + e 0 ) ∈ Z m×n q × Z m q , for each s ∈ Z n q , we consider (in a superposition over all such s) a lattice point As together with its small shifts of As − je 0 , where j's are drawn from a small interval symmetric around 0. So far this is exactly what we did in the first (weaker) reduction. Note that we receive a configuration of points in Z m q as depicted in Figure 3. Note that contrary to Regev's reduction, where there is only one shift (i.e., the DCP case), our extrapolated version considers poly(κ) shifts thus leading us to the EDCP case.
Let us fix some As together with its shifts. Draw a ball around each shift of a maximal radius R such that there is no intersection between the shifts coming from different lattice points, i.e. there is no j, j ′ s.t. B(As − je 0 , R) ∩ B(As ′ − j ′ e 0 , R) = ∅ for any two s, s ′ such that s = s ′ . To satisfy this condition, we can take R almost as large as the first minimum of the lattice Λ q (A) (again, see Figure 3). With such an R, due to the fact that the shifts are small, the intersection of the balls drawn around the shifts is large enough (see Lemma 13 in Appendix B). Hence, once we measure the register that 'stores' our balls, the resulting state collapses (with large enough probability) to a superposition of some As for one s and all its shifts. Informally, the higher this probability is, the tighter the parameters achieved by the reduction.

Reduction from dLWE to dEDCP
As a corollary to the above theorem, we show that the decisional LWE can be reduced to decisional EDCP. In fact, to establish the reduction, we use the same algorithm as for Theorem 3 (a weaker reduction given in Theorem 2 will work as well). Recall that in the proof, starting from an EDCP sample, we obtain an LWE sample with non-negligible probability. Corollary 1 below shows that in case we are given a tuple (A, b) drawn uniformly at random from Z m×n q × Z m q , the procedure described in Theorem 3 outputs a state of the form |j |x mod N , a uniform counterpart to EDCP in the sense of Definition 5. The proof of the following corollary is given in Appendix B.

Reduction from EDCP to LWE
In this section, we reduce G-EDCP ℓ n,N,r to LWE ℓ n,N,α , where r ≈ 1/α up to a factor of poly(n log N ). Combined with the result of the previous section, this gives us equivalence between the two problems: LWE and EDCP, for both search and decisional variants. .
Our aim is to find s 0 given access to an LWE ℓ n,N,α oracle. For each input state, the quantum Fourier transform over Z n N is applied to the second register, which yields (without loss of generality, consider the k th sample) Then we measure the second register and let a k denote the observed value. Note that each element of Z n N is measured with probability 1/N n and that the distributions for different k's are independent. Omitting the global phase of each state, we obtain j∈Z ω j· s0,a k N · ρ r (j) |j |a k .
We omit the second register as we know each a k classically. Since N ≫ r, from Lemma 1 it follows that the resulting state is within ℓ 2 distance of 2 −Ω(κ) away from the state j∈ZN ω j· a k ,s0 N · ρ r (j) |j .
For each such an input state, the quantum Fourier transform over Z N yields b∈ZN j∈ZN ω j·( a k ,s0 +b) N · ρ r (j) |b .
Once again we use Lemma 1 to argue that the state above is within ℓ 2 distance of 2 −Ω(κ) away from the state b∈ZN j∈Z ω j·( a k ,s0 +b) N · ρ r (j) |b .
Using the Poisson summation formula (Lemma 3) and changing the summation variable to e ← N · j + a k , s 0 + b, the above state can be rewritten as b∈ZN j∈Z where a ′ k = −a k mod N . Since r = Ω( √ κ), we can apply Lemma 1 to the above state (for a scaled Z-lattice), and instead of the above state, consider the state that is within a 2 −Ω(κ) ℓ 2 -distance from it, namely: Once we measure the state above, we obtain an LWE sample where e k ←֓ D Z,N/r . Now we can call the LWE n,N,α oracle for α = 1/r with the above states as input and obtain s 0 as output of the oracle.

Reduction from dEDCP to dLWE
Similar to the previous section where as a corollary we show that dLWE can be reduced to dEDCP, we finish this section by a reverse reduction. Again we use exactly the same reduction algorithm as for the search versions (see Figure 6). Thus it remains to show that we can obtain a uniform random sample (a, b) ∈ Z n N × Z N given as input a state of the form |j |x mod N . Corollary 2 (dEDCP ≤ dLWE). Let (n, N, r) be valid dG-EDCP parameters and (n, N, α) be valid dLWE parameters. Given ℓ = Ω(κ) many EDCP n,N,r samples, there exists a quantum reduction, with run-time polynomial in κ, from dG-EDCP ℓ n,N,r to dLWE ℓ n,N,α , where α = 1/r. Proof. Assume we are given ℓ many samples of EDCP n,N,r either of the form or of the form where j k ←֓ D 2 Z,r and x k ∈ Z n N is uniform. Our aim is to distinguish between the above two forms given access to a dLWE n,N,α oracle.
As explained above, we assume that random samples of EDCP are given. For each input state, after the quantum Fourier transform over Z n N on the second register, we obtain Then we measure the second register and let a k denote the observed value. Note that each element of Z n N is measured with probability 1/N n and that the distributions for different k's are independent. Up to a global phase, we have |j k |a k .
We omit the second register which is known to us. According to Lemma 1, with probability 1 − 2 −Ω(κ) , the value stored in the first register is in the range [−⌊N/2⌋, ⌈N/2⌉ − 1]. Applying QFT over Z N to the first register, we obtain b∈ZN ω j k ·b N |b .
Once we measure the state above and let b k denote the observed value. Note that each element of Z N is measured with probability 1/N and that the distributions for different k's are independent. We obtain a sample where (a k , b k ) are uniformly random from Z n N × Z N .
The same arguments apply to the uniform EDCP: from U-EDCP N,ℓ,r1 to U-EDCP N,O(ℓ/κ c+1 ),r2 In this case, via quantum rejection sampling, we transform a wide uniform distribution into a narrow uniform distribution.

B.1 Proof of Theorem 3
We need two lemmata to establish a proof of Theorem 3. The first lemma due to Regev (see [24,Corollary 3.9]) shows how large the intersection of two shifted balls is. Note that a quantum state we work with is a discretized ball 1 L Z n ∩ B n (0, R). The difference between Regev's lemma and the one we present below is that we consider intersections of the balls taken mod q.
Lemma 13 (Adapted from [24,Corollary 3.9]). Let L = 2 n and consider the scaled integer grid 1 L Z n . For any R ≥ 1, letB n (0, R) = B n (0, R) +d for some vectord such that R/poly(n) ≤ d ≤ R. Then, for an integer q > 2R +d we have The following technical lemma is again due to Regev [24]. It shows that while we cannot create a quantum state that perfectly corresponds to a uniform superposition of x ∈ 1 L Z n ∩ B n (0, R) (i.e., a ball), we can have a good approximation to this state. This fact will only increase the running time of the reduction by a factor of poly(κ).
Lemma 14 ([24, Lemma 3.11]). For any 1 ≤ R ≤ 2 poly(n) , let |x be the uniform superposition on grid points inside a ball of radius R around the origin where L = 2 n . Then, for any c > 0, a state |η whose trace distance from |η is at most 1/n c can be efficiently computed.
Now we are ready to give the proof of Theorem 3.
Proof (of Theorem 3). Assume we are given an LWE n,q,α instance (A, b 0 ) ∈ Z m×n q × Z m q , with b 0 = As 0 + e 0 mod q. Our aim is to find s 0 given access to a G-EDCP ℓ n,q,r oracle.
We first prepare a necessary number of registers in the state |0 and transform it to the state of the form (normalization omitted) s∈Z n q |0 |s |0 .
We use Lemma 4 to obtain a state within ℓ 2 distance of 2 −Ω(κ) away from s∈Z n q j∈Z ρ r (j) |j |s |0 .
We evaluate the function f (j, s) → As − j · b mod q and store the result in the third register. A change of variable on s yields ρ r (j) |j |s + js 0 |As − je 0 .
We take an auxiliary register |0 . We set L = 2 m as a discretization parameter and R = Θ( √ mq (m−n)/m ). As the LWE problem is well defined with m = Θ(n) many samples, it suffices to satisfy √ mq (m−n)/m /(3 √ 2πe) ≤ q. Thus according to Lemma 6, we also have R ≤ λ 1 (Λ q (A))/3, where the inequality holds with probability 2 −m = 2 −Ω(κ) for some appropriate choice of constants. Using Lemma 14, we prepare a state which is at most 1/n c away from |η = x∈ 1 L Z m ∩Bm(0,R) |x for any constant c > 0. We set c such that it satisfies (1 − 1/n c ) > (1 − 1/κ) to have the success probability claimed at the end of the reduction. We pretend we work with the state |η , which we tensor with our current state, and obtain ρ r (j) |j |s + j · s 0 |A · s − j · e 0 |x .
We apply the function g(x, y) = (x, x + y mod q) on the third and fourth registers (note that the mod q operation is done over rational numbers). The state becomes a superposition over the balls of radius R centered at all lattice points As and their shifts defined by j. Formally, we obtain ρ r (j) |j |s + j · s 0 |As − j · e 0 |As − j · e 0 + x mod q .
Note that due to the minimal distance of Λ q (A), the balls emerging from two different lattice points (or their shifts) do no intersect. Hence, the measurement yields ρ r (j) |j |s + j · s 0 |As − j · e 0 for some s ∈ Z n q , with probability O(1 − 1/ℓ) taken over the uniform distribution defined on B m (0, R).
Finally, we evaluate the function (j, s, b) → b − As + j · b 0 on the first three registers. Discarding the last register, the state is of the form ρ r (j) |j |s + j · s 0 .
We repeat the above procedure ℓ times, and with non-negligible probability (1 − 1/ℓ) ℓ , we obtain ℓ many G-EDCP n,q,r states    j∈Z ρ r (j) |j |x k + j · s 0    k≤ℓ , where x k ∈ Z n q . Now we can call the G-EDCP m n,q,r oracle with the above states as input and obtain s 0 as the output of the oracle.
Proof (of Corollary 1). We are given m many samples from Z m×n q × Z m q either of the form (A, As 0 + e 0 ), or of the form (A, b), where A ∈ Z m×n q is uniformly chosen, s 0 ∈ Z n q is fixed, e 0 ∈ D Z m ,αq and b ∈ Z m q is uniformly chosen and independent from a. Our aim is to distinguish between the above two cases given access to a dG-EDCP ℓ n,q,r oracle. We follow the procedure of the reduction algorithm used in the proof of Theorem 3 except that now we set R = Θ( √ mq (m−n−1)/m ). As the LWE problem is well defined with m = Θ(n) many samples, we can guarantee (for an appropriate choice of constants) that √ mq (m−n)/m /(3 √ 2πe) ≤ q. Thus, we also have R ≤ λ 1 (Λ q (A|b))/3, where the inequality holds with probability 2 −m = 2 −Ω(κ) (see Lemma 6). We run the algorithm described in the proof of Theorem 3 until we obtain a state of the form ρ r (j) |j |s |As − j · b |As − j · b + x .
We measure the fourth register and ignore it from now on. Due to the bound on r, we have q ≥ 2 √ κr. Thus all the balls created with centers over the lattice points As and their shifts As − jb, do not intersect with each other. Therefore, with probability 1 − O(1/ℓ) we obtain |j k |s k |As k − j k · b for some j k ∈ Z is distributed as D 2 Z,r and some uniform s k ∈ Z n q . Finally, we evaluate the function (j, s, b) → b − As + j · b 0 on the first three registers. This zeroizes the last register, which we can safely discard. Now the state is of the form |j k |s k , where j k ←֓ D 2 Z,r and s k ∈ Z n q is uniformly chosen. We repeat the above procedure ℓ times, and with probability (1 − O(1/ℓ)) ℓ , we obtain ℓ many random samples of the form where s k is chosen uniformly at random from Z n q . This is exactly an input to dEDCP with respect to of Definition 5.


Development of Electronic Control Circuits for WSN: Towards a Livestock Tracking and Identification System

Corresponding Author: Oduetse Matsebe Department of Mechanical, Energy and Industrial Engineering, Faculty of Engineering and Technology, Botswana International University of Science and Technology, Private Bag BO 016, Palapye, Botswana Email: matsebeo@biust.ac.bw Abstract: Botswana’s beef sector contributes 0.3% of the total world beef exports, i.e. US$ 42.4 billion as of the year 2013 and her major market is the European Union (EU). Unfortunately, her failure to comply with the frequently changing European Commission (EC) export regulations on livestock tracking and identification means that beef export to this market is sometimes suspended. Research trends indicate that smart agriculture solutions have gained popularity in agricultural production and can help keep up with the frequently changing EC export regulations especially on active tracking and identification of livestock. It is against this background that this paper presents the development of electronic control circuits for Wireless Sensor Network (WSN) and Group Special Messaging (GSM) to be utilized in a livestock tracking and identification system. It is envisaged that the proposed solution would help fulfill potential changes of EC regulations. Proteus 8 software is used to develop the circuit models. The controller used for this work is Arduino microcontroller. Simulation results show that the XBee shields are able to communicate successfully. This communication forms the basis for the WSN. The results indicate that the developed electronic control circuits for the WSN are viable. Future work will focus on the development of a prototype that will be tested and validated in real environment.

Introduction
A study conducted by the International Trade Centre (ITC) on the review of the beef sector value chain, strategy and intervention for the Private Sector Development Program (PSDP) indicates that Botswana beef sector contributes 0.3% of the total world beef exports, i.e. US$ 42.4 billion as of the year 2013. Her failure to comply with the frequently changing European Commission (EC) export regulations on livestock tracking and identification has sometimes led to the loss of major markets in the EU (Boy, 2013.). The study by ITC recommended the adoption of electronic ear tag system, Spongi form Encephalopathy (BSE) or Mad Cow disease and encouraged the use of technology to improve the out break in 1997 (Jin et al., 2006). The EU market issued regulation beef sector.
Traditionally, Batswana have and still use ear cuttings and branding to identify their livestock (Ndubo et al., 2012). They rely on word of mouth for tracking, ear cuttings descriptions, thigh brandings and livestock coat colour for identification purposes in Fig. 1 and Fig. 2.
These methods provide visible identification of livestock, they are cheap and easy to administer. Unfortunately, the methods do not provide tracking capability and history. They are easily tempered with and result in ambiguous ownership since they normally represent family identification. These methods were acceptable by the EC export regulations until the Bovine Spongiform Encephalopathy (BSE) or Mad Cow disease outbreak in 1997 (Jin et al., 2006). The EU market issued regulation EC820/97 which required member states to have a computerized identification and tracking system for beef going to the EU market (Ndubo et al., 2012). As a result the Botswana Meat Commission (BMC) temporarily closed exports to EU while the Ministry of Agriculture (MoA) devised a system that would comply with the new regulations. The Department of Veterinary Services (DVS) under MoA responded to regulation EC820/97 with the introduction of Livestock Identification and Traceback System (LITS) program using reticular bolus Fig. 3 encasing a passive RFID chip for identification and trace back. The embedded RFID chip stores owner's details, animal's coat colour, sex, age, owner's brand number and location of the closest extension office to the cattle post (Barner Rasmussen et al., 2013). Some of the advantages of reticular bolus include; reduction in stock theft, unique animal identification, ability to trace back animal movements. It also stores the owner's and animal's details in an electronic database for historic purposes. The bolus system proved to be a challenge for the DVS, which is responsible for administering and educating farmers on the LITS program. The program was faced with challenges such as high administration costs for insertion and monitoring of boluses, lack of enough trained personnel to administer the boluses and it is a complex process farmers could not be taught in a short time, repeat insertions were also common because of lack of visibility, loss of tags by livestock, shortage of bolus tags limited the speed of program roll out to farmers hence failure to fulfil the EC export regulations.
In 2000, the EC released an updated regulation EC 1760/00 which forced an upgrade to the program to meet the new regulations. Some of the requirements of the new regulations were: • Bovine animals must be registered and individually identified with ear tags on each ear • Individual passport of transport are required to accompany any bovine movements • Computerized cattle tracing database in an attempt to meet these requirements The DVS upgraded the LITS program from ingestible bolus to electronic RFID ear tags (Ndubo et al., 2012). The electronic ear tags in Fig. 4 and Fig. 5 are visible and easy to administer. The DVS managed to educate farmers on installation of these ear tags and eliminated dependency on DVS officials hence significantly reducing administration costs. The ministry was only responsible for stocking the ear tags and logging the numbers of sold tags in a centralized database. However, sold ear-tags do not necessarily mean they have been used to tag livestock and the DVS still relied on farmer to record the details and report them back for updating. This resulted in errors as some farmers tend to loose the records. Some of the advantages of the RFID ear tags include; visible and unique identification, ability to trace back livestock, stores owner's details, information is stored in a centralized database for historic purposes, easy to remove tags from dead animals, it is user friendly and the tags are reasonably cheap. However, the RFID ear tags do not safe guard against stock theft, tags can be easily cut off, it does not provide constant monitoring of animal's movements; assumes livestock is within range of its zone, it can get lost if the animal gets caught in a fight or by tree brunches. The system only provides a trace back of livestock with gaps between readings or scannings, i.e. during vaccination periods, when they are transported across Foot and Mouth Disease (FMD) zones and during transportation to the BMC for sale.  (Omondi, 2015) Therefore, this system led to an inaccurate history of livestock movement over their lifespan. It is against this background that this research work proposes a solution that incorporates the current LITS features, and also enables real time tracking and identification of livestock using WSN, and the existing GSM network. The system uses a hybrid power module (solar and battery) for prolonged operation. However, the system will require access to the GSM network and an improved functionality that will help keep up with the frequently changing EC export regulations. The rest of the paper is structured as follows; section 2 reviews related works, section 3 outlines the methods and techniques, section 4 presents the results and discussions, sections 5 and 6 respectively presents the conclusion and future work.

Literature Review
A localization and monitoring system based on ZigBee protocol for cattle is presented in . In this work, Link Quality Indicator (LQI) accompanied with a modified Ratio metric vector Iterations (RVI) routing algorithm for ranging is used. The authors use estimation and localization algorithms instead of a Global Positioning Satellite (GPS) which is a more precise localization method but expensive for livestock applications. A link of static anchors and mobile sensors attached to cattle ear tags encased in plastic casing and powered by cylindrical lithium ion battery are used. The anchor nodes are solar powered. Using Jennic JN5139 modules at 2.4Ghz, the research work manages to get distances of about 200m in the lab, about 220m in the field. The nodes can be detected from a height of 20cm to 2m above ground. Localization is achieved with an error of about 20m using low cost hardware overhead. A system to remotely monitor the health of cattle using sensor network and Bluetooth as gateway or base station for telemetry is described in (Choi, 2013). The research work was motivated by restrictions and lack of an early warning system for mad cow disease in Canada. The system uses variable sensors to capture vital signs and to identify a threat to an outbreak. GPS is used for localization and trace back. The mobile sensors attached on the cow's ears contains a probe for temperature, pulse-oximeter, electronic belt, and respiration transducer for oxygen level, reticular bolus for core body temperature and Bluetooth transceiver for data transfer when the animal is in range of watering or feeding point. The data is then transferred to a workstation for computation and diagnosis. Unfortunately, the system could not be tested in the field but future modification included a short range telemetry link.
A system to monitor vital signs; temperature, heart rate, respiration and a tracking unit for cattle is presented in (Kwong et al., 2012). The system employs solar powered ear tags attached to cattle and rechargeable batteries for prolonged life span of the WSN. A combination of static nodes and mobile nodes using triangulation through RSSI localization and estimation are used. A low power WSN with a graphical user interface is developed in a MATLAB environment. This provides positioning information through triangulation within a fenced area. A ZigBee-based protocol is used. The authors propose the use of RFIDs and other sensors to improve the applicability of the system depending on farmer's requests. The conclusion made here is that a wireless system is viable for cattle monitoring and state of health research as well as natural patterns or cattle behaviour.
Barner Rasmussen et al. (2013), researchers adapted a WSN application for dairy farming in an enclosed area. The system developed is low cost, has a low power consumption sensor node and enables real time communication using channel bandwidth and radio frequency. Belts wrapped around the targeted animal's neck with two antennas on sides are used, utilizing MICA and MICAz nodes powered by AA batteries. Various frequencies from 315 MHz to 2.4GHz were considered, and a penetration depth of those frequencies. The main challenge reported is adapting wireless sensor networks to support nodes mobility caused by animal movements. A cluster based routing protocol and architecture for tracking livestock with focus on scalability, mobility and energy efficiency is developed in (Lin et al., 2004). The research work indicates that large herds of livestock and vast pastureland livestock herding are a major limitation in open ranges, the application of WSN is also limited by scalability and energy efficiency (Ficek et al., 2013); hence the authors use a clustering algorithm for the architecture while nodes are subdivided by the introduction of mobile sinks through GSM network. Existing cluster based routing protocols; LEACH-Mobile Enhanced and Mobile Sink based Routing Protocol (MSRP) based on the remoteness mobility metric are employed.

Methodology
Proteus 8 software is used to model and simulate the electronic control circuits for the WSN. The major advantage of using Proteus 8 is that it has the ability to render third party libraries such as those of Arduino Microcontrllers, GPS receiver, XBee shield and SIM900 a GSM shiled. The controller used for this work is the Arduino MCU since it is a programmable off-shelf component and it can be uploaded with Arduino emulator code that will run on the physical microcontroller without modifications.

Mobile Node to Mobile Node Radio Transmission Model
The model in Fig. 6 shows the radio connection between two XBee shields, these represent the mobile nodes in a mesh WSN. The XBee modules are connected to Arduino MCU, virtual monitors display the shared packets during transmission. Figure 7 shows a virtual GPS receiver connected to a virtual Arduino Uno MCU, and a virtual terminal monitor. This represents the reception of GPS coordinates which are displayed on the terminal monitor. This scenario arises when a static node is connected to the network. Figure 8 depicts the mobile node to static node connection. The mobile node consists of the Arduino pro mini and XBee shield while the static node is made up of XBee shield, GPS receiver, Sim900D Shield, Arduino MCU and a monitor. This represents a connection between an ear-tag and static node. The packets being shared are displayed on the monitor.  Figure 9 shows the connections between static node and mobile node. Packets received from the mobile node are sent to the base station or gateway for storage in the database. This represents the connection between WSN and GSM networks.

Results
This section presents the simulation results for the different circuit models.  Figure 11 shows the GPS coordinates received.

Static Node to Base Station Connection
Data packets shared between the components is displayed in Fig. 12.

Discussion
The wireless shields (Fig. 10) create a Personal Area Network between them by exchanging data. This communication indicates a building block for the mesh WSN architecture. The GPS coordinates received (Fig. 11) are stored for further processing. These are fixed locations of the static nodes and are used to triangulate distance from the mobile nodes.
The static node (Fig. 12) computes distance information from radio signals obtained through the XBee shield. This information is then sent to the GSM terminal through the shared Arduino memory. The identifier variables; owner and livestock information shown in Fig. 13 are shared with XBEE TERM_2 connected to the static node. The MCU then computes the livestock (x, y) positions from range data. The information is then appended to the data packet and passed to GSM_TERM.

Conclusion
This paper presents the development of electronic control circuits for the WSN that will be utilised in a livestock tracking and identification system. Proteus 8 software is used to model and simulate the mobile node to mobile node radio transmission, GPS receiver connection, mobile to static node radio connection and static node to GSM connection. Simulation results show that the XBee shields are able to communicate successfully; this communication forms the basis for the WSN. GPS coordinates are received and stored for further processing. The static sensor nodes are able to compute distance information from the radio signals and the information is then passed to the GSM terminal. Identifier variables for owner and livestock are generated. Livestock(x, y) positions are also computed from range data received. These results indicate that the developed electronic control circuits for the WSN are viable. The complete system would improve livestock tracking and identification and hence keep up with the frequently changing EC export regulations.

Further Study
Future work will focus on the development of a prototype that will be tested and validated in real environment.

Acknowledgement
We express our appreciation to Dr. M.A Zungeru for his advice and to the Botswana International University of Science and Technology's for funding this research work.

Author's Contributions
Mr Obakeng Maphane: Participated in the conceptualisation of the research, collection of data, modelling and simulation, analysis and interpretaion of the results, drafting and reviewing of the manuscript. He approves this version of the document to be submitted.
Dr. Oduetse Matsebe: Is the supervisor and coordinator of the research. He participated in the conceptualisation, coordination and designing of the research, contributed to the the analysis and interpretation of results. He also drafted and reviewed the manuscript. He approves this version of the manuscript to be submitted.
Dr. Molaletsa Namoshe: Is the co-supervisor of the research. He participated in the conceptualisation and designing of the research, contributed to the the analysis and interpretation of results. He also reviewed the manuscript. He approves this version of the manuscript to be submitted.

Ethics
The are no ethical issues.