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

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.

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.