Re: [CFRG] Psychic Signatures

As someone with experience in ECC implementation, this doesn’t make sense to me, at least not in a typical deployment (prime-order curves with (x,y) both given).

A straightforward check that a point given by (x,y) is on the curve is 2-3 orders of magnitude faster than a signing or verification operation.  You only need to check that y^2 = x^3 + ax + b, or whatever the curve equation is, which takes about 3 multiplies.  Compare to eg ECDH which costs at least 11 * bit length for the Montgomery ladder (and that’s new, it used to be 14), plus the final division for a total of around 3000 multiplies.  Or compare ECDSA verification which is even slower.  The slightly faster operation, ECDSA sign, doesn’t take a public key.  So in all these cases it doesn’t make sense to skip public key validation for performance reasons.

There is a cost in less common deployments.  If you have to check the order of the public key, because the curve has a cofactor, then this costs at least a Jacobi symbol but often much more.  Likewise if you have only x, and you’re doing an x-only ladder but need to check that there exists a y such that (x,y) is on the curve, because your curve isn’t twist-secure, then this isn’t free (it’s basically a Jacobi symbol computation; you could batch it with the final inversion but that’s a relatively new technique).  Or if you need to decompress the public key from a form like (x, one bit of y) then this isn’t free either, but it also can’t be skipped without breaking things.

Regards,
— Mike

> On Apr 22, 2022, at 8:49 AM, Mehmet Adalier <madalier@antarateknik.com> wrote:
> 
> Indeed. the verification operation is usually substantially slower than the signing operation, at least with ecc.
> Some library implementers offer verification functions without 'validation' for faster performance paths, assuming that the astute integrator will check for inputs independently via other (potentially) provided validation functions. 
> 
> Patent 9804891 describes methods of validating and pre-computing public keys for performance. these are applicable for both embedded or high-performance computing platforms
> 
> mehmet
> 
> On 4/22/22, 2:10 AM, "CFRG on behalf of Peter Gutmann" <cfrg-bounces@irtf.org on behalf of pgut001@cs.auckland.ac.nz> wrote:
> 
>    David Jacobson <david=40dmjacobson.com@dmarc.ietf.org> writes:
> 
>> I suspect that the reason for the library requiring a separate validation
>> function was patent US 7215773.
> 
>    It'd be interesting to hear from people working on embedded crypto libraries,
>    but I think it'd be due to a different reason.  In terms of the patent I
>    suspect most people don't even know that it exists (I didn't until now) and
>    even if they did, having the input verification function in the library right
>    next to the public/private-key function isn't doing anything to avoid it.
> 
>    I assumed it was because the verification operations are quite expensive for a
>    process that's already slow (compared to RSA's much-faster-than-signing
>    signature verification), and building the input verification into the
>    signature verification would make it even slower.  By skipping the input
>    verification you can appear to be faster than your competitors/RSA/some
>    arbitrary line in the sand.
> 
>    Peter.
> 
>    _______________________________________________
>    CFRG mailing list
>    CFRG@irtf.org
>    https://www.irtf.org/mailman/listinfo/cfrg
> 
> 
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg