1
$\begingroup$

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

I know that elements of a non-prime order cyclic group G can be moved to its subgroup H by a process called "cofactor clearing". You just have to simply multiply a cofactor by an element of main group that ends up giving an element in its subgroup. Example given on- Why such a complicated way of cofactor clearing?

I want to know if there's a way/formula/algorithm for we can do the things in opposite, i.e., "moving elements from cyclic subgroup to its cyclic parent group" such that we get elements which belong to the parent group (respecting group laws ofc). I have tried taking (cofactor^-1) but didn't work.

NOTE: homomorphism should not be used as it would map the element of subgroup order to an element of same subgroup order. Here we want element of parent group order.

If someone can help me with this (with a good example) would be really appreciated...

EDIT: Let me clarify what I am looking for in a simple terms, pls read carefully - I need a formula that can be applied on any curve, say for e.g. y^2 = x^3 + 2 with prime = 157, parent group order = 172 and subgroups = 4 x 43. Suppose I have a random generator point "A" (on subgroup 43) and multiply it with some unknown scalar k that gives point "B" (on subgroup 43). So how should I get resulting points A' and B' on parent group G having order 172 keeping the scalar k preserved (and unknown)? A SAGE code would be helpful. You can think of a mapping of two points A and B H→G where all properties are preserved along with scalar mult. but the resulting points A' and B' have to belong to the parent group G (which has order 172) respecting scalar k.

$\endgroup$
9
  • $\begingroup$ The most obvious meaningful way is contruct $C\cong C_n\times C_p$ where $C_n$ and $C_p$ are cylic. Find their smallest generator, and map it to the smallest generator of the $C$ $\endgroup$
    – kelalaka
    Sep 22, 2023 at 11:18
  • $\begingroup$ $y^2 = x^3 + 2$ over $GF(157)$ is not cyclic. There is no point with order 172 on that curve $\endgroup$
    – Ruggero
    Oct 26, 2023 at 7:55
  • 1
    $\begingroup$ At least give a link to the other page, this is unhelpful $\endgroup$
    – kodlu
    Feb 5 at 4:28
  • 1
    $\begingroup$ It is bad form to edit ones Question in such a way as to make existing Answers "obsolete". $\endgroup$
    – hardmath
    Feb 5 at 5:09
  • 3
    $\begingroup$ Please don't vandalize your own questions. $\endgroup$
    – Maeher
    Feb 5 at 6:28

2 Answers 2

0
$\begingroup$

Consider the Ed25519 curve, which has a co-factor of 8. The prime-order group has the order $\ell=2^{252} + 27742317777372353535851937790883648493$. The total number of points on the curve is $8\ell$.

If you take random points on the curve and multiply them by $\ell$, you will find that you only get 8 possible resulting points. In hex, their compressed representations are as follows:

1: c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa
2: 0000000000000000000000000000000000000000000000000000000000000000
3: 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc85
4: ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f
5: 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05
6: 0000000000000000000000000000000000000000000000000000000000000080
7: c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a
8: 0100000000000000000000000000000000000000000000000000000000000000

You may recognize that the 8th item is the identity element for the Ed25519 prime-order group.

If you take the 1st point and add it to itself, you get the 2nd point. If you keep adding the 1st point, you'll get all of the remaining points.

To know if you have a point in the prime-order group, you multiply it by $\ell$ and check that the answer is the 8th point. No matter what you multiply a point in the prime-order group by, it'll stay in the prime-order group.

To knock a point out of the prime-order group, all you have to do is add the 1st point to it.

$\endgroup$
2
  • $\begingroup$ @Josh666 think of a point in the prime-order group as a multiple of $8\Delta$, where $\Delta$ is the 1st point in the list (c717...03fa). If you have a random point $A$ in the prime-order group, then $A=a8\Delta$ for some value of $a$. If you knock it out of that group, you have e.g. $A'=a8\Delta+\Delta$. This means that if you have $B=15A$ and $B'=15A'$, then $B'=B+15\Delta=15a8\Delta+15\Delta$. This is why you can "clear the cofactor" by ensuring that you scalar multiply by a multiple of 8, because it means the resulting point must be of the form $P=x8\Delta$ $\endgroup$
    – knaccc
    Sep 22, 2023 at 15:31
  • $\begingroup$ @Josh666 You can add $\Delta$ to any point in the prime-order group to bump it out of the prime-order group $\endgroup$
    – knaccc
    Sep 22, 2023 at 16:07
0
$\begingroup$

Assuming that by

keep the scalar preserved

you mean: $B=k*A \implies B'=k*A'$ then the map must include the value of $k$.

Reasoning: an element of the larger group can be written as addition of points on the smaller groups. So that $A'=A+C$, multiplying by $k$ will give $kA+kC$ so in order to maintain your property on $B=kA$ you should add $kC$ to it. $B'=kA+kC$.

Since $C$ has small order $n$ you can do that scalar multiplication just by $k \mod n$

This will work as map, see the following sage script for an example curve of order 3*61 (as the curve you proposed doesn't really work as there is no element with order 172)

#define the elliptic curve
ec = EllipticCurve(GF(157),[0,11])
#compute its order
print (ec.order(), factor(ec.order()))
#take a generator and verify its order is the cardinality of the curve
Gall=ec.gens()[0]
assert (Gall.order()==ec.cardinality())
#derive A as generator of the larger subgroup
A = 3*Gall
print ("A's order = ", A.order())
#derive C as generator of the smaller subgroup (of order 3)
C = Gall*61
print ("C's order = ",C.order())
for k in range(1,A.order()-1):
    B = k*A
    Ap = A + C
    Bp = B + k*C
    assert k*Ap == Bp    

On the security side it depends on what you disclose because if you disclose $A$ and $A'$ an attacker can easily recover $C$ and the value of $k$ modulo the smaller subgroup's order.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.