How to solve LWE/RLWE under partial information about $s$

us flag

For LWE/RLWE, it's difficult to find $s$ from $\left(A, b = As + e\right)$. But if the partial information of $s$ is leakaged, such as partial $s$ or parity of $s$, how easy would it become to solve LWE?

I don't know much about the algorithm for attacking LWE/RLWE, if there is some relevant literature recommended that would be great.

sa flag

If all you know is the parity of $s$ then you can rule out half of possible solutions, so no real improvement will happen.

If there is more substantial information, there can be improvements but the situation gets quite technical. There is a 2020 talk entitled LWE with side information: attacks and concrete security estimation

Leo Ducas, CWI, talk at the Simons Institute

that may be a good point for you to start. There may be other relevant talks during that workshop called Lattices:From Theory to Practice, in April 2020.


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.