# Ring-LWE Search $\leq$ Decision for Cyclotomic Number Fields

[Vadim Lyubashevsky, Chris Peikert, and Oded Regev 2012/2013](https://eprint.iacr.org/2012/230.pdf)

## Search $\leq$ Decision for vanilla LWE

Before doing the search-to-decision reduction for Ring-LWE, it's useful to do the search-to-decision reduction for plain LWE. Let $\mathbf{s} \in (\mathbb{Z}/q\mathbb{Z})^m$ be a secret chosen uniformly at random. In LWE, one is given multiple samples of the form $\Gamma_i := (\mathbf{a}_i, \langle\mathbf{a}_i,\mathbf{s}\rangle + e_i)$ where $\mathbf{a}_i \in (\mathbb{Z}/q\mathbb{Z})^m$ is drawn uniformly at random, and $e_i \in  \mathbb{Z}/q\mathbb{Z}$ is drawn from some discrete univariate distribution $\chi$ over a subset of "small" elements in $\mathbb{Z}/q\mathbb{Z}$. Also consider another set of similar looking samples $\Theta_i := (\mathbf{u}_i, v_i)$, where $\mathbf{u}_i \in (\mathbb{Z}/q\mathbb{Z})^m$ and $v_i \in \mathbb{Z}/q\mathbb{Z}$ are chosen uniformly at random 

The **decisional-LWE** problem asks to distinguish $\left \{\Gamma_1, \Gamma_2, \cdots, \Gamma_n \right \}$ from $\left \{\Theta_1, \Theta_2, \cdots, \Theta_{n'} \right \}$ with non-negligible probability.

The **search-LWE** problem asks to find $\mathbf{s}$ with high probability, given $\left \{\Gamma_1, \Gamma_2, \cdots, \Gamma_n \right \}$.

### Setup

The setup for search to decision reduction is as follows: An oracle $\mathcal{D}$ that can distinguish between $\left \{ \Gamma_i \right \}$ and $\left \{\Theta_i \right \}$ is given. Input to $\mathcal{D}$ are numbers of the form $(\mathbf{a}, x) \in (\mathbb{Z}/q\mathbb{Z}^m, \mathbb{Z}/q\mathbb{Z})$ where $\mathbf{a}$ is guaranteed to be uniformly random and


<ol  style="list-style-type: lower-alpha">
  <li> $\mathcal{D}$ outputs $1$ if $x = \langle \mathbf{a}, \mathbf{s}\rangle + e$ for some $\mathbf{s}$ and $e \leftarrow \chi$, otherwise</li>
  <li>$\mathcal{D}$ outputs $0$ if $x$ is uniformly distributed</li>
</ol>

For **any other distribution** of $\mathbf{a}$ or $x$, the oracle $\mathcal{D}$ makes no promises about its output---not even the promise that $\mathcal{D}$ will terminate (i.e., not get in an infinite loop)! For any reduction that uses $\mathcal{D}$ as a subroutine, the caller must prove that inputs to $\mathcal{D}$ are either of the type (a) or (b). Otherwise, the reduction will be invalid.

To solve the search-LWE problem, we need to come up with an algorithm $\mathcal{A}$ that _somehow_ uses $\mathcal{D}$ to find the secret $\mathbf{s}$. Input to the search algorithm $\mathcal{A}$ is guaranteed to be a list of valid LWE samples $\Gamma_i$ computed from the same secret $\mathbf{s}$, and $\mathcal{A}$ is expected to return $\mathbf{s}$ as its output.

**Digression**: You might object that in the definition of both search and decisional LWE, $\mathbf{s}$ was assumed to be chosen uniformly at random, but in setup above no such assumption was made. It turns out, Decisional-LWE is random-self-reducible (RSR)! That is, if there's an oracle $\mathcal{D}$ that can distinguish $\{\Gamma_i\}$ from $\{\Theta_i\}$ on an average (i.e., $\mathbf{s}$ chosen uniformly at random), then there's an algorithm $\mathcal{D}'$, that can distinguish $\{\Gamma_i^{\mathsf{WC}}\}$ from $\{\Theta_i\}$, where $\Gamma_i^{\mathsf{WC}}$ are worst-case LWE samples generated from $\mathbf{s}^{\mathsf{WC}}$. Because of this, no assumption on LWE samples are needed.

#### Proof (Decisional-LWE is Random Self Reducible)
Basically, the algorithm $\mathcal{D}'$ on worst case input $(\mathbf{a}, x)$---where $x$ is either uniformly random or $\langle\mathbf{a}, \mathbf{s}^{\mathsf{WC}} \rangle + e$---generates a random $\mathbf{s} \leftarrow (\mathbb{Z}/q\mathbb{Z})^m$ and creates a new LWE sample  $(\mathbf{a}, x + \langle\mathbf{a}, \mathbf{s}\rangle)$ and feeds it to the average case decision oracle $\mathcal{D}$. It then uses the output of $\mathcal{D}$ as its own ouput. Note that if $x$ was chosen uniformly at random, and assuming $q$ is prime,  $x + \langle\mathbf{a}, \mathbf{s}\rangle$ is also distributed uniformly at random. On the other hand, if $ x = \langle\mathbf{a}, \mathbf{s}^{\mathsf{WC}} \rangle + e$, then 

$$
\begin{aligned}
x + \langle\mathbf{a}, \mathbf{s}\rangle &= \langle\mathbf{a}, \mathbf{s}^{\mathsf{WC}} \rangle + e + \langle\mathbf{a}, \mathbf{s}\rangle \\
 &= \langle\mathbf{a}, \mathbf{s}^{\mathsf{WC}} + \mathbf{s} \rangle + e \\
\end{aligned}
$$

but $\mathbf{s}^{\mathsf{WC}} + \mathbf{s}$ is distributed uniformly at random since $\mathbf{s}$ is (because $q$ is prime). Therefore the input $(\mathbf{a}, x + \langle\mathbf{a}, \mathbf{s}\rangle)$ to the average case oracle $\mathcal{D}$ has the desired distribution in both the cases. (??? Does this reduction work when $q$ is not prime? ???)

Back to search-to-decision reduction.

### The Search to Decision Reduction

Let $\mathbf{s} = \{\psi_1, \psi_2,\cdots,\psi_m\}$, where $\psi_i$s are unknown at the start of the reduction.  Let $\{(\mathbf{a}_i, x_i)\}_{i \in [1,\cdots,n]}$ be the input to search algorithm $\mathcal{A}$. To simplify notation, let $\mathbf{A} := \begin{pmatrix}\mathbf{a}_1\\ \vdots \\ \mathbf{a}_n \end{pmatrix} \in (\mathbb{Z}/q\mathbb{Z})^{n\times m}$, $\mathbf{e} := \begin{pmatrix}e_1\\ \vdots \\ e_n \end{pmatrix} \in (\mathbb{Z}/q\mathbb{Z})^{n}$ and $\mathbf{b} := \begin{pmatrix}{x}_1\\ \vdots \\ x_n \end{pmatrix}$. (In this notation, input to $\mathcal{A}$ is $(\mathbf{A},\mathbf{b})$ satisfying $\mathbf{A}\cdot\mathbf{s} + \mathbf{e} = \mathbf{b}$.)

The basic idea of this reduction is to guess the value of $\psi_i$ for each coordinate one at a time and create a _new set of_ of LWE samples  $(\mathbf{A}', \mathbf{b}')$ from $(\mathbf{A}, \mathbf{b})$ such that 

1. when our guess for $\psi_i$ is correct, $(\mathbf{A}', \mathbf{b}')$ has the same distribution as a normal LWE sample, and 
2. when our guess is incorrect, then $(\mathbf{A}', \mathbf{b}')$ has uniform distribution.

Assuming, we can create such an $\mathbf{A}'$ and $\mathbf{b}'$, then finding $\psi_i$ just requires $O(m)$ calls to the decision oracle $\mathcal{D}$ with $(\mathbf{A}', \mathbf{b}')$ as its input. The algorithm $\mathcal{A}$ can then output those values of $\psi_i$ for which $\mathcal{D}$ has returned 1 (i.e., it's an LWE sample).

Here's how to construct $(\mathbf{A}', \mathbf{b}')$ from $(\mathbf{A}, \mathbf{b})$:  Suppose we are trying to guess the $i$-th coordinate of $\mathbf{s}$. Let's say our guess for the $i$-th coordinate is $\psi_i$. To construct $(\mathbf{A}', \mathbf{b}')$, sample $\mathbf{c}_i := [c_{1i}, c_{2i},\cdots,c_{ni}] \leftarrow (\mathbb{Z}/q\mathbb{Z})^n$ uniformly at random, and construct a matrix $\mathbf{C}_i$ whose $i$-th column is $\mathbf{c}$ and every other column is $\mathbf{0}^n$, i.e.,

$$
\mathbf{C}_i := \begin{pmatrix}0 & \cdots & 0 & c_{1i} & 0 & \cdots & 0 \\  & \ddots &  & \vdots &  & \ddots & \\ 0 & \cdots & 0 & c_{ni} & 0 & \cdots & 0 \end{pmatrix}
$$

and let $\mathbf{A}' = \mathbf{A} + \mathbf{C}_i$ and $\mathbf{b}' = \mathbf{b} + \psi_i\mathbf{c}_i$. Notice that $\mathbf{C}_i\cdot\mathbf{s} = \psi_i\mathbf{c}_i$ because only the $i$-th column of $\mathbf{C}_i$ is nonzero.

**Claim-1**: If the guess for $\psi_i$ is correct, then $(\mathbf{A}', \mathbf{e}')$ is distributed like an LWE sample with the same secret $\mathbf{s}$.

**Proof**: Since $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$, therefore, 

$$
\begin{aligned}
\mathbf{b}' &= \mathbf{A}\mathbf{s} + \mathbf{e} + \psi_i\mathbf{c} & (1)\\
  &= (\mathbf{A}' - \mathbf{C})\mathbf{s} + \mathbf{e} + \psi_i\mathbf{c} & (2) \\
  &= (\mathbf{A}'\mathbf{s} + \mathbf{e}) + (\psi_i\mathbf{c} - \mathbf{C}_i\mathbf{s}) & (3) \\
  &= \mathbf{A}'\mathbf{s} + \mathbf{e} & [\text{because}\, \mathbf{C}_i\mathbf{s} = \psi_i\mathbf{c}_i] (4)
\end{aligned}
$$
Therefore, $(\mathbf{A}', \mathbf{b}')$ is a valid LWE sample and the decision oracle $\mathcal{D}$ should output $1$ for this input.

**Claim-2**: If the guess for $\psi_i$ is incorrect, then $(\mathbf{A}', \mathbf{e}')$ has a uniform distribution.

**Proof**: Since both $\mathbf{A}$ and $\mathbf{c}_i$ are uniformly distributed, $\mathbf{A}'$ is also uniformly distributed. From equation (3) above, $\mathbf{b}' = (\mathbf{A}'\mathbf{s} + \mathbf{e}) + (\psi_i\mathbf{c} - \mathbf{C}_i\mathbf{s})$ and $\psi_i\mathbf{c} - \mathbf{C}_i\mathbf{s}$ is distributed uniformly since $\mathbf{c}_i$ is uniformly distributed. Therefore, $\mathbf{b}'$ is uniformly distributed.

## Implementation

```LWEDecisionalOracle``` implements the decisional oracle and ```LWESearch``` below implements the algorithm above. 


```python
class LWEDecisionalOracle:
    def __init__(self, q, m):
        self._m = m
        self._ring = IntegerModRing(q)
        self._s = random_vector(self._ring, m)
        self._chi = GeneralDiscreteDistribution(range(int(sqrt(q)))) # why not q/4?
        
    def __repr__(self):
        return "secret: {}, m: {}".format(self._s, self._m)
        
    def q(self):
        return self._ring.characteristic()
    
    def m(self):
        return self._m
    
    def secret(self):
        return self._s
        
    def ring(self):
        return self._ring
        
    def lwe_sample(self):
        a = random_vector(self._ring, self._m)
        e = self._ring(self._chi.get_random_element())
        return (a, a*self._s + e)
    
    def uniform_sample(self):
        return (random_vector(self._ring, self._m), random_vector(self._ring, 1)[0])

    def decide(self, a, b):
        return (b - (a * self._s)).lift() < (self.q() // 4)
        
    def decide_matrix(self, A, b):
        count = 0
        for i in range(A.nrows()):
            if self.decide(A[i], b[i]):
                count = count + 1
        return count >= (A.nrows() // 2)
        
    def lwe_sample_matrix(self, n):
        A=Matrix(self.ring(), n, self.m())
        for i in range(n):
            A[i] = random_vector(self.ring(), self.m())
        return (A, A*self._s)
        
class LWESolver:
    def __init__(self, oracle):
        self._oracle = oracle
        self._ring = oracle.ring()
        self._m = oracle.m()
        self._q = oracle.q()
        
    def oracle(self):
        return self._oracle
        
    def search(self, A, b):
        assert A.ncols() == self._m
        
        m = self._m
        secret = vector(self._ring, m) # Initialize secret to zero
        
        # Start guessin the m co-ordinates one at a time
        for i in range(m):
            # First create the transpose of C matrix with m rows, n cols
            # This is easier to program
            found = False
            for ψ in range(self._q):

                is_lwe_count = 0
                
                # Run the decisional oracle 10 times and if
                # more than 5 are true, then the guess of ψ
                # is correct
                for k in range(10): 
                    CiT = Matrix(self._ring, A.ncols(), A.nrows())
                    c = random_vector(self._ring, A.nrows())
                    CiT[i] = c            
                    Ci = CiT.transpose()
                    Aprime = A + Ci
                    Bprim = b + ψ*c
                    
                    if self.oracle().decide_matrix(Aprime, Bprim):
                        is_lwe_count = is_lwe_count + 1
                    if is_lwe_count > 5:
                        break
                if is_lwe_count > 5:
                    secret[i] = ψ
                    found = True
                    break
            if not found:
                raise "Invalid LWE samples"
                
        return secret
                        
        
D=LWEDecisionalOracle(257, 5); 
S=LWESolver(D)
A,b=D.lwe_sample_matrix(10)
print(S.search(A,b))
print(D.secret())

```

    (247, 237, 5, 174, 19)
    (247, 237, 5, 174, 19)


### Ring-LWE Basics

Let $\mathcal{O} := \mathbb{Z}[x]/\langle f(x) \rangle$ be an order (not necessarily maximal) in a number field $K := \mathbb{Q}[x]/\langle f(x) \rangle$ of degree $n$ and let $\mathcal{O}_q := \mathcal{O}/\langle q\rangle = \mathcal{O}/q\mathcal{O}$. Let $s(X)$ be an element in $\mathcal{O}_q$, and let $e(X) \leftarrow \mathcal{O}_q$ be a random element drawn from a distribution $\chi$ over a subset of "small" elements in $\mathcal{O}_q$. (**NOTE**: In the LPR13 paper, the secrete $s$ is chosen from $\mathcal{O}^{\vee}/q\mathcal{O}^{\vee}$ --- the quotient of [co-different](https://kconrad.math.uconn.edu/blurbs/gradnumthy/different.pdf) ideal. However, this only affects $\text{SVP}_\gamma$-to-Ring-LWE quantum reduction, and doesn't impact search-to-decision reduction and will not be covered here.)

In Ring-LWE, one is given samples of the form $\Gamma_i := (a, a\cdot s + e) \in \mathcal{O}_q\times\mathcal{O}_q$, where $a(X)$ is a random element in $\mathcal{O}_q$ and $e(X)$ and $s(X)$ are described as above. In addition, one is also given samples of the form $\Theta_i := (u, v)$, where both $u(X)$ and $v(X)$ are random elements of $\mathcal{O}_q$.

The **decisional Ring-LWE problem** asks one to distinguish $\left \{\Gamma_1, \Gamma_2, \cdots, \Gamma_n \right \}$ from $\left \{\Theta_1, \Theta_2, \cdots, \Theta_{n'} \right \}$ with non-negligible probability.

The **search Ring-LWE** problem asks one to find $s(X)$ with high probability, given $\left \{\Gamma_1, \Gamma_2, \cdots, \Gamma_n \right \}$.

Note that the term $a(X) \times s(X)$ in the Ring-LWE problem is an element of the pricipal ideal $\langle s\rangle = s\mathcal{O}_q$, however, since $e$ is chosen randomly with a distribution different from uniform, $a\cdot s + e$ destroys the ideal structure. The decisional Ring-LWE problem states that it's not possible to computationally distinguish such elements from uniformly random elements in $\mathcal{O}_q$.

The ```RLWEDecisionalOracle``` below generates example RLWE samples. As you can see in the examples below, while the decision oracle always outputs ```True``` for RLWE samples, it may sometimes return ```True``` even for Uniform distribution.


```python
def gen_rlwe_q(m):
    """
    We need q to be prime AND q == 1 (mod m). Given m, this function will generate 
    such a random q. In more practical settings, this function needs to be less brain 
    dead
    """  
    upper_bound = 2*m
    lower_bound = m
    q = 3
    while q % m != 1:
        if q > upper_bound//2:
            upper_bound = 2*upper_bound
    
        if q > lower_bound:
            lower_bound = q
    
        q = random_prime(upper_bound, lbound=lower_bound)
    
    return q


class CyclotomicModQ:
    def __init__(self, degree, q):
        self._degree  = degree
        self._q       = q
        self._K       = CyclotomicField(degree, names='ζ'); 
        self._Ok      = self._K.maximal_order()
        ### Grrrr.... WTF
        self._K.inject_variables(verbose=False)
        
    def number_field(self):
        return self._K
    
    def maximal_order(self):
        return self._Ok
        
    def q(self):
        return self._q
    
    def order(self):
        return self._degree
    
    def random_element(self, clamp=None):
        if clamp is None:
            clamp=self._q
            
        ## WARNING WARNING WARNING: This is **most** likely not uniformly distributed
        e = self._Ok.random_element(clamp)
        return self.mod_q(e)
    
    def mod_q(self, e):
        ex = e.lift()
        result = self._Ok(0)
        coef = ex.coefficients(sparse=False)
        coef.reverse()
        for c in coef:
            result = self._Ok(ζ)*result + self._Ok(c % self._q)
        return result
    
    def from_poly(self, poly):
        result = self._Ok(0)
        coef = poly.coefficients(sparse=False)
        coef.reverse()
        
        for c in coef:
            result = self._Ok(ζ)*result + self._Ok(int(c) % self._q)
            
        return result
    
    def __repr__(self):
        return "Oq={}\nq={}\nm={}".format(self._Ok, self._q, self._degree)
    


class RLWEDecisionalOracle:
    """
    Returns samples for RLWE.
    """
    def __init__(self, k :int, q:int):
        m = 2^k
        self._Rq = CyclotomicModQ(m,q)
        self._s = self._Rq.random_element()
        
    def __repr__(self):
        return "secret: {}, Oq: {}".format(self._s, self._Rq)
        
    def q(self):
        return self._Rq.q()
    
    def m(self):
        return self._Rq.order()
    
    def n(self):
        return self.m() // 2
    
    def k(self):
        return len(self.m().bits()) -1 
    
    def secret(self):
        return self._s
        
    def cyclotomic_mod_q(self):
        return self._Rq
        
    def rlwe_sample(self, clamp=None):
        a = self._Rq.random_element()
        if clamp is None:
            clamp = int(sqrt(self.q()))
        else:
            assert clamp < self.q() // 4
        
        ## Since when is this distribution 
        ## automorphically closed??? This is why 
        ## the reduction gives wrong results
        e = self._Rq.random_element(clamp)
        
        return (a, self._Rq.mod_q(a*self._s + e))
    
    def uniform_sample(self):
        return (self._Rq.random_element(), self._Rq.random_element())

    def decide(self, a, b):
        x = (b - self._Rq.mod_q(a*self._s)).lift()
        count_small = 0
        for c in x.coefficients(sparse=False):
            if int(c) < (self._Rq.q() // 4):
                count_small = count_small + 1
        
        if count_small > (3*self.n() // 4):
            return 1
        else:
            return 0
        
k=3 # 8th-roots of Unity
p=353 # Obtained by running gen_rlwe_q(2^k)

RLWE_oracle = RLWEDecisionalOracle(k,p)

for i in range(10):
    (a,b) = RLWE_oracle.rlwe_sample()
    (u,v) = RLWE_oracle.uniform_sample()
    print("RLWE: {}, Uniform: {}".format(RLWE_oracle.decide(a,b),RLWE_oracle.decide(u,v)))
```

    RLWE: 1, Uniform: 0
    RLWE: 1, Uniform: 0
    RLWE: 1, Uniform: 0
    RLWE: 0, Uniform: 0
    RLWE: 1, Uniform: 0
    RLWE: 1, Uniform: 1
    RLWE: 0, Uniform: 0
    RLWE: 1, Uniform: 0
    RLWE: 1, Uniform: 1
    RLWE: 1, Uniform: 0


### Cyclotomic Number Fields

Let $\zeta_m := e^{2\pi i/m} \in \mathbb{C}$ be the $m$-th root of unity and let $\Phi_m(X) := \prod_{i \in \mathbb{Z}^\times}(X-\zeta_m^i)$ be the $m$-th cyclotomic polynomial. A famous result in field theory states that $\Phi_m(X)$ is irreducible over $\mathbb{Z}[X]$ for all $m > 1$. 

Let $K := \mathbb{Q}(\zeta_m) \cong \mathbb{Q}[X]/\langle \Phi_m(X) \rangle$ be a __cyclotomic number field__ of degree $n = \phi(m)$. It's [well known](http://virtualmath1.stanford.edu/~conrad/154Page/handouts/cycint.pdf) that the ring of integers of $\mathbb{Q}(\zeta_m)$ is monogenic for all $m$, and therefore in our notation $\mathcal{O} := \mathbb{Z}[\zeta_m] \cong \mathbb{Z}[X]/\langle \Phi_m(X) \rangle$ and let $\mathcal{O}_q := \frac{\mathbb{Z}[X]/\langle \Phi_m(X) \rangle}{q(\mathbb{Z}[X]/\langle \Phi_m(X) \rangle)} \cong \frac{(\mathbb{Z}/q\mathbb{Z})[X]}{\langle \Phi_m(X) \rangle}$. For the rest of this document, elements of $\mathcal{O}$ and $\mathcal{O}_q$ will be treated as polynomials in $X$ of degree $n-1$. 

**Example**: If we consider $8$th roots of unity and let $q = 17$ ($q \equiv 1\,\,\text{mod}\, 8$), then $K = \mathbb{Q}(\zeta_8) \cong \mathbb{Q}[X]/\langle X^4 + 1 \rangle$, $\mathcal{O} = \mathbb{Z}/{\langle X^4 + 1 \rangle}$, $\mathcal{O}_q = \frac{(\mathbb{Z}/17\mathbb{Z})[X]}{\langle X^4 + 1 \rangle}$, and an element $r \in \mathcal{O}_q$ will be represented as a  polynomial $r(X) := a + bX + cX^2 + dX^3$, where $a,b,c,d \in (\mathbb{Z}/17\mathbb{Z})$. Similarily, elements of $\mathcal{O}$ are represented as polynomials in $\mathbb{Z}/{\langle X^4 + 1 \rangle}$.

#### Chinese Remainder Representation

Since by choice, $q \equiv 1\,\, (\text{mod}\,\,m)$, $\Phi(X)$ is no longer irreducible and completely splits over $(\mathbf{Z}/q\mathbf{Z})[X]$.  In this case, if $u$ is a _primitive root of unity_  in $(\mathbf{Z}/q\mathbf{Z})^\times$ then

$$
\begin{equation}
\Phi(X) = \prod_{i\in (\mathbf{Z}/m\mathbf{Z})^\times} (X-u^i) \in (\mathbf{Z}/q\mathbf{Z})[X]
\end{equation}
$$


Note that $i$ in the expression above ranges over those integers that are coprime to $m$. Let $n=\phi(m)$ and $e_1,e_2,\cdots,e_n$ be the $\phi(m)$ integers that are co-prime to $m$. Then the ideal generated by $\Phi(X)$ can be written as a product of ideals generated by its linear factors

$$
\begin{aligned}
\langle\Phi(X)\rangle &= \prod_{i \in \{e_1,\cdots,e_n\}}\langle x-u^{e_i}\rangle\,\,\text{and}\\
\langle\Phi(X)\rangle &= \langle x-u^{e_i} \rangle + \langle x-u^{e_j} \rangle, \forall e_i \neq e_j
\end{aligned}
$$

Therefore, by chinese remainder theorem, 

$$
\frac{(\mathbb{Z}/q\mathbb{Z})[X]}{\langle \Phi_m(X) \rangle} \cong \frac{(\mathbb{Z}/q\mathbb{Z})[X]}{\langle X - u^{e_1}\rangle} \times \cdots \times \frac{(\mathbb{Z}/q\mathbb{Z})[X]}{\langle X - u^{e_n}\rangle}
$$

Let $r(X)$ be the polynomial representation of an element in $\mathcal{O}_q$. Then computing $r(X)\,\, \text{mod}\, \langle X - u^{e_i} \rangle$ is equivalent to substituting all occurances of $X$ with $u^{e_i}$, i.e.,  $r(X)\,\, \text{mod}\, \langle X - u^{e_i} \rangle = r(u^{e_i})$. Therefore, the CRT representation of the elements of $\mathcal{O}_q$ corresponds to lifting $r(X)$ as a _polynomial function_ in $(\mathbf{Z}/q\mathbf{Z})[X]$ and evaluating it $u^{e_i}$. 

Let the CRT representation of $r(X)$ be denoted by $\mathbf{\hat{r}} := [\hat{r}_1, \hat{r}_2,\cdots,\hat{r}_n]$. Given $\mathbf{\hat{r}}$, it's easy to compute the coefficients in polynomial representation. Suppose $c_1, c_2,\cdots, c_n$ are the polynomial coefficients for  $r(X)$, whose CRT representation $\hat{r}$ is given, and we want to find out $c_i$s. Then in matrix notation:

$$
\begin{pmatrix}1  &   u_1  &  u_1^2 	&  \cdots  &  u_1^{n-1} \\ 1 &   \cdots  & \cdots    & \ddots & \cdots   \\ 1 & u_n & u_n^2 & \cdots & u_n^{n-1}
\end{pmatrix}\begin{pmatrix}c_0 \\ \vdots \\ c_{n-1}\end{pmatrix} = \begin{pmatrix}\hat{r}_1 \\ \vdots \\ \hat{r}_n\end{pmatrix}
$$

where $u_i = u^{e_i}$. Therefore, $c_i$s can be computed by inverting the matrix. (This matrix is non-singular. Why?) In the python class ```CRTRepresentation``` below, going from polynomial to CRT representation is implemented by ```split``` and going back is implemented by ```combine```.

As a side note, all this may seem like a long winded way of doing polynomial interpolation, however, polynomials in $\frac{(\mathbb{Z}/q\mathbb{Z})[X]}{\langle \Phi_m(X) \rangle}$ are abstract elements and not entirely equivalent to polynomial functions, so this machinary is absolutely essential!

A great advantage of CRT representation over coefficient representation is that both addition and multiplication operation in CRT representation is coordinate wise. (In polynomial representation, multiplication is not coordinate wise.)

**Example**: As before, let $q=17$ and $m=8$. Then $\Phi_8(X) = (X-2)(X+2)(X-8)(X+8)$. Let 

$$
\begin{aligned}
a(X) &= 1+2X+3X^3,\\
s(X) &= 14X^2+11,\text{and}\\ 
e(X) &= X^3+16X+1
\end{aligned}
$$ 

The sagemath script below computes $a(x)s(x)+e(x)$ using polynomial multiplication as well as CRT.


```python
class CRTRepresentation:
    def __init__(self, cyclo_power, q ):
        assert q % 2^cyclo_power == 1
        self._m = 2^cyclo_power
        self._GfQ = GF(q)
        self._PolyR = PolynomialRing(GF(q), 'X')
        self._PolyR.inject_variables(verbose=False)
        self._min_poly = self._PolyR(cyclotomic_polynomial(self._m))
        self._Oq = PolynomialQuotientRing(self._PolyR, self._min_poly)
        min_prim = q
        
        for r,_ in self._min_poly.roots():
            if int(r) < min_prim:
                min_prim = int(r)
        self._prim_roots = [self._GfQ(min_prim)^ei for ei in self.phi_m_elements()]
        
        
    def min_poly(self):
        return self._min_poly
    
    def Oq(self):
        return self._Oq
    
    def Fq(self):
        return self._GfQ
    
    def primitive_roots(self):
        return self._prim_roots
    
    def m(self):
        return self._m
    
    def phi_m_elements(self):
        result = list()
        for i in range(self._m):
            if gcd(i,self._m) == 1:
                result.append(i)
        return result

    def split(self, fx):
        """
        Compute the CRT representation
        """
        return [ self._Oq(fx).lift()(prim) for prim in self.primitive_roots() ]
    
    def combine(self, crt_list):
        """
        Combine the CRT representation. If u1, u2, u3 ... un
        """
        M=Matrix(self._GfQ, [[x^i for i in range(self._min_poly.degree())] 
                             for x in self._prim_roots] 
                )
        coeff=M.inverse()*vector(crt_list)
        poly = self._PolyR(0)
    
        for (i,c) in enumerate(coeff):
            poly = poly + c*X^i
            
        return self._Oq(poly)
    
    def crt_mul(self, a, b):
        assert len(a) == len(b)
        return [self._GfQ(a[i]*b[i]) for i in range(len(a))]
    
    def crt_add(self, a, b):
        assert len(a) == len(b)
        return [self._GfQ(a[i] + b[i]) for i in range(len(a))]
    
    def tau(self, fx, j):
        assert (gcd(j, self._m) == 1) or (j == 1)
        return [ self._Oq(fx).lift()(prim^j) for prim in self.primitive_roots()]
        
    
### NOTE: q mod 2^k == 1 must hold
crt_cartel = CRTRepresentation(3,17);
a=1+2*X+3*X^3; a_crt=crt_cartel.split(a); print(a_crt); 
s=14*X^2+11; s_crt = crt_cartel.split(s); print(s_crt)
e=X^3+16*X+1; e_crt = crt_cartel.split(e); print(e_crt)

b1 = crt_cartel.Oq()(a*s+e)
b2 = crt_cartel.combine(
        crt_cartel.crt_add(crt_cartel.crt_mul(a_crt, s_crt), 
                           e_crt)
    )
assert b1 == b2
print(b1)
print(b2)
```

    [12, 6, 7, 13]
    [16, 6, 16, 6]
    [7, 12, 12, 7]
    11*Xbar^3 + 14*Xbar^2 + 13*Xbar + 12
    11*Xbar^3 + 14*Xbar^2 + 13*Xbar + 12


### Automorphisms in $\mathcal{O}_q$

Let $f(Y) = \sum_{i} a_iY^i $ be a polynomial in $(\mathbb{Z}/q\mathbb{Z})[Y]$. Then define the the map $\tau_j\,\,\,\,\forall{j \in (\mathbb{Z}/m\mathbb{Z})^\times}$ as:

$$
\begin{aligned}
\tau_j &: \mathcal{O} \mapsto \mathcal{O}\\
\tau_j(f) &= \tau_j\left(\sum_{i} a_iY^i \right) = \sum_{i} a_i(Y^j)^i
\end{aligned}
$$

Note that we are defining $\tau_j$ only on those values of $j$ that are coprime to $m$. The following theorem is a crucial result for search-to-decision reduction:

**Theorem**: As before, let the CRT representation of $r(X) \in \mathcal{O}_q$ be $\mathbf{\hat{r}} = [\hat{r}_1, \cdots, \hat{r}_{n=\phi(m)}]$. Then the CRT representation of $\tau_j(r)$ is a permutation of $\hat{r}_i$s i.e., if $p_j(X) := \tau_j(r)$, then $\mathbf{\hat{p}}_j = [\hat{r}_{\sigma_{j}(1)},\hat{r}_{\sigma_{j}(2)},  \cdots, \hat{r}_{\sigma_{j}(n)}]$, where $\sigma_j$ is a permutation over $[1,\cdots,n]$ and $\sigma_j \neq \sigma_k\,\,\,\forall j \neq k$.

**Proof**: If $r(X)$ as an element of $\frac{(\mathbb{Z}/q\mathbb{Z})[X]}{\langle \Phi_m(X) \rangle}$ has polynomial representation $\sum_{i \in [1,\cdots,n]} a_iX^i$, then if we lift it as an element $\tilde{r}(Y)$ of $(\mathbb{Z}/q\mathbb{Z})[Y]$, it must be of the form (by definition):

$$
\tilde{r}(Y) =  h(Y)\Phi(Y) + r(Y)
$$

where $h(Y)$ is some polynomial in $(\mathbb{Z}/q\mathbb{Z})[Y]$. Recall, that if $u$ is the $m$-th *primitive root* of unity, then the other primitive roots of unity are $u^k$ where $k$ is coprime to $m$. Therefore, $\tau_j(\tilde{r})(u^k) = h(u^k)\Phi(u^k) + r((u^k)^j)$. But since $u^k$ is a root of unity, $\Phi(u^k) = 0$, and since $u^m = 1 \implies u^{jk} = u^{jk\,\text{mod}\, m}$. Therefore, $\tau_j(\tilde{r})(u^k) = r(u^{jk\,\text{mod}\,\,m})$. Therefore, $p(u^k) = r(u^{jk\,\text{mod}\,\,m})$, which is a permutation of $\hat{r}_i$.

The following sage script shows this in action:


```python
crt_cartel = CRTRepresentation(3,17)
a=1+2*X+3*X^3; a_crt=crt_cartel.split(a);

for i in crt_cartel.phi_m_elements():
    print(crt_cartel.tau(a,i))
```

    [12, 6, 7, 13]
    [6, 12, 13, 7]
    [7, 13, 12, 6]
    [13, 7, 6, 12]


## Ring-LWE Search $\leq$ Ring-LWE Decision 

### Setup

The setup for search to decision reduction for Ring-LWE is as follows: One is given polynomially many samples of the form $\Gamma_i := (a_i, b_i) \in \mathcal{O}_q\times \mathcal{O}_q$ where $b_i(X)$ is known to be of form $a_i(X)\cdot s(X) + e_i(X)$. In addition, one has oracle access to a distingusher $\mathcal{D}$ that can distinguish between $\left \{ \Gamma_i \right \}$ and $\left \{\Theta_i \right \}$, where $\Theta_i$ is uniformly distributed over $\mathcal{O}_q\times \mathcal{O}_q$. 

Input to $\mathcal{D}$ are polynomial pairs $(a, b)$ where $a(X)$ is guaranteed to be uniformly random over $\mathcal{O}_q$, and


<ol  style="list-style-type: lower-alpha">
  <li> $\mathcal{D}$ outputs $1$ if $b(X) = a(X)\cdot s(X) + e(X)$ for some $s(X)$ and $e(X) \leftarrow \chi$, otherwise</li>
  <li>$\mathcal{D}$ outputs $0$ if $b(X)$ is uniformly distributed over $\mathcal{O}_q$</li>
</ol>

For **any other distribution** of $a(X)$ or $b(X)$, the oracle $\mathcal{D}$ makes no promises about its output---not even the promise that $\mathcal{D}$ will terminate! For any reduction that uses $\mathcal{D}$ as a subroutine, the caller must prove that input to $\mathcal{D}$ is either of the type (a) or (b).

The goal of search Ring-LWE reduction is to come up with an algorithm $\mathcal{A}$ that makes polynomially many calls to $\mathcal{D}$ to find $s(X)$. Note that input to $\mathcal{A}$ are always valid Ring-LWE samples. If $\mathcal{A}$ is fed with anything else, $\mathcal{A}$ is not required to even terminate.

Why can't we use the vanilla LWE reduction for Ring-LWE? In LWE, we had a single value of $b_i \in \mathbb{Z}/q\mathbb{Z}$ per-sample that allowed us to guess each coordinate of the secret $\mathbf{s}$ one at a time. In case of Ring-LWE, we have $n$ coefficients of the polynomial per $b_i(x)$, so we need to guess all the $n$ coefficients of $s(X)$ simulatenoulsy, which the LWE reduction cannot handle.

Here's how the reduction works:

1. First, instead of working with polynomial representation of $b(X)$, we convert it to CRT representation $\mathbf{\hat{b}} = [\hat{b}_1,\cdots,\hat{b}_n] \in (\mathbb{Z}/q\mathbb{Z})^n$. (Recall, $n = \phi(m)$.)


2. Then create $n+1$ hybrid samples $\mathbf{\hat{h}}_i$, $i = 0,1,\cdots,n$, such that the first $i$ CRT terms of $\mathbf{\hat{h}}_i$ are uniformly random, but the rest are same as $\mathbf{\hat{b}}$. One way to generate this is to compute $\mathbf{\hat{h}}_i = \mathbf{\hat{b}} + [u_1,\cdots,u_{i},0,\cdots,0]$ where $u_1, u_2, \cdots, u_{i}$'s are chosen uniformly at random from $(\mathbb{Z}/q\mathbb{Z})$. In this notation, $\mathbf{\hat{h}}_0 = \mathbf{\hat{b}}$, and $\mathbf{\hat{h}}_{n}$ is uniformly random. From the CRT representation of $\mathbf{\hat{h}}_i$'s, Ring-LWE style polynomial pairs $(a(X), h_i(X))$. 
$$
$$
Assuming the distinguisher $\mathcal{D}$ has advantage $\epsilon$, a simple hybrid argument shows that there exists an index $k \in [0,\cdots,n],$ such that on input $(a, h_{k-1})$, $\mathcal{D}$ outputs 1 (i.e, Ring-LWE sample), while on input $(a, h_{k})$, it outputs 0 (i.e., uniformly random). The distinguishing advantage of $\mathcal{D}$ for such inputs is $\epsilon/n$. One can sequentially run $\mathcal{D}$ with $h_i$'s as input and find $k$ by making at max $n+1$ calls to $\mathcal{D}$.
$$
$$
An important point to note here is that $\mathcal{D}$ always takes input in polynomial representation, but $h_i(X)$ was generated from its CRT representation $\mathbf{\hat{h}}_i$. So why should polynomials generated from hybrid samples in CRT representation not behave more erratically? Answer: CRT representation is in a bijective relationship with polynomial representation.


3. Once we know the value of $k$ as above, we will create a search algorithm $\mathcal{A}_k$ that will guess the $k$-th CRT coefficient corresponding to $s(X)$. This step is very similar to vanilla LWE reduction, where we randomly guess the $k$-th CRT value of $s(X)$, and let $\mathcal{D}$ tell us if our guess is correct. 
$$
$$
In more detail, let the CRT representation of $s(X)$ be $\mathbf{\hat{s}} = [\hat{s}_1,\cdots,\hat{s}_n]$. Algorithm $\mathcal{A}_k$, will then find $\hat{s}_k$. To do this, $\mathcal{A}_k$ first samples two vectors $\mathbf{u}$ and $\mathbf{v}$ such that the first $k-1$ entries of $\mathbf{u}$ are uniformly random and the rest are zero, while $\mathbf{v}$ has all zeros except for a random value in $k$-th location:
$$
$$
$$
\begin{aligned}
\mathbf{u} &:= [u_1, u_2,\cdots,u_{k-1},0,\cdots,0],\,\,\,\text{and}\\
\mathbf{v} &:= [0,\cdots,0,v_k,0,\cdots,0]
\end{aligned}
$$
$$
$$
As in the case of vanilla LWE, $\mathcal{A}_k$ also makes a guess $\psi \in (\mathbb{Z}/q\mathbb{Z})$ as the potentional value of $\hat{s}_k$, and computes
$$
\hat{\Gamma} := (\mathbf{\hat{a}}+\mathbf{v}, \mathbf{\hat{b}}+\mathbf{u} +\psi\mathbf{v})
$$
and converts it to its polynomial representation $\Gamma' := (a'(X), b'(X))$. $\mathcal{D}$ is then invoked with $\Gamma'$ to get the answer if it's Ring-LWE sample or random.
$$
$$
**Claim-1**: If the guess of $\psi$ is correct, then $\hat{\Gamma}$ is distributed as $(\mathbf{\hat{a}}+\mathbf{v}, \mathbf{\hat{h}}_{k-1})$.$$$$
**Proof**: When the guess of $\psi$ is correct (i.e., $\psi = \hat{s}_k$), then since multiplication in CRT representation is component wise, $\psi\mathbf{v} = \hat{s}_k\mathbf{v} = $ $ [0,\cdots,0,\,\,v_k\hat{s}_k,\,\,0,\cdots,0] = \mathbf{\hat{s}}\mathbf{v}$. Therefore,
$$
\begin{aligned}
\mathbf{\hat{b}}+\mathbf{u} +\psi\mathbf{v} &= \mathbf{\hat{a}}\cdot \mathbf{\hat{s}}+\mathbf{\hat{s}}\mathbf{v}+\mathbf{u}\\
&= (\mathbf{\hat{a}}+\mathbf{v})\cdot \mathbf{\hat{s}}+\mathbf{u}
\end{aligned}
$$
and $\hat{\Gamma}$ is distributed as $(\mathbf{\hat{a}}+\mathbf{v}, \mathbf{\hat{h}}_{k-1})$ since the first $k-1$ entries of $\mathbf{\hat{h}}_{k-1}$ are uniformly random because of $\mathbf{u}$, _while the $k$-th entry and the rest_ are valid Ring-LWE entries.
$$
$$
**Claim-2**: If the guess of $\psi$ is incorrect, then $\hat{\Gamma}$ is distributed as $(\mathbf{\hat{a}}+\mathbf{v}, \mathbf{\hat{h}}_{k})$.$$$$
**Proof**: When the guess of $\psi$ is incorrect (i.e., $\psi \neq \hat{s}_k$), $\psi\mathbf{v} = [0,\cdots,0,\,\,v_k\psi,\,\,0,\cdots,0]$. However, since $v_k$ is uniformly random in $(\mathbb{Z}/q\mathbb{Z})$, $v_k\psi$ is also uniformly random in $(\mathbb{Z}/q\mathbb{Z})$ and $\mathbf{u} + \psi\mathbf{v} - \hat{s}_k\mathbf{v} = $ $[u_1,\cdots, u_{k-1},\,\,v_k(\psi-\hat{s}_k),\,\,0,\cdots,0]$, is a vector with first $k$ entries uniformly random. Let $\mathbf{u}' = \mathbf{u} + \psi\mathbf{v} - \hat{s}_k\mathbf{v}$, then
$$
\begin{aligned}
\mathbf{\hat{b}}+\mathbf{u} +\psi\mathbf{v} &= \mathbf{\hat{a}}\cdot\mathbf{\hat{s}}+\mathbf{u} +\psi\mathbf{v}\\
 &= (\mathbf{\hat{a}} + \mathbf{v}) \cdot\mathbf{\hat{s}}- \mathbf{\hat{s}}\cdot\mathbf{v} + \mathbf{u} +\psi\mathbf{v}\\
 &= (\mathbf{\hat{a}} + \mathbf{v}) \cdot\mathbf{\hat{s}} + \mathbf{u}'
\end{aligned}
$$
Therefore, $\hat{\Gamma}$ is distributed as $(\mathbf{\hat{a}}+\mathbf{v}, \mathbf{\hat{h}}_{k})$ since the first $k$ entries of $\mathbf{\hat{h}}_{k}$ are uniformly random because of $\mathbf{u}'$.
$$$$
Therefore, the algorithm $\mathcal{A}_k$ can make use of the distinguisher $\mathcal{D}$ with all possible values of $\psi$ in $\mathbb{Z}/q\mathbb{Z}$, to find the right value of $\hat{s}_k$.
$$$$

4. So far we have only been able to compute a single CRT value of $s(X)$. As we have seen before, each $\tau_j$ permutes the elements of CRT representation, so if we systematically permute the elements of $(\mathbf{\hat{a}}, \mathbf{\hat{b}})$ and run step-3 for each $\tau_j$, we will recover all the $\hat{s}_i$. For this to work, however, we need guarantees about the distribution of $a(X)$ and $b(X)$.
$$$$
Let $u$ be any primitve $m$-th root  of unity in $(\mathbb{Z}/q\mathbb{Z})$. For any polynomial $f(X)$, fix the CRT representation $\mathbf{\hat{f}} := [f(u^{e_1}),f(u^{e_2}),\cdots,f(u^{e_n})]$, where $e_i$s are integers coprime to $m$. (Essentially we are fixing which coordinates come from which power of $u$.)
$$$$
**Claim**: Let $\Gamma_{e_j} := (\tau_{e_j}(a), \tau_{e_j}(b))$. Then $\Gamma_{e_j}$ is a valid Ring-LWE sample which is distributed identially as $\Gamma$ provided the error distribution $\chi$ is **automorphically closed**, i.e., $\tau_{e_j}(\chi) = \chi$ for all $e_j$.$$$$
**Proof**: Since $\tau_{e_j}$ is a permutation on elements of $\mathcal{O}_q$ and $a(X)$ is uniformly distributed, $\tau_{e_j}(a)$ is uniformly distributed. Since $b(X) = s(X)a(X) + e(X)$, $\tau_{e_j}(b) = \tau_{e_j}(s\cdot a +e) = \tau_{e_j}(s)\cdot\tau_{e_j}(a) + \tau_{e_j}(e)$. Since $a(X)$ is uniformly distributed, $\tau_{e_j}(s)\cdot\tau_{e_j}(a)$ is also uniformly distributed, even if $s(X)$ might have been drawn from worst-case distribution. (If you find this argument unconvincing, then note that Ring-LWE also has random self reducibility (RSR), so one can translate the whole problem to a uniformly distributed $s(X)$ and run it through RSR.) Also, by assumption, $e(X)$ is drawn from automorphically closed distribution, therefore  $\tau_{e_j}(s)\cdot\tau_{e_j}(a) + \tau_{e_j}$ is distributed identially as $s(X)\cdot a(X) + b(X)$.
$$$$
To find all the secrets, let $k$ be the index for which we can compute $\hat{s}_k$. Since the CRT representation is fixed, this means $\hat{s}_k$ corresponds to $u^{e_k}$ primitive root of unity. Therefore, to compute all the other roots, let $t_i = e_ie_k^{-1}$, then $(\tau_{t_i}(a), \tau_{t_i}(b))$ will return $i$-th CRT coordinate.


```python
class RingLWESolver:
    def __init__(self, decisionalOracle):
        """
        Create a RingLWE solver using prime q and X^m-1 = 0 where m = 2^k
        """
        self._decisionalOracle = decisionalOracle
        self._crt_rep = CRTRepresentation(decisionalOracle.k(),decisionalOracle.q())
        
    def m(self):
        return self._decisionalOracle.m()
        
    def n(self):
        return self._decisionalOracle.n()
    
    def Fq(self):
        return self._crt_rep.Fq()
    
    def oracle(self):
        return self._decisionalOracle
    
    def to_crt(self, fx):
        return self._crt_rep.split(fx)
    
    def from_crt(self, fx_hat):
        return self._crt_rep.combine(fx_hat)
    
    def _u(self, i):
        u = random_vector(self._crt_rep.Fq(), self.n())
        if i < 0:
            i = 0
        for j in range(i,self.n()):
                u[j]=0
        return u.list()
    
    def _v(self, i):
        v = vector(self._crt_rep.Fq(), self.n())
        assert i < self.n()
        v[i] = self._crt_rep.Fq().random_element()
        return v.list()
                
    def hybrids(self, fx):
        """
        Generates $n+1$ hybrids 
        """
        result = list()
        fx_hat = self.to_crt(fx)
        # result.append(fx)
        
        for i in range(self.n()+1):
            u = self._u(i)
            fx_hat_prime = self._crt_rep.crt_add(fx_hat, u)
            fx_prime = self.oracle() \
                            .cyclotomic_mod_q() \
                            .from_poly(self.from_crt(fx_hat_prime).lift())
            result.append(fx_prime)
            
        return result
    
    def find_k(self, a, b):
        """
        Find the index at which the decisional oracle flips.
        """
        max_flip=0
        max_index=0
        trials = 0
        flip_index = dict()
        while trials < 50:
            hybrids = self.hybrids(b)
            assert len(hybrids) == self.n() + 1
            for i in range(self.n()):
                x = self.oracle().decide(a, hybrids[i])
                y = self.oracle().decide(a, hybrids[i+1])
                # print("{} : x ={}, y={}".format(i,x,y))
                if x == 1 and y == 0:
                    trials = trials + 1
                    if flip_index.get(i) is None:
                        flip_index[i] = 1
                    else:
                        flip_index[i] = flip_index[i] +1
        
        for (i,v) in flip_index.items():
            if v > max_flip:
                max_flip = v
                max_index = i
            
        return max_index
    
    def search_sk(self, k, a, b):
        a_hat = self.to_crt(a)
        b_hat = self.to_crt(b)
        
        for i in range(self.oracle().q()):
            is_rlwe_count = 0
            trials = 0
            for _ in range(10):
                u = self._u(k-1)
                v = self._v(k)
                a_hat_prime = self._crt_rep.crt_add(a_hat, v) 
                b_hat_prime = self._crt_rep.crt_add(b_hat, [self.Fq()(i*x) for x in v])
                b_hat_prime = self._crt_rep.crt_add(b_hat_prime, u)
                
                a_prime_X = self.from_crt(a_hat_prime)
                b_prime_X = self.from_crt(b_hat_prime)
                a_prime   = self.oracle().cyclotomic_mod_q().from_poly(a_prime_X.lift())
                b_prime   = self.oracle().cyclotomic_mod_q().from_poly(b_prime_X.lift())
                
                if self.oracle().decide(a_prime, b_prime) == 1:
                    is_rlwe_count = is_rlwe_count + 1
            if is_rlwe_count > 5:
                return i
            else:
                ## The solver lies!!!
                return 0
    
    def search(self, a, b):
        k = self.find_k(a,b)
        e_k_inv = self.Fq()(1 / self._crt_rep.primitive_roots()[k])
        
        a_X = self.from_crt(self.to_crt(a))
        b_X = self.from_crt(self.to_crt(b))
        
        crt_list = list()
        for x in self._crt_rep.primitive_roots():
            t_k = self.Fq()(x * e_k_inv)
            a_tau = self._crt_rep.tau(a_X, t_k)
            b_tau = self._crt_rep.tau(b_X, t_k)
            s_k = self.search_sk(k, a_tau, b_tau)
            crt_list.append(s_k)
            
        return self.from_crt(crt_list)
    
    def __repr__(self):
        return "RLWESolver{{ Oracle: {} }}".format(self._decisionalOracle)
    
k=3
print(gen_rlwe_q(8))
q=41
decisional_oracle = RLWEDecisionalOracle(k,q)
a,b = decisional_oracle.rlwe_sample();

rlwe_solver = RingLWESolver(decisional_oracle); print(rlwe_solver)
hybrids = rlwe_solver.hybrids(b);
rlwe_solver.search(a,b)
```

    73
    RLWESolver{ Oracle: secret: ζ^3 + 25*ζ^2 + 6*ζ + 35, Oq: Oq=Maximal Order in Cyclotomic Field of order 8 and degree 4
    q=41
    m=8 }





    0



66eb4ec4e2daa258e5a3609e19ccec73f3039f11
ipynb
Jupyter Notebook
RLWE-Search-to-Decision-LPR13.ipynb
axelexic/lattice_ladoos
b2e5f8061b05718d2b37e57d103141b7c39b36e2
BSD-3-Clause
RLWE-Search-to-Decision-LPR13.ipynb
axelexic/lattice_ladoos
b2e5f8061b05718d2b37e57d103141b7c39b36e2
BSD-3-Clause
RLWE-Search-to-Decision-LPR13.ipynb
axelexic/lattice_ladoos
b2e5f8061b05718d2b37e57d103141b7c39b36e2
BSD-3-Clause
2020-05-31T10:46:17.000Z
2020-05-31T10:46:17.000Z
Qwen/Qwen-72B
1. YES
2. YES