Can schnorr-signatures be used to ensure public keys are of the correct form (namely $Y= x \cdot G$)?

Question

Assume a Schnorr-signature scheme in an elliptic curve setting with a publicly known generator base point $G$ where the the discrete logarithm is hard. That is, given $x \cdot G$, it is hard to find $x$. I am curious to know if this signature scheme can be used to perform public key validation in the following sense:

1. Alice provides Bob with a signature $(e,s)$ for some message $m$ and a public key $Y$.
2. Bob verifies that the signature $(e,s)$ like so:
   1. Calculate $R = (s \cdot G) - (e \cdot Y)$
   2. Set $e_v = H(R_x || m)$
   3. Accept signature iff $e_v = e$

Can this scheme be used to ensure the public key provided by Alice is indeed of the form $Y = n \cdot G$ (and not say of another form $Y = n \cdot G + n' \cdot G'$?). Assume Alice is computationally bounded and in particular cannot solve the discrete logarithm problem. Or is there a way for Alice to carefully choose the values $(e,s)$ such that Bob accepts the signature even if $Y$ is of them form $Y = x \cdot G + x' \cdot G'$?

Answer 1

As long as the public key is in the elliptic curve group, there is no such thing as being "of the correct form" or not. For any point $P$ in the group, there exists a value $x$ such that $P=x\cdot G$. Thus, all that is necessary is to check that $P$ is indeed in the group. This is carried out by checking (1) that $P=(x,y)$ is on the elliptic curve itself (i.e., it fulfills the equation), (2) that $P$ is not the identity (i.e., the point at infinity, or zero), and (3) that $q \cdot P = 1$, where $q$ is the order of the Elliptic curve group that you are working in. (The third check is needed when the number of points on the Elliptic curve is greater than the size of the subgroup you are working in.)

A completely separate question is whether or not the public-key owner can prove that he knows the associated private-key. That is, do they actually know $x$ such that $P=x\cdot G$. This can be done using a zero-knowledge proof, but actually a Schnorr signature is exactly a zero-knowledge proof of this fact. Indeed, providing an ECDSA signature would also work. However, you need to make sure that this can't be used to extract a meaningful signature that they never meant to sign...

Answer 2

Yes it can be tested if a given $Y$ is of the form $x\cdot G$ (for some $x\ne0\bmod n$ ), even though it is not possible to find $x$. How depends on the Elliptic Curve (but I don't see that also possessing a matching signature helps).

For an Elliptic Curve with $h=1$ (meaning $G$ generates the full curve), it's enough to check if the point $Y$ is on the curve and not the point at infinity. For a curve in the field $\mathbb F_p$ with $p$ prime and $h=1$ (including all curves in sec2v2 section 2):

• if $G$ is expressed as $(x,y)$ coordinates, it's enough to check $0<x<p$,   $0<y<p$, and $y^2\equiv x^3+a\,x+b\pmod p$, where $a$ and $g$ are public curve parameters.
• if $Y$ is expressed as $x$ and parity or "sign" of $y$ (compressed form), it's enough to check $0<x<p$ and $(x^3+a\,x+b)^{(p-1)/2}\bmod p=1$, implying $y^2\equiv x^3+a\,x+b\pmod p$ has a solution.

For curves where $h>1$ (that is, $G$ is not a generator of the full curve, but only of a fraction $1/h$ of that), in addition to the equivalent of the above tests in whatever the field used, we must check that $n\cdot Y=G$, where $n$ is the order of $G$.

Answer 3

No, unless I'm misunderstanding something in your question.

$Y = z \cdot g = (2^{-1}y)\cdot g + y\cdot (2^{-1}g) = x\cdot g +x' \cdot g'$

That is even a "valid" $Y$ can be expressed as a sum of points.

---

If you recognize that elliptic curves are a group, this should be apparent.