Re: [CFRG] compact representation and HPKE

[Dan Harkins <[e-mail]>]

   For all of these curves, p = 3 mod 4 so doing a modular square root 
is just
exponentiation to (p + 1)/4. Not sure how onerous an additional 
exponentiation
is.

   But then Mike Hamburg was saying that one can do a x-only Montgomery 
Ladder
for these curves if an exponentiation is, indeed, onerous so there are
options to consider.

   Really, there isn't a downside. We get a cleaner and more consistent 
API,
and less cruft required to be exported/imported.

   regards,

   Dan.

On 2/10/21 4:29 AM, Michael Scott wrote:
> ... 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 <[e-mail] 
> <mailto:[e-mail]>> 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 <[e-mail]
>     <mailto:[e-mail]>> 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 <[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]  <mailto:[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]  <mailto:[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] <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