1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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)$).

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.