Attacks on Ring-LWE exploiting structure of ideal lattice?

Lee Seungwoo

4/7/24, 8:12 AM

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.

0 + 6

lattice-crypto

ring-lwe

Hhan

4/7/24, 9:13 AM

There *exist* some attacks exploiting the ring structure; see, e.g., https://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.

Mark

4/8/24, 5:20 PM

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.

Hilder Vitor Lima Pereira

4/10/24, 5:07 PM

@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](https://eprint.iacr.org/2021/999), where a matrix version of NTRU (so no structure) is also attacked.

Hhan

4/11/24, 12:51 PM

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

Hilder Vitor Lima Pereira

4/11/24, 3:08 PM

@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

Lee Seungwoo

4/12/24, 1:25 AM

I appreciate all your answers. I will check the links and what you mentioned. Thank you all.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Attacks on Ring-LWE exploiting structure of ideal lattice?

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.