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.