# Guessing the Secret in RLWE Search-to-Decision

In On Ideal Lattices and Learning with Errors over Rings, the authors prove a search-to-decision reduction by guessing the RLWE secret $$s$$, and using the guess to transform a sample from $$\mathfrak{q}_{i}$$-$$\mathrm{LWE}_{q, \Psi} \text { to } \mathrm{DecLWE}_{q, \Psi}^{i}$$ (Lemma 5.9). They say nothing about the properties of the guess, $$g$$, although they do go on to consider whether $$g\equiv s$$ mod $$\mathfrak{q}_{i}$$ or $$g \not\equiv s$$ mod $$\mathfrak{q}_{i}$$. My question is: what can we assume to be true about $$g$$? What can we say about its distribution? about other behaviour modulo $$\mathfrak{q}_{i}$$, or in the ring? Or can it have no more structure than merely being a ring element?

The "guesses" are part of the enumeration of all possible values of $$s\bmod \mathfrak{q}_iR^\vee$$. The reduction has two parts essentially:
1. A way of telling if the guess was correct (the $$\mathsf{WDLWE}_{q, \Psi}^i$$ oracle)
2. A small space of values to try (as values $$s\bmod \mathfrak{q}_i R^\vee$$ are within $$R_q^\vee/\mathfrak{q}_iR_q^\vee$$, which from context in the paper appears to have size $$N(\mathfrak{q}_i) = q = \mathsf{poly}(n)$$).