After watching this talk https://www.youtube.com/watch?v=Eg_pyyeT_Qc&feature=plcp, I tried to formalize the presented search-to-decision reduction for Ring LWE, but got stuck at one point.

I understand how we can construct an algorithm that finds the k-th coefficient of the secret (in "Chinese remainder representation", so really $s(\zeta^k)$ with a root of unity $\zeta^k$) for a given k. To do that, we use an oracle that can distinguish between real RLWE samples and uniform ones. As far as I know, this "distinguishing" means that $Pr[O(f, fs + e)] - Pr[O(f, U)]$ is non-negligible, where $f, U, s$ are uniformly distributed random variables on $R_q$. But this would mean, that the oracle and therefore our algorithm* is only guaranteed to find $s(\zeta^k)$ for a non-negligible fraction of all inputs. Using the average-to-worst case reduction, we can make it work for all $s$, but not necessarily for all $f$, so our algorithm may only work on samples $(f, fs + e)$ where $f$ is in some not-too-small set $S$.

My question is now: Is my understanding so far correct, and if it is, how can the automorphism idea (to find the other coefficients) work? If $\sigma$ is a field automorphism that can preserves the error distribution, we know that $(\sigma(f), \sigma(fs + e))$ is also a valid RLWE sample, but it is not guaranteed that the algorithm will work correctly on this sample (it only has to work on a non-negligible fraction of all $f$s). Since $(\sigma(f), \sigma(fs + e))$ and $(f, fs + e)$ are not independent either, the algorithm does not have to work with relatively high probability.

In other words: Why is it impossible, that the assumed oracle distinguishes real RLWE samples $(f, fs+e)$ and uniform samples perfectly for half the $f$ and accepts with probability $0.5$ in the other cases* in such a way that for every $f$ there are automorphisms $\sigma$ (preserving the error distribution) so that the oracle does not work on $(\sigma(f), \sigma(fs + e))$?

I also had a look at this paper (I think the proof has been published there originally) http://citeseerx.ist.psu.edu/viewdoc/download?doi=, but I did not find details on this question.

(*of course, the oracle is not invoked on $(f, fs + e)$ but rather on $(f + v, fs + e + vk)$, but this should not fundamentally change things)

If my problem is unclear or not formal enough, please tell me. I did not include my complete current proof part as this question is already quite long.


1 Answer 1


(The full version of the paper is at https://eprint.iacr.org/2012/230, and my answer below refers to it.)

The answer to your question is that a different part of the reduction ensures that the oracle has advantage very close to 1 over the random samples $(a_i, a_i s + e_i + r_i)$, i.e., the oracle outputs the correct answer for almost all choices of $s, a_i, e_i, r_i$. With this guarantee, Lemmas 5.5 and 5.9 give a reduction that solves the search problem using the automorphisms and the "guess and check" technique.

The other part of reduction to which I refer is described in Section 5.2, on "worst-case to average-case decision" (Lemma 5.12). This uses a pretty standard "amplification" technique to improve the oracle's distinguishing advantage, by repeatedly invoking it on independent samples and measuring how often it accepts.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.