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

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.

• What was the problem with the answers in the previous question? Sep 23 at 11:10
• @user93353 just need a fresh page to continue our proofs. We are still finding a formula and a sage code. Sep 23 at 11:14
• @fgrieu in early times isogeny was considered to be one-way but later someone proved that there exists dual-isogeny, isn't it? Sep 23 at 14:00
• This new question differs from version 4 of the other in the requirement on A' and B' (thus the present question is not a duplicate). In particular, the first verification requirement is specific to the present question. It remains unclear (1) if we can somewhat restrict $k$; (2) if we can choose the method to compute A' from A and B' from B with knowledge of A or/and B, (3) if said method needs to be practicable with 43 and 157 replaced by primes of cryptographic interest, e.g. of ≈200 bits rather than ≈6 bits.
– fgrieu
Sep 23 at 14:57

2 Answers

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.

• @fgrieu: if we insist that $f(k \cdot G) = k \cdot f(G)$ holds for $k=0$, your objection is correct. I was specifically avoiding that case; if you don't insist on it, then such an $f$ can be defined (e.g. set $f(G)$ to an arbitrary generator in the group G (grumble, using $G$ to denote two different things), and to compute $f(kG)$, you solve the discrete log problem to recover $k$ and then return $k \cdot f(G)$. That meets all the requirements; however it is not computable for large groups (and I endeavored to show that this is no alternative method which is much more efficient). Sep 23 at 15:11
• @Josh666: the point I was making is that the mapping you're asking for can be used to compute discrete logs, hence computing that mapping cannot be significantly more efficient. Sep 23 at 15:12
• There must be an efficient method (maybe complex) to perform such mappings because if cofactor clearing is possible then its reverse is also possible with different technique. We don't want to solve DLP. We just have to reverse the cofactor clearing and get the points A' and B' (in parent group G) that correspond to A and B (in subgroup H) respectively. Sep 23 at 15:16
• @Josh666: "There must be an efficient method to perform such mappings because if cofactor clearing is possible then its reverse is also possible"; actually, we believe there exist mappings that cannot be efficiently inverted. However, in this case, if we look at cofactor clearing $hA = B$, if we are given $B \in$ G, there are $h$ values of $A$ that solve it, and it is easy to compute that set, What's not easy is selecting a single value from those $h$ values in a way that is consistent (in the way you specified); I just showed that doing that is hard assuming the DLP problem is hard Sep 23 at 16:29
• Can you write a sage example for your answer? Oct 27 at 8:29

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).

• There was a small mistake in my parameters- "the finite field 157 of main-group order 172 does not have points which have point order of 172 means even if we do some conversion we won't find that point(s)". So to tackle that issue lets change the param to- finite field p = 1097, main-group-order = 1098, subgroups = 1098, 549, 122, 183, 366 and so on. Same curve eq: y2=x3+2. Suppose we have A and B (with scalar k) in subgroup of ord 122, how to transform to points U and V in main subgroup of ord 1098? I'm providing a simple verification sage in next comment for U and V Oct 8 at 6:24
• Check in sage for point orders of resulting points U and V (reminder: "keeping the scalar k preserved (and unknown)"). SAGE: p = 1097 Fp = GF(p) E = EllipticCurve(Fp, [0, 2]) U = E(7, 695) #example V = E(35, 810) #example print(U.order()) print(V.order()) Oct 8 at 6:31
• Also here we have to consider "Point order" aka "order of element". Oct 8 at 7:38