What does "underlying field" mean in the context of groups?

489 Views Asked by At

I read a statement in this answer which said "In conics, the discrete logarithm problem of this group (conics) is no more difficult than the discrete logarithm over the underlying field".

Every field is a group (in the way that a field has a group inside it) - Groups are subsets of fields, every group isn't a field.

So I am unable to understand the concept of "underlying field" of a group. If any group is a field, then all fields have an underlying group (and not the reverse) - so what exactly does underlying field of a group mean?

1

There are 1 best solutions below

3
On BEST ANSWER

There are a bunch of issues here in what you write. In particular, you have misidentified what "underlying field" refers to (it's not about the group in question, but about the conic in question). The answer to the question in the subject line, what does 'underlying field' mean in the context of groups, is "nothing". But that's because of the aforementioned misunderstanding. It will take a while to explain what the quote says, and I will likely say things you already know/understand, but it is difficult to pinpoint those through comments. So please have some patience.

Groups

Almost-formally speaking (there are other ways, and one would define a group as an ordered list of information, etc. but pay not attention to that), a group is a set $G$, together with a binary operation $*\colon G\times G\to G$, usually denoted in infix position or by juxtaposition (so $a*b$ instead of $*(a,b)$, and $ab$ instead of $a*b$), that satisfies the following three conditions:

  1. $*$ is associative: for all $a,b,c\in G$, $a(bc)=(ab)c$.
  2. There exists an element $e\in G$, called "the identity of $G$", such that for all $a\in G$, $ae=ea=a$.
  3. For each $a\in G$ there exists a $b\in G$ such that $ab=ba=e$, where $e$ is the same element from part 2.

The notion of group is extremely versatile, and instances of it show up a lot, as you know. There are some surprising ones, including the group of points of an elliptic curve. A close variation is the group of points on a conic (which I will get to below).

If we want to consider the set on which we have defined a group, we often talk about "the underlying set of the group", as if we had a set as substructure and we put the group stuff "on top" of it.

Conics

Take your favorite field; there's $\mathbb{Q}$, there's $\mathbb{R}$, there's $\mathbb{C}$; there's the field of rational functions with real coefficients $\mathbb{R}(x)$; there's finite field of prime order $\mathbb{F}_p$ (or $GF(p)$), which are essentially the rings $\mathbb{Z}/p\mathbb{Z}$. But there are other finite fields: for every prime $p$ and every positive integer $n$, there is exactly one, up to isomorphim, field of order $p^n$. Wikipedia includes some explicit examples of constructions.

In analogy to how we do analytic geometry on the real plane, we can do analytic geometry over any field $k$. You consider the collection of ordered pairs, $$k^2=\{(x,y)\mid x,y\in k\},$$ called the affine plane over $k$, and call its elements "points". You can then take an equation $p(x,y)=0$ (not necessarily polynomials; any equation involving $x$, $y$, constants from the field, addition, multiplication, division, etc), and ask for all pairs that satisfy the equation. That is the "curve" defined by $p(x,y)=0$.

Note that if you have several fields fitting inside each other, say $\mathbb{Q}\subseteq \mathbb{R}\subseteq \mathbb{C}$, you can consider the affine planes as fitting inside each other, and the same equation may (if all constants are taken from the smallest field) determine curves in each of them. We can imagine the "rational affine plane" as being literally "inside" the real affine plane (it consists of points with both coordinates rationals). So if we take, for example, the equation $x^2+y^2-1=0$, this defines the unit circle in $\mathbb{R}^2$, and we can imagine sitting inside of it the "unit circle" in $\mathbb{Q}^2$, consisting of some of the points in the unit circle.

A conic over the field $k$ is the curve determined by a degree 2 polynomial equation.

Group of points of a conic

“Incidentally, am I alone in finding the expression “it turns out” to be incredibly useful? It allows you to make swift, succinct, and authoritative connections between otherwise randomly unconnected statements without the trouble of explaining what your source or authority actually is. It’s great. It’s hugely better than its predecessors “I read somewhere that...” or the craven “they say that...” because it suggests not only that whatever flimsy bit of urban mythology you are passing on is actually based on brand new, ground breaking research, but that it is research in which you yourself were intimately involved. But again, with no actual authority anywhere in sight. Anyway, where was I?” -- Douglas Adams, The Salmon of Doubt

It turns out that one can take the points on a conic over $k$, and turn this set into a group by using a geometrically defined operations.

This can probably best be imagined with a circle on the plane (as in the link you provide): take your conic, and fix a point $Z$ on it. If $P$ and $Q$ are points on the conic, here is how we define $P+Q$ (the operation here is denote $+$):

  1. Start by taking the line through $P$ and $Q$; if $P$ and $Q$ are the same point, you take the tangent at the point $P$. (For conics, these can be defined geometrically easily enough, so we don't need to worry about calculus or the geometry involved). Call this line $L_1$.

  2. Now take the line through $Z$ that is parallel to $L_1$. Call this line $L_2$.

  3. One can prove that the line $L_2$ intersects the conic in exactly two points, one being $Z$. Denote the other point by $R$ (if the line is tangent to the conic at $Z$, then this "other point" is also $Z$).

  4. Define $P+Q$ to be $R$.

It is not hard to check properties 2 and 3 of a group for this definition. For example, $Z$ will be the identity: given a point $P$, the line through $P$ and $Z$ is parallel to itself, and the "other point" it intersects the conic with besides $Z$ is $P$ itself, so $P+Z=P$. (The operation is commutative, since the line through $P$ and $Q$ is the same as the line through $Q$ and $P$, so I only need to check $P+Z$). This proves $2$. For property $3$, take the line through $P$ that is parallel to the tangent at $Z$; this line intersects the conic at a second point besides $P$; call it $Q$ (if the line is tangent to the conic at $P$, then $Q$ is the same as $P$). Then $P+Q=Z$.

The hardest part of proving this is a group is the associativity of this operation. I won't show it, but it turns out (there's that phrase again) that this is associative, and so defines a group.

This is what is called "the group of the conic."

Added in light of comments. The definition of this group depends on the field. The fact that intersections occur and so on is because we are in a field. In fact, one can find rational functions $f$ and $g$ with coefficients in the field such that if $P=(p_1,p_2)$ and $Q=(q_1,q_2)$, then $P+Q$ will have coordinates $(f(p_1,p_2,q_1,q_2), g(p_1,p_2,q_1,q_2))$. However, this group (while depending on the field for its definition) is not isomorphic in any way to the field. For example, if the field is $\mathbb{Q}$ and the conic is the unit circle, the antipode of the point $Z$ has order $2$; but the additive group of rational numbers does not have any element of finite order other than $0$. The group of points is not isomorphic to the group $\mathbb{Q}$ in any way.

Discrete logarithm

Consider a finite field $k$; it turns out that the multiplicative group of the field (the group consisting of the nonzero elements of the field, with the operation of multiplication) is a cyclic group; let $g$ be a generator.

If the field has $p^n$ elements, then every nonzero element of $k$ can be written uniquely as $g^a$ with $0\leq a\lt p^n-1$.

The discrete logarithm problem for $k$ relative to $g$ is the following: given a nonzero element $x\in k$, find $a$, $0\leq a\lt p^n-1$ such that $x=g^a$. That is, find the "logarithm of $x$ to the base $g$".

In the real numbers, we have some very fast algorithms to compute $\log_b(x)$ for any $b$ and any $x$. The same is not true in finite fields. If the field is small enough, we can just list all the powers of $g$ until we spot $a$. But if the field is very large (say, order $2^{15}$), then this is no longer feasible. We have some algorithms to make the calculation a little better than blind guessing or trying to figure it out by listing everything, but this is still considered a hard computational problem.

The discrete logarithm problem is the basis of some cryptographic systems or algorithms, such as the Diffie-Hellman Key Exchange. If you want to use algorithms whose security is no better than the difficulty in solving the discrete logarithm problem, then you want the specific implementation of your problem to be hard. As computers get better and algorithms get better, a specific field that used to be "very big" will suddenly be not so big. Also, if you keep using the same field, then people can see and collect information over time, that may make a look-up faster.

Now, there is nothing special about a field. Given any group $G$, and any element $g\in G$, we can consider the cyclic group generated by $g$, denoted $\langle g\rangle$. If it has order $n$, then every element $x\in\langle g\rangle$ can be written uniquely as $g^a$ with $0\leq a\lt n$. So we can define a "discrete logarithm problem in $G$ relative to $g$: given $x\in \langle g\rangle$, find $a$ such that $g^a=x$ and $0\leq a\lt n-1$.

Here is where how you describe the group matters. Consider the discrete logarithm for the field of $13$ elements. This is a cyclic group of order $12$, and one of its generators is $2$. The powers of $2$ modulo $13$ seem to be somewhat random: $$1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7.$$ so if I ask you for the discrete logarithm of $9$, it will take you a second to look through the list and see that $9$ is in position $9$, so that the discrete logarithm base $2$ is $8$.

As a group, abstractly, this multiplicative group is "just" the cyclic group of order $12$. Now, you can take the integers modulo $12$, with generator $1$. There is an isomorphism between this group and the multiplicative group above. But the "discrete logarithm problem" in the integers modulo $12$ is must easier: if I ask you what is the "discrete logarithm" base $1$ of $8$, it is obviously $8$! (Here we are using an additive group, so we are asking for an $a$ such that $1a=8$). No thought necessary. Even changing the generator (say, to $5$, doesn't get you much, because asking for the "discrete logarithm" base $5$ of $8$ in the integers modulo $12$ amounts to solving the congruence $5x\equiv 8\pmod{12}$, and we have very fast algorithms for solving these problems, even if the modulos is really big.

Moral: The difficulty of the discrete logarithms problem depends not only on how big the group is, but also of how we "know" the group: how it is presented/stored/etc.

Using conics?

Because the discrete logarithm problem over finite fields requires constantly staying ahead of the state of the art, it was suggested to instead use other groups in which the problem might be difficult. Koblitz, for example, suggested using elliptic curves because there are good algorithms for computing "powers" of an element, but we don't have good algorithms for the discrete logarithm problem in them. The advantage is that if you pick a finite field which is fairly large, instead of having just one field of that size, you have lots of elliptic curves over that field, so that you can switch curves and keep your same algorithms.

Now, to define an elliptic curve to use you need two things: the equation of the curve, and the field you are using. That field is called, finally, the underlying field of the elliptic curve,

It turns out that the difficulty of solving the discrete logarithm problem on an elliptic curve over a field $k$ is generally harder than solving it for the field $k$. So it is worth your while to use elliptic curves, because you can do so with fields that are "smaller", you have lots of options of curves to use, and you still have the security of a harder problem (as if your field were much larger).

So one might wonder if we can do the same thing with conics instead of elliptic curves, because conics are easier, and the operation on conics is easier than the operation on elliptic curves. If the discrete logarithm problem for a conic defined over a field $k$ Is generally harder than the discrete logarithm problem in $k$, then you can get the same advantages as for elliptic curves above: use a smaller field, have lots of options of conics to use, yet still have much better security than if you were just using the field.

Finally an explanation of your quote

What this quote is saying is that this hope is not to be. If you have a conic defined over a field $k$, then solving the discrete logarithm problem for points on the conic is no harder than solving it for $k$.

That's what the quote means. The "underlying field" refers to the field over which you are doing the definition of the conic, figuring out the points, finding lines and intersections, etc. It refers to the conic and its geometry; it does not refer to a random group.

Given an abstract group, there is no "underlying field" lying about.

Given a conic, the "underlying field" is the field over which we are doing the geometry that defined the conic.