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

From: Rene Struik <[email-masked]>
Date: Wed, 12 Dec 2012 09:17:11 -0500

Hi Andrey:

One can already implement the x-coordinate only representation of an 
elliptic curve point simply by converting the affine representation into 
compressed representation and randomizing the compression "bit". The 
reverse operation then yields the point or its inverse (which have the 
same x-coordinate).

To my knowledge, this does not require any changes to data formatting 
(nor additional bytes).

Best regards,

Rene

On 12/11/2012 6:37 PM, Andrey Jivsov wrote:
> On 12/11/2012 03:15 PM, Peter Gutmann wrote:
>> Andrey Jivsov <[email-masked]> writes:
>>
>>> I thought that it would be useful for the Internet community to have 
>>> an IETF
>>> document that describes how to encode an ECC point.
>>
>> Maybe I'm missing something here, but wouldn't this just consist of:
>>
>> -- Snip --
>>
>> See [1].
>>
>> [1] X9.62-2005, "Public Key Cryptography for the Financial Services 
>> Industry:
>> The Elliptic Curve Digital Signature Standard (ECDSA)", November, 2005.
>>
>> -- Snip --
>>
>> That's what every existing RFC that uses ECC seems to be using.
>>
>> Peter.
>>
>
> Hello Peter.
>
> "X9.62-2005" in the search engine lends me on a page that asks for 
> $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is 
> more popular as a reference (assuming they are identical regarding the 
> point compression method).
>
> I claim that what I submitted is better in many respects than SEC1.
>
> Let me expand on one of the benefits not covered in the spec. It's 
> very likely that an employee of a commercial company thinking about 
> using [SEC1] compression with any ECC method would get an order from 
> the legal department to stay away from compression. The fact that 
> somebody on the Internet posted something to the contrary has little 
> weight for them. My contribution is an attempt towards a compact 
> representation that is actually usable in practice. It's the most 
> direct extension to the 1985 idea by [Miller] (see my document for 
> details).
>
> Thank you.
>
> _______________________________________________
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 12 Dec 2012 16:52:03 +0000

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Rene Struik
> Sent: Wednesday, December 12, 2012 9:17 AM
> To: Andrey Jivsov
> Cc: [email-masked]; [email-masked]; Peter Gutmann
> Subject: Re: [Cfrg] [saag] A proposal for compact representation of an
> elliptic curve point (ECC point compression)
> 
> Hi Andrey:
> 
> reverse operation then yields the point or its inverse (which have the same
> x-coordinate).
> 
> To my knowledge, this does not require any changes to data formatting (nor
> additional bytes).

That randomization of the y-component works fine for ECDH (at least, if you use only the x-component of the shared secret); however, it doesn't work for ECDSA public keys.

> >>> an IETF document that describes how to encode an ECC point.
> >>
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Rene Struik <[email-masked]>
Date: Wed, 12 Dec 2012 14:22:57 -0500

Hi Andrey:

I just wanted to understand the problem one tries to solve. My simple 
suggestion was aimed at realizing the same effect.

[I had a short offline exchange with Scott Fluhrer on this, including on 
the ECDSA verification angle - summarized by the sentence below]

In most common implementations, ECDSA signature verification cost is 
roughly the same, no matter whether one know the y-coordinate of the 
signature verification key or not.

Given this, it seems that for ECDSA signature verification and ECDH the 
argument for yet another construct seems to be somewhat weak: my simple 
suggestion would also work, does not require new formatting, or 
transition periods (and, to my knowledge, does not read on any 
"nontechnical issues").

I hope this helps.

Best regards, Rene

On 12/12/2012 2:02 PM, Andrey Jivsov wrote:
> I have the same comment as Scott, but I am not sure exactly what Rene 
> means.
>
> 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.
>
> The format I proposed indeed fits very well with the feature of the 
> ECDH-based  protocol that Scott refers to (which covers ECC encryption 
> and key agreement). As the draft shows, one simply drops the y 
> coordinate to obtain the compact representation, while there are no 
> extra steps for ECDH key generation (because ECDH keys are not 
> sensitive to maintaining the "right" y).
>
> The extra key generation step is only needed for ECDSA keys.
>
> On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote:
>>
>>
>> That randomization of the y-component works fine for ECDH (at least, 
>> if you use only the x-component of the shared secret); however, it 
>> doesn't work for ECDSA public keys.
>>
>>>
>>> Best regards,
>>>
>>> Rene
>>>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 12 Dec 2012 20:10:53 +0000

> From: Andrey Jivsov [mailto:[email-masked]]
> Sent: Wednesday, December 12, 2012 2:03 PM
> To: Scott Fluhrer (sfluhrer)
> Cc: Rene Struik; [email-masked]; [email-masked]; Peter Gutmann
> 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.
> 
> The format I proposed indeed fits very well with the feature of the ECDH-
> based  protocol that Scott refers to (which covers ECC encryption and key
> agreement). As the draft shows, one simply drops the y coordinate to obtain
> the compact representation, while there are no extra steps for ECDH key
> generation (because ECDH keys are not sensitive to maintaining the "right"
> y).
> 

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.

> >> From: [email-masked] [mailto:[email-masked]] On Behalf
> >> Of Rene Struik
> >> Subject: Re: [Cfrg] [saag] A proposal for compact representation of
> >> an elliptic curve point (ECC point compression)
> >>
> >> Hi Andrey:
> >>
> >> elliptic curve point simply by converting the affine representation
> >> into compressed representation and randomizing the compression "bit".
> >> The reverse operation then yields the point or its inverse (which
> >> have the same x-coordinate).
> >>
> > That randomization of the y-component works fine for ECDH (at least, if
> you use only the x-component of the shared secret); however, it doesn't
> work for ECDSA public keys.
> >
> >>
> >> Best regards,
> >>
> >> Rene
> >>
> >>>>> I thought that it would be useful for the Internet community to
> >>>>> have an IETF document that describes how to encode an ECC point.
> >>>>
> >>> $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1]
> >>> is more popular as a reference (assuming they are identical
> >>> regarding the point compression method).
> >>>

---

From: Vadym Fedyukovych <[email-masked]>
Date: Thu, 13 Dec 2012 13:21:13 +0200

On Wed, Dec 12, 2012 at 08:10:53PM +0000, Scott Fluhrer (sfluhrer) wrote:
> [...]
> [...]

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.

> [...]