How to map elements from subgroup to larger subgroup of its parent group?

Question

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, largest subgroup order(J) = 1098 and subgroups = 1098, 549, 122, 183, 366, 61 and so on. Suppose I have a random generator point "A" (on subgroup 61) and multiply it with some unknown scalar k that gives point "B" (on subgroup 61). So how should I get corresponding points R and S in larger subgroup J having order 1098 keeping the scalar k preserved (k is unknown and not used in the process)? You can think of a mapping of two points A and B from H→J where all properties are preserved along with scalar multiplication. but the resulting points R and S must belong to the larger subgroup J (which has order 1098) respecting scalar k.

Key Points:

1. A, B ∈ H and R, S ∈ J on E.C. y^2 = x^2 + 2 of prime = 1097

2. H is cyclic subgroup of order 61 and J is the large subgroup of order 1098.

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

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

5. The cofactor h = 1098/61 = 18.

6. Brute force should not be used. We use only math.

Our Goal: transform A, B ∈ H → R, S ∈ J while preserving scalar k (but NOT using k for conversion). This can be understood as the opposite of cofactor clearing or some mapping.

Sage Verification:

p = 1097 
Fp = GF(p) 
E = EllipticCurve(Fp, [0, 2])

``
**YOUR TRANSFORMATION CODE HERE**
``

🔹A.order() #result must be 61 
🔹B.order() #result must be 61 
🔹R.order() #result must be 1098 
🔹S.order() #result must be 1098 

🔹S == k * R #result must be 'True'

A SAGE code for such transformation will 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

THIS ANSWER APPLIES TO VERSION 6 OF THE QUESTION. It does not apply to version 11 which uses a different class of curves, with $p$ such that the curve's order is $p+1$.

---

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 such that the corresponding elliptic curve group $G$ has order $h⋅n$ with $n$ prime and the cofactor $h=4$. Up to version 6, the question used such parameters: $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).