When working in a subgroup of EC in EdDSA (especially Ed255190), how is it OK to use operations different from that of the main group?

Question

Ed25519 uses a composite order Elliptic Curve but works in the prime order subgroup of the main group. As per group theory, the subgroups use the group operation.

However, as per this, Ed25519 implementations don't do this.

But every existing implementation implements scalar arithmetic $\bmod q$, the order of the prime-order group, not $\bmod 8q$, the order of the full group.

Here, the order of the main group is $8q$ with $q$ as the prime.

This is kind of confusing.

• Why do Ed25519 implementations do this?
• If the operations are done under a different subgroup operation, then are we not just working in a totally different Elliptic Curve - i.e. an Elliptic Curve defined over a prime field ($\bmod q$) - what is the point of having the parent group at all?
• What are the advantages & disadvantages of doing this?

Answer 1

The statement

every existing implementation implements scalar arithmetic $\bmod q$, the order of the prime-order group, not $\bmod 8q$, the order of the full group.

does not imply that working in a subgroup, it is used operations different from that of the main group. The group operation is point addition among two Elliptic Curve points, and is the same in the subgroup and the group. Scalar multiplication involves an integer $k$ and a point $P$, and produces a point $[k]P$ defined as $\underbrace{P+P+\ldots+P+P}_{k\text{ times}}$.

My understanding is that the quote states that implementations use that $[k]P=[k\bmod q]P$, which is valid when $P$ belongs to a subgroup of order $q$.

Answer 2

Little preamble on EC(C)

In cryptography, we use an Elliptic Curve (EC) over a finite field. To form an EC over a finite field, first, select a finite field $\mathbb F_p$ where $p$ is either a prime or a prime power ($\mathbb F_{p^m}$) ( also written as $GF(p)$ due to Galois)^* than the curve equation. The points with integer coordinates that satisfy the curve equation are called the points of the curve ( rational points). These points form an abelian group under the point addition ( the tangent-cord rule). Now, we need to determine the order of the group. One can use Schoof's algorithm ( or Schoof–Elkies–Atkin algorithm faster under heuristic assumptions)

Once we have the order, we can talk more about the group $\#E(k)$, is it prime or not? If it is prime we have a prime curve where all the elements ( except the identity - most of the time it is the point at infinity) are a generator. In the case the order of the curve is not prime we have a cofactor $h = \#E(k)/n$ where $n$ is the largest prime order subgroup.

However, as per this, Ed25519 implementations don't do this.

But every existing implementation implements scalar arithmetic $\bmod q$, the order of the prime-order group, not $\bmod 8q$, the order of the full group.

Because that is not formally defined for Ed25519 to work in the prime subgroup or in the full group as Mike Hamburg states in their Decaf paper.

Implementation-defined behavior. Some systems, such as Ed25519 [7], do not specify behavior when the inputs have a nonzero h-torsion component. In particular, Ed25519 signature verification can be different for batched vs singleton signatures, or between different implementations. This can cause disruption in protocols where all parties must agree on whether a signature is valid, such as a blockchain or Byzantine agreement. In other cases, it may make it easier to fingerprint implementations.

Let the point $P$ has order $q$, then we have $[q]P = \mathcal{O}$. The modulo operation on the scalar multiplication $[k]P= [k \bmod q]P$ eliminates the unnecessary scalar calculations. This simply uses the quotient remainder theorem; $$[k]P = [d\cdot q + k \bmod q]P = [d\cdot q ]P + [ k \bmod q]P = [k \bmod q]P$$

• Why do Ed25519 implementations do this?

As far as I know, there is no attack on this like Lim–Lee's active small-subgroup attacks on ECDHE. High probably, the one programmer chose this to be on the safe side and the others chose to be the same so that they can verify each other's signatures.

• If the operations are done under a different subgroup operation, then are we not just working in a totally different Elliptic Curve - i.e. an Elliptic Curve defined over a prime field ($\bmod q$) - what is the point of having the parent group at all?

Well, as we discussed in the preamble, we are not in a different Elliptic curve. Once we formed the curve, we are working in an abelian group as usual and with the scalar multiplication, we have a $\mathbb Z$-module.

Prime curves are safer than non-prime curves since the Lim-Lee attack is not applicable, however, this is one side. Curves with a cofactor greater than 1 provide faster addition formulas like the Montgomery ladder that beats the much slower Joyce ladder. Montgomery curves have cofactor>1. Every Montgomery Curve is birationally Equivalent to the Edward curves that brings the fast addition law to every Montgomery Curve ( one needs an element 4 to have birationally equivalent Theorem 3.3)

• What are the advantages & disadvantages of doing this?

Interoperability. Nothing more as far as we know.

---

^*Normally, It is generally written as $\mathbb{F}_q$ where $q$ is either a prime or prime power. When it is only prime $\mathbb{F}_p$ is preferred ($\operatorname{GF}(p)$). For the sake of the question, we switched $p$ with $q$.

Answer 3

every existing implementation implements scalar arithmetic $\operatorname{mod} q$

This works perfectly in all scenarios as long as all scalars and all EC points are trusted or validated.

Just in case it's not perfectly clear (I misread it the first time myself):

All they're saying is that when there is a scalar operation with another scalar (e.g. addition, subtraction, multiplication), the result is reduced $\operatorname{mod}q$.

Scalars are validated by checking they are less than $q$, and EC points are validated as being in the prime subgroup by multiplying them by $q$ and checking the result is the point at infinity.

When you're working with trusted or validated scalars/points, you don't have to worry about any of the problems discussed in the post you've linked to.

The reason that libraries don't validate is that depending on the scenario, there is no advantage to performing the validation, and the validation has a computational cost due to the additional scalar multiplication involved to validate the EC point.