Re: [Cfrg] Fwd: New Version Notification for draft-barnes-cfrg-mult-for-7748-00.txt

On Mon, Nov 4, 2019 at 6:53 PM Richard Barnes <rlb@ipv.sx> wrote:

> Hi CFRG folks,
>
> This draft is a proposal to address a deficiency in X25519 and X448 that
> has been noted a couple of times on this list (e.g., [1]), namely the fact
> that multiplication of scalars and point multiplication do not commute.
> While looking into applications of updateable public-key encryption in the
> context of MLS [2], my co-authors came upon a solution that while not
> perfect, works in all but a statistically insignificant number of cases.
>

If you have a ladder that doesn't require the high bit to be in any
particular place, then you're fine.  What's the application where you
cannot modify the implementation to compute n*X for any n, not just one of
a particular length? Secondly the calculation assumes d uniformly random:
but if d is say 2, then whether or not the generation fails is entirely
dependent on the second bit of y if we write sk=2^254+8y, as 2*sk is
2^255+8*2*y, which if it's in the fail range proves y<x/2, which is true
for about half the possibly y if I understand the notation correctly. What
I don't know is if you can do this again, and extract another bit, and
another, etc.

> The draft describes how to do scalar multiplication in a way that is
> compatible with point multiplication in the X25519 and X448 groups,
> describes the cases where these algorithms can fail, and provides methods
> for detecting failure.  While "move to Ristretto" is also a solution to
> this problem, it seemed like a solution for X25519 / X448, even if partial,
> might have a slightly faster path to deployment.
>
> As with any -00 draft, feedback is very welcome!  If Go is your preferred
> medium, we've also implemented the relevant concepts in the corresponding
> GitHub repo [3].
>
> Thanks,
> --Richard
>
> [1] https://mailarchive.ietf.org/arch/msg/cfrg/JVg30dldjr4pcwZ1perpA1k-OGQ
> [2] https://eprint.iacr.org/2019/1189
> [3] https://github.com/bifurcation/draft-barnes-cfrg-mult-for-7748/
>
>
> ---------- Forwarded message ---------
> From: <internet-drafts@ietf.org>
> Date: Mon, Nov 4, 2019 at 6:44 PM
> Subject: New Version Notification for
> draft-barnes-cfrg-mult-for-7748-00.txt
> To: Richard L. Barnes <rlb@ipv.sx>, Joël Alwen <jalwen@wickr.com>, Sandro
> Corretti <corettis@gmail.com>
>
>
>
> A new version of I-D, draft-barnes-cfrg-mult-for-7748-00.txt
> has been successfully submitted by Richard L. Barnes and posted to the
> IETF repository.
>
> Name:           draft-barnes-cfrg-mult-for-7748
> Revision:       00
> Title:          Homomorphic Multiplication for X25519 and X448
> Document date:  2019-11-04
> Group:          Individual Submission
> Pages:          10
> URL:
> https://www.ietf.org/internet-drafts/draft-barnes-cfrg-mult-for-7748-00.txt
> Status:
> https://datatracker.ietf.org/doc/draft-barnes-cfrg-mult-for-7748/
> Htmlized:
> https://tools.ietf.org/html/draft-barnes-cfrg-mult-for-7748-00
> Htmlized:
> https://datatracker.ietf.org/doc/html/draft-barnes-cfrg-mult-for-7748
>
>
> Abstract:
>    In some contexts it is useful for holders of the private and public
>    parts of an elliptic curve key pair to be able to independently apply
>    an updates to those values, such that the resulting updated public
>    key corresponds to the updated private key.  Such updates are
>    straightforward for older elliptic curves, but for X25519 and X448,
>    the "clamping" prescribed for scalars requires some additional
>    processing.  This document defines a multiplication procedure that
>    can be used to update X25519 and X448 key pairs.  This algorithm can
>    fail to produce a result, but only with negligible probability..
>    Failures can be detected by the holder of the private key.
>
>
>
>
> Please note that it may take a couple of minutes from the time of
> submission
> until the htmlized version and diff are available at tools.ietf.org.
>
> The IETF Secretariat
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.