2
$\begingroup$

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'$?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you -- I am curious: Given the value $P$ in the group, it is hard to find the value $x$ such that $P = x \cdot G$, right? The context is: I saw this being used to ensure that the public key is of form: $P = x \cdot G$ not say $P= x \cdot G + x' \cdot G'$, where the attacker fixes, $x, x', G'$. This strikes me as wrong intuitively, but I don't seem to find a way to generate the values $(s,e)$ to give a valid signature for this new the public key $x \cdot G + x' \cdot G'$. $\endgroup$ – cryptobeginner Feb 18 at 9:34
  • 1
    $\begingroup$ It doesn't make sense to say of the form $x\cdot G$ versus $x\cdot G + x'\cdot G'$ since all values are of the form $x\cdot G$ for some $x$. The question is one of knowledge, and yes, signatures of this form that are ZK proofs can actually guarantee knowledge. $\endgroup$ – Yehuda Lindell Feb 18 at 9:53
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks! The question is: Say Alice knows $x$, $x'$, can she easily find a $z$ such that $z \cdot g = x \cdot g + x' \cdot g'$?. From my understanding, this should not be possible under the Discrete Logarithm assumption, no? $\endgroup$ – cryptobeginner Feb 18 at 9:29
  • $\begingroup$ The context is: I saw this being used to ensure that the public key is of form: $P = x \cdot G$ not say $P= x \cdot G + x' \cdot G'$, where the attacker fixes, $x, x', G'$. This strikes me as wrong intuitively, but I don't seem to find a way to generate the values $(s,e)$ to give a valid signature for this new the public key $x \cdot G + x' \cdot G'$. $\endgroup$ – cryptobeginner Feb 18 at 9:34
  • 1
    $\begingroup$ You'd have to know the relation between $G$ and $G'$. Given random $G$ and $G'$, this is difficult, but whoever is choosing $G'$ can pick it to be $G' = a \cdot G$, where they know $a$. $\endgroup$ – Aman Grewal Feb 18 at 13:59

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.