-2
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ What was the problem with the answers in the previous question? (moderator note: this one. Both the present question and the other changed since then). $\endgroup$
    – user93353
    Sep 23, 2023 at 11:10
  • $\begingroup$ The question's field changed from $p=157$ in rev 6 to $p=1097$, making curve $E$ singular. That changes the problem markedly, and invalidates my detailed answer. While the cost to solve the problem for a nonsingular curve of cofactor $4$ was like $\mathcal O(\sqrt p)$ thus exponential in the size of $p$, that may no longer be the case. So we don't know what the general question is! I leave it to others to decide if this Q and that one should remain open. $\endgroup$
    – fgrieu
    Feb 13 at 10:12
  • $\begingroup$ @fgrieu This question has all valid params and you may attempt to solve this. Apologies for many revisions. $\endgroup$
    – Homer
    Feb 16 at 7:23
  • $\begingroup$ @Homer: for small $p$ (up to millions), a solution is possible by enumeration, lacks cryptographic interest, and is thus off-topic. Implicitly, we want to tackle large classes of parameters. And you changed the class of parameters by changing $p$ from a value yielding a curve of order 4 times a prime where the DLP is hard and your problem (thus) intractable for large $p$, to one of order $p+1$ (and as an aside 18 times a prime) where this reasoning does not apply. I won't try to solve your problem until you specify some infinite but narrow class of curves, with clear and on-topic motivation. $\endgroup$
    – fgrieu
    Feb 16 at 8:23

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @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). $\endgroup$
    – poncho
    Sep 23, 2023 at 15:11
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Sep 23, 2023 at 15:12
  • 2
    $\begingroup$ @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 $\endgroup$
    – poncho
    Sep 23, 2023 at 16:29
  • $\begingroup$ Can you write a sage example for your answer? $\endgroup$
    – Homer
    Oct 27, 2023 at 8:29
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Also here we have to consider "Point order" aka "order of element". $\endgroup$
    – Homer
    Oct 8, 2023 at 7:38

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.