Score:1

How does big Galois groups yield better security in NTRU Prime?

tc flag

I'm still kinda new to Galois theory so I apologize if this question is very obvious to some people.

Basically I'm reading this paper by the NTRU Prime team and in section 2.5 it's explaining how cyclotomic fields should be replaced with prime degree fields with "big Galois group", namely because how structures within cyclotomic fields (e.g. subfields and automorphism) can potentially lead to an attack in the future, it then states "Fields with big Galois groups are far from having automorphisms". Is it true to assume this means that if a field's Galois closure is big (i.e. its Galois closure has a lot of automorphisms), then the field itself would have very few automorphisms, thus less structure to work with when developing an attack?

It also goes on to state how NTRU Prime field has a Galois group of size p!, whereas NTRU field's has size p-1. How exactly does the size of the Galois group correlate to security of the KEM?

Score:0
ng flag

It is hard to answer this question, as what you are reading is speculation on the part of Bernstein about a hypothetical weakness in standard lattice-based cryptography (i.e. using cyclotomics, with unusually small Galois groups). This speculation roughly proceeds as

  1. cyclotomics have very small galois groups (the $n$th cyclotomic has galois group $(\mathbb{Z}/n\mathbb{Z})^\times$ I believe, compared to $S_n$ for a random polynomial)
  2. this means that compared to random polynomials, cyclotomics are quite structured, and therefore
  3. we should replace cyclotomics with unstructured (relative to random) polynomials.

It is not bad reasoning, but the speculation that better attacks exist against cyclotomics (versus polynomials with larger galois groups) hasn't really panned out, i.e. it has remained within the world of speculative things to worry about. Note that there have been better attacks against other specific (non-cyclotomic) polynomials, see for example this. There have also been other attacks against non-RLWE knapsack-type problems that took advantage of Galois-theoretic symmetries, see for example this.

This is compounded by the following fact. The initial worry was that picking the polynomial $f$ improperly such that arithmetic is defined over $\mathbb{Z}_q[x]/(f)$ could lead to attacks. There has been a line of work provably addressing this concern that goes by the name of "Middle Product LWE". The idea is that one can define a product operation on $\mathbb{Z}_q[x]$ such that, for an exponentially large family of $\{f_i\}_i$, if RLWE is hard for any of the rings $\mathbb{Z}_q[x]/(f_i)$, then Middle Product LWE is secure. See this for a sample paper on the topic. So if you are concerned that power-of-two cyclotomics are plausibly weak, it is perhaps better to move to Middle Product LWE instantiations, rather than pick another $f_i$ out of a hat and hope it is strong.

faust avatar
tc flag
Thanks for pointing out the existence of MP-LWE it is pretty interesting. I was looking for a MP-LWE based KEM and I found a NIST PQC candidate called Titanium, but I couldn't really find any elaboration on why it failed to pass the first round. I'm assuming it's due to MP-LWE's large key size and ciphertext?
Daniel Apon avatar
co flag
Titanium's key size, ciphertext size, and running time were significantly closer to the costs of Plain LWE systems than other structured-LWE-based systems. So, if you're willing to pay the costs of Titanium, you might as well pay the costs of, say, FrodoKEM (and have 'no structure' at all).
I sit in a Tesla and translated this thread with Ai:

mangohost

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.