Re: [CFRG] compact representation and HPKE

... but then again if y is definitely not needed, maybe there truly is no
downside.

Mike

On Wed, Feb 10, 2021 at 12:28 PM Michael Scott <mike.scott@miracl.com>
wrote:

> Well, there is a minor downside - the recipient has to do some extra work
> (a modular square root) to reconstitute the y coordinate.
>
> For an enfeebled recipient this might be quite onerous.
>
> Mike
>
> On Mon, Feb 8, 2021 at 10:42 PM Dan Harkins <dharkins@lounge.org> wrote:
>
>>
>>   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> 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> wrote:
>>
>>> +1
>>>
>>> Sending the keys uncompressed makes HPKE unsuitable for constrained IoT.
>>>
>>> -----Original Message-----
>>> From: CFRG <cfrg-bounces@irtf.org> on behalf of Dan Harkins <
>>> dharkins@lounge.org>
>>> Date: Friday, 6 November 2020 at 21:00
>>> To: CFRG <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
>>>
>>> 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
>>> https://www.irtf.org/mailman/listinfo/cfrg
>>>
>> _______________________________________________
>> CFRG mailing list
>> CFRG@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>>
>> _______________________________________________
>> CFRG mailing listCFRG@irtf.orghttps://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 listCFRG@irtf.orghttps://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
>> CFRG@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>