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.
