Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression)

[Vadym Fedyukovych <[e-mail]>]

On Wed, Dec 12, 2012 at 08:10:53PM +0000, Scott Fluhrer (sfluhrer) wrote:
> 
> > -----Original Message-----
> > From: Andrey Jivsov [mailto:[e-mail]]
> > Sent: Wednesday, December 12, 2012 2:03 PM
> > 
> [...]
> > I will assume that Rene says that because there are two y for each x, one can
> > calculate the corresponding y or p-y and choose one at random.
> [...]
> Actually, as Rene pointed out to me privately, it isn't much more for ECDSA, at least with the standard algorithm.
> 
> The ECDSA verification is a check whether r = (uG + vQ)_x, where Q is the public key.  If you are given only the x coordinate of Q, what you do is to pick a corresponding y coordinate (so you get a point S where either S=Q or S=-Q, where Q is the original public key), and check if one of these two holds:
> 
> r = (uG + vS)_x
> r = (uG - vS)_x
> 
> If either does, the signature verifies.  This adds the cost of a single point addition (and the cost of generating the y coordinate of S); fairly small.

This looks like a non-trivial change of threat model to me.

There may be two different messages signed with such a signature.
To be practical, one would consider generating (well, calculating) a key
to fit any two pre-selected messages later.
"IOY amount/10" could be an example for a nice article in game theory.

> > On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote:
> > >
> > >
> > >> -----Original Message-----
> > >> From: [e-mail] [mailto:[e-mail]] On Behalf
> > >> Of Rene Struik
> > >> Sent: Wednesday, December 12, 2012 9:17 AM
> [...]