9

I'm trying to find applications of Galois theory in different areas. Currently the most interesting for me is the cryptography. As I understood the theory of finite fields (a part of Galois theory) has a strong connection with cryptography. My question is the following:

Is there an important cryptographic problem that cannot be solved without the Galois theory application?

Kenta S
  • 16,151
  • 15
  • 26
  • 53
Ivan
  • 347
  • 2
    BTW, as you seem to be interested in all applications of Galois theory I want to make sure you have heard of cyclic division algebras and their use in multiantenna signal constellation design. The Golden code is possibly the best known example of those. Those are about (simple) Galois theory of suitable number fields. – Jyrki Lahtonen Apr 16 '17 at 07:24
  • 3
    Maybe this question should have been asked on the cryptography stack exchange site. In any case, while Galois fields are frequently used in cryptography, the use of Galois theory itself is actually limited. (I do not consider just using finite fields to be Galois theory.) – AnotherTest Apr 16 '17 at 07:33
  • I've looked at the Golden code and it seems to be very close to that I am looking for. – Ivan Apr 16 '17 at 14:32
  • 3
    Finite fields are useful. But you can study those without any Galois theory. I think Galois theory is totally irrelevant for cryptography as it is currently done. – Henno Brandsma Apr 17 '17 at 09:35
  • 1
    Agree with Henno and others. You can grok finite fields without Galois theory. In coding/crypto communities they just happen to be called Galois fields, and denoted $GF(q)$ (in favor of $\Bbb{F}_q$ which seems to be more common elsewhere in math). – Jyrki Lahtonen Apr 18 '17 at 19:30
  • I begin to understand why I could not find the requested info. I also could find only few examples of practical usage for the Galois theory. One of them is the Golden code mentioned by Jyrki Lahtonen – Ivan Apr 18 '17 at 20:05

2 Answers2

7

Your question is a bit difficult to answer precisely. Or may be I am the wrong person to attempt an answer :-). Giving my impressions anyway.

  • Finite fields play a role in many suggested cryptosystems such as McEliece, Elliptic curve crypto, XTR, possibly others I'm not aware of. But from the crypto point of view they just provide the playground of a hopefully untractable discrete logarithm problem (ECC, XTR) or another problem known to be in one those nasty NP-categories in terms of complexity (McEliece).
  • But I don't think that finite fields are essential to setting up the scene for those problems known (or believed) to be ultra difficult to crack computationally. You can certainly look elsewhere. Word problem for braid groups has been suggested, as well as the closest lattice point problem in NTRU. In this sense finite fields are not at all necessary for crypto - just one of the alternatives. They are a natural alternative because they provide you with a way of doing arithmetic with all the field operations without any chance of overflows/underflows ruining your day.
  • In fact, when discussing elliptic curve cryptography with cryptopeople my enthusiasm with the beautiful algebra of ECs raised philosophical concerns. If there is a lot of deep algebra and geometry going on, it may turn out that the problem can be cracked with those powerful theories. This is important. Ideally cryptopeople would like a largely unstructured (hence hopefully untractable) way of going about their business. They want high entropy, and if you have a lot of math going on, order may emerge out of that chaos.
  • On the other hand, the cryptopeople don't want to be caught as snake-oil peddlers. They cannot sell a system that hasn't been studied adequately, and thus can be honestly advertised as being secure against known attacks. So they need math problems that have been studied long and hard, and are known (or strongly believed) to be nasty complexity-wise. They depend on well-studied math for providing such problems.

My impression is that the trade-off game of the last two bullets is the key. The exact math problem is not important as long as it meets the two somewhat contradictory goals.

Summary: Finite fields (or Galois theory if you prefer that way) are probably not essential to secure crypto, but they offer the playground for suitable problems that can be translated to cryptoprimitives.

Jyrki Lahtonen
  • 133,153
5

I think Jyrki's answer is great, and I completely agree with it. It focuses on public key cryptography, which is probably most interesting from a mathematical point of view. Let me try to give what I think is a nice example from symmetric cryptography, which again is more finite field theory than Galois theory.

Perhaps the most well-known example is AES, the Advanced Encryption Standard. It works with 8-bit values (i.e. bytes), which are thought of as elements in $\mathbb{F}_{2^8}$. To be more precise, of $\mathbb{F}[x]/(x^8+x^4+x^3+x+1)$. All AES operations can be expressed by $\mathbb{F}_{2^8}$-operations.

A different example which I like myself, is that of Linear Feedback Shift Register. It is a way to approximate an "infinitely" long random strong by only using a small input. This way you can easily store a small secret, and generate a lot of randomness from it. You can do this as follows:

Suppose our key is an $n$-bit value $f$. We choose a degree $n$ primitive polynomial $p(x)\in\mathbb{F}_2[x]$. We think of $f\leftrightarrow f(x)$ as a polynomial in $\mathbb{F}_2[x]/(p(x))$, where each bit of $f$ corresponds to a coefficient of $f(x)$. Let $z_i$ be the most significant bit of $f\cdot x^i$. Then our LFSR takes as input $f$, and outputs $z_0,z_1,z_2,\ldots$. This construction is called a Galois LFSR.

Since $p$ is primitive, $x$ generates $\mathbb{F}_{2^8}^*$. Therefore the values $f\cdot x^i$ loop through all of $\mathbb{F}_{2^8}^*$ before repeating. Hence if $n$ is large enough, this will not repeat itself. As it turns out, this is hopelessly broken on its own. However, it can (and it is) be used as part of a larger construction, as it is really fast and lightweight.

CurveEnthusiast
  • 942