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 &quot;guesses&quot; are part of the enumeration of all possible values of $s\bmod \mathfrak{q}_iR^\vee$. The reduction has two parts essentially:

A way of telling if the guess was correct (the $\mathsf{WDLWE}_{q, \Psi}^i$ oracle)
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)$).

You then enumerate all possible guesses, and return the one which verifies to be correct.
This is a deterministic process (although you're free to choose the particular order to enumerate things in).