Why crypto algorithms are primarily based on finite fields?

Question

I want to learn why people use finite fields in cryptography? I mean there are other fields like number fields, function fields that are not finite. There are also some other topological fields, like local and global fields, where we cannot discuss about finiteness (as long as I know). But, why finite fields? If someone can help me understand why mathematically other fields don't work, I would be glad. On the other hand, are there any other fields that work too?

Answer 1

The problem with other fields is precisely that they are not finite. We are talking about computer information, which deals in blocks of 1s and 0s. Any real number can only be stored by a computer as an approximation, and while rational numbers can be stored accurately as a pair $(m,n)$ (to represent $m/n$), even that is subject to limitations in a computer because there is typically a largest integer that the computer can store. Similar problems come up for other infinite fields.

So that is why we use a finite algebraic structure instead of an infinite one. So then the real question is, why a finite field instead of some other structure? Fields have a lot of structure, which makes it convenient to do computations but also that structure leads to weakness in cryptographic applications because it can be exploited. Fortunately solving logarithms in finite fields (the discrete log problem) seems to be difficult enough (for now) that finite fields are acceptable.

Things are moving away from finite fields recently though, and into elliptic curve cryptography. Finite fields are still involved, to define the curve, but the algebra involved in encrypting/decrypting is based on an algebraic group defined by the curve. This should still be secure if progress is made towards solving the discrete log problem in finite fields (rather, the hope is that the discrete log problem in an elliptic curve group is more difficult than in a finite field, though this is not known for sure).

Answer 2

You can easily map information into a finite field. For example, if you're working on $F_{p^n}$ where $p$ is prime, you write your data in base $p$. Its not entirely obvious how to do this for other fields (e.g. how would you encode and transmit something in $\mathbb{R}$? Most real numbers would require infinite bits. You want something with finite storage requirements and some structure).

And the algebraic structure has a good amount of theory to it for finite fields, and computationally efficient operations. This is useful for designing algorithms to encrypt and decrypt.