Galois theory and cryptography

Question

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?

Answer 1

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.

Answer 2

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.