Re: [CFRG] compact representation and HPKE

[Dan Harkins <[e-mail]>]

   Hello again,

   I'd like to resurrect this before it becomes "it's too late to make 
changes
that affect the wire". I created a pull request on github some time ago but
it's been ignored so let me try again here (we still technically do our work
on mailing lists).

   When I brought it up initially there was a +1 and, as Mike notes, the
y-coordinate is not needed. This 04 || x || y format for a key is just some
ancient Certicom proposal and there's really no reason to perpetuate that.

   The y-coordinate is extraneous. Getting rid of it for the NIST curves 
will
make the API much cleaner and consistent.

   This will reduce the size of the serialized public key by more than 50%
and for apps that care about such things this would be a tremendous
improvement.

   Richard noted that one can lop off the 04 and the y-coordinate after
serialization and pass x alone as part of the app using HPKE and then have
the other size reconstruct it (with either y since the sign doesn't
matter) before passing it on to be deserialized. While technically true,
that completely defeats the whole point of formalizing this process.

   In my pull request I noted that it does change the test vectors and that
I would be happy to generate them. Well, I did it. I have new test vectors
(based on -07) and will happily contribute them if asked. If the test 
vectors
get changed again (with a new version string) I can reproduce new ones minus
the y-coordinate in a matter of minutes.

   Please consider this request. There is no downside to it.

   regards,

   Dan.

On 11/6/20 4:44 PM, Dan Harkins wrote:
>
>   Yes, this is exactly right. The y-coordinate is not needed for these 
> KEMs
> as the sign is unimportant.
>
>   The spec will be simpler and the interface more uniform if you do this.
>
>   The whole point of HPKE is to make a callable API out of this 
> process that
> had been done ad hoc. Requiring a app that is taking advantage of this 
> API
> to take the output of the API and parse through it, throwing away one half
> of one of the output strings and lopping off the first octet, is defeating
> the whole purpose and is expecting a lot. The more this is a black box the
> better.
>
>   regards,
>
>   Dan.
>
> On 11/6/20 3:19 PM, Mike Hamburg wrote:
>> Hello Richard,
>>
>> I haven’t paid much attention to HPKE, so it’s likely I’m missing 
>> something here, but why not use the x-only Montgomery ladder on NIST 
>> curves?  That’s the fastest and simplest approach, and it can operate 
>> with or without the y-coordinates.
>>
>> Also, some implementations do not compute both the x- and 
>> y-coordinates, and it would be more convenient not to compute or send 
>> even a sign bit if you’re intending to use an x-only ladder.
>>
>> Cheers,
>> — Mike
>>
>>> On Nov 6, 2020, at 10:19 PM, Richard Barnes <[e-mail] 
>>> <mailto:[e-mail]>> wrote:
>>>
>>> Nothing about this says that you have to *send* the keys 
>>> uncompressed.  You can use whatever representation you want on the 
>>> wire.  You just have to decompress them before you put them into the 
>>> key schedule. Which you're probably doing anyway, because you need 
>>> both coordinates to do point multiplication with these curves.  So I 
>>> am inclined not to make this change.
>>>
>>> --Richard
>>>
>>> On Fri, Nov 6, 2020 at 4:52 PM John Mattsson 
>>> <john.mattsson=[e-mail] 
>>> <mailto:[e-mail]>> wrote:
>>>
>>>     +1
>>>
>>>     Sending the keys uncompressed makes HPKE unsuitable for
>>>     constrained IoT.
>>>
>>>     -----Original Message-----
>>>     From: CFRG <[e-mail]
>>>     <mailto:[e-mail]>> on behalf of Dan Harkins
>>>     <[e-mail] <mailto:[e-mail]>>
>>>     Date: Friday, 6 November 2020 at 21:00
>>>     To: CFRG <[e-mail] <mailto:[e-mail]>>
>>>     Subject: [CFRG] compact representation and HPKE
>>>
>>>        Hello,
>>>
>>>        When doing a DH-based KEM with the NIST curves, HPKE
>>>     specifies that
>>>     SerializePublicKey and DeserializePublicKey use the uncompressed
>>>     format
>>>     from SECG. This ends up using 2*Ndh+1 octets to represent the serial
>>>     form of the public key.
>>>
>>>        Since compact output is being used in DH-based KEMs-- that
>>>     is, the
>>>     secret result of DH() is the x-coordinate of the resulting EC
>>>     point--
>>>     it would also be possible to use compact representation (per RFC
>>>     6090)
>>>     and have SerializePublicKey merely do integer-to-octet string
>>>     conversions of the x-coordinate. DeserializePublicKey would then
>>>     do octet string-to-integer conversion for the x-coordinate and
>>>     use the
>>>     equation of the curve to choose the y-coordinate. The sign isn't
>>>     important because we're doing compact output.
>>>
>>>        This would make the interface for the NIST curves and the
>>>     Bernstein
>>>     curves be uniform-- Serialize would produce an octet string of Ndh
>>>     and Deserialize would consume an octet string of Ndh-- at the cost
>>>     of some CPU inside DeserializePublicKey.
>>>
>>>        Please consider this suggestion.
>>>
>>>        regards,
>>>
>>>        Dan.
>>>
>>>     -- 
>>>     "The object of life is not to be on the side of the majority, but to
>>>     escape finding oneself in the ranks of the insane." -- Marcus
>>>     Aurelius
>>>
>>>     _______________________________________________
>>>     CFRG mailing list
>>>     [e-mail] <mailto:[e-mail]>
>>>     https://protect2.fireeye.com/v1/url?k=513cd874-0ea7e231-513c98ef-867b36d1634c-ce26b08a2499b9a3&q=1&e=4f2b4ce0-8d52-4a80-b41e-0f7537355d35&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg
>>>
>>>     _______________________________________________
>>>     CFRG mailing list
>>>     [e-mail] <mailto:[e-mail]>
>>>     https://www.irtf.org/mailman/listinfo/cfrg
>>>
>>> _______________________________________________
>>> CFRG mailing list
>>> [e-mail] <mailto:[e-mail]>
>>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>> _______________________________________________
>> CFRG mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>
> -- 
> "The object of life is not to be on the side of the majority, but to
> escape finding oneself in the ranks of the insane." -- Marcus Aurelius
>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg

-- 
"The object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." -- Marcus Aurelius