[Docs] [txt|pdf|xml|html] [Tracker] [Email] [Nits]

Versions: 00 01 02 03 04 05

Network Working Group                                 P. M. Hallam-Baker
Internet-Draft                                     Venture Cryptography.
Intended status: Informational                            5 January 2020
Expires: 8 July 2020


              Threshold Signatures Using Ed25519 and Ed448
                  draft-hallambaker-threshold-sigs-00

Abstract

   A Threshold signature scheme is described.  The signatures created
   are computationally indistinguishable from those produced using the
   Ed25519 and Ed448 curves as specified in RFC8032 except in that they
   are non-deterministic.  Threshold signatures are a form of digital
   signature whose creation requires two or more parties to interact but
   does not disclose the number or identities of the parties involved.

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/
   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.






Hallam-Baker               Expires 8 July 2020                  [Page 1]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Definitions . . . . . . . . . . . . . . . . . . . . . . . . .   4
     2.1.  Requirements Language . . . . . . . . . . . . . . . . . .   4
     2.2.  Defined Terms . . . . . . . . . . . . . . . . . . . . . .   4
     2.3.  Related Specifications  . . . . . . . . . . . . . . . . .   4
     2.4.  Implementation Status . . . . . . . . . . . . . . . . . .   4
   3.  Threshold Signature Construction  . . . . . . . . . . . . . .   4
     3.1.  Threshold signature . . . . . . . . . . . . . . . . . . .   6
     3.2.  Ed2519 Signature  . . . . . . . . . . . . . . . . . . . .   8
     3.3.  Ed448 Signature . . . . . . . . . . . . . . . . . . . . .   9
     3.4.  Security Analysis . . . . . . . . . . . . . . . . . . . .  10
       3.4.1.  Replay Attack . . . . . . . . . . . . . . . . . . . .  10
       3.4.2.  Malicious Contribution Attack . . . . . . . . . . . .  11
       3.4.3.  Rogue Key Attack  . . . . . . . . . . . . . . . . . .  11
   4.  Unanimous Signature . . . . . . . . . . . . . . . . . . . . .  12
     4.1.  Using threshold key generation  . . . . . . . . . . . . .  12
     4.2.  Using key splitting . . . . . . . . . . . . . . . . . . .  13
   5.  Quorate Signature . . . . . . . . . . . . . . . . . . . . . .  13
     5.1.  Key Generation  . . . . . . . . . . . . . . . . . . . . .  13
     5.2.  Calculating the secret scalar value . . . . . . . . . . .  14
   6.  Test Vectors  . . . . . . . . . . . . . . . . . . . . . . . .  15
     6.1.  Unanimous Threshold Signature Ed25519 . . . . . . . . . .  15
     6.2.  Unanimous Threshold Signature Ed448 . . . . . . . . . . .  17
     6.3.  Quorate Threshold Signature Ed25519 . . . . . . . . . . .  20
     6.4.  Quorate Threshold Signature Ed448 . . . . . . . . . . . .  23
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  25
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  25
   9.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  25
   10. Normative References  . . . . . . . . . . . . . . . . . . . .  26
   11. Informative References  . . . . . . . . . . . . . . . . . . .  26

1.  Introduction

   Threshold encryption and key generation provide compelling advantages
   over single private key approaches because splitting the private key
   permits the use of that key to be divided between two or more roles.

   All existing digital signatures allow the signer role to be divided
   between multiple parties by attaching multiple signatures to the
   signed document.  This approach, known as multi-signatures is
   distinguished from a threshold signature scheme in that the identity
   and roles of the individual signers is exposed.  In a threshold
   signature scheme, the creation of a single signature requires the
   participation of multiple signers and the signature itself does not
   reveal the means by which it was constructed.




Hallam-Baker               Expires 8 July 2020                  [Page 2]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   Rather than considering multi-signatures or threshold signatures to
   be inherently superior, it is more useful to regard both as two
   points on a continuum of choices:

   Multi-signatures  Multiple digital signatures on the same document.
      Multi-signatures are simple to create and provide the verifier
      with more information but require the acceptance criteria to be
      specified independently of the signature itself.  This requires
      that the application logic or PKI provide some means of describing
      the criteria to be applied.

   Multi-party key release  A single signature created using a single
      private key stored in an encrypted form whose use requires
      participation of multiple key decryption shares.

   Threshold signatures  A single signature created using multiple
      signature key shares.  Signature creation may be subject to
      complex criteria such as requiring an (n,t) quorum of signers but
      these criteria are fixed at the time the signature is created

   Aggregate Signatures  A single signature created using multiple
      signature key shares such that validation of the aggregate
      signature serves to validate the participation of each of the
      individual signers.

   This document describes a scheme that creates threshold signatures
   that are computationally indistinguishable from those produced
   according to the algorithm specified in [RFC8032].  The scheme does
   not support the creation of aggregate signatures.

   Two versions of the algorithm are presented.  Both versions allow a
   creation of a signature to be divided between a set of n signers such
   that a minimum of t signers are required to create a signature.  The
   first version of the algorithm (unanimous signature) requires that
   every member of the set of signers participate in the signing process
   (i.e. n=t).  The second version (quorate signature) allows a
   signature to be created by a subset of the authorized signers.

   The unanimous signature scheme allows key shares to be generated by
   either dividing a master key or using threshold key generation to
   construct the master key from two or more key contributions as
   described in [draft-hallambaker-threshold].

   The quorate signature scheme requires that the signature key shares
   be derived from a master signature key using Shamir secret sharing.
   The process of key share generation is thus fundamentally one of
   dividing a master key.




Hallam-Baker               Expires 8 July 2020                  [Page 3]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   If required, division of the signing key administration roles may be
   achieved by using threshold key generation to construct the master
   key and performing the key splitting process separately for each
   contribution.

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

   See [draft-hallambaker-threshold].

2.3.  Related Specifications

   This document extends the approach described in
   [draft-hallambaker-threshold] to support threshold signatures.  The
   use of Lagrange polynomials to resolve Shamir Secret Shares is
   currently described in the Uniform Data Fingerprint specification
   [draft-hallambaker-mesh-udf].  It is expected that these three
   documents will eventually form the basis for two CFRG proposals.

2.4.  Implementation Status

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

3.  Threshold Signature Construction

   The threshold signatures created according to the algorithms
   described in this document are compatible with but not identical to
   the signatures created according to the scheme described in
   [RFC8032].  In particular:

   *  The signature verification algorithm is unchanged.

   *  The unanimous threshold scheme produces values of R and S that are
      deterministic but different from the values that would be obtained
      by using the aggregate private key to sign the same document.




Hallam-Baker               Expires 8 July 2020                  [Page 4]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   *  The deterministic quorate threshold scheme produces values of R
      and S that are deterministic for a given set of signers but will
      change for a different set of signers or if the aggregate private
      key was used to sign the same document.

   *  ?The non-deterministic quorate threshold scheme produces values of
      R and S that will be different each time the document is signed.

   Recall that a digital signature as specified by [RFC8032] consists of
   a pair of values S, R calculated as follows:

   R = r.B

   S = r + k.s mod L

   Where  B is the base point of the elliptic curve.

      r is an unique, unpredictable integer value such that 0 r L

      k is the result of applying a message digest function determined
      by the curve (Ed25519, Ed448) to a set of parameters known to the
      verifier which include the values R, A and PH(M).

      A is the public key of the signer, A = s.B

      PH(M) is the prehash function of the message value.

      s is the secret scalar value

      L is the order of the elliptic curve group.

   To verify the signature, the verifier calculates:

   S.B = R + k.A

   Therefore:

   S.B = (r + k.s).B = r.B +k.(s.B) = R + k.A

   The value r plays a critical role in the signature scheme as it
   serves to prevent disclosure of the secret scalar.  If the value r is
   known, s can be calculated as s = (S-r).k^(-1) mod L.  It is
   therefore essential that the value r be unguessable.

   Furthermore, if the same value of r is used to sign two different
   documents, this results two signatures with the same value R and
   different values of k and S.  Thus




Hallam-Baker               Expires 8 July 2020                  [Page 5]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   S_(1) = r + k_(1).s mod L

   S_(2) = r + k2.s mod L

   s = (S_(1) - S_(2))(k_(1) - k_(2))^(-1) mod L

   The method of constructing r specified in [RFC8032] ensures that the
   value r is unique and unguessable provided that the private key from
   which the secret scalar value is derived is kept secret.

   The use of a deterministic means of generating the value r permits
   auditing of hardware and software implementations to determine if the
   correct means of constructing r is used by importing a known private
   key and verifying that the expected values of R are produced when a
   set of documents is signed.

   The threshold schemes described in this document have been designed
   to preserve the ability to audit the means of constructing the values
   of r for each individual key share even though the sum of these
   values and hence the value R will vary according to the number of
   signature shares used.

3.1.  Threshold signature

   A threshold signature R, S is constructed by summing a set of
   signature contributions from two or more signers.  Each signer _i_
   provides a contribution as follows:

   A_(i) = s_(i).B

   R_(i) = r_(i).B

   S_(i) = r_(i) + k.s_(i) mod L

   Where s_(i) and r_(i) are the secret scalar and unguessable value for
   the individual signer.

   The contributions of signers {1, 2, ... n} are then combined as
   follows:

   R = R_(1) + R_(2) + ... + R_(n)

   S = S_(1) + S_(2) + ... + S_(n)

   A = s.B

   Where s = (s_(1) + s_(2) + ... + s_(n)) mod L




Hallam-Baker               Expires 8 July 2020                  [Page 6]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   The threshold signature is verified in the same manner as before:

   S.B = R + k.A

   Substituting for S.B we get:

   = (S_(1) + S_(2) + ... + S_(n)).B

   = S_(1).B + S_(2).B + ... + S_(n).B

   = (r_(1) + k.s_(1)).B + (r_(2) + k.s_(2)).B + ... + (r_(n) +
   k.s_(n)).B

   = (r_(1).B + k.s_(1).B) + (r_(2).B + k.s_(2).B) + ... + (r_(n).B +
   k.s_(n).B)

   = (R1 + k.A1) + (R1 + k.A1) + ... + (Rn + k.An)

   Substituting for R + k.A we get:

   = R_(1) + R_(2) + ... + R_(n) + k.(A_(1) + A_(2) + ... + A_(n))

   = R_(1) + R_(2) + ... + R_(n) + k.A_(1) + k.A_(2) + ... + k.A_(n)

   = (R_(1) + k.A_(1)) + (R_(1) + k.A_(1)) + ... + (R_(n) + k.A_(n))

   As expected, the operation of threshold signature makes use of the
   same approach as threshold key generation and threshold decryption as
   described in [draft-hallambaker-threshold].  As with threshold
   decryption it is not necessary for each key share holder to have a
   public key corresponding to their key share.  All that is required is
   that the sum of the secret scalar values used in calculation of the
   signature modulo the group order be the value of the aggregate secret
   scalar corresponding to the aggregate secret key.

   While verification of [RFC8032] signatures is unchanged, the use of
   threshold signatures requires a different approach to signing.  In
   particular, the fact that the value k is bound to the value R means
   that the participants in the threshold signature scheme must agree on
   the value R before the value k can be calculated.  Since k is
   required to calculate the signature contributions S_(i) can be
   calculated, it is thus necessary to calculate the values R_(i) and
   S_(i) in separate phases.  The process of using a threshold signature
   to sign a document thus has the following stages orchestrated by a
   coordinator as follows:

   0.  The coordinator determines the values F, C and PH(M) as specified
       in [RFC8032] and transmits them to the signers {1, 2, ... n}.



Hallam-Baker               Expires 8 July 2020                  [Page 7]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   1.  Each signer generates a random value r_(i) such that 1 r_(i) L,
       calculates the value R_(i) = r_(i).B and returns R to the
       coordinator.

   2.  The coordinator calculates the value R = R_(1) + R_(2) + ... +
       R_(n) and transmits R and A to the signers {1, 2, ... n}.

   3.  Each signer uses the suppled data to determine the value k and
       hence S_(i) = r_(i) + k.s_(i) mod L and transmits it to the
       coordinator.

   4.  The coordinator calculates the value S = S_(1) + S_(2) + ... +
       S_(n) and verifies that the resulting signature R, S verifies
       according to the mechanism specified in [RFC8032].  If the
       signature is correct, the coordinator publishes it.  Otherwise,
       the coordinator MAY identify the signer(s) that provided
       incorrect contributions by verifying the values R_(i) and S_(i)
       for each.

   For clarity, the coordinator role is presented here as being
   implemented by a single party.

3.2.  Ed2519 Signature

   The process for creating an Ed25519 signature contribution is as
   follows

   0.   Determine the value of the secret scalar value s_(i) according
        to the means used to construct the secret shares.

   1.   Generate a random integer r_(i) such that 1 r_(i) L

   2.   Compute the point R_(i) = r_(i)B.  For efficiency, do this by
        first reducing r_(i) modulo L, the group order of B.  Let the
        string R_(i) be the encoding of this point.

   3.   Transmit the value R_(i) to the coordinator

   4.   Note that the construction of prefix is chosen so as to
        guarantee that the use of a different message value M or secret
        scalar value s_(i) will result in a different value of prefix
        and thus ensure a different choice of the value r_(i).

   5.   At some later point, the coordinator MAY complete the signature
        by returning the values F, C, A and R as specified in [RFC8032].
        The signer MAY then complete the signature contribution as
        follows:




Hallam-Baker               Expires 8 July 2020                  [Page 8]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   6.   Compute SHA512(dom2(F, C) || R || A || PH(M)), and interpret the
        64-octet digest as a little-endian integer k.

   7.   Compute S_(i) = (r_(i) + k * s_(i)) mod L.  For efficiency,
        again reduce k modulo L first.

   8.   Return the values R_(i), S_(i) to the coordinator.

   9.   The coordinator assembles the signature values R = S = S_(1) +
        S_(2) + ... + S_(n)

   10.  The coordinator verifies that the signature R, S is valid.

3.3.  Ed448 Signature

   The process for creating an Ed448 signature contribution is as
   follows

   0.  Determine the value of the secret scalar value s_(i) according to
       the means used to construct the secret shares.

   1.  Generate a random integer r_(i) such that 1 r_(i) L

   2.  Compute the point R_(i) = r_(i)B.  For efficiency, do this by
       first reducing r_(i) modulo L, the group order of B.  Let the
       string R_(i) be the encoding of this point.

   Transmit the value R_(i) to the coordinator

   At some later point, the coordinator MAY complete the signature by
   returning the values F, C, A and R as specified in [RFC8032].  The
   signer MAY then complete the signature contribution as follows:

   0.  Compute SHAKE256(dom4(F, C) || R || A || PH(M), 114), and
       interpret the 114-octet digest as a little-endian integer k.

   1.  Compute S_(i) = (r_(i) + k * s_(i)) mod L.  For efficiency, again
       reduce k modulo L first.

   2.  Return the values R_(i), S_(i) to the coordinator.

   3.  The coordinator assembles the signature values R = S = S_(1) +
       S_(2) + ... + S_(n)

   4.  The coordinator verifies that the signature R, S is valid.

   Note that the process of generating the signature contribution is
   deterministic for a given secret scalar value but the signature



Hallam-Baker               Expires 8 July 2020                  [Page 9]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   computed MAY be deterministic or non-deterministic according to the
   desired signature properties.

3.4.  Security Analysis

   We consider a successful breach of the threshold signature scheme to
   be any attack that allows the attacker to create a valid signature
   for any message without the participation of the required threshold
   of signers.

   Potential breaches include:

   *  Disclosure of the signature key or signature key share.

   *  Modification of signature data relating to message M to allow
      creation of a signature for message M'.

   *  Ability of one of the signers to choose the value of the aggregate
      public key.

   *  Access control attacks inducing a signer to create a signature
      contribution that was not properly authenticated or authorized.

   We regard attacks on the access control channel to be out of scope
   for the threshold signature algorithm, though they are certainly a
   concern for any system in which a threshold signature algorithm is
   employed.

   We do not consider the ability of a signer to cause creation of an
   invalid signature to represent a breach.

3.4.1.  Replay Attack

   The most serious concern in the implementation of any Schnorr type
   signature scheme is the need to ensure that the value r_(i) is never
   revealed to any other party and is never used to create signatures
   for two different values of k.s_(i).

   Ensuring this does not occur imposes significant design constraints
   as creating a correct signature contribution requires that the signer
   use the same value of r_(i) to construct its value or R_(i) and
   S_(i).

   For example, a HSM device may be required to perform multiple
   signature operations simultaneously.  Since the storage capabilities
   of an HSM device are typically constrained, it is tempting to attempt
   to avoid the need to track the value of r_(i) within the device
   itself using an appropriately authenticated and encrypted opaque



Hallam-Baker               Expires 8 July 2020                 [Page 10]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   state token.  Such mechanisms provide the HSM with the value of r_(i)
   but do not and cannot provide protection against a replay attack in
   which the same state token is presented with a request to sign
   different values of k.

3.4.2.  Malicious Contribution Attack

   In a malicious contribution attack, one or more parties present a
   signature contribution that does not meet the criteria R_(i) =
   r_(i).B and S_(i) = r_(i) + ks_(i).

   Such an attack is not considered to be a breach as it merely causes
   the signature process to fail.

3.4.3.  Rogue Key Attack

   A threshold signature scheme that allows the participants to 'bring
   their own key' may be vulnerable to a rogue key attack in which a
   signer is able to select the value of the aggregate public signature
   key by selecting a malicious public signature key value.

   The scheme described in this document is a threshold signature scheme
   and does not support this feature.  Consequently, this attack is not
   relevant.  It is described here for illustrative purposes only.

   This particular attack only applies when the individual signers
   create their own signature shares.  It is not a concern when the
   signature shares are created by splitting a master signature private
   key.

   Consider the case where the aggregate public key signature is
   calculated from the sum of public signature key share values
   presented by the signers:

   A = A_(1) + A_(2) + ... + A_(n)

   If the public key values are presented in turn, the last signer
   presenting their key share can force the selection of any value of A
   that they choose by selecting A_(n) = A_(m) - (A_(1) + A_(2) + ... +
   A_(n-1))

   The attacker can thus gain control of the aggregate signature key by
   choosing A_(m) = s_(m).B where s_(m) is a secret scalar known only to
   the attacker.  But does so at the cost of not knowing the value s_(n)
   and so the signer cannot participate in the signature protocol.

   This attack allows the attacker and the attacker alone to create
   signatures which are validated under the aggregate signature key.



Hallam-Baker               Expires 8 July 2020                 [Page 11]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   The attack is a consequence of the mistaken assumption that a
   signature created under the signature key A_(1) + A_(2) + ... + A_(n)
   provides evidence of the individual participation of the
   corresponding key holders without separate validation of the
   aggregate key.

   Enabling the use of threshold signature techniques by ad-hoc groups
   of signers using their existing signature keys as signature key
   shares presents serious technical challenges that are outside the
   scope of this specification.

4.  Unanimous Signature

   A unanimous threshold signature is a signature created by a set of
   two or more signers that requires the participation of every member
   of the set.  The key shares used by the signers MAY be generated by
   either:

   *  Each key share holder generating their own unique key share and
      combining them.

   *  Generating a master signature key and dividing it.

   Both approaches are described in [draft-hallambaker-threshold].

4.1.  Using threshold key generation

   To create a threshold signature key share using threshold key
   generation, each signer generates a pair {A_(i), s_(i)} and transmits
   the public component to the coordinator.

   The coordinator calculates the aggregate public key A = A_(1) + A_(2)
   + ... + A_(n)

   = s_(1).B + s_(2).B + ... + s_(n).B

   = ((s_(1) + s_(2) + ... + s_(n)) mod L).B

   = s.B

   Where s = s_(1) + s_(2) + ... + s_(n)) mod L

   The coordinator MUST require and verify proof of possession of the
   private key component s_(i) to defeat rogue key attacks of the type
   described in Section 3.4.3.

   For example, the coordinator MAY require each signer to create a test
   signature for their individual signature key share or to participate



Hallam-Baker               Expires 8 July 2020                 [Page 12]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   in creating a test signature under the aggregate signature key.  Such
   a test signature MAY be a Certificate Signing Request as specified in
   [RFC2314].

   Relying parties MUST NOT accept signatures purporting to be aggregate
   signatures under ad-hoc collections of public keys as proof of the
   involvement of the signers.

4.2.  Using key splitting

   To divide a keypair {A, p} into n parts, we begin by generating n-1
   key pairs according to the method described in [RFC8032].

   To calculate the final secret scalar share s_(n) we begin by
   calculating the secret scalar value s corresponding to the master
   private key p and the key shares s_(1), s_(2), ..., s_(n-1).  The
   final secret scalar is given by:

   s_(n) = s - s_(1), s_(2), ..., s_(n-1)

   Since the final secret scalar is not derived from a private key by
   means of a digest, it is not possible to use [RFC8032] format to
   store keys.  The format described in [draft-hallambaker-threshold] is
   used instead.

5.  Quorate Signature

   Constructing the set of secret scalar key shares using the Shamir
   secret sharing scheme allows a signature scheme in which the
   threshold of signers t required to create a signature is smaller than
   the number of key shares n.

5.1.  Key Generation

   The key generation process begins with the generation of a master
   signature key {A, p}. The private key p is used to calculate the
   secret scalar value s according to the procedure specified in
   Section 4.1 above.

   The secret scalar is then divided as follows.

   First, we construct a polynomial of degree t in the modular field L,
   where L is the order of the curve sub-group:

   f(x) = a_(0) + a_(1).x + a_(2).x^(2) + ... a_(t).x^(t) mod L

   where  a_(0) = s




Hallam-Baker               Expires 8 July 2020                 [Page 13]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


      a_(1) ... a_(t) are randomly chosen integers in the range 1 a_(i)
      L

   The values of the key shares are the values _f_(x_(1)), _f_(x_(2)),
   ... ,_f_(x_(n)).  That is

   p_(i) = _f_(x_(i))

   where  p_(1) ... p_(n) are the private key shares

      x_(1) ... x_(n) are distinct integers in the range 1 x_(i) L

   The means of constructing distinct values x_(1) ... x_(n) is left to
   the implementation.  It is not necessary for these values to be
   secret.

   As with the final secret scalar value above, it is not possible to
   use [RFC8032] format to store keys.  The format described in
   [draft-hallambaker-threshold] is used instead.

5.2.  Calculating the secret scalar value

   The value of the secret scalar value used to create a signature
   depends on the specific choice of signature shares used to construct
   it.  Since the numbering of the key shares is arbitrary, we choose
   the set of signers {1, 2, ... , t}.

   Lagrange polynomials are used to compute a set of coeficients l_(1),
   l_(2), ... l_(t) such that

   s = a_(0) = l_(1)p_(1) + l_(2)p_(2) + ... + l_(t)p_(t)

   The value of the secret scalars s_(1) + s_(2) + ... + s_(n) are thus
   given by

   s_(i) = l_(i)p_(i)

   The coordinator identifies the signers to participate in the
   signature event and uses the set of x coordinates corresponding to
   their key shares to calculate the corresponding Lagrange coefficient
   li for each as described in [draft-hallambaker-mesh-udf].

   [Note: The discussion of Shamir Secret Sharing should probably be
   moved from its current location in [draft-hallambaker-mesh-udf] to
   either this document or the base document
   [draft-hallambaker-threshold].  Which document is better suited will
   depend on whether it is decided to implement (n,k) threshold
   signatures and/or key escrow of elliptic curve scalar secrets.]



Hallam-Baker               Expires 8 July 2020                 [Page 14]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


6.  Test Vectors

6.1.  Unanimous Threshold Signature Ed25519

   The signers are Alice and Bob. Each creates a key pair:

   ED25519Alice's Key (ED25519)
       UDF:        ZAAA-GTSI-GXED-255X-XALI-CEXS-XKEY
       Scalar:     56271244081186130980636545017945156580516101894352492
           459594967614223399428880
       Encoded Private
     33 40 0E 22  D8 67 17 F4  8A 9F 6A 46  61 B4 0E AD
     8C D0 DD C3  79 CD 85 BD  95 5C 90 B9  6C CB 8C 23
       X: 11116793672970427161790264469280294507189044728140547954071022
           7976454124042406369344932655633664630560242213431409139866940
           284702002648469365756492647970
       Y: 61655404171611396573021808119108664749574235125343680206454285
           6299141386615046548323087409388548650272224487089895079970526
           0143544115364878870129761259200
       Encoded Public
     E2 AB 8F 37  62 C8 7B F9  E9 BC 59 0C  2E 99 A5 58
     0C C3 19 D5  CD DA 53 DF  3E C1 F0 C0  FE D3 55 5E
   ED25519Bob's Key (ED25519)
       UDF:        ZAAA-GTSI-G2ED-255X-XBOB-XSXK-EY
       Scalar:     54940772670153459146152925564198105262971485730889818
           986727608573229799020168
       Encoded Private
     68 9A 68 92  8A 06 17 84  35 3C B7 08  F8 56 00 3F
     BA 31 8C 42  B0 42 FE 2D  18 F2 7F AB  CD 10 49 F1
       X: 14271495069349838216379540196263140964032393512903842206168182
           5518850827098876289800868735522232908519794251130907125878675
           6343411484065706313568410880015
       Y: 28094328948004112428189466223757440886388684291254605355859923
           6240968229706795825282419594219442074647093851302547452470435
           9438513477629978601366725015573
       Encoded Public
     32 E5 8D 5E  66 B2 F9 E9  14 79 08 71  96 3B 9A 75
     A2 31 59 4B  8E ED 18 EF  BD FF 11 D4  47 2A 8C F4

   The Aggregate Signature Key A = A_(a) + A_(b)











Hallam-Baker               Expires 8 July 2020                 [Page 15]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   Aggregate Key = Alice + Bob ()
       UDF:        TBS
       Scalar:     26569330913556569171916721364983482306308422345436973
           56293312113171384684213
       Encoded Private
     B5 CE 0E B3  9C CF 18 99  CF 8D 4C BB  AE 81 79 1F
     CE 13 AA 3E  63 59 5B AC  8D 2C EB A4  55 C5 DF 05
       X: 67872685043898469012456949773240814121645904736114813455820339
           8688906486811443744733724675994181258029547346985079901494367
           752381127781166234556148580090
       Y: 36481740058369645484420180976004932062085375941522344052907594
           0118552792158551197107484892204562290802810655253510302448455
           4128548992118101415797909250954
       Encoded Public
     29 65 63 86  4F FB 10 8D  BA 7A 0A 68  04 6D 00 DA
     9B 1D C3 A4  AF BA 95 B4  5D 27 B4 35  00 2F DF 32

   To sign the text "This is a test", Alice and Bob first generate their
   values r which they multiply by the base point to obtain the value
   R_(i):

   Alice:
   r_a =  63604859197442869293148706887422539627692219221403898700132668
       2121229168067
   R_a =  System.Byte[]

   Bob:
   r_a =  90588289213224300609691011367428583037027596393781713986313426
       4309321564224
   R_a =  System.Byte[]

   The aggregate value R = R_(a) + R_(b)

   R =
     FB 4A B1 B4  53 C4 90 54  C4 F3 FD 00  87 AE EF 3D
     33 CE 2B 5B  F2 88 DB 13  FD F7 28 67  26 EE 07 1F

   The value k is calculated

   k =  4033579620745134235581641900982768938545463892767267607223155591
       591374371726

   Alice and Bob both calculate their signature scalar contribution:








Hallam-Baker               Expires 8 July 2020                 [Page 16]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   Alice:
   S_a =  66555407144639732988508254705363964829787697756754631094914457
       8662199168944

   Bob:
   S_b =  14755481297036888929325321941188765612781723011853930571004511
       25046339648114

   The coordinator calculates the aggregate value S = S_(a) + S_(b)

   S =  2141102201150086222817614741172516209576049278752939368049595703
       708538817058

   The coordinator checks to see that the signature verifies:

   S.B = R + kA =
       X: 20168784599297644264752251999842912626695351875278949808545814
           238064903547119
       Y: 17798208503807446200181400098695224792791795831502230059016274
           558554804974562

6.2.  Unanimous Threshold Signature Ed448

   The signers are Alice and Bob. Each creates a key pair:



























Hallam-Baker               Expires 8 July 2020                 [Page 17]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   ED448Alice's Key (ED448)
       UDF:        ZAAA-ITSI-GXED-44XA-LICE-XSXK-EY
       Scalar:     63495803583658817688110446314786076976347236361354035
           5597788771064742993095132758589292255654895141583596922516472
           738879360490167934280
       Encoded Private
     A0 53 4C 93  3C 34 00 76  AE 5D B5 4A  C2 71 5F 43
     E1 D6 63 2C  5C 56 53 C8  98 A0 8F 03  FF F5 22 96
     91 45 8C 2B  CF E3 FD 7E  2A 9E 0B D6  F4 CC 66 61
     43 62 72 7B  34 B4 79 92
       X: 24743197509267833262111449556527285120868167712209919570838426
           3466168536901525943558973091346360088759980994772668117646359
           614426660579
       Y: 21342899120576770537664462049685258390853729788303428349051130
           8752175233505795318243164692156369495328007220135137156078814
           081547431302
       Encoded Public
     0A 3B F3 27  E7 E1 67 63  2C 59 E2 1C  D1 84 C7 83
     E8 1E D1 68  9F 32 A1 16  99 00 5C DA  29 B9 6C 08
     E4 15 57 7E  E5 63 C2 32  08 23 41 68  5F 49 1F FF
     BC 4D CD 3A  4E A6 85 49  00
   ED448Bob's Key (ED448)
       UDF:        ZAAA-ITSI-G2ED-44XB-OBXS-XKEY
       Scalar:     72649803773199751564998543891898904839718409312910780
           0262041941160989643727331987658132182181970054245587322070535
           846720571414845714224
       Encoded Private
     BC 53 B4 74  3E A7 A7 FA  9F 05 9A BC  8C 22 26 15
     A1 4E BB 10  0E B5 59 6B  DE 9C 1B E9  F2 3C 65 42
     E7 B4 47 18  60 AC 18 A6  D2 78 B8 BC  CE F5 F4 28
     B2 3A FF 08  61 EF 6B 7C
       X: 58235851934808640621920816872959059172692411187640950432203039
           8116748997750134460231406698091317008063030408798536634284207
           667468558264
       Y: 34390767697909283892495761259186538632120422458392131201372282
           6056455656591826216381185634080685718154852726725624178995827
           091591132128
       Encoded Public
     93 63 5A 45  2D 4C 94 32  45 23 CD E2  A8 46 E4 78
     A0 80 59 DA  36 CB 6B 0C  06 64 6F BE  51 AB C0 BF
     1E DB A8 3F  2B 3B 80 0F  BF 00 E6 78  DD E0 83 E9
     AC 20 02 55  87 07 39 38  00

   The Aggregate Signature Key A = A_(a) + A_(b)







Hallam-Baker               Expires 8 July 2020                 [Page 18]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   Aggregate Key = Alice + Bob ()
       UDF:        TBS
       Scalar:     89488306051273634069773238262841883041784075539841550
           3672228636597106090916876462340541507950185640860121886233669
           49466515613996100051
       Encoded Private
     D3 29 DD AB  F6 0D 99 8B  75 65 B8 06  36 C9 3A 2C
     D4 08 C3 9B  7C F9 77 8C  68 29 0E 3D  5D C7 3E 00
     92 8B DC AE  26 FB 16 39  CD 25 1B 23  4A 5A 05 61
     1D 5C C4 70  0A C9 84 1F
       X: 17985659098670117617173315763082238685735647626871251468000984
           2080317111091696183607307614171726960576308774975742249260532
           199160570999
       Y: 31506323224859159594386181995639405170623657273945727288760063
           1624406694682617334725040181287905351066763414658543828623841
           509161975864
       Encoded Public
     9B 3E DF 49  55 40 9F 7B  EA 0B AA 40  B7 3D 15 82
     60 9F 7C 40  CF 67 DE 56  56 0D 03 87  63 3B 15 F2
     45 33 FE 48  BD 2D A0 A2  8B CC 74 DA  94 0F 39 00
     AC 39 CB 0A  9F A4 EB B0  00

   To sign the text "This is a test", Alice and Bob first generate their
   values r which they multiply by the base point to obtain the value
   R_(i):

   Alice:
   r_a =  73759418290054794861373572858566288781619358129342401750774507
       86228048858000588481919454774928817062768941685761418007593280530
       2999804
   R_a =  System.Byte[]

   Bob:
   r_a =  46237963278513215322396148050034865586946889704122042348536832
       25811783723521941968309643248450810747601167927994249458319388189
       6018677
   R_a =  System.Byte[]

   The aggregate value R = R_(a) + R_(b)

   R =
     A0 FF BC 4A  92 40 39 FE  A3 E2 98 19  8A CB 60 54
     65 E1 EF C5  3E E2 AA 54  8D 27 78 CB  F8 34 DC E2
     9C DF A0 D7  F1 D2 7F EA  33 A2 A7 07  76 29 A1 7C
     EB D4 97 F1  A3 CE 0B 61  80

   The value k is calculated




Hallam-Baker               Expires 8 July 2020                 [Page 19]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   k =  4253302316461679481082434282193340085469714728082631996749509171
       36528863341161130189337827407821840447093029569242109238035123293
       90659

   Alice and Bob both calculate their signature scalar contribution:

   Alice:
   S_a =  98531765382438321188310203252700171214078910507928709174117939
       03719918811956876581076180944672089155783210289818359855928311296
       3570131

   Bob:
   S_b =  10826185029558642533243398893637670455024435365016467182849367
       92853602994592020853268312315426021226313042112304897550405147626
       03231952

   The coordinator calculates the aggregate value S = S_(a) + S_(b)

   S =  2508393460412302388341324021707574217591292398626386593223906852
       74134836172312654213972856976306382258260204195816912950241197071
       52304

   The coordinator checks to see that the signature verifies:

   S.B = R + kA =
       X: 87229317542997013818252634997777965098763712747235444768375375
           25263195569863
       Y: 48426719549368988040047207185774675871089544448034802040243984
           177418779288237

6.3.  Quorate Threshold Signature Ed25519

   The administrator creates the aggregate key pair


















Hallam-Baker               Expires 8 July 2020                 [Page 20]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   ED25519Aggregate Key (ED25519)
       UDF:        ZAAA-GTSI-GQED-255X-XAGG-REGA-TEXK-EY
       Scalar:     39348647608109113656999806950437958090469802387424444
           589375066079861075223816
       Encoded Private
     37 39 5E 7A  8B A5 A0 19  46 4B 58 22  EA 24 A5 71
     45 2C 2A AC  7A 3E FB CA  CE 3F D4 12  9A BA EB 70
       X: 14198837758377867455716504277518729070915183249890461230792115
           9904969716778427995951234766002164511738587575257530388758374
           7824906047250057721855068523970
       Y: 20211025649802071998810413948266748565975140520947927724517956
           2067625505077751598018629551746824533726709810990193455662385
           6152736116303441031851305458040
       Encoded Public
     6E 13 79 B4  39 DA 97 9C  5A 34 CE 79  CD 1B 50 DF
     A0 76 AD 49  81 6D 52 59  A4 2C DB CE  44 FF 3E F5

   Three key shares are required for Alice, Bob and Carol with a
   threshold of two.  The parameters of the Shamir Secret Sharing
   polynomial are:

   a0 = 3934864760810911365699980695043795809046980238742444458937506607
       9861075223816
   a1 = 6478235074936669232922546709062853526800747723284435893560379998
       498854036401

   The key share values for the participants are

   xa = 1
   ya = 2404849219052209606083234281242846172127851954429434846923740448
       647203754283

   xb = 2
   yb = 1646078716656616625032594427262705458071483318333963134482169508
       860603539695

   xc = 3
   yc = 8873082142610236439819545732825647440151146822384914220405985690
       74003325107

   Alice and Carol are selected to sign the message "This is another
   test"

   The Lagrange coefficients are:







Hallam-Baker               Expires 8 July 2020                 [Page 21]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   la = 3618502788666131106986593281521497120428558179689953803000975469
       142727125496
   lc = 3618502788666131106986593281521497120428558179689953803000975469
       142727125494

   Alice and Carol select their values ra, rc

   ra = 5467990291185231529722642292282910677180928186673090898286725351
       703148584114
   Ra = System.Byte[]

   rc = 3842295179874978910349644562407562715869337917437976620141371939
       137906271828
   Rc = System.Byte[]

   The aggregate value R = R_(a) + R_(c)

   R =
     B1 23 76 E0  38 C5 15 2A  B4 0F AB E2  FA 0C AC 81
     D0 34 28 B7  13 14 75 A2  29 08 3C C0  62 3B 97 2D

   The value k is

   k = 24387631527158770388984723649123275410144206977564237560989138844
       76357243053

   The values R and k (or the document to be signed) and the Lagrange
   coefficients are passed to Alice and Carol who use them to calculate
   their secret scalar values:

   sa = 7225776617244445516111444703385766378620336111334106073386586142
       113532756919;
   sc = 3174848681535619284995615994880214748421000838570708091980676184
       605725462941

   The signature contributions can now be calulated:

   Sa = 5258509372798138258048339062398668871787395474915394506826958407
       016143211994
   Sc = 2369087102951219635858054121785113036716245524183189984191118268
       317926650670

   The coordinator calculates the aggregate value S = S_(a) + S_(b)

   S =  3905908984170956799332066211407876676465246397186768850161257370
       48615611675

   The coordinator checks to see that the signature verifies:



Hallam-Baker               Expires 8 July 2020                 [Page 22]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   S.B = R + kA =
       X: 44137199296357774791154193859950611817340233105447413062332736
           902705770844448
       Y: 29688538012678578878269116100526571773188243259702429043049505
           096610475369173

6.4.  Quorate Threshold Signature Ed448

   The administrator creates the aggregate key pair

   ED448Aggregate Key (ED448)
       UDF:        ZAAA-ITSI-GQED-44XA-GGRE-GATE-XKEY
       Scalar:     50890460656419721531273587958284096015810982760541575
           4207268050539683337837216003977228732536078674802149039736292
           653681850024283019712
       Encoded Private
     78 22 7E 3B  89 95 80 5D  04 19 DC 27  F1 7F 9B E4
     86 2B 0B DD  55 64 EE 04  19 49 4D DE  B9 04 3B 9E
     8B 7D DC EC  EC 8F DD 1D  E7 88 86 FD  11 FD 78 EF
     1A 8B 84 8F  77 00 73 65
       X: 44109173355278142669484438370724914685176368933547176239809629
           7503768465595321590690311221269514682222687386378631457535068
           446135118173
       Y: 53219402718535721212460981200104434180077825188675868294070079
           5084662920552823356888138706016038637934794839496624474125511
           419755284720
       Encoded Public
     43 61 20 A0  B1 DF AA BD  6B 55 00 97  A3 BE CB B8
     09 57 20 88  16 69 E4 B9  E1 7E 9C 13  C0 41 5B CB
     4D 3E E4 99  2E 2D 48 89  1C C0 FB 26  58 C2 DD 5C
     C1 DC 17 82  D7 A0 43 EE  80

   Three key shares are required for Alice, Bob and Carol with a
   threshold of two.  The parameters of the Shamir Secret Sharing
   polynomial are:

   a0 = 0
   a1 = 3230310441090132544881502506497842088200690521964525360879407271
       94765745753141655224661941966620396823169163035586912417623145586
       91569

   The key share values for the participants are









Hallam-Baker               Expires 8 July 2020                 [Page 23]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   xa = 1
   ya = 3230310441090132544881502506497842088200690521964525360879407271
       94765745753141655224661941966620396823169163035586912417623145586
       91569

   xb = 2
   yb = 6460620882180265089763005012995684176401381043929050721758814543
       89531491506283310449323883933240793646338326071173824835246291173
       83138

   xc = 3
   yc = 9690931323270397634644507519493526264602071565893576082638221815
       84297237259424965673985825899861190469507489106760737252869436760
       74707

   Alice and Carol are selected to sign the message "This is another
   test"

   The Lagrange coefficients are:

   la = 9085484053695086131866547598600056679420517008591475753518627489
       75730019807697928580978776458461879816551468545458311523868779298
       24891
   lc = 9085484053695086131866547598600056679420517008591475753518627489
       75730019807697928580978776458461879816551468545458311523868779298
       24889

   Alice and Carol select their values ra, rc

   ra = 9916409373832855445680225409665819204694890272466243758088723611
       70412660541692764122871086733859409013013307204388508168153245726
       71888
   Ra = System.Byte[]

   rc = 1073609511703983208477950323599584281909008734279687416788909134
       22950735978683478421395579947183492087041733558644230420650276766
       461770
   Rc = System.Byte[]

   The aggregate value R = R_(a) + R_(c)

   R =
     30 A1 B3 17  69 AB 99 0E  57 5E 0B A5  2E 51 72 C0
     BA 31 35 39  51 7C 83 B8  22 01 9F 85  45 93 9B 54
     19 A2 FA FD  34 7A CA 88  7D 05 52 A6  21 5C E0 B7
     69 62 F4 94  6C 15 C3 11  80

   The value k is



Hallam-Baker               Expires 8 July 2020                 [Page 24]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


   k = 10235373755332719753132453070965244233375545860969817073088585850
       34984308611997081872546544930901042673608404328479261067005777756
       07973

   The values R and k (or the document to be signed) and the Lagrange
   coefficients are passed to Alice and Carol who use them to calculate
   their secret scalar values:

   sa = 1393094971533028494918880135834681981172155279153826379483773839
       76787863843741041141797168940839247505130521309883868015030349767
       862243;
   sc = 4240018392059887314544293838853293547119481225644687712199516581
       83581401177985445743985863508531284581797723992077942897434060917
       87536

   The signature contributions can now be calulated:

   Sa = 1176422144911387757819650694682546452875900733977789124175969611
       96064995455877990887534924392638074098909532952322658866770310075
       667839
   Sc = 1261695317878032144403764439936251221873899581791569343175257655
       85463382113907822175563223482227224266776195506309879565242141085
       378620

   The coordinator calculates the aggregate value S = S_(a) + S_(b)

   S =  6210206520504026758501056148987863388656969140510633166475017698
       63823736082462273469023925831729224023754347495408761272386953013
       96680

   The coordinator checks to see that the signature verifies:

   S.B = R + kA =
       X: 41458922531347602467333936260245029252955857925674064823925020
           498684283758735
       Y: 46892836594134893138380416498249507660693894634845371281694628
           683354340901899

7.  Security Considerations

   TBS.

8.  IANA Considerations

   This document requires no IANA actions.

9.  Acknowledgements




Hallam-Baker               Expires 8 July 2020                 [Page 25]


Internet-Draft    Threshold Signatures Ed25519 & Ed448      January 2020


10.  Normative References

   [draft-hallambaker-mesh-udf]
              Hallam-Baker, P., "Mathematical Mesh 3.0 Part II: Uniform
              Data Fingerprint.", Work in Progress, Internet-Draft,
              draft-hallambaker-mesh-udf-07, 18 October 2019,
              <https://tools.ietf.org/html/draft-hallambaker-mesh-udf-
              07>.

   [draft-hallambaker-threshold]
              "[Reference Not Found!]".

   [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>.

   [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>.

11.  Informative References

   [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>.

   [RFC2314]  Kaliski, B., "PKCS #10: Certification Request Syntax
              Version 1.5", RFC 2314, DOI 10.17487/RFC2314, March 1998,
              <https://www.rfc-editor.org/rfc/rfc2314>.

















Hallam-Baker               Expires 8 July 2020                 [Page 26]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/