A RLWE promise problem

Question

Let $(R , \chi$) be a standard RLWE problem instance. I.e. $R$ is a finite degree polynomial ring over a finite field and $\chi$ is some gaussian distribution over R with small variance.

I wonder if the following promise problem is hard.
Let $a_0$ and $a_1$ be two random elements from $R$
The challenger choses a boolean $b$ and two elements $s,e \in \chi$, and calculates $c= a_b s + e$.

The problem is then:
Given $c, a_0, a_1$, calculate $b$ with non-negible advantage.

For motivation:
If that promise problem turns out to be hard, one could use as natural PQ replacement of PACE, the password authenticated key agreement protocol used in electronic passports. (See ICAO doc 9303)

Answer 1

(It seems that the proof can be salvaged.)

Let $\text{RLWE}$ denote the standard ring-LWE problem where the secret $s$ is drawn uniformly at random from $R$. Thus, the $\text{RLWE}$ assumption is: $$(a,as+e)\approx(a,r):a,r,s\leftarrow R, e\leftarrow\chi,$$ where $\approx$ denotes computational indistinguishability. $\text{RLWE}$ assumption implies the non-standard LWE assumption [Lemma 2, ACPS09], denoted $\text{RLWE'}$, where the secret is drawn from $\chi$: $$(a,as+e)\approx(a,r):a,r\leftarrow R, s,e\leftarrow\chi.$$ The hardness of the promise problem, denoted $\text{RLWE''}$, follows by a hybrid argument (see below) assuming $\text{RLWE'}$ holds. Thus, the chain of reduction is: $$\text{RLWE}<\text{RLWE'}<\text{RLWE''}.$$

The hybrid argument. We want to show that the two distributions $$D_L:=(a_0,a_1,a_0s+e) \text{ and } D_R:=(a_0,a_1,a_1s+e)$$ are computationally indistinguishable, for $a_0,a_1\leftarrow R$ and $s,e\leftarrow \chi$. Consider the hybrid distribution $$D_H:=(a_0,a_1,r)$$ where $a_0,a_1,r\leftarrow R$. We show that $D_L\approx D_H$ and $D_H\approx D_R$, and it follows by transitivity that $D_L\approx D_R$.

To see that $D_L\approx D_H$, suppose for contradiction that it is not: that is there exists an algorithm $\mathsf{A}$ that distinguishes $D_L$ from $D_H$. We show that $\mathsf{A}$ can be used to break $\text{RLWE'}$. The reduction $\mathsf{R}$ is straightforward: given a $\text{RLWE'}$ challenge $(a,b)$ (where $a\leftarrow R$ and $b$ is either $as+e$ or $r$), $\mathsf{R}$ samples $a'\leftarrow R$ and sends $(a,a',b)$ to $\mathsf{A}$ and outputs to its challenger whatever $\mathsf{A}$ outputs. If $b=as+e$ then $\mathsf{A}$ simulates $D_L$; otherwise it simulates $D_H$.

The argument showing $D_H\approx D_R$ is similar.

References.

[ACPS09] Applebaum, Cash, Peikert and Sahai. Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. CRYPTO 2009.

Answer 2

TL;DR To summarize, Boolean lattices (regardless of application) pertaining to any LWE or R-LWE are trivial to crack, break, etc. Also, every lattice has an invertible element via mod switch to Boolean lattices. (forum)

Problem:

Let $(R,χ)$ be a standard R-LWE problem instance, where $R$ is a finite degree polynomial ring over a finite field and $χ$ is some Gaussian distribution over $R$ with small variance.

Let $a_0$ and $a_1$ be two random elements from $R$. The challenger chooses a Boolean $b$ and two elements $s,e ∈ χ$ and calculates $c=a_{b}s+e$.

Given $c, a_0, a_1$, calculate $b$ with non-negligible advantage.

We can frame the promise problem over the language $L\subseteq \{0,1 \}^*$ where any input in $L$ ACCEPTS, and any input not in $L$ REJECTS. The two languages $L_{YES}$ and $L_{NO}$ are disjoint, and the union of the two sets is defined as the promise. For any input not belonging to the set of YES or NO instances of the language, the output may be arbitrary or fail to halt. (source)

To show that Promise R-LWE solves the R-LWE CVP decision problem, choose target vector $t \in \mathbb{Z}^m$ with respect to lattice basis $\mathbf{B} \in \mathbb{Z}^{m\times n}$. Determine whether an integer vector $x \in \mathbb{Z}^n$ satisfies $\| \mathbf{Bx}-\mathbf{t}\| \leq \|\mathbf{By}-\mathbf{t}\|$ for any other $y \in \mathbb{Z}^n$. (source)

For rational $r>0$, determine if a non-zero lattice vector $\mathbf{x}$ exists such that $\|\mathbf{x-t}\| \leq r$

Method Using Trivial Lattice

Using the values of $(a_{0}, a_{1})$ and $a_{b}$, our goal is to determine the shortest non-zero vector which satisfies $\|a_{b} - b \|\leq r$ for $\{r >0 | r \in \mathbb Q\}$.

Input $a_{0}$ to the Promise Oracle, understanding that the input is in $L$. If, for all $a_{0} \in L_{YES} = 1$ and $a_{0} \in L_{NO} = 0$ then there is a polynomial time algorithm $A_p$ such that $A_{p}(a_{0})$ outputs either 0 for instances of NO or 1 for instances of YES. These same conditions hold for $a_{1}$. (source).

We then input the decision form of CVP with respect to integer vectors $(x,y) \in \mathbb Z^{n}$ for ring elements $a_{0}, a_{1}$. Given $\mathbb Z[x]/(x^{n} - 1)$, with $n$ a power of 2, let $x = 1$ in the least residue system modulo 2. If $s \equiv 1 \ \mathrm{mod} \ p$ for prime $p$, then the shortest vector returns 1, and 0 otherwise.

For some multiple of $2$, define $x = 1 + 2n, \ n \in \mathbb Z$ and $x = 1$ in least residue system modulo 2.

Choose vectors $(314, 159)$ and $(271, 828)$ for the ring element $a_{0}(314, 159)\mod 2$ and $a_{1}(271, 828)\mod 2$.

Let $x_{0} = (314, 159), x_{1} = (271, 828)$.

For $x^{2n} + 1$ and $x^{2^{n}} + 1$ with $n = 2$, the following holds:

$a_{0}(314,159) \mod 2 = (0,1)$ and $a_{1}(271, 828)\mod 2 = (1,0)$.

We can now define the algorithm $A_{p}$ for solving the CVP in polynomial time under the Promise Oracle.

All elements of $L_{YES}$ return 1 for successful queries given shortest, non-zero vector inputs. Any 0 returned for all elements in $L_{NO}$ result if, and only if, the input is not the shortest non-zero vector given the trivial lattice. The algorithm $A_{p}$ with binary relation $R_b$ using the least residue method illustrated shows there exist $(x,y)$ such that for all $x \in L_{YES}$ there is a relative $y$ resulting in $(x,y) \in R_b$. Thus, for all $x$ there is a $y$ having a multiple in common for ring $R$. Consequently, for every $x \in L_{NO}$ and every $y$, it holds that $(x,y) \notin R_{b}$. (source)

If $A_{p}(x,y) = 1$ then $x \in L_{YES}$ and $(x,y) \in R_{b}$. If $A_{p} = 0$ then $x \in L_{NO}$ and $(x,y) \notin R_{b}$.

Therefore, given $c$ and having inputs $(a_{0}, a_{1})$ the Promise Oracle returns 1 if, and only if, the input is shortest non-zero vector having binary relation with respect to $y$, otherwise returning 0. Recall the conditions for solving the Decision CVP:

$\| \mathbf{Bx}-\mathbf{t}\| \leq \|\mathbf{By}-\mathbf{t}\|$ for any other $y \in \mathbb{Z}^n$.

Treating the target vector $t$ as the target value $b$ under the Promise version of R-LWE, instances of $(x,y)$ which satisfy the CVP Decision conditions are equivalent to solving the CVP under R-LWE for target vector $s$. Therefore calculating $b$ for Promise R-LWE is as difficult as calculating values $s$ from $(a,b)$ in R-LWE using integer ring $\mathbb{Z}[x] / (x^{n} - 1)$ for $n$ multiples of 2, or $n$ a power of 2 when $n = 2$.

The probability of choosing $s$ correctly from $(c)$ is equivalent to distinguishing between nearly uniform noise $e$ and ring elements $(a_{0}, a_{1})$. The probability of determining values of $b$ with respect to $(a_{0}, a_{1})$ given $c$ is equivalent to finding $s$ such that $s$ satisfies the conditions of the target vector in the decision form of the CVP.