RLWE decision to search: probability that oracle work on all automorphic images

Question

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=10.1.1.400.7900&rep=rep1&type=pdf, 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.

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.