[curves] Schnorr NIZK over Curve 25519

[Ben Smith]

Hi all,

2018-03-20 21:55 GMT+01:00 Stojan Dimitrovski <sdimitrovski at gmail.com>:
>    At the end of the protocol, Bob performs the following checks.  If
>    any check fails, the verification is unsuccessful.
>
>    1.  To verify A is a valid point on the curve and A x [h] is not the
>        point at infinity;
>
>    2.  To verify V = G x [r] + A x [c].
>
>    The first check ensures that A is a valid public key, hence the
>    discrete logarithm of A with respect to the base G actually exists.

That's not quite correct.  If A is a legitimate multiple of G and T is
a point of order 2, say, then A+T also passes this test, but it has no
discrete log w.r.t. G (and is therefore not a valid public key).  What
Test 1 is really telling you is that A is a point on the curve and
that the order of A is not a divisor of h.  In this case, where the
curve order is h*prime, this lets you deduce that the order of A is
divisible by the prime---but that's all (there might be bits of h left
over).  Multiplying everything by 8 pushes everything right into the
interesting subgroup, and removes that sort of ambiguity.


ben

-- 
You know we all became mathematicians for the same reason: we were lazy.
  --Max Rosenlicht