Careful with the Ring: Enhanced Hybrid Decoding Attacks against Module/Ring-LWE

본문 미리보기

In order to reduce size and improve efficiency, many lattice-based cryptographic schemes adopt structured variants of the Learning With Errors (LWE) problem, such as the Module-LWE and Ring-LWE. Nevertheless, when analyzing the concrete security of lattice-based schemes, these algebraic structures are usually not considered, given the absence of techniques to exploit them for accelerating known attacks. For the widely-used polynomial ring $\mathbb{Z}_q[x]/(x^N+1)$, we first propose an enhance