0
$\begingroup$

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.

Improve this question
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ – A M Feb 26 '20 at 21:23
  • $\begingroup$ @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... $\endgroup$ – poncho Feb 26 '20 at 23:30
  • $\begingroup$ Thank you @poncho! $\endgroup$ – A M Feb 27 '20 at 0:00
  • $\begingroup$ 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. $\endgroup$ – A M Feb 27 '20 at 19:42
  • $\begingroup$ It is, in fact, the point at infinity... $\endgroup$ – poncho Feb 27 '20 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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