1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – faust
    Jun 13, 2023 at 4:44
  • $\begingroup$ 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). $\endgroup$ Jul 28, 2023 at 18:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.