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

[Rene Struik <[e-mail]>]

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:
>>
>>
>>> -----Original Message-----
>>> From: [e-mail] [mailto:[e-mail]] On Behalf Of
>>> Rene Struik
>>> Sent: Wednesday, December 12, 2012 9:17 AM
>>> To: Andrey Jivsov
>>> Cc: [e-mail]; [e-mail]; Peter Gutmann
>>> Subject: Re: [Cfrg] [saag] A proposal for compact representation of an
>>> elliptic curve point (ECC point compression)
>>>
>>> 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).
>>
>> 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
>>>
>>> On 12/11/2012 6:37 PM, Andrey Jivsov wrote:
>>>> On 12/11/2012 03:15 PM, Peter Gutmann wrote:
>>>>> Andrey Jivsov <[e-mail]> 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
>>>> [e-mail]
>>>> https://www.ietf.org/mailman/listinfo/saag
>>>
>>>
>>> -- 
>>> email: [e-mail] | Skype: rstruik
>>> cell: [phone] | US: [phone]
>>>
>>> _______________________________________________
>>> Cfrg mailing list
>>> [e-mail]
>>> http://www.irtf.org/mailman/listinfo/cfrg
>


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]