PAGE 2: Can I move elements from cyclic subgroup to its cyclic parent group?

Question

We will continue our previous topic here⬇️ for clarity...

The following context is based on elliptic curves in short-weierstrass form y^2 = x^3 + b.

pls read carefully-

I am looking for a function/formula/algorithm that can be applied on any curve, say for e.g. y^2 = x^3 + 2 with prime = 1097, parent group order = 1098 and subgroups = 1098, 549, 122, 183, 366 and so on. Suppose I have a random generator point "A" (on subgroup 122) and multiply it with some unknown scalar k that gives point "B" (on subgroup 122). So how should I get resulting points U and V on parent group G having order 1098 keeping the scalar k preserved (and unknown and not using in the process)? You can think of a mapping of two points A and B from H→G where all properties are preserved along with scalar multiplication. but the resulting points U and V have to belong to the parent group G (which has order 1098) respecting scalar k.

Key Points:

1. A, B ∈ H and U, V ∈ G on E.C. y^2 = x^2 + 2 of prime = 1097

2. H is cyclic subgroup of order 122 and G is the cyclic main/parent group of order 1098.

3. Scalar "k" is unknown and should not be used for conversion H→G.

4. A is a random generator point on subgroup H of order 122 and B is its element obtained from scalar multiplication B = k*A (on same subgroup H of order 122).

5. The cofactor h = 1098/122 = 9.

Our Goal: transform A, B ∈ H → U, V ∈ G while preserving scalar k. This can be understood as the opposite of cofactor clearing.

Verification:

let q be the parent/whole group order (1098), and let n be its prime subgroup of order (122).

🔹If n = 122 then, n * U and n * V ≠ point at infinity

🔹If q = 1098 then, q * U and q * V = point at infinity

🔹V == k * U must be 'True'

A SAGE code would be helpful.

Answer 1

Here's the issue; any such efficiently computable mapping would allow someone to compute discrete logs in H, hence there is no such efficiently computable mapping for any subgroup of cryptographical interest.

Here are the properties I am assuming:

• There is an efficiently computable function $f$ that maps points in H to points in G

• $f$ has the property that $f(k \cdot G) = k \cdot f(G)$ for any $0 < k < h$ (where $h$ is the order of H)

• $f(G)$ has an order $> h$, that is, $h \cdot f(g) \ne 0$ (where $0$ is the point at infinity, aka the neutral element).

With those assumptions, given $kG$ (with $0 < k < h$), we can compute $f(k\cdot G)$ and $f(2 \cdot k \cdot G)$. We have $f(2k \cdot G) = f((2k \bmod h) \cdot G)$ (because $G$ is of order $h$).

If $k < h/2$, then $2k \bmod h = 2k$, and so we have $f(2k \cdot G) = 2k\cdot f(G) = 2 \cdot f(k \cdot G)$, that is, doubling $f(k \cdot G)$ gives us $f(2k \cdot G)$

If $k > h/2$, then $2k \bmod h = 2k - h$, and so we have $f(2k \cdot G) = (2k-h) \cdot f(G) = 2f(k \cdot G) - h \cdot f(G)$. Since $h \cdot f(G) \ne 0$, this is not $2f(k \cdot G)$, and so doubling $f(k \cdot G)$ gives us something other than $f(2k \cdot G)$

Hence, if $2 \cdot f(k \cdot G) = f(2 \cdot k \cdot G)$, then we know $k < h/2$; if $2 \cdot f(k \cdot G) \ne f(2 \cdot k \cdot G)$, then we know that $k > h/2$

With this efficient test for determining whether $k$ is on the left side or right side of $h/2$, we can use it $log_2 h$ times (via binary search) to determine the exact value of $k$, that is, solving the discrete log problem.

Answer 2

We assume an elliptic curve $y^2=x^3+b$ over the field $\mathbb F_p$, with $p$ prime such that $p\bmod3=1$, and $b$ such that $b^{(p-1)/3}\bmod p=1$, and that the corresponding elliptic curve group $G$ has order $h⋅n$ with $n$ prime and the cofactor $h=4$. The question uses $p=157$, $b=2$, $n=43$.

Without proof: the group $G$ is the product of the cyclic group $\mathbb Z/n\mathbb Z$ of prime order $n$, and of the Klein 4 group $K_4$, which group law is: $$\begin{array}{c|cccc} +&0&u&v&w\\ \hline 0&0&u&v&w\\ u&u&0&w&v\\ v&v&w&0&u\\ w&w&v&u&0\\ \end{array}$$

Elements of $G$ can be classified according to their order, as:

• $1$ neutral/point at infinity $\mathcal O$, of order $1$. It's component in $\mathbb Z/n\mathbb Z$ and $K_4$ are $0$.
• $3$ points of order $2$, of coordinate $(x,0)$ with $x$ one of the three $x$ with $x^3+b\bmod p=0$. They are the elements of $G$ which component in $\mathbb Z/n\mathbb Z$ is $0$, and component in $K_4$ is $\ne0$.
• $n-1$ points of order $n$, forming (with $\mathcal O$) a uniquely defined subgroup $H$ of order $n$. They are the elements of $G$ which component in $\mathbb Z/n\mathbb Z$ is $\ne0$, and component in $K_4$ is $0$.
• $3⋅n-3$ points of order $2⋅n$. They are the elements of $G$ which components in $\mathbb Z/n\mathbb Z$ and $K_4$ are $\ne0$.

Notice that $\forall P\in G,\,(2⋅n)∗P=\mathcal O$. Also, if $P$ has order $2⋅n$, then $2*P$ has order $n$ and is a generator of $H$, and $n*P$ has order $2$.

In order to meet the question's "Verification Requirements", the question's $k$ must be odd. Proof by contraposition:

• Assume $k$ is not odd, and the verification requirements are met.
• Write $k$ as $k=2⋅j$. VR3 becomes $B′=(2⋅j)∗A′$
• The second part of VR1 tells $n∗B′\ne\mathcal O$
• Substitution yields that $n∗((2⋅j)∗A′)\ne\mathcal O$
• Rearranging yields $j*((2⋅n)∗A′)\ne\mathcal O$, using associativity and commutativity of integer multiplication $⋅$, and that $\forall u,v\in\mathbb Z,\,\forall X\in G,\, (u⋅v)*X=u*(v*X)$
• $(2⋅n)∗A′$ is $\mathcal O$ due to the aforementioned structure of $G$
• Substitution yields that $j*\mathcal O\ne\mathcal O$, which is false. Hence the original assumption is false.

More generally, in order to meet VR1 and VR3, $k$ must be coprime with the order of $G$.

For the "cofactor clearing function", we can pick any even $c$ coprime with $n$ and define function $g_c$ by $g_c(P)=c*P$. That $g_c$ is linear, and such that $\forall P\in G,\,g_c(P)\in H$. $c=2$ is the simplest. Another interesting choice is $c=n+1$, yielding function $\dot g$ with $\dot g(P)=(n+1)*P$, which has the property $\forall P\in H,\,\dot g(P)=P$. This cofactor clearing function $\dot g$ is projection on $H$, clearing the Klein Four-Group component of the input.

For the desired "inverse cofactor clearing function" $f$ such that $\forall P\in H,\,g(f(P))=P$, we can pick an element $S$ of order $2⋅n$, and construct $A$ from $S$ using our cofactor clearing function. Our $f$ will map $A$ to $S$, which passes the first requirement. Then the required linearity for $f$ (VR3) dictates what $f$ must do for many other inputs.

Here is Sage code for this:

p,b = 157,2                     # parameters for the curve
assert p in Primes() and p%3 == 1 and pow(-b,(p-1)//3,p) == 1
G = EllipticCurve(GF(p),[0,b])  # define the parent group
ordG = G.order()                # parent group order
n = factor(ordG)[-1][0]         # order of H
assert ordG == 4*n              # check cofactor is 4
O = G(0,1,0)                    # the neutral / point at infinity
c = n+1                         # cofactor clearing by projection (or c = 2)
ordS = 2*n                      # desired order for S
for S in G.points():            # search S 
    if S.order()==ordS:
        break
A = c*S                         # decide A
assert A.order() == n           # check the order of A (and H) is n
print("p =",p,"  b =",b,"  n =",n,"  c =",c,"  A =",A.xy(),"  S =",S.xy())

def clearing(P):                # our clearing function
    return c*P                  # multiply by an even constant coprime with n

def revclear(P):                # our reverse clearing function
    Q,R = A,S                   # A is to Q what S is to R..
    while Q != P:               # and throughout our search..
        Q,R = Q+A,R+S           # that remains, insuring linearity 
    return R                    # result found!

A2 = revclear(A)                # find A'
for k in range(1,n,2):          # check each possible (odd) k
    B = k*A                     # build B from k as specified
    B2 = revclear(B)            # find B'
    assert clearing(B2) == B, "revclear fails to reverse clearing"
    assert n*B2 != O            # requirement 1
    assert ordG*B2 == O         # requirement 2 (a tautology)
    assert B2 == k*A2           # requirement 3
print("all good")

The above matches the letter of "keeping the scalar $k$ preserved (and unknown)" prescription of the question: the function revclear is not given access to k.

However my revclear performs in the order of $\Theta(n)$ operations. I could reduce that to $\Theta(\sqrt n)$ (and make it less apparent that revclear sorts of finds $k$). Problem is, that's impractical for applications of cryptographic interest, where $n$ must be like 200-bit or higher. This answer proves that there is little hope to find a practical method (note: this answer's $h$ is my $n$ rather than the $h=4$ in the question).