Is it secure to use ECDSA for any arbitrary point on the Elliptic Curve as the Generator point?

My question concerns the elliptic curve $$E$$ over a prime field $$\mathbb F_p$$. To the best of my understanding, ECDSA requires a Generator point $$G$$ of prime order $$n$$, and the $$r$$ and $$s$$ values of the signature must be within the range $$[1,n-1]$$. The concept of ECDSA is to show a person that one is in possession of a secret $$k$$ s.t. $$kG = K$$, without (obviously) revealing $$k$$.

However, suppose that you are aware of public key $$K$$ and are looking to do a tweak of $$K$$. Let $$t$$ be the tweaking factor, and so $$tK = K'$$. If you then wanted to prove that you are in possession of $$t$$, how would you do that?

An immediate thought (which I am confident will not work) is to use ECDSA with $$K$$ as the generator point. However, it might be the case that $$K$$ is of a very small order $$n$$ which may not be prime.

If someone can shed light on how to prove that one is in possession of secret $$t$$, I would be very happy. Also, the verifying party is in possession of both $$k, K$$, the secret key and public key pair.

However, suppose that you are aware of public key $$K$$ and are looking to do a tweak of $$K$$. Let $$t$$ be the tweaking factor, and so $$tK=K'$$. If you then wanted to prove that you are in possession of $$t$$, how would you do that?

The obvious way to do this is a Schnorr proof of knowledge, which does precisely what you're looking for; given a public $$K, tK$$, it demonstrates that you know $$t$$. Wikipedia lists the interactive version; it can be made noninteractive by having the prover generate $$c$$ based on a hash of the commitment $$t$$ (and possibly other stuff if you need to bind the proof to something).

An immediate thought (which I am confident will not work) is to use ECDSA with $$K$$ as the generator point. However, it might be the case that $$K$$ is of a very small order $$n$$ which may not be prime.

That would also work (which isn't that surprising; ECDSA is essentially based on Schnorr, tweaked enough to avoid patents that have since expired); it's kludgier, however it might be preferable if you just happen to have an ECDSA implementation just lying around. If $$K$$ does have small factors, you might need to work around it (as some values might not be invertable), however that wouldn't appear to be a major issue.

And, if $$K$$ is a very small order, then deriving $$t$$ would be easy, no matter what proof-of-knowledge method you use (and so there's little point in the problem). In any case, we almost always use elliptic curves where the order of the curve is $$hq$$, where $$h$$ is a small value (the most common values are 1 and 8), and $$q$$ is a large prime - except for a handful of points (actually, a total of $$h$$ points), all points have a large order (at least $$q$$).

• Ok, wow. Thank you for the detailed response. Could you expand a bit more on the issues with using ECDSA on public keys (ECC points) that have small factors? Would it be easy to check if a particular public key is ideal for this proof? In the next paragraph you mention that typically points on a curve have an order of $q$ which is a large prime, and only $h$ points don't. Is it trivial to check if a point is one of these $h$ points? – A M Feb 26 at 21:23
• @AM: well, the problem with ECDSA really is with curves of composite order; to sign, we select a random $k$ and then compute $k^{-1}$ modulo the curve order. If the curve order has small factors and $k$ just happens to be a multiple of one of those small factors, then there won't be any such $k^{-1}$ - we typically avoid such issues by using ECDSA only with curves with a prime order. As for checking if a point $P$ happens to be one of the $h$ points with small order, that's easy - compute $hP$ and check if that's the point at infinity... – poncho Feb 26 at 23:30
• Thank you @poncho! – A M Feb 27 at 0:00
• Also, I searched online to check the $h$ value for the elliptic curve I am working with and I found $h = 1$, which likely suggests that there is only one point on the curve which is of a small group. My intuition tells me that the point is the point at infinity, but either way it doesn't matter since the likelihood that $K$ is that point is very low. – A M Feb 27 at 19:42
• It is, in fact, the point at infinity... – poncho Feb 27 at 20:13