Skip to main content

Threshold Key Generation and Decryption in Ed25519 and Ed448
draft-hallambaker-threshold-00

The information below is for an old version of the document.
Document Type
This is an older version of an Internet-Draft whose latest revision state is "Expired".
Author Phillip Hallam-Baker
Last updated 2020-01-05
RFC stream (None)
Formats
Stream Stream state (No stream defined)
Consensus boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-hallambaker-threshold-00
Network Working Group                                 P. M. Hallam-Baker
Internet-Draft                                     Venture Cryptography.
Intended status: Informational                            5 January 2020
Expires: 8 July 2020

      Threshold Key Generation and Decryption in Ed25519 and Ed448
                     draft-hallambaker-threshold-00

Abstract

   Threshold cryptography schemes are described with application to the
   Ed25519, Ed448, X25519 and X448 Elliptic Curves.  Threshold key
   generation allows generation of keypairs to be divided between two or
   more parties with verifiable security guaranties.  Threshold
   decryption allows elliptic curve key agreement to be divided between
   two or more parties such that all the parties must co-operate to
   complete a private key agreement operation.  The same primitives may
   be applied to improve resistance to side channel attacks.

   https://mailarchive.ietf.org/arch/browse/cfrg/
   (http://whatever)Discussion of this draft should take place on the
   CFRG mailing list (cfrg@irtf.org), which is archived at .

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on 8 July 2020.

Copyright Notice

   Copyright (c) 2020 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/

Hallam-Baker               Expires 8 July 2020                  [Page 1]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Definitions . . . . . . . . . . . . . . . . . . . . . . . . .   3
     2.1.  Requirements Language . . . . . . . . . . . . . . . . . .   3
     2.2.  Defined Terms . . . . . . . . . . . . . . . . . . . . . .   3
     2.3.  Related Specifications  . . . . . . . . . . . . . . . . .   5
     2.4.  Implementation Status . . . . . . . . . . . . . . . . . .   5
   3.  Principles  . . . . . . . . . . . . . . . . . . . . . . . . .   5
     3.1.  Application to Diffie Hellman (not normative) . . . . . .   5
     3.2.  Threshold Decryption  . . . . . . . . . . . . . . . . . .   7
       3.2.1.  Key Splitting . . . . . . . . . . . . . . . . . . . .   7
       3.2.2.  Decryption  . . . . . . . . . . . . . . . . . . . . .   7
     3.3.  Threshold Key Generation  . . . . . . . . . . . . . . . .   8
       3.3.1.  Device Provisioning . . . . . . . . . . . . . . . . .   8
       3.3.2.  Key Rollover  . . . . . . . . . . . . . . . . . . . .   9
       3.3.3.  Host Activation . . . . . . . . . . . . . . . . . . .  10
       3.3.4.  Separation of Duties  . . . . . . . . . . . . . . . .  10
     3.4.  Side Channel Resistance . . . . . . . . . . . . . . . . .  10
   4.  Application to Elliptic Curves  . . . . . . . . . . . . . . .  11
     4.1.  Implementation for Ed25519 and Ed448  . . . . . . . . . .  11
       4.1.1.  Ed25519 . . . . . . . . . . . . . . . . . . . . . . .  12
       4.1.2.  Ed448 . . . . . . . . . . . . . . . . . . . . . . . .  12
     4.2.  Implementation for X25519 and X448  . . . . . . . . . . .  13
       4.2.1.  Point Encoding  . . . . . . . . . . . . . . . . . . .  14
       4.2.2.  X25519 Point Encoding . . . . . . . . . . . . . . . .  14
       4.2.3.  X448 Point Encoding . . . . . . . . . . . . . . . . .  14
       4.2.4.  Point Addition  . . . . . . . . . . . . . . . . . . .  14
       4.2.5.  Montgomery Ladder with Coordinate Recovery  . . . . .  15
   5.  Test Vectors  . . . . . . . . . . . . . . . . . . . . . . . .  17
     5.1.  Threshold Key Generation  . . . . . . . . . . . . . . . .  17
       5.1.1.  X25519  . . . . . . . . . . . . . . . . . . . . . . .  17
       5.1.2.  X448  . . . . . . . . . . . . . . . . . . . . . . . .  19
       5.1.3.  Ed25519 . . . . . . . . . . . . . . . . . . . . . . .  21
       5.1.4.  Ed448 . . . . . . . . . . . . . . . . . . . . . . . .  22
     5.2.  Threshold Decryption  . . . . . . . . . . . . . . . . . .  24
       5.2.1.  Key Splitting X25519  . . . . . . . . . . . . . . . .  24
       5.2.2.  Decryption X25519 . . . . . . . . . . . . . . . . . .  25
       5.2.3.  Key Splitting X448  . . . . . . . . . . . . . . . . .  27
       5.2.4.  Decryption X448 . . . . . . . . . . . . . . . . . . .  29
   6.  Security Considerations . . . . . . . . . . . . . . . . . . .  31
   7.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  31
   8.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  31
   9.  Normative References  . . . . . . . . . . . . . . . . . . . .  31

Hallam-Baker               Expires 8 July 2020                  [Page 2]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   10. Informative References  . . . . . . . . . . . . . . . . . . .  32

1.  Introduction

   Public key cryptography provides greater functionality than symmetric
   key cryptography by introducing separate keys for separate roles.
   Knowledge of the public encryption key does not provide the ability
   to decrypt.  Knowledge of the public signature verification key does
   not provide the ability to sign.  Threshold cryptography extends the
   scope of traditional public key cryptography with further separation
   of roles.

   A Threshold scheme is _interchangeable_ if the inputs and outputs of
   the threshold scheme are identical to those of a conventional scheme.
   A threshold scheme is _auditable_ if it to verify that the output
   made use of a particular contribution.

   This document describes a threshold decryption and an auditable
   threshold key generation scheme for the elliptic curve scheme
   described in [RFC7748] and [RFC8032].  Both schemes are
   interchangeable in their own right but require minor modifications to
   the underlying elliptic curve systems to encode the necessary
   information in the public (X25519/X448) or private key (Ed25519/
   Ed448).

   Threshold key agreement and threshold signatures will be specified in
   future drafts.

2.  Definitions

   This section presents the related specifications and standard, the
   terms that are used as terms of art within the documents and the
   terms used as requirements language.

2.1.  Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

2.2.  Defined Terms

   The following terms are used as terms of art in this document.

   Auditable  Whether it is possible (or not) to verify that the output
      of a threshold scheme made use of a particular contribution.

Hallam-Baker               Expires 8 July 2020                  [Page 3]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   Interchangeable  A Threshold scheme is _interchangeable_ if the
      inputs and outputs of the threshold scheme are identical to those
      of a conventional scheme

   Multi-Encryption  The use of multiple decryption fields to allow a
      document encrypted under a session key to be decrypted by multiple
      parties under different decryption keys.

      Multi-Encryption allows a document to be shared with multiple
      recipients but does not allow the decryption role to be divided
      between multiple parties.

   Multi-Signatures  The use of multiple independently verifiable
      digital signatures to authenticate a document.

      Multi-Signatures allow separation of the signing roles and thus
      achieve a threshold capability.  But they are not true threshold
      signatures as the set of signers is visible to external parties.

   Onboarding  The process by which an embedded device is provisioned
      for deployment in a local network.

   Threshold Key Generation  An aggregate public, private key pair is
      constructed from a set of contributions such that the private key
      is a function of the private key of all the contributions.

      A Threshold Key Generation function is auditable if and only if
      the public component of the aggregate key can be computed from the
      public keys of the contributions alone.

   Threshold Decryption  Threshold decryption divides the decryption
      role between two or more parties.

   Threshold Key Agreement  A bilateral key agreement exchange in which
      one or both sides present multiple public keys and the key
      agreement value is a function of all of them.

      This approach allows a party to present multiple credentials in a
      single exchange, a de

   Threshold Signatures  Threshold signatures divide the signature role
      between two or more parties in such a way that the parties and
      their roles is not visible to an external observer.

Hallam-Baker               Expires 8 July 2020                  [Page 4]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

2.3.  Related Specifications

   This document extends the elliptic curve cryptography systems
   described in [RFC7748] and [RFC8032] to provide threshold
   capabilities.

   This work was originally motivated by the requirements of the
   Mathematical Mesh [draft-hallambaker-mesh-architecture]

2.4.  Implementation Status

   The implementation status of the reference code base is described in
   the companion document [draft-hallambaker-mesh-developer].

3.  Principles

   The threshold cryptography mechanisms described in this specification
   are made possible by the fact that Diffie Hellman key agreement and
   elliptic curve variants thereof support properties we call the Key
   Combination Law and the Result Combination Law.

   Let {_X_, _x_}, {_Y_, _y_}, {_A_, _a_} be {public, private} key pairs
   and r [.] S represent the Diffie Hellman operation applying the
   private key r to the public key S.

   The Key Combination law states that we can define an operator [x]
   such that there is a keypair {_Z_, _z_} such that:

   _Z_ = _X_ [x] _Y_ and _z_ = (_x_ + _y_) mod _o_ (where _o_ is the
   order of the group)

   The Result Combination Law states that we can define an operator [+]
   such that:

   (_x_ [.] _A_) [+] (_y_ [.] _A_) = (_z_ [.] _A_) = (_a_ [.] _Z_)

   It will be noted that each of these laws is interchangeable.  The
   output of the key combination law to a Diffie Hellman key pair is a
   Diffie Hellman key pair and the output of the result combination law
   is a Diffie Hellman result.  This allows modular and recursive
   application of these principles.

3.1.  Application to Diffie Hellman (not normative)

   Diffie Hellman in a modular field provides a concise demonstration of
   the key combination and result combination laws [RFC2631].  The
   realization of the threshold schemes in a modular field is outside
   the scope of this document.

Hallam-Baker               Expires 8 July 2020                  [Page 5]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   For the Diffie Hellman system in a modular field p, with exponent e:

   *  r [.] S = S^(r) mod p

   *  o = p-1

   *  _A_[x] _B_ = _A_[.] _B_ = _AB_mod _p_.

   _Proof:_

   Let z = x + y

   By definition, X = e^(x) mod p, Y = e^(y) mod p, and Z = e^(z)mod p.

   Therefore,

   Z = e^(z) mod p  = e^(x+y) mod p

      = (e^(x)e^(y)) mod p

      = e^(x)mod p.e^(y) mod p

      = X.Y

   Moreover, A = e^(a) mod p,

   Therefore,

   (A^(x) mod p).(A^(y) mod p)  = (A^(x)A^(y)) mod p)

      = (A^(x+y)) mod p)

      = A^(z) mod p

      = e^(az) mod p

      = (e^(z))^(a) mod p

      = Z^(a) mod p

   Since e^(o) mod p = 1, the same result holds for z = (x + y) mod o
   since e^(x+y+no) = e^(x+y).e^(no) = e^(x+y).1 = e^(x+y).

Hallam-Baker               Expires 8 July 2020                  [Page 6]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

3.2.  Threshold Decryption

   Threshold decryption allows a decryption key to be divided into two
   or more parts, allowing these roles to be assigned to different
   parties.  This capability can be employed within a machine to divide
   use of a private key between an implementation running in the user
   mode and a process running in a privileged mode that is bound to the
   machine.  Alternatively, threshold cryptography can be employed to

   The key combination law and result combination law provide a basis
   for threshold decryption.

3.2.1.  Key Splitting

   We begin by creating a base key pair { X, x }. The public component X
   is used to perform encryption operations by means of a key agreement
   against an ephemeral key in the usual fashion.  The private component
   x may be used for decryption in the normal fashion or to provide the
   source material for a key splitting operation.

   To split the base key into n shares { S_(1), s_(1) }, { S_(2), s_(2)
   }, ... { S_(n), s_(n) }, we begin by generating the first n-1 private
   keys in the normal fashion.  It is not necessary to generate the
   corresponding public keys as these are not required.

   The private key of the final key share s_(n) is given by:

   _s_(n) = (x - s1 - s2 - ... - sn-1) mod o_

   Thus, the base private key x is equal to the sum of the private key
   shares modulo the group order.

3.2.2.  Decryption

   To encrypt a document, we first generate an ephemeral key pair { Y, y
   }. The key agreement value e^(xy) is calculated from the base public
   key X = e^(x) and the ephemeral private key y.  A key derivation
   function is then used to obtain the session key to be used to encrypt
   the document under a symmetric cipher.

   To decrypt a document using the threshold key shares, each key share
   holder first performs a Diffie Hellman operation using their private
   key on the ephemeral public key.  The key shares are then combined
   using the result combination law to obtain the key exchange value
   from which the session key is recovered.

   The key contribution c_(i) for the holder of the i^(th) key share is
   calculated as:

Hallam-Baker               Expires 8 July 2020                  [Page 7]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   c_(i) = Y^(si)

   The key agreement value is thus

   A = c_(1) . c_(2) . ... . c_(n)

   This value is equal to the encryption key agreement value according
   to the group law.

3.3.  Threshold Key Generation

   The key combination law allows an aggregate private key to be derived
   from private key contributions provided by two or more parties such
   that the corresponding aggregate public key may be derived from the
   public keys corresponding to the contributions.  The resulting key
   generation mechanism is thus, auditable and interoperable.

3.3.1.  Device Provisioning

   Auditable Threshold Key Generation provides a simple and efficient
   means of securely provisioning keys to devices.  This is encountered
   in the IoT space as a concern in 'onboarding' and in the provisioning
   of unique keys for use with cryptographic applications (e.g.  SSH, S/
   MIME, OpenPGP, etc.).

   Consider the case in which Alice purchases an IoT connected Device D
   which requires a unique device key pair _{ X , x }_ for its
   operation.  The process of provisioning (aka 'onboarding') is
   performed using an administration device.  Traditional key pair
   generation gives us three options:

   *  Generate and install a key pair during manufacture.

   *  Generate a new key pair during device provisioning.

   *  Generate a key pair on the administration device and transfer it
      to the device being provisioned.

   The first approach has the obvious disadvantage that the manufacturer
   has knowledge of the private key.  This represents a liability for
   both the user and the manufacturer.  Less obvious is the fact that
   the second approach doesn't actually provide a solution unless the
   process of generating keys on the device is auditable.  The third
   approach is auditable with respect to the device being provisioned
   but not with respect to the administration device being used for
   provisioning.  If that device were to be compromised, so could every
   device it was used to provision.

Hallam-Baker               Expires 8 July 2020                  [Page 8]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   Threshold key generation allows the administration device and the
   joining device being provisioned to jointly provision a key pair as
   follows:

   *  The joining device has public, private key pair_{ D, d }_.

   *  A provisioning request is made for the device which includes the
      joining device public key _D_.

   *  The administration device generates a key pair contribution _{ A,
      a }_.

   *  The administration device private key is transmitted to the Device
      by means of a secure channel.

   *  The joining device calculates the aggregate key pair _{ A [x] D,
      a+d }_.

   *  The administration device authorizes the joining device to
      participate in the local network using the public key _A [x] D_.

   The Device key pair MAY be installed during manufacture or generated
   during provisioning or be derived from a combination of both using
   threshold key generation recursively.  The provisioning request MAY
   be originated by the device or be generated by a purchasing system.

   Note that the provisioning protocol does not require either party to
   authenticate the aggregate key pair.  The protocol provides security
   by ensuring that both parties obtain the correct results if and only
   if the values each communicated to the other were correct.

   Out of band authentication of the joining device public key _D_ is
   sufficient to prevent Man-in-the-Middle attack.  This may be achieved
   by means of a QR code printed on the device itself that discloses or
   provides a means of obtaining _D._

   [Note add serious warning that a party providing a private
   contribution MUST make sure they see the public key first.  Otherwise
   a rogue key attack is possible.  The Mesh protocols ensure that this
   is the case but other implementations may overlook this detail.]

3.3.2.  Key Rollover

   Traditional key rollover protocols in PKIX and other PKIs following
   the Kohnfelder model, require a multi-step interaction between the
   key holder and the Certificate Authority.

Hallam-Baker               Expires 8 July 2020                  [Page 9]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   Threshold key generation allows a Certificate Authority to implement
   key rollover with a single communication:

   Consider the case in which the service host has a base key pair { B ,
   b }. A CA that has knowledge of the Host public key B may generate a
   certificate for the time period _t_ with a fresh key as follows:

   *  Generate a key pair contribution { A_(t), a_(t) }.

   *  Generate and sign an end entity certificate C_(t) for the key B
      [x] A_(t).

   *  Transmit C_(t), a_(t) to the host by means of a secure channel

3.3.3.  Host Activation

   Modern Internet service architectures frequently make use of short
   lived, ephemeral hosts running on virtualized machines.  Provisioning
   cryptographic material in such environments is a significant
   challenge and especially so when the underlying hardware is a shared
   resource.

   The key rollover approach described above provides a means of
   provisioning short lived credentials to ephemeral hosts that
   potentially avoids the need to build sensitive keys into the service
   image or configuration.

3.3.4.  Separation of Duties

   Threshold key generation provides a means of separating
   administration of cryptographic keys between individuals.  This
   allows two or more administrators to control access to a private key
   without having the ability to use it themselves.  This approach is of
   particular utility when used in combination with threshold
   decryption.  Alice and Bob can be granted the ability to create key
   contributions allowing a user to decrypt information without having
   the ability to decrypt themselves.

3.4.  Side Channel Resistance

   Side-channel attacks, present a major concern in the implementation
   of public key cryptosystems.  Of particular concern are the timing
   attacks identified by Paul Kocher [Kocher96] and related attacks in
   the power and emissions ranges.  Performing repeated observations of
   the use of the same private key material provides an attacker with
   considerably greater opportunity to extract the private key material.

Hallam-Baker               Expires 8 July 2020                 [Page 10]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   A simple but effective means of defeating such attacks is to split
   the private key value into two or more random shares for every
   private key operation and use the result combination law to recover
   the result.

   The implementation of this approach is identical to that for
   Threshold Decryption except that instead of giving the key shares to
   different parties, they are kept by the party performing the private
   key operation.

   While this approach doubles the number of private key operations
   required, the operations MAY be performed in parallel.  Thus avoiding
   impact on the user experience.

4.  Application to Elliptic Curves

   For elliptic curve cryptosystems, the operators [x] and [.] are point
   addition.

   Implementing a robust Key Co-Generation for the Elliptic Curve
   Cryptography schemes described in [RFC7748] and [RFC8032] requires
   some additional considerations to be addressed.

   *  The secret scalar used in the EdDSA algorithm is calculated from
      the private key using a digest function.  It is therefore
      necessary to specify the Key Co-Generation mechanism by reference
      to operations on the secret scalar values rather than operations
      on the private keys.

   *  The Montgomery Ladder traditionally used to perform X25519 and
      X448 point multiplication does not require implementation of a
      function to add two arbitrary points.  While the steps required to
      create such a function are fully constrained by [RFC7748], the
      means of performing point addition is not.

4.1.  Implementation for Ed25519 and Ed448

   [RFC8032] provides all the cryptographic operations required to
   perform threshold operations and corresponding public keys.

   The secret scalars used in [RFC8032] private key operations are
   derived from a private key value using a cryptographic digest
   function.  This encoding allows the inputs to a private key
   combination to be described but not the output.  Contrawise, the
   encoding allows the inputs to a private key splitting operation to be
   described but not the output

Hallam-Baker               Expires 8 July 2020                 [Page 11]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   It is therefore necessary to provide an alternative representation
   for the Ed25519 and Ed448 private keys.  Moreover, the signature
   algorithm requires both a secret scalar and a prefix value as inputs.

   Since threshold signatures are out of scope for this document and
   [RFC8032] does not specify a key agreement mechanism, it suffices to
   specify the data formats required to encode private key values
   generated by means of threshold key generation.

4.1.1.  Ed25519

   Let the inputs to the threshold key generation scheme be a set of 32
   byte private key values _P_(1), P2 ... Pn.  For each private key
   value i in turn:_

   0.  Hash the 32-byte private key using SHA-512, storing the digest in
       a 64-octet large buffer, denoted_h_(i)_. Let n_(i) be the first
       32 octets of h_(i) and m_(i) be the remaining 32 octets of h_(i).

   1.  Prune n_(i): The lowest three bits of the first octet are
       cleared, the highest bit of the last octet is cleared, and the
       second highest bit of the last octet is set.

   2.  Interpret the buffer as the little-endian integer, forming a
       secret scalar s_(i).

   The private key values are calculated as follows:

   The aggregate secret scalar value _s_(a) = s1 + s2 + ... sn mod L,
   where L is the order of the curve._

   The aggregate prefix value is calculated by either

   *  Some function TBS on the values m_(1), m_(2), ... m_(n), or

   *  Taking the SHA256 digest of s_(a).

   The second approach is the simplest and the most robust.  It does
   however mean that the prefix is a function of the secret scalar
   rather than both being functions of the same seed.

4.1.2.  Ed448

   Let the inputs to the threshold key generation scheme be a set of 57
   byte private key values _P_(1), P2 ... Pn.  For each private key
   value i in turn:_

Hallam-Baker               Expires 8 July 2020                 [Page 12]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   0.  Hash the 57-byte private key using SHAKE256(x, 114), storing the
       digest in a 114-octet large buffer, denoted_h_(i)_. Let n_(i) be
       the first 57 octets of h_(i) and m_(i) be the remaining 57 octets
       of h_(i).

   1.  Prune n_(i): The two least significant bits of the first octet
       are cleared, all eight bits the last octet are cleared, and the
       highest bit of the second to last octet is set.

   2.  Interpret the buffer as the little-endian integer, forming a
       secret scalar s_(i).

   The private key values are calculated as follows:

   The aggregate secret scalar value _s_(a) = s1 + s2 + ... sn mod L,
   where L is the order of the curve._

   The aggregate prefix value is calculated by either

   *  Some function TBS on the values m_(1), m_(2), ... m_(n), or

   *  Taking the SHAKE256(x, 57) digest of s_(a).

   The second approach is the simplest and the most robust.  It does
   however mean that the prefix is a function of the secret scalar
   rather than both being functions of the same seed.

4.2.  Implementation for X25519 and X448

   [RFC7748] defines all the cryptographic operations required to
   perform threshold key generation and threshold decryption but does
   not describe how to implement them.

   The Montgomery curve described in [RFC7748] allows for efficient
   scalar multiplication using arithmetic operations on a single
   coordinate.  Point addition requires both coordinate values.  It is
   thus necessary to provide an extended representation for point
   encoding and provide an algorithm for recovering both coordinates
   from a scalar multiplication operation and an algorithm for point
   addition.

   The notation of [RFC7748] is followed using {u, v} to represent the
   coordinates on the Montgomery curve and {x, y} for coordinates on the
   corresponding Edwards curve.

Hallam-Baker               Expires 8 July 2020                 [Page 13]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

4.2.1.  Point Encoding

   The relationship between the u and v coordinates is specified by the
   Montgomery Curve formula itself:

   _v^(2)_ = _u^(3) + Au2 + u_

   An algorithm for extracting a square root of a number in a finite
   field is specified in . [RFC8032]

   Since _v^(2)_ has a positive (_v_) and a negative solution (_-v_), it
   follows that _v^(2)_ mod p will have the solutions _v_, _p-v_.
   Furthermore, since _p_ is odd, if _v_ is odd, _p-v_ must be even and
   vice versa.  It is thus sufficient to record whether _v_ is odd or
   even to enable recovery of the _v_ coordinate from _u_.

4.2.2.  X25519 Point Encoding

   The extended point encoding allowing the v coordinate to be recovered
   is as given in [draft-ietf-lwig-curve-representations]

   [TBS]

4.2.3.  X448 Point Encoding

   The extended point encoding allowing the v coordinate to be recovered
   is as given in [draft-ietf-lwig-curve-representations]

   [TBS]

4.2.4.  Point Addition

   The point addition formula for the Montgomery curve is defined as
   follows:

   Let P_(1) = {u_(1), v_(1)}, P_(2) = {u_(2), v_(2)}, P_(3) = {u_(3),
   v_(3)} = P_(1) + P_(2)

   By definition:

   u_(3) = B(v_(2) - v_(1))^(2) / (u_(2) - u_(1))^(2) - A - u_(1) -
   u_(2)

   = B((u_(2)v_(1) - u_(1)v_(2))^(2) ) / u_(1)u_(2) (u_(2) - u_(1))^(2)

   v_(3) = ((2u_(1) + u_(2) + A)(v_(2) - v_(1)) / (u_(2) - u_(1))) - B
   (v_(2) - v_(1))^(3) / (u_(2) -u_(1))^(3) - v_(1)

Hallam-Baker               Expires 8 July 2020                 [Page 14]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   For curves X25519 and X448, B = 1 and so:

   u_(3) = ((v_(2) - v_(1)).(u_(2) - u_(1))^(-1))^(2) - A - u_(1) -
   u_(2)

   v_(3) = ((2u_(1) + u_(2) + A)(v_(2) - v_(1)).(u_(2) - u_(1))^(-1)) -
   ((v_(2) - v_(1)).(u_(2) -u_(1))^(-1))^(3) - v_(1)

   This may be implemented using the following code:

   B = v2 - v1
   C = u2 - u1
   CINV = C^(p - 2)
   D = B * CINV
   DD = D * D
   DDD = DD * D

   u3 = DD - A - u1 - u2
   v3 = ((u1 + u1 + u2 + A) * B * CINV) - DDD - v1

   Performing point addition thus requires that we have sufficient
   knowledge of the values v_(1), v_(2).  At minimum whether one is odd
   and the other even or if both are the same.

4.2.5.  Montgomery Ladder with Coordinate Recovery

   As originally described, the Montgomery Ladder only provides the u
   coordinate as output.  L?pez and Dahab [Lopez99] provided a formula
   for recovery of the v coordinate of the result for curves over binary
   fields.  This result was then extended by Okeya and Sakurai [Okeya01]
   to prime field Montgomery curves such as X25519 and X448.  The
   realization of this result described by Costello and Smith
   [Costello17] is applied here.

   The scalar multiplication function specified in [RFC7748] takes as
   input the scalar value k and the coordinate u_(1) of the point P_(1)
   = {u_(1), v_(1)} to be multiplied.  The return value in this case is
   u_(2) where P_(2) = {u_(2), v_(2)} = k.P_(1).

   To recover the coordinate v_(2) we require the values x_2, z_2, x_3,
   z_3 calculated in the penultimate step:

Hallam-Baker               Expires 8 July 2020                 [Page 15]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

      x_1 = u
      x_2 = 1
      z_2 = 0
      x_3 = u
      z_3 = 1
      swap = 0

      For t = bits-1 down to 0:
          k_t = (k >> t) & 1
          swap ^= k_t
          // Conditional swap as specified in RFC 7748
          (x_2, x_3) = cswap(swap, x_2, x_3)
          (z_2, z_3) = cswap(swap, z_2, z_3)
          swap = k_t

          A = x_2 + z_2
          AA = A^2
          B = x_2 - z_2
          BB = B^2
          E = AA - BB
          C = x_3 + z_3
          D = x_3 - z_3
          DA = D * A
          CB = C * B
          x_3 = (DA + CB)^2
          z_3 = x_1 * (DA - CB)^2
          x_2 = AA * BB
          z_2 = E * (AA + a24 * E)

      (x_2, x_3) = cswap(swap, x_2, x_3)
      (z_2, z_3) = cswap(swap, z_2, z_3)
      Return x_2, z_2, x_3, z_3

   The values x_2, z_2 give the projective form of the u coordinate of
   the point P_(2) = {u_(2), v_(2)} = k.P_(1) and the values x_3, z_3
   give the projective form of the u coordinate of the point P_(3) =
   {u_(3), v_(3)} = (k+1).P_(1) = P_(1) + k.P_(1) = P_(1) + P_(2).

   Given the coordinates {u_(1), v_(1)} of the point P1 and the u
   coordinates of the points P_(2), P_(1) + P_(2), the coordinate v_(2)
   MAY be recovered by trial and error as follows:

   v_test = SQRT (u3 + Au2 + u)
   u_test = ADD_X (u, v, u_2, v_test)
   if (u_test == u_3)
      return u_test
   else
      return u_test +p

Hallam-Baker               Expires 8 July 2020                 [Page 16]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   Alternatively, the following MAY be used to recover {u_(2), v_(2)}
   without the need to extract the square root and using a single
   modular exponentiation operation to convert from the projective
   coordinates used in the calculation.  As with the Montgomery ladder
   algorithm above, the expression has been modified to be consistent
   with the approach used in [RFC7748] but any correct formula may be
   used.

   x_p = u
   y_p = v

   B = x_p * z_2    //v1
   C = x_2 + B      //v2
   D = X_2 - B      //v3
   DD = D^2         //v3
   E = DD. X_3      //v3
   F = 2 * A * z_2  //v1

   G = C + F        //v2
   H = x_p * x_2    //v4
   I = H + z_2      //v4
   J = G * I        //v2
   K = F * z_2      //v1
   L = J - K        //v2
   M = L * z_3      //v2

   yy_2 = M - E     //Y'
   N = 2 * y_p      //v1
   O = N * z_2      //v1
   P = O * z_3      //v1
   xx_2 = P * x_q   //X'
   zz_2 = P * z_ q  //Z'

   ZINV = (zz_2^(p - 2))
   u2 = xx_2 * ZINV
   v2 = yy_2 * ZINV

   return u2, v2

5.  Test Vectors

5.1.  Threshold Key Generation

5.1.1.  X25519

   The key parameters of the first key contribution are:

Hallam-Baker               Expires 8 July 2020                 [Page 17]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   X25519Key1 (X25519)
       UDF:        ZAAA-CTKG-X255-XXKE-YX
       Scalar:     56751742936444772792970879017152360515706108153669948
           486190735258502824077920
       Encoded Private
     60 2A E2 12  AC 8E C8 86  A1 79 51 7E  79 90 5E C2
     9B AD 10 01  B9 2D 51 33  65 DB F4 9E  23 59 78 7D
       U: 25222393324990721517739552691612440154338285166262054281502859
           684220669343438
       V: 15622452724514925334849257786951944861130311422605147559630230
           860481236780294
       Encoded Public
     CE 36 B9 F1  56 BD 92 5C  F4 B6 F5 E1  E0 BA CA 6A
     9B 7C 37 7D  F8 DC 39 CC  12 2E A6 8F  64 5E C3 37
     00

   The key parameters of the second key contribution are:

   X25519Key2 (X25519)
       UDF:        ZAAA-CTKG-X255-XXKE-Y2
       Scalar:     30800688691513612134093999707357841640579640775881469
           593062950189697563564400
       Encoded Private
     70 19 5B 38  A4 46 21 79  31 AC 48 83  60 C9 BD F8
     E1 EE 04 53  67 F2 B5 D8  9E 42 53 66  6F 92 18 44
       U: 35108630063567318397224393939085269372284744000330218923799041
           589332061533992
       V: 13827314478911339710714490558315610168380330915483870499348836
           357802235649136
       Encoded Public
     28 37 F5 39  16 C6 10 C6  8A AC 75 E9  20 EF 67 6D
     C2 6C AF 2C  E4 F6 4F C9  E9 30 6C BD  C9 C7 9E 4D
     00

   The aggregate private key is:

   Scalar_A = (Scalar_1 + Scalar_2) mod L
     = 70836469997123835938663996799427126600035261699252680723027418877
         4936630452

   Encoded Aggrgate Private Key:

     B4 54 B7 EF  13 30 0D DF  C6 CB FE 5D  6A A3 A8 C0
     7C 9C 15 54  20 20 07 0C  04 1E 48 05  93 EB 90 01

   The aggregate public key is:

Hallam-Baker               Expires 8 July 2020                 [Page 18]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   Point_A = Point_1 + Point_2

   U: 416454936139914218771704724014904891682742086807613599097165979348
       46285027335
   V: 473400233126764321363639652645349333601103100790621508110841442520
       99552212729

   Encoded Public
     07 98 75 38  67 9C 66 21  A3 0A D1 06  CF F5 81 04
     94 C0 52 C9  9C FD AE 4E  13 3B 43 9D  9A 83 12 5C

   Note that in this case, the unsigned representation of the key is
   used as the aggregate key is intended for unsigned CurveX key
   agreement.  If the result is intended for use as a key contribution,
   the signed representation is required.

5.1.2.  X448

   The key parameters of the first key contribution are:

   X448Key1 (X448)
       UDF:        ZAAA-ETKG-X44X-KEYX
       Scalar:     68165415229434843487640754974827937311214322558126978
           8055715553507401814865302008262214951100710804646043741434925
           630887320553400661768
       Encoded Private
     08 77 91 25  66 19 C6 1A  03 C7 60 9A  8C C8 10 9D
     DE F5 20 E1  A7 7F 3E 83  56 57 FE A6  C9 97 79 FB
     DC 85 55 6F  CE 17 79 70  CA 3E B5 D1  6A B0 50 6A
     60 F6 BF 3A  88 E5 15 F0
       U: 60697849609835675975297341597995979787516605306209816088918249
           8293453953345846660594020472424536065173283947670623780408505
           23120715561
       V: 60813500494147049417364978264586877278456315581444885337361828
           5076034450004202627339591608123302429557097118744860203117206
           220854848663
       Encoded Public
     29 C7 E7 1A  ED 85 B5 66  F4 CA 8F 4D  07 72 EC 4B
     15 42 FA 95  4D A3 25 F6  D2 BF C0 5E  11 C4 27 D3
     A1 43 D8 74  B6 4C C8 22  7D 64 56 58  A4 8C C6 5D
     DA F2 AA 75  DE DE 60 15  80

   The key parameters of the second key contribution are:

Hallam-Baker               Expires 8 July 2020                 [Page 19]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   X448Key2 (X448)
       UDF:        ZAAA-ETKG-X44X-KEY2
       Scalar:     67824881411761849798195083121628378835623370171088982
           6937962011129206719268741815680700006802689991287015918654801
           310197484516725932432
       Encoded Private
     90 C1 CE 67  A2 88 20 95  B9 A8 8A E7  5A 12 73 C6
     4C E3 B0 0E  3A A4 1A 72  03 39 FC 9B  47 D9 6A E0
     A2 81 63 57  77 EB 97 E5  CE 05 2C CB  EE D7 64 F6
     51 C1 42 E7  FE D9 E2 EE
       U: 32395912186842981800922536415382601434069282464793284039370624
           1565981551756628007189667971676177150776689230729229736979561
           639842244556
       V: 18056267944998342850921302138832444826477211000541459460301605
           4105989977716699286334066341414636204710801397092415122728296
           636211077711
       Encoded Public
     CC 67 05 A8  AE D3 8C 6E  17 F8 7F 66  77 14 7F 32
     D3 F6 12 1C  E2 80 A9 BF  A9 AA 41 FC  88 EF E3 F9
     38 C7 1C AA  1A 14 54 EC  F0 4D 6D 20  ED 4F 63 24
     F2 A0 68 F5  1C 09 1A 72  80

   The aggregate private key is:

   Scalar_A = (Scalar_1 + Scalar_2) mod L
     = 87935198894654874397041717160555226349504546089353009501069716070
         586506403266723929544670861554164189887604126085304951388779109
         045747

   Encoded Aggrgate Private Key:

     F3 55 F6 DD  05 50 99 B7  68 84 84 A1  C5 89 8A 79
     3A 5B F6 27  DE 24 31 97  F5 94 73 D9  14 71 E4 DB
     7F 07 B9 C6  45 03 11 56  99 44 E1 9C  59 88 B5 60
     B2 B7 02 22  87 BF F8 1E

   The aggregate public key is:

Hallam-Baker               Expires 8 July 2020                 [Page 20]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   Point_A = Point_1 + Point_2

   U: 611634634479536677984900819195998637894371405676964036939736481366
       88134799342739585406562158256601376457049422599663606975867088547
       575
   V: 547531628982729065710146631050685048629332114514125362339393102647
       61134803271330580187933395652539791547319114595107754138802418952
       4364

   Encoded Public
     F7 2E 68 4B  64 DC 2E 24  61 B9 28 14  2E 1D D9 41
     6A 29 4F A2  5F F1 AF 07  24 6C 9B 8A  9E C0 E5 58

   Note that in this case, the unsigned representation of the key is
   used as the aggregate key is intended for unsigned CurveX key
   agreement.  If the result is intended for use as a key contribution,
   the signed representation is required.

5.1.3.  Ed25519

   The key parameters of the first key contribution are:

   ED25519Key1 (ED25519)
       UDF:        ZAAA-GTKG-ED25-5XXK-EYX
       Scalar:     39507802390720856312219571924476007168388547774368948
           368537778683821975155688
       Encoded Private
     1C C7 DE DF  19 7B 39 5F  82 98 26 62  AA DE 6C 66
     04 C3 E3 A2  C8 3D 18 58  06 2C 3E EC  7C D4 B4 F2
       X: 42353721841561159243771574200946096579404715276724838688117248
           3158919506245796568293273125470706294881250827210288815928170
           449575540044968280671060652600
       Y: 14453248808291445687399372639220007070442564445118267751942208
           0837579501036794314829741330844154033441251810135221340268136
           7161993702790547954006637246092
       Encoded Public
     6D F1 94 33  33 CC 66 4D  93 89 E2 FB  38 61 21 D5
     C5 6B 29 0F  5C 12 A8 4D  99 06 31 2D  35 32 22 A5

   The key parameters of the second key contribution are:

Hallam-Baker               Expires 8 July 2020                 [Page 21]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   ED25519Key2 (ED25519)
       UDF:        ZAAA-GTKG-ED25-5XXK-EY2
       Scalar:     39507802390720856312219571924476007168388547774368948
           368537778683821975155688
       Encoded Private
     1C C7 DE DF  19 7B 39 5F  82 98 26 62  AA DE 6C 66
     04 C3 E3 A2  C8 3D 18 58  06 2C 3E EC  7C D4 B4 F2
       X: 42353721841561159243771574200946096579404715276724838688117248
           3158919506245796568293273125470706294881250827210288815928170
           449575540044968280671060652600
       Y: 14453248808291445687399372639220007070442564445118267751942208
           0837579501036794314829741330844154033441251810135221340268136
           7161993702790547954006637246092
       Encoded Public
     6D F1 94 33  33 CC 66 4D  93 89 E2 FB  38 61 21 D5
     C5 6B 29 0F  5C 12 A8 4D  99 06 31 2D  35 32 22 A5

   The aggregate private key is:

   Scalar_A = (Scalar_1 + Scalar_2) mod L
     = 66455490081190904847072782185220719282059319549388206770560479847
         89407801486

   Encoded Aggrgate Private Key:

     8E 20 46 06  EE 61 70 82  FA 37 43 E2  5A 68 E7 3C
     73 4A 36 B7  AC A4 DF 68  A7 95 5C 8E  58 3F B1 0E

   The aggregate public key is:

   Point_A = Point_1 + Point_2

   X: -78285292761951767745666894197721180606214882184104422609189932681
       69896558088044165355551471001743951239695738047106458517545601916
       4578961762059345997440
   Y: 260549350612676062448188625658154114443427558625932490186172625180
       16179787773477706605100876536271693949174654809503102876480720244
       0555166017893772852160

   Encoded Public
     8E 89 98 D0  2D 7F 76 C3  A7 FF B3 1D  2B 41 7E E9
     51 6B 51 B5  F2 84 8D 17  6F 59 9B 5B  6F 01 CF 73

5.1.4.  Ed448

   The key parameters of the first key contribution are:

Hallam-Baker               Expires 8 July 2020                 [Page 22]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   ED448Key1 (ED448)
       UDF:        ZAAA-ITKG-ED44-XKEY-X
       Scalar:     53741526827163371875813321995189037002816220481405056
           0575131176561199901538761967283817989566517114321868559709090
           857214825841130713784
       Encoded Private
     E5 0F 73 50  27 0A 2F 7D  FD D0 96 E5  03 D3 35 2C
     99 CB 71 7C  0B D9 49 E0  40 5E C7 FB  D1 F5 05 18
     18 6B 04 81  8B 4D 81 DC  33 CE DF 81  D5 EA 90 43
     D9 E5 D0 A7  F1 EF 9C F3
       X: 46070586985722000292864744471871508558334313374829024264732526
           0256877451971853613261831326120959789917482766653217856979552
           299464523257
       Y: 60551781313893332009337150573641968782237423331690407655569563
           6098829567124403075067563581124781122484845054468415282443786
           254887063867
       Encoded Public
     B5 B9 3F B5  B2 5B 82 E1  08 F5 6C 79  80 A1 68 5A
     5C BB 2A FD  27 B2 9A F8  DF 91 CD CA  60 B8 75 3F
     62 96 40 38  78 96 77 0C  21 40 E6 D4  0B 05 8F 24
     D6 FD 65 61  A2 6C C1 86  80

   The key parameters of the second key contribution are:

   ED448Key2 (ED448)
       UDF:        ZAAA-ITKG-ED44-XKEY-2
       Scalar:     53741526827163371875813321995189037002816220481405056
           0575131176561199901538761967283817989566517114321868559709090
           857214825841130713784
       Encoded Private
     E5 0F 73 50  27 0A 2F 7D  FD D0 96 E5  03 D3 35 2C
     99 CB 71 7C  0B D9 49 E0  40 5E C7 FB  D1 F5 05 18
     18 6B 04 81  8B 4D 81 DC  33 CE DF 81  D5 EA 90 43
     D9 E5 D0 A7  F1 EF 9C F3
       X: 46070586985722000292864744471871508558334313374829024264732526
           0256877451971853613261831326120959789917482766653217856979552
           299464523257
       Y: 60551781313893332009337150573641968782237423331690407655569563
           6098829567124403075067563581124781122484845054468415282443786
           254887063867
       Encoded Public
     B5 B9 3F B5  B2 5B 82 E1  08 F5 6C 79  80 A1 68 5A
     5C BB 2A FD  27 B2 9A F8  DF 91 CD CA  60 B8 75 3F
     62 96 40 38  78 96 77 0C  21 40 E6 D4  0B 05 8F 24
     D6 FD 65 61  A2 6C C1 86  80

   The aggregate private key is:

Hallam-Baker               Expires 8 July 2020                 [Page 23]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   Scalar_A = (Scalar_1 + Scalar_2) mod L
     = 16628213117375882432961168004377507211427270876895354579839960414
         666978326982600598665720267457234882718565087272340290578290296
         3178673

   Encoded Aggrgate Private Key:

     B1 0C A6 9F  18 5C CE 75  68 CF A3 94  FD 1C 20 DC
     08 4A 1A 8D  EA 8F ED 45  17 68 B6 9F  55 03 DA 18
     5F A8 2E F3  98 92 24 C7  C2 05 8E 86  9E BD 4E A2
     6F 38 45 74  67 F6 90 3A

   The aggregate public key is:

   Point_A = Point_1 + Point_2

   X: 577530061094566245645474620282168197911998758313406086914794815409
       17246422939462333536659252558650386613682198540830437043888246526
       5810
   Y: 505836808606768081321267696834164575314792405646755177389264860926
       82650383803094471233632502605998926567195957732072433352975006488
       1824

   Encoded Public
     99 67 9B 7C  5E 1C 7E 51  CD 39 A2 41  83 62 73 3E
     60 93 17 A9  20 0E E3 BA  25 B3 B5 23  A3 A7 84 2E
     9D 67 6F D7  0B 33 02 1D  EB 76 83 F8  77 D8 48 F8
     8B A3 72 E8  A9 6F 20 18  80

5.2.  Threshold Decryption

5.2.1.  Key Splitting X25519

   The encryption key pair is

Hallam-Baker               Expires 8 July 2020                 [Page 24]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   X25519KeyA (X25519)
       UDF:        ZAAA-CTHD-X255-XXKE-YA
       Scalar:     36212799908425711450656372795692477094724455418915704
           216848228525958587810064
       Encoded Private
     10 01 D5 D1  E2 D3 DB 42  9E 40 5F D9  DB AE E8 09
     DE 43 C3 E6  D1 4F 3A 31  92 BF 19 8A  E9 B7 0F 50
       U: 14523539712308371644546850739155588238080554014514563739095172
           886049239361031
       V: 56685060472089790044070522288405984326906734250304251487683593
           932889808473139
       Encoded Public
     07 66 84 48  25 85 F6 4A  3A EE DF B7  69 1B 57 51
     EC 18 BE AF  08 BA 0D FE  BE F8 74 4E  3C 08 1C 20

   To create n key shares we first create n-1 key pairs in the normal
   fashion.  Since these key pairs are only used for decryption
   operations, it is not necessary to calculate the public components:

   X25519Key1 (X25519)
       UDF:        ZAAA-CTHD-X255-XXKE-YX
       Scalar:     32951726132685026729149224926255648061071804906258082
           061427666995947179849152
       Encoded Private
     C0 B5 33 D4  F3 D0 16 4F  96 DF C3 AD  97 93 02 EF
     B4 25 E2 46  A3 69 1D 22  9B 5B A2 78  1C 04 DA 48

   The secret scalar of the final key share is the secret scalar of the
   base key minus the sum of the secret scalars of the other shares
   modulo the group order:

   Scalar_2 = (Scalar_A - Scalar_1) mod L
       = 403147584512037825404691865456117698808221309075461782425833707
           7336679400315
   This is encoded as a binary integer in little endian format:

     7B 43 64 61  E9 28 4D 79  AB 9C 6E CC  9F 79 14 3D
     92 69 A5 2D  75 B9 57 53  2D 1B BC 02  06 BC E9 08

5.2.2.  Decryption X25519

   The means of encryption is unchanged.  We begin by generating an
   ephemeral key pair:

Hallam-Baker               Expires 8 July 2020                 [Page 25]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   X25519KeyE (X25519)
       UDF:        ZAAA-CTHD-X255-XXKE-YE
       Scalar:     41955577142906312619127105554814681129195921605852142
           704362465226652441661496
       Encoded Private
     38 50 3C 88  22 4F 61 D7  9A 2E 1D 71  F0 31 74 44
     A2 3B 2B 35  21 21 CA 19  4B 11 EB F0  DF 03 C2 5C
       U: 10080018124246254127076649374753145019412450363156572968151721
           892767560820008
       V: 43683938787921854603630290352714276342923724280578266457509078
           671566344321831
       Encoded Public
     28 E5 5E 1D  DD 1D 93 71  24 53 0A 83  B3 68 0D 28
     8F 37 AC 53  B6 65 97 7E  C1 54 44 41  8C 16 49 16

   The key agreement result is given by multiplying the public key of
   the encryption pair by the secret scalar of the ephemeral key to
   obtain the u-coordinate of the result.

   U: 247351751388894803426442650867524924086144759194834658830326105266
       22202018180

   The u-coordinate is encoded in the usual fashion (i.e. without
   specifying the sign of v).

     84 39 A5 21  13 F9 13 F0  7F F4 44 C0  DF 5D 44 DD
     DD F4 9B 87  4C DD E1 AB  64 00 8F A2  ED 9C AF 36

   The first decryption contribution is generated from the secret scalar
   of the first key share and the public key of the ephemeral.

   The outputs from the Montgomery Ladder are:

   x_2 57800249527850149046770413207257250301842844049677844025524059085
       132359257003
   z_2 37229326806761131733056994095424883574786241198535734197174081138
       402379671391
   x_3 30722194817314627970562030033494699359853137448471883846088158083
       361967945513
   z_3 29143359268139878301695995826542801325089258636824690596939399658
       126254126746

   The coordinates of the corresponding point are:

   u 2625200443692459084967263034650122583671912028244890150161521677645
       8728744244
   v 2340339249609928967870268630489687123941624857494487121340604194885
       7707717709

Hallam-Baker               Expires 8 July 2020                 [Page 26]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   The encoding of this point specifies the u coordinate and the sign
   (oddness) of the v coordinate:

     28 E5 5E 1D  DD 1D 93 71  24 53 0A 83  B3 68 0D 28
     8F 37 AC 53  B6 65 97 7E  C1 54 44 41  8C 16 49 16

   The second decryption contribution is generated from the secret
   scalar of the second key share and the public key of the ephemeral in
   the same way:

   u 2568180775076864300893967221119748767931055928591855851227298301978
       9028635830
   v 5237624535641756510077423429806596028526835148653096601777403098805
       4910628425

     28 E5 5E 1D  DD 1D 93 71  24 53 0A 83  B3 68 0D 28
     8F 37 AC 53  B6 65 97 7E  C1 54 44 41  8C 16 49 16

   To obtain the key agreement value, we add the two decryption
   contributions:

   u 5363809193902384353244842537457427150937755976201184630020143767288
       0976727749
   v 2576238777948215852102595446870010694371604288066653261024661407554
       3602367190

   This returns the same u coordinate value as before, allowing us to
   obtain the encoding of the key agreement value and decrypt the
   message.

5.2.3.  Key Splitting X448

   The encryption key pair is

Hallam-Baker               Expires 8 July 2020                 [Page 27]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   X448KeyA (X448)
       UDF:        ZAAA-ETHD-X44X-KEYA
       Scalar:     70596789123829480733485730386174565339013185647363028
           6777277621057939099785091228353248522408450794128800398810019
           569879502484967206280
       Encoded Private
     88 2D AF 58  10 66 9E 1E  F9 F2 C5 76  A2 00 86 F5
     B0 B9 C6 B9  E6 34 12 57  64 E3 63 B7  99 48 01 77
     9B A3 49 2D  7C B8 80 D7  63 44 6B C9  CB 83 F0 01
     B6 55 E0 92  1C 2A A6 F8
       U: 54256629638851994806054576189463839532492460394052748417730874
           4299533502601001906894660938607827805200569088593927035891085
           28218439174
       V: 12640494198304757803713993624351573936804262085795518571061045
           0631383333635306581037675004961525698205648857075020359124084
           524068583614
       Encoded Public
     06 FE 38 7A  1B 1E 99 D4  89 00 07 B9  88 6F 97 01
     BD 88 BB 9D  A9 31 30 CC  47 E6 2F 9C  44 35 AF A4

   To create n key shares we first create n-1 key pairs in the normal
   fashion.  Since these key pairs are only used for decryption
   operations, it is not necessary to calculate the public components:

   X448Key1 (X448)
       UDF:        ZAAA-ETHD-X44X-KEYX
       Scalar:     63066265672668423343291438147840057172035337936373473
           3594300758463732521976388313294665447253881782852832499090049
           354258188417511652528
       Encoded Private
     B0 FC CE 55  87 AA A5 36  D2 5B E5 F2  5C 1B F7 9A
     5A 3D 97 D8  BB C0 81 84  98 3B 7C 29  C3 02 FC AE
     91 1B EA 67  68 C5 5E 87  7A ED 16 1F  CB D0 20 9D
     C0 D6 62 BD  0F 35 20 DE

   The secret scalar of the final key share is the secret scalar of the
   base key minus the sum of the secret scalars of the other shares
   modulo the group order:

Hallam-Baker               Expires 8 July 2020                 [Page 28]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   Scalar_2 = (Scalar_A - Scalar_1) mod L
       = 646627804476669823064550215361382899916128546345584148789705309
           5564959403070244163454368262048594523846084193642728800427461
           1461310355
   This is encoded as a binary integer in little endian format:

     93 47 14 FF  94 BE F6 5C  77 63 44 89  DD CA 83 A6
     1A 79 82 CA  9E F6 6B 7D  98 23 59 77  60 4B FD 25
     2D BF 33 95  E4 7D DF 5E  DE 31 82 E8  96 54 11 9F
     76 2C 43 50  2C 5F C6 16

5.2.4.  Decryption X448

   The means of encryption is unchanged.  We begin by generating an
   ephemeral key pair:

   X448KeyE (X448)
       UDF:        ZAAA-ETHD-X44X-KEYE
       Scalar:     40831502887772840901106715270468009328116701340228919
           4447950742749557088789408677311466089336893170031425082958041
           776608657845012501716
       Encoded Private
     D4 94 79 EE  56 3A 43 D5  FC EB 88 3E  F0 63 EF 2F
     B0 92 B2 9D  FD E1 43 8F  67 70 2A FC  2A AB A3 8B
     40 5A C6 D8  DE 8E B8 81  BF AD 17 BA  14 7F A4 B0
     D4 B1 9F CE  D3 0D D0 8F
       U: 41902542857582644710501442087876846551351583947506685319975417
           2921931242764163121977613761818608927787788470856012050834001
           655292441835
       V: 40254626888669687592165362896510117701831215997629302922912638
           4107109948063151002535904960734463095918076287222011626898597
           213849340021
       Encoded Public
     EB 34 D3 9E  92 3E 82 CC  E6 EC 77 9F  3D 11 83 3C
     B6 5B 5C 04  E8 1F D6 E1  07 C0 62 FE  F8 F6 34 BB

   The key agreement result is given by multiplying the public key of
   the encryption pair by the secret scalar of the ephemeral key to
   obtain the u-coordinate of the result.

   U: 414519841929159382730636919036875317796178034011999213235983537052
       30510678702415242441193107876747178183775523375063128358893667955
       0233

   The u-coordinate is encoded in the usual fashion (i.e. without
   specifying the sign of v).

Hallam-Baker               Expires 8 July 2020                 [Page 29]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

     19 ED 3F 7A  63 6D AA 9A  3E 05 29 DE  CC BA C7 F1
     E0 A7 FA C0  C4 70 E0 E1  A5 FC DA 0A  B0 52 EC 8A

   The first decryption contribution is generated from the secret scalar
   of the first key share and the public key of the ephemeral.

   The outputs from the Montgomery Ladder are:

   x_2 60087238657789265874539701675840521614326868580285788286550399232
       20277081132468800878653228200859196207538481852097024468118288584
       83595
   z_2 12573140552649037921890899942919440571502561130496393232716617155
       24490660805576517881339517005970098784771472127066810694797758409
       67645
   x_3 40216911160845555507626938485596306260547743077930604703891475599
       53207238052152872831803734397389643529057507149471429452955111471
       57394
   z_3 48671808823760924633626118221453591105199403417491562559814414359
       34079336265430685974504655698846599309734305554546571306740770389
       79747

   The coordinates of the corresponding point are:

   u 5310627084956226133549480379012439149584638171147187426442235629260
       04186474991811830611467926523417739685244466041108245014409383321
       437
   v 6480384951984610654865132490606294355962228129695701220316681167173
       89634554460437237795204236689985354028508124817314496063921770833
       81

   The encoding of this point specifies the u coordinate and the sign
   (oddness) of the v coordinate:

     EB 34 D3 9E  92 3E 82 CC  E6 EC 77 9F  3D 11 83 3C
     B6 5B 5C 04  E8 1F D6 E1  07 C0 62 FE  F8 F6 34 BB

   The second decryption contribution is generated from the secret
   scalar of the second key share and the public key of the ephemeral in
   the same way:

   u 2432029307606011854651950642127064534858415441240032460817128643691
       02601495764607628214871657677482439232238254450281582409532827123
       057
   v 3304237495909049135999182737314299324454426462198935317955136317282
       40167193898154033571033048069157608137872491595181800632292085611
       537

Hallam-Baker               Expires 8 July 2020                 [Page 30]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

     EB 34 D3 9E  92 3E 82 CC  E6 EC 77 9F  3D 11 83 3C
     B6 5B 5C 04  E8 1F D6 E1  07 C0 62 FE  F8 F6 34 BB

   To obtain the key agreement value, we add the two decryption
   contributions:

   u 2259776336573351712090323684006287979378142231675451855263136351631
       84627019682834233607456823018602790573389381890060345691088913511
       436
   v 3356804465434915738990773252496451168197759413718456519751139752920
       22788339143143140400339843420207702195408750068698590142923542805
       226

   This returns the same u coordinate value as before, allowing us to
   obtain the encoding of the key agreement value and decrypt the
   message.

6.  Security Considerations

   This section TBS

   One concern to be particularly careful of is that when adding two
   public keys, a rogue key attack is possible.  The security of the
   private keys is the maximum of the two inputs but the trustworthiness
   of the public keys is the minimum.

7.  IANA Considerations

   This document requires no IANA actions (yet).

   It will be necessary to define additional code points for the signed
   version of the X25519 and X448 public key and the threshold
   decryption final private keys.

8.  Acknowledgements

   Rene Struik, Tony Arcieri, Scott Fluhrer, Scott Fluhrer, Dan Brown,
   Mike Hamburg

9.  Normative References

   [draft-ietf-lwig-curve-representations]
              Struik, R., "Alternative Elliptic Curve Representations",
              Work in Progress, Internet-Draft, draft-ietf-lwig-curve-
              representations-08, 24 July 2019,
              <https://tools.ietf.org/html/draft-ietf-lwig-curve-
              representations-08>.

Hallam-Baker               Expires 8 July 2020                 [Page 31]
Internet-Draft   Threshold Key Generation and Decryption    January 2020

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/rfc/rfc2119>.

   [RFC7748]  Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
              for Security", RFC 7748, DOI 10.17487/RFC7748, January
              2016, <https://www.rfc-editor.org/rfc/rfc7748>.

   [RFC8032]  Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
              Signature Algorithm (EdDSA)", RFC 8032,
              DOI 10.17487/RFC8032, January 2017,
              <https://www.rfc-editor.org/rfc/rfc8032>.

10.  Informative References

   [Costello17]
              Costello, C. and B. Smith, "Montgomery curves and their
              arithmetic", 2017.

   [draft-hallambaker-mesh-architecture]
              Hallam-Baker, P., "Mathematical Mesh 3.0 Part I:
              Architecture Guide", Work in Progress, Internet-Draft,
              draft-hallambaker-mesh-architecture-11, 23 October 2019,
              <https://tools.ietf.org/html/draft-hallambaker-mesh-
              architecture-11>.

   [draft-hallambaker-mesh-developer]
              Hallam-Baker, P., "Mathematical Mesh: Reference
              Implementation", Work in Progress, Internet-Draft, draft-
              hallambaker-mesh-developer-09, 23 October 2019,
              <https://tools.ietf.org/html/draft-hallambaker-mesh-
              developer-09>.

   [Kocher96] Kocher, P. C., "Timing attacks on implementations of
              Diffie-Hellman, RSA, DSS, and other systems.", 1996.

   [Lopez99]  L?opez, J. and R. Dahab, "Fast multiplication on elliptic
              curves over GF(2m) without precomputation.", 1999.

   [Okeya01]  Okeya, K. and K. Sakurai, "Efficient elliptic curve
              cryptosystems from a scalar multiplication algorithm with
              recovery of the y-coordinate on a Montgomeryform elliptic
              curve.", 2001.

   [RFC2631]  Rescorla, E., "Diffie-Hellman Key Agreement Method",
              RFC 2631, DOI 10.17487/RFC2631, June 1999,
              <https://www.rfc-editor.org/rfc/rfc2631>.

Hallam-Baker               Expires 8 July 2020                 [Page 32]