Re: [CFRG] compact representation and HPKE

Great work Dan. I strongly think this is the way to go. Forcing implementations to calculate a not needed y-coordinate would be strange.

Cheers,
John

From: CFRG <cfrg-bounces@irtf.org> on behalf of Dan Harkins <dharkins@lounge.org>
Date: Monday, 8 February 2021 at 23:42
To: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [CFRG] compact representation and HPKE

  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 <rlb@ipv.sx<mailto:rlb@ipv.sx>> 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=40ericsson.com@dmarc.ietf.org<mailto:40ericsson.com@dmarc.ietf.org>> wrote:
+1

Sending the keys uncompressed makes HPKE unsuitable for constrained IoT.

-----Original Message-----
From: CFRG <cfrg-bounces@irtf.org<mailto:cfrg-bounces@irtf.org>> on behalf of Dan Harkins <dharkins@lounge.org<mailto:dharkins@lounge.org>>
Date: Friday, 6 November 2020 at 21:00
To: CFRG <cfrg@irtf.org<mailto:cfrg@irtf.org>>
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
CFRG@irtf.org<mailto:CFRG@irtf.org>
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
CFRG@irtf.org<mailto:CFRG@irtf.org>
https://www.irtf.org/mailman/listinfo/cfrg<https://protect2.fireeye.com/v1/url?k=8e4205de-d1d93cdc-8e424545-869a14f4b08c-465b9e5abce36ec9&q=1&e=a61452db-e5d8-46d2-b87b-d0f281c2fac8&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg>
_______________________________________________
CFRG mailing list
CFRG@irtf.org<mailto:CFRG@irtf.org>
https://www.irtf.org/mailman/listinfo/cfrg<https://protect2.fireeye.com/v1/url?k=7a0c280b-25971109-7a0c6890-869a14f4b08c-9306a6e8c390632d&q=1&e=a61452db-e5d8-46d2-b87b-d0f281c2fac8&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg>

_______________________________________________

CFRG mailing list

CFRG@irtf.org<mailto:CFRG@irtf.org>

https://www.irtf.org/mailman/listinfo/cfrg<https://protect2.fireeye.com/v1/url?k=66576edf-39cc57dd-66572e44-869a14f4b08c-8204a953b7ece8f9&q=1&e=a61452db-e5d8-46d2-b87b-d0f281c2fac8&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg>

--

"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

CFRG@irtf.org<mailto:CFRG@irtf.org>

https://www.irtf.org/mailman/listinfo/cfrg<https://protect2.fireeye.com/v1/url?k=9c603329-c3fb0a2b-9c6073b2-869a14f4b08c-2a44603a4c6091cb&q=1&e=a61452db-e5d8-46d2-b87b-d0f281c2fac8&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg>

--

"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