Regarding Equation 5.44, Example 92 and Exercise 82

Question

Regarding Equation 5.44, Example 92 and Exercise 82

Opened this issue a year ago · 8 comments

We (together with @bufferhe4d & @skaunov) have reason to believe that eqn 5.44 is wrong (or missing details), and the following logic within example 92 is also fallacious. Furthermore, the problem with 5.44 becomes an issue for exercise 82.

About the Exercise

The discussion began during exercise 82. If you find the full 2-torsion group for TinyJubJub (TJJ), you end up with 2 elements. The book tells us that we should have 2^2 elements instead.

Furthermore, 5.44 tells us that $\forall n > k(r)$ we should have:

$$ E(\mathbb{F}_{p^n})[r] = E[r] $$

In this case, since $k(2) = 1$ we should expect the torsion groups for all extended curves to be equal. However, for this exercise we seem to have a different outcome, where the number of elements in the torsion group alternate between 2 and 4, instead of being equal for all $n$. I will add a snippet in the comment for this below.

About the Example

The problem with example 92 is that after the torsion group is computed for $k=4$ (the embedding degree), the torsion group for $k=3$ is computed to show evidence that indeed torsion group for $k=4$ is the full-torsion group. However, we think this should only be the case if the checked $k'$ is a factor of $k$, which would be if $k=2$ for instance. Since 3 is not a factor of 4, the example does not make sense on this part.

How this can be a problem is also shown in the exercise above, where equality does not hold for all extended curves.

About the Equation

With all that said, could there be a certain set of conditions that make 5.44 true, that do not hold for exercise 82? In particular, the scenario when embedding degree is 1 feels like the problem.

Thanks to @bufferhe4d and his discussion with several people, we have learned that when $k(r)=1$, it is not necessary to have $r^2$ elements in the full $r$-torsion group.

Answer 1 · 2023-11-04T14:15:01.000Z

Consider the following Sage code:

def exercise82(max_k: int = 7):
    # curve parameters for TJJ_13
    p = 13
    a, b = 8, 8

    F13 = GF(p)      # field
    F13t.<t> = F13[]  # polynomial ring # type: ignore 
    r = 2            # prime factor


    def pairings(E, E_tor):
        # frobenius
        def fro_pi(P):
            if P != E(0):
                (x, y) = P.xy()
                return E(x^p, y^p)
            else:
                return P

        G1 = [P for P in E_tor if fro_pi(P) == P]
        print("G1:", G1)
        # {(4 : 0 : 1), (0 : 1 : 0)}

        G2 = [P for P in E_tor if fro_pi(P) == p*P]
        print("G2:", G2)

    # try for some values of k
    for k in range(1, max_k):
        # curve
        if k == 1:
            # over base field
            TJJ = EllipticCurve(F13, [a, b])
        else:
            # over extension field
            F13_K = GF(p^k, name='t', modulus=F13t.irreducible_element(k)) # type: ignore 
            TJJ = EllipticCurve(F13_K, [a, b])
    

        # r-torsion group over base curve
        TJJ_tor = TJJ(0).division_points(r)
        print("{}-torsion over p^{} ({} elements)\n{}".format(r, k, len(TJJ_tor), TJJ_tor))
        pairings(TJJ, TJJ_tor) 
        print("")

Running this for $k$ up to 12, we get:

2-torsion over p^1 (2 elements)
[(0 : 1 : 0), (4 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

2-torsion over p^2 (4 elements)
[(0 : 1 : 0), (4 : 0 : 1), (2*t + 10 : 0 : 1), (11*t + 12 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

2-torsion over p^3 (2 elements)
[(0 : 1 : 0), (4 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

2-torsion over p^4 (4 elements)
[(0 : 1 : 0), (4 : 0 : 1), (2*t^3 + 7*t^2 + 5*t + 7 : 0 : 1), (11*t^3 + 6*t^2 + 8*t + 2 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

2-torsion over p^5 (2 elements)
[(0 : 1 : 0), (4 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

2-torsion over p^6 (4 elements)
[(0 : 1 : 0), (4 : 0 : 1), (7*t^5 + 8*t^4 + 12*t^3 + 2*t + 1 : 0 : 1), (6*t^5 + 5*t^4 + t^3 + 11*t + 8 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

2-torsion over p^7 (2 elements)
[(0 : 1 : 0), (4 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

2-torsion over p^8 (4 elements)
[(0 : 1 : 0), (4 : 0 : 1), (3*t^7 + 2*t^6 + t^5 + 9*t^4 + t^3 + 9*t^2 + 4*t + 2 : 0 : 1), (10*t^7 + 11*t^6 + 12*t^5 + 4*t^4 + 12*t^3 + 4*t^2 + 9*t + 7 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

2-torsion over p^9 (2 elements)
[(0 : 1 : 0), (4 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

2-torsion over p^10 (4 elements)
[(0 : 1 : 0), (4 : 0 : 1), (6*t^8 + t^6 + 11*t^5 + 7*t^4 + 2*t^3 + 5*t^2 + 7*t + 4 : 0 : 1), (7*t^8 + 12*t^6 + 2*t^5 + 6*t^4 + 11*t^3 + 8*t^2 + 6*t + 5 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

2-torsion over p^11 (2 elements)
[(0 : 1 : 0), (4 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

2-torsion over p^12 (4 elements)
[(0 : 1 : 0), (4 : 0 : 1), (11*t^10 + t^9 + 2*t^8 + 11*t^7 + t^5 + 4*t^4 + 3*t^3 + 2*t^2 + 6*t + 3 : 0 : 1), (2*t^10 + 12*t^9 + 11*t^8 + 2*t^7 + 12*t^5 + 9*t^4 + 10*t^3 + 11*t^2 + 7*t + 6 : 0 : 1)]
G1: [(0 : 1 : 0), (4 : 0 : 1)]
G2: [(0 : 1 : 0), (4 : 0 : 1)]

Although the resulting pairing groups are equal for all cases, the 2-torsion groups are not, as described in the issue.

Answer 2 · 2023-11-20T23:46:32.000Z

Hmm. I have no idea. My initial intuition would be that maybe $2$ is special as a prime number, but IDK. '2'-torsion essentially means P+P=0, so its the group of self inverse points.

You said:

"
Thanks to @bufferhe4d and his discussion with several people, we have learned that when , it is not necessary to have elements in the full -torsion group.
"

can you elaborate on this or send a link to the discussion? I would also like to understand the reason in detail.

Answer 3 · 2023-11-21T10:24:00.000Z

@PlanetMacro Some part of the discussions were done in private and some in the CryptoHack discord.

First of all, note that (5.44) and Example 92 remains wrong independent of this discussion (i.e. there aren't any cases which can make it true, independent of r).

The case of an embedding degree with respect to 2 is a bit problematic. There are two possible cases:

The embedding degree definition is correct and it is equal to 1, then the fact that fact that the r-torsion group has r^2 elements is not necessarily the case.
The embedding degree definition does not hold for 2, hence the embedding degree is not equal to 1 (but 2 in this case). Then, the fact that r-torsion group has r^2 elements is true.
I am more inclined towards the latter but it is hard to find a resource where embedding degree with respect to 2 is specifically considered.

Answer 4 · 2024-03-29T19:31:37.000Z

Firstly, I believe that in Example 92, it is illustrative to look at the size of the r-torsion group of the curve E over the extension field when k = 3 compared to the r-torsion group of the curve E over the extension field when k is 4 and this is valid value of k. The value of k does not have to divide k(r), 1 <= k it is only required that r is a divisor of the group of points on E.

In the Sage program, I would expect that the size of the subgroups to stay at 4 and, like you are surprised by this. In the creation of the extension field F13_K, are we positive that we are creating a subgroup chain so that the new extension field contains the previous extension field?

Thank you for your patient consideration.

Answer 5 · 2024-03-30T21:35:20.000Z

IMHO, I believe that the chain of r-torsion subgroups (since E is cyclic) displayed in 5.44 is correct (if replace strict subset symbol with \subseteq allowing for equality) since the successive sets are subsets of the successive extension fields as k increases from 1. Since we are dealing with a cyclic group E, I believe the r-torsion set is also a subgroup. The construction of one extension field from the previous in the Sage code needs a little tweek so that the new F13_K generated in each iteration contains the previous extension field. As is, I believe we are just looking at representatives of each extension field for a given k.

Thank you for your consideration of this comment.

Answer 6 · 2024-03-30T23:02:53.000Z

@KelleClark I don't understand how 5.44 can be true even with the subseteq notation. F_p^(k+i) is not an extension of F_p^k for any i in which k does not divide k+i. I don't think it can be made true unless it's written in F_p^(k*i) form.

Answer 7 · 2024-04-01T15:53:24.000Z

@bufferhe4d
Hi, thanks to ur for responding and please forgive me for posting twice. I am a bit rusty, so I looked at a small example on paper to see if I could get anywhere. Taking the field Z_5 = F using mod 5 addition and mult. I looked at the 15 separable degree 2 polynomials (leading coeff 1) and the 10 irreducible polys (leading coeff 1) in Z_5[x]. So, I believe the extension field F_5^2 is isomorphic to Z_5/<x^2 +2> and to Z_5(sqrt(2)). If we want F_5^3 then I'm just thinking what happens … it seems that could go to (x + 2sqrt(3))(x + 3sqrt(3))(x + sqrt(2)) = x^3 + sqrt(2)x^2 + 3x + 3sqrt(2) which is irreducible over the extension field (so we extend the extension field Z_5(sqrt) by including sqrt(3) or maybe equivalently using (x^2 +3)(x^2 + 2) over the OG field....So wondering if increasing the degree of the irreducible poly over the OG field by 1 doesn’t seem to be the solution since you have to always up the degree of the irreducible by 2 (2, 4, 6) and then the extension field increases by a power of p (5^2, 5^3, 5^4, etc) …kind of like the “basis elements” for elements in the field Z_5^3 for Z_5(sqrt(2), sqrt(3)) become 1, sqrt(2), sqrt(3). Sorry, I haven’t moved passed this to the implication on the r torsion group yet.

Answer 8 · 2024-04-01T15:55:30.000Z

@bufferhe4d

looking forward to learning your opinion.