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)

  • $\begingroup$ It feels like it ought to follow immediately from the standard rLWE assumption ("given $a$ and either $as + e$ or a random value $r$, it is hard to determine whether you received $as + e$ or $r$"); however I just can't see the reduction... $\endgroup$
    – poncho
    Aug 13, 2017 at 18:54
  • $\begingroup$ @poncho: That is exactly my problem; I can also not see a reduction to RLWE decision. Meanwhile I think that this problem is weaker then RLWE decision/search. $\endgroup$
    – user27950
    Aug 13, 2017 at 19:02
  • 1
    $\begingroup$ If you're looking for a RLWE-based PAKE, there's eprint.iacr.org/2016/552.pdf $\endgroup$
    – poncho
    Aug 13, 2017 at 19:14
  • $\begingroup$ Thank you for the link. But I want to have a natural replacement for PACE. $\endgroup$
    – user27950
    Aug 14, 2017 at 3:58
  • $\begingroup$ @Cryptostasis I think the use of a Boolean $b$ might make it weaker, but that could be contingent on the dimension of the lattice. $\endgroup$
    – floor cat
    Aug 18, 2017 at 20:01

1 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.


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

  • $\begingroup$ In the question, I presume that $s\leftarrow\chi$ is a mistake. $\endgroup$
    – ckamath
    Aug 18, 2017 at 10:01
  • 1
    $\begingroup$ No, $s \leftarrow \chi$ is correct, see the NewHope paper eprint.iacr.org/2015/1092.pdf $\endgroup$
    – user27950
    Aug 18, 2017 at 10:26
  • $\begingroup$ Ah. Then I don't think the above argument holds. $\endgroup$
    – ckamath
    Aug 18, 2017 at 10:41
  • $\begingroup$ The proof can be salvaged, it seems. $\endgroup$
    – ckamath
    Aug 21, 2017 at 10:48
  • $\begingroup$ Sorry, my comment was nonsense. I removed it. $\endgroup$
    – user27950
    Aug 22, 2017 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy