There are a large number of algebraic NTRU variants: for example, in some (such as ETRU), the underlying ring has been changed to the ring of integers of a certain number field; there is GR-NTRU, which is over group rings; there is NTRU over quaternions, and octonions, and even sedenions; and there are various other non-commutative and non-associative schemes. I am aware that non-commutativity helps avoid an attack of Coppersmith and Shamir, but my question is the following: are any of these variants considered essentially superior to standard NTRUEncrypt? Is the more exotic algebraic structure of these variants considered preferable by experts, or are these schemes academically interesting but impractical/not trusted for real world use?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
If one expands the discussion to include LWE-type schemes, isn't Module-LWE naturally a "non-commutative" hardness assumption which has practical applications? For example, the Kyber NIST PQC candidate is an MLWE scheme, and is a round 3 finalist.
In general though, I mostly see lattices over "exotic" (at least more so than things like RLWE/MLWE) algebraic structures discussed by coding theorists (two specific examples are Fredrique Oggier and Cong Ling). As there seems to be a larger theoretical basis of research on "that side" of things, it might be easier to search for practical applications.
-
$\begingroup$ It's unclear to me in this answer what you mean with "that side" of things. I presume you mean RLWE/MLWE? And I don't understand "it might be easier to search for practical applications" either - for what purpose exactly / easier than what? $\endgroup$– Maarten Bodewes ♦Feb 1, 2021 at 19:17
-
$\begingroup$ I mean that I think it is plausible that there are benefits to lattices built from exotic algebraic structures (for example, one of the most natural constructions of the Leech lattice is as a rank 3 lattice over the octonians), but I have personally seen a stronger tradition of "investigating lattices from exotic algebraic structures" from coding theorists, not cryptographers. This could be because they are uniquely useful to coding theory, they are useful to neither (and theorists in coding theory are just having fun), or they are useful to both but coding theory is just "ahead of the curve". $\endgroup$– MarkFeb 1, 2021 at 19:36
-
$\begingroup$ It's worth mentioning (RE the Leech lattice comment) that there do not appear to be significant applications of the leech lattice within lattice cryptography, although this is partially due to cryptographers liking powers of two and the leech lattice having dimension 24 (see this for some analysis), which lead to a "mismatch" when one tries to use a 256-dimensional lattice for error correction. I am not convinced this is a fundamental obstacle, but it was the "stopping point" for the above masters thesis. $\endgroup$– MarkFeb 1, 2021 at 19:39
-
$\begingroup$ Ah, now I get it, it was indeed pointing to the coding theorists, I'd expect something like "their side of things" in that case, so I misread. $\endgroup$– Maarten Bodewes ♦Feb 1, 2021 at 22:44
-
$\begingroup$ @mark In what sense are you saying that MLWE is non-commutative? Though I agree that MLWE has more algebraic structure and is also very useful - for example, it has had wide use in schemes participating in NIST's post-quantum standardization process (cf. Saber, a module LWR scheme). However, I note that none of the NIST contenders are algebraic NTRU variants... $\endgroup$– a196884Feb 2, 2021 at 10:14