Join Log in
Score:11
iammadab avatar Crypto

Why are finite fields so important in cryptography?

id flag
iammadab

I am just getting into cryptography and currently learning by trying to implement some crypto algorithms.

Currently implementing the Shamir secret sharing algorithm, what I have noticed is that finite fields keep coming up.

I just don't understand why they are relevant yet.

One thing I see is that they can make sure that none of your results are decimal, so no rounding errors, but I strongly doubt that is the reason they are so important. It would be great if someone could give me an intuition for why they are needed.

Also, does the fact that they are finite harm security?

3809
5 + 4
kelalaka avatar
in flag
kelalaka
Dlog is easy in reals and complex fields. Your question doesn't have a perfect answer. In Cryptography we rely on hard problems and form schemes on top of them. Researchers use them whenever available. Your insight mostly correct but no sufficient: [Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?](https://crypto.stackexchange.com/q/54263/18298)
4
Reply
fgrieu avatar
ng flag
fgrieu
Finite fields are important in cryptography because fields are important in science, and cryptography is a science that deals with finite sets.
1
Reply
TonyK avatar
us flag
TonyK
iammadab, Dlog means the [discrete logarithm problem](https://en.wikipedia.org/wiki/Discrete_logarithm). @kelalaka, I don't really see how iammadab was supposed to find this out -- it's not googlable.
0
Reply
kelalaka avatar
in flag
kelalaka
@TonyK out of context, however, if you paste a Google search result, there Google is using some tags on the query that may leak some information(never searched what are they!). I've deleted my unnecessary comments.
0
Reply
Score:17
Mark avatar Crypto
ng flag
Mark

One particularly important topic for this question is that of the encoding size. This comes from the following "trivial fact":

For an infinite set $A$, there does not exist some $s\in \mathbb{N}$ such that every $a\in A$ can be described in $s$ bits.

One can get around this issue by appealing to variable-length encodings, but this can easily lead to security issues --- it can be somewhat easy to passively get some information about the size of some encoded element. If this gave some indication of what element was encoded, this would be bad. So if you want objects in your cryptosystem to have some uniformly sized encoding, you're stuck with finite objects.

A (smaller) benefit to working in finite structures is that the uniform distribution exists. It is:

  • The maximum entropy distribution on a set
  • Invariant under bijections
    • This includes, for a group $G\ni g$, the bijection $x\mapsto x+g$, which is incredibly common.

These properties suffice to show security of the one-time pad, which is fairly fundamental, and one often wants to appeal to it (often after replacing "real" objects with idealized ones, e.g. replacing a PRG with a random function).

For certain infinite groups one can get distributions with similar properties, in particular the Haar measure. But it is much more technically complex, so the fact that the uniform distribution is so simple (while having great properties) is definitely a point in favor of finite-land, although less important than the fixed encoding size point in my eyes.

None of this answers why finite fields, instead of just finite algebraic structures. But often finite fields are used solely as a source of finite groups, for example $\mathbb{F}_p^\times$. One could argue why one wants groups rather than weaker algebraic structures, but I only have vague points on this topic.

Perhaps the final point is "why not finite structures" --- something like $(\mathbb{Z}/pq\mathbb{Z})^\times$ for $p, q$ of $\approx 1024$ bits is so ridiculously large that, while it is not technically infinite, it is "essentially" so --- for example, there are roughly $2^{270}$ atoms in the universe, which is much smaller than $2^{2048}$, so in a certain sense it is "larger than our universe" (while still being finite of course). While something like $\mathbb{R}$ is infinite, if one induces rounding errors (as you mention) you're likely working with floating-point approximations, which generally use at most $128$ bits, so one is actually (implicitly) working with a smaller finite set than the one cryptographers use.

0 + 0
Score:8
SSA avatar Crypto
ng flag
SSA

I will try to give generic answer to this.

A Finite Field denoted by ${F_p}$, where p is a prime number, works well with cryptographic algorithms like AES, RSA , etc. because of the following reasons:

  • We need to decrypt the encrypted message, this is only possible when a unique (bijective) inverse of a function is available. This is only possible when there is no zero divisor in the function and also it is injective and surjective too.

  • Also it gives closed operation, which means, any operation you do in the field, the result will remain in the field, this makes it vary easy to implement cryptographic algorithms.

  • Finite field generated by prime (prime number or irreducible polynomial) has these required characteristics.

  • It is not only used in Cryptography, but in channel coding like BCH or Reed-Solomon coding. it is pervasive in most of the communication error correcting codes, data/content security, also their extensions like Groups and Rings is used in Chemistry and other scientific fields.

0 + 4
poncho avatar
my flag
poncho
Minor note: RSA isn't done in a finite field...
3
Reply
ar flag
Ilmari Karonen
@poncho: It's somewhat interesting to note, though, that the RSA ring (of integers modulo $n=pq$) is "almost a field" in the sense that divisors of zero are rare and, in fact, finding a non-zero one is equivalent to factoring the modulus $n$ and thus breaking the cryptosystem.
5
Reply
poncho avatar
my flag
poncho
"almost a field' $\ne$ 'a field'
2
Reply
id flag
supercat
@poncho: RSA is "done" in a finite field, in that while the full ring of integers mod pq isn't a field, successful RSA operations will only use those parts of the ring where it behaves as a field (operations that stumble onto parts where it doesn't behave as a field will fail).
2
Reply
Score:5
avatar Crypto
bd flag
Jyrki Lahtonen

The points raised by Mark and SSA are the main things. We have a well studied class of structures that come together with suitable problems currently believed to be computationally intractable (in spite of being well studied). Actually all the affine linear mappings $x\mapsto ax+b$ are bijections (see what Mark said about maximum entropy) whenever $a$ is a non-zero element of the field. If we did not have a field in particular, this would not hold.

I also want to add a few properties of finite fields of characteristic two in particular ($GF(2^n)$ or $\Bbb{F}_{2^n}$):

  • The keyspace (or message space or whatnot) then has a size that is an exact integer number of bits. This is admittedly not a pressing concern. More like a convenience.
  • Having the field structure around makes it possible to analyze certain computationally efficient operations from the point of view of security. For example, the monomial functions have been studied extensively from the point of view of differential cryptanalysis. Search for APN (=Almost Perfect Non-linear) functions. With a more random structure such analyses would be more taxing.

However, there are also drawbacks to these fields

  • the extra structure means that for example the DLP may be more tractable than A) in a "black box" group of the same size, or even B) in a prime field of nearly the same size
0 + 1
bd flag
Jyrki Lahtonen
This is more like a comment, but too long for such. Apologizies for the consumed bandwidth.
2
Reply
Score:3
avatar Crypto
sa flag
K.G.

Why a field: The idea behind Shamir's secret sharing is both to reconstruct the secret (functionality) and prove that any shared secret is possible (security) using polynomial interpolation.

While polynomial interpolation can be done over many algebraic structures, it will always work over a field. (Over a field, a non-zero polynomial has at most as many zeros as its degree. Over other related algebraic structures, this is usually not true.)

While Shamir's secret sharing is usually done over fields, it has been done over many other algebraic structures. This usually requires great care and is complicated. Unless you really have to, doing it over fields is much easier and preferable.

Why finite: It is not sufficient for security that any shared secret is possible, every shared secret must also be (almost) equally likely. Using finite fields allows us to choose randomness from a uniform distribution, which turns out to give us exactly what we want.

We could work over an infinite field such as the rational numbers, but in this case it would be very difficult to get every shared secret to be almost equally likely. This is related to not having a uniform distribution on infinite sets. Roughly speaking, one way to look at it is that the size of the value is related to the size of the coefficients and where we evaluate, so if we want to hide one of the coefficients, we need to "drown it out" by having the other coefficients be much larger.

Doing it over the integers (not a field!) can be done, but getting to security requires quite a lot of work. As a side effect (at least for the scheme I have looked at), the shares end up being much bigger. You do not want these costs unless you have a good reason. (Which you do, sometimes.)

We could try to work over an approximation of an infinite field such as the real or complex numbers, but in this case things become much more complicated, since we must also deal with inexact arithmetic. I have not seen anyone trying to do this, except by mistake.

Other areas of cryptography: Finite fields are used all over cryptography. Typically, this is related to non-zero elements in fields having multiplicative inverses, which we very often want. The operation also has many other nice, provable properties.

The finite part is usually required for practicality, and sometimes because of particular properties of finite fields.

  • AES: One example is in the AES sbox, where many desirable properties follow from the algebraic properties. You would not get the same algebraic properties from the integers modulo 256 (a ring), for example.

  • Multiplicative subgroup: Another example is the multiplicative subgroup of the finite field (the non-zero elements of a finite field form a cyclic group), which for a carefully chosen finite field turns out to be a suitable group for d.log.-based cryptography. (Discrete logarithms are defined in a similar way to ordinary logarithms, but it turns out that in some groups they seem to be very hard to compute without a quantum computer.)

    In this case, we could also use certain rings, but it turns out that in practice prime finite fields are better for this sort of application. For instance, security does not depend on a secret group order, which allows us to do some things you cannot do if the group order is unknown. (RSA works over such rings, but has other properties and requirements.)

  • Elliptic curves: Yet another example are elliptic curves, which are extensively used in cryptography (even post-quantum crypto). While something very much like elliptic curves can be defined over other algebraic structures such as rings, the rich theory of elliptic curves requires working over fields.

    The study of elliptic curves is an important part of number theory, but for cryptographic purposes curves defined over infinite fields are impractical or unsuitable for functional purposes and do not have the required security properties. (For example, an approximate discrete log can be computed by looking at the size of the coordinates, which would have broken security, had it not first comprehensively broken practicality.) Even though elliptic curves defined over infinite fields are not used functionally in cryptography, their study is essential for the analysis of elliptic curve cryptography.

    Elliptic curves over certain finite rings have been considered in cryptographic contexts, but except for obscure cases do not offer anything of interest. (Elliptic curve factoring obviously excepted!)

  • Further examples: Lattice-based cryptography and code-based cryptography, which uses algebraic structures defined over finite fields. Multi-variate cryptography, which is based on systems of polynomial equations over finite fields.

    Again, much of this can be done over certain finite rings, but there are many disadvantages and not much to be gained.

0 + 0
Score:1
avatar Crypto
ph flag
bmm6o

For Shamir's Secret Sharing specifically, the Wikipedia article talks about why finite fields are used, instead of another ring. In a finite field, no information about the secret is leaked by knowing a number of shares below the threshold. The reason for this is that every function on a finite field is has a unique polynomial representation (of degree at most q-1)

0 + 0
ธงชาติไทย
Elon Musk
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.