2
$\begingroup$

Currently every LWE-based cryptographic schemes analyze their security using lattice estimators and lattice estimators analyze the security of standard LWE even though the actual scheme is based on Ring-LWE or Module-LWE. As far as I know, there is no specific attack algorithm on Ring(or Module)-LWE exploiting the ring structure(or, structure of ideal lattice rather than standard lattice) exists.

But why is it so? Is the answer for my question just 'not yet'? Or is there any theorem implying that, say, 'hardness problem in ideal lattice is no easier than in standard lattice'?

Thank you in advance.

$\endgroup$
6
  • 1
    $\begingroup$ There exist some attacks exploiting the ring structure; see, e.g., arxiv.org/abs/1502.03708. But these attacks are for the artificial rings, and I am unaware of the ring LWE attack for cyclotomic fields. The subfield attacks on the NTRU problem are also worth mentioning, where the cyclotomic structure allows efficient attack. $\endgroup$
    – Hhan
    Commented Apr 7, 2023 at 9:13
  • 2
    $\begingroup$ It's worth mentioning also in the quantum setting you can leverage the ideal structure to speed some things up as well (standard reference is Biasse and Song 16). There's also the short principle generator problem --- not exactly a "structured form of a standard unstructured problem", but something that was used in some ideal lattice cryptosystems and ended up being easier than people expected. $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 8, 2023 at 17:20
  • 2
    $\begingroup$ @Hhan the subfield attacks on NTRU were first discovered by exploiting the algebraic structure of the fields/rings, but it turns out that they are actually just sublattice attacks and do not depend on the rings. This is discussed in Ducas and van Woerden, 2021, where a matrix version of NTRU (so no structure) is also attacked. $\endgroup$ Commented Apr 10, 2023 at 17:07
  • 1
    $\begingroup$ @HilderVitorLimaPereira True, thanks for pointing this out. But still the later part (decryption, etc.) becomes easier for the subfield attack, and the sublattice attack is elusive. Also, I believe the intuitive idea of subfield attack is more easier and still worth thinking about it. $\endgroup$
    – Hhan
    Commented Apr 11, 2023 at 12:51
  • 2
    $\begingroup$ @Hhan yes, sure, depending on the background of the person, it may be easier to understand the algebraic aspects than to understand how the BKZ algorithm is projecting the vectors back from the sublattice to the "full" lattice (: I just meant that maybe it is not fair to blame the ring structure for the insecurity in this case $\endgroup$ Commented Apr 11, 2023 at 15:08

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.