Network Working Group                                 P. M. Hallam-Baker
Internet-Draft                                      ThresholdSecrets.com
Intended status: Informational                           2 November 2020
Expires: 6 May 2021


                Threshold Signatures in Elliptic Curves
                  draft-hallambaker-threshold-sigs-05

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.

   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 6 May 2021.

Copyright Notice

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








Hallam-Baker               Expires 6 May 2021                   [Page 1]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   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.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  Applications  . . . . . . . . . . . . . . . . . . . . . .   4
       1.1.1.  HSM Binding . . . . . . . . . . . . . . . . . . . . .   4
       1.1.2.  Code Signing  . . . . . . . . . . . . . . . . . . . .   4
       1.1.3.  Signing by Redundant Services . . . . . . . . . . . .   5
   2.  Definitions . . . . . . . . . . . . . . . . . . . . . . . . .   5
     2.1.  Requirements Language . . . . . . . . . . . . . . . . . .   5
     2.2.  Defined Terms . . . . . . . . . . . . . . . . . . . . . .   5
     2.3.  Related Specifications  . . . . . . . . . . . . . . . . .   5
     2.4.  Implementation Status . . . . . . . . . . . . . . . . . .   6
   3.  Principles  . . . . . . . . . . . . . . . . . . . . . . . . .   6
     3.1.  Direct shared threshold signature . . . . . . . . . . . .   7
     3.2.  Shamir shared threshold signature . . . . . . . . . . . .   9
     3.3.  Stateless computation of final share  . . . . . . . . . .  10
       3.3.1.  Side channel resistance . . . . . . . . . . . . . . .  11
     3.4.  Security Analysis . . . . . . . . . . . . . . . . . . . .  12
       3.4.1.  Calculation of r values . . . . . . . . . . . . . . .  12
       3.4.2.  Replay Attack . . . . . . . . . . . . . . . . . . . .  13
       3.4.3.  Malicious Contribution Attack . . . . . . . . . . . .  13
       3.4.4.  Rogue Key Attack  . . . . . . . . . . . . . . . . . .  13
   4.  Ed2519 Signature  . . . . . . . . . . . . . . . . . . . . . .  14
   5.  Ed448 Signature . . . . . . . . . . . . . . . . . . . . . . .  15
   6.  Test Vectors  . . . . . . . . . . . . . . . . . . . . . . . .  16
     6.1.  Direct Threshold Signature Ed25519  . . . . . . . . . . .  16
     6.2.  Direct Threshold Signature Ed448  . . . . . . . . . . . .  19
     6.3.  Shamir Threshold Signature Ed25519  . . . . . . . . . . .  22
     6.4.  Shamir Threshold Signature Ed448  . . . . . . . . . . . .  25
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  28
     7.1.  Rogue Key attack  . . . . . . . . . . . . . . . . . . . .  28
     7.2.  Disclosure or reuse of the value r  . . . . . . . . . . .  28
     7.3.  Resource exhaustion attack  . . . . . . . . . . . . . . .  28
     7.4.  Signature Uniqueness  . . . . . . . . . . . . . . . . . .  28
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  29
   9.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  29
   10. Normative References  . . . . . . . . . . . . . . . . . . . .  29
   11. Informative References  . . . . . . . . . . . . . . . . . . .  29







Hallam-Baker               Expires 6 May 2021                   [Page 2]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


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.

   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 builds on the approach described in
   [draft-hallambaker-threshold] to define 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.






Hallam-Baker               Expires 6 May 2021                   [Page 3]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   The approach used is based on that developed in FROST [Komlo].  This
   document describes the signature scheme itself.  The techniques used
   to generate keys are described separately in
   [draft-hallambaker-threshold].

   As in the base document, we first describe signature generation for
   the case that _n_ = _t_ using 'direct' coefficients, that is the
   secret scalar is the sum of the secret shares.  We then show how the
   scheme is modified using Shamir secret sharing [Shamir79] and
   Lagrange coefficients for the case that _n_ > _t_.

1.1.  Applications

   Threshold signatures have application in any situation where it is
   desired to have finer grain control of signing operations without
   this control structure being visible to external applications.  It is
   of particular interest in situations where legacy applications do not
   support multi-signatures.

1.1.1.  HSM Binding

   Hardware Security Modules (HSMs) prevent accidental disclosures of
   signature keys by binding private keys to a hardware device from
   which it cannot be extracted without substantial effort.  This
   provides effective mitigation of the chief causes of key disclosure
   but requires the signer to rely on the trustworthiness of a device
   that represents a black box they have no means of auditing.

   Threshold signatures allow the signer to take advantage of the key
   binding control provided by an HSM without trusting it.  The HSM only
   contributes one of the key shares used to create the signature.  The
   other is provided by the application code (or possibly an additional
   HSM).

1.1.2.  Code Signing

   Code signing is an important security control used to enable rapid
   detection of malware by demonstrating the source of authorized code
   distributions but places a critical reliance on the security of the
   signer's private key.  Inadvertent disclosure of code signing keys is
   commonplace as they are typically stored in a form that allows them
   to be used in automatic build processes.  Popular source code
   repositories are regularly scanned by attackers seeking to discover
   private signature keys and passwords embedded in scripts.

   Threshold signatures allow the code signing operation to be divided
   between a developer key and an HSM held locally or by a signature
   service.  The threshold shares required to create the signature can



Hallam-Baker               Expires 6 May 2021                   [Page 4]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   be mapped onto the process roles and personnel responsible for
   authorizing code release.  This last concern might be of particular
   advantage in open source projects where the concentration of control
   embodied in a single code signing key has proved to be difficult to
   reconcile with community principles.

1.1.3.  Signing by Redundant Services

   Redundancy is as desirable for trusted services as for any other
   service.  But in the case that multiple hosts are tasked with
   compiling a data set and signing the result, there is a risk of
   different hosts obtaining a different view of the data set due to
   timing or other concerns.  This presents the risk of the hosts
   signing inconsistent views of the data set.

   Use of threshold signatures allows the criteria for agreeing on the
   data set to be signed to be mapped directly onto the requirement for
   creating a signature.  So if there are three hosts and two must agree
   to create a signature, three signature shares are created and with a
   threshold of two.

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
   deterministic mechanism described in specification
   [draft-hallambaker-mesh-udf] is used to generate the private keys
   used in the test vectors.







Hallam-Baker               Expires 6 May 2021                   [Page 5]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


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

   *  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



Hallam-Baker               Expires 6 May 2021                   [Page 6]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


      _L_ is the order of the elliptic curve group.

   To verify the signature, the verifier checks that:

   _S.B_ = _R_ + _k.A_

   This equality must hold for a valid signature since:

   _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

   _S_(1)_ = _r_ + _k_(1)_._s_ mod _L_

   S_(2) = _r_ + _k_(2).s mod L_

   s = (_S_(1)_ - _S_(2)_)(_k_(1)_ - _k_(2)_)^(-1) mod _L_

   The method of constructing _r_ MUST ensure that it is unique and
   unguessable.

3.1.  Direct shared threshold signature

   A threshold signature R, S is constructed by summing a set of
   signature contributions from two or more signers.  For the case that
   the composite private key is the sum of the key shares (_n_ = _t_),
   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.




Hallam-Baker               Expires 6 May 2021                   [Page 7]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   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

   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.






Hallam-Baker               Expires 6 May 2021                   [Page 8]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   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
   dealer as follows:

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

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

   2.  The dealer 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
       dealer .

   4.  The dealer 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 dealer publishes it.  Otherwise, the dealer MAY
       identify the signer(s) that provided incorrect contributions by
       verifying the values R_(i) and S_(i) for each.

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

3.2.  Shamir shared threshold signature

   To construct a threshold signature using shares created using Shamir
   Secret Sharing, each private key value _s_(i)_ is multiplied by the
   Lagrange coefficient _l_(i)_ corresponding to the set of shares used
   to construct the signature:

   A_(i) = s_(i)l_(i).B

   R_(i) = r_(i).B

   _S_(i) = ri + klisi mod L_




Hallam-Baker               Expires 6 May 2021                   [Page 9]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   It is convenient to combine the derivation of _S_(i)_ for the
   additive and Shamir shared threshold signatures by introducing a key
   multiplier coefficient _c_(i)_:

   _S_(i) = ri + kcisi mod L_

   Where  _c_(i)_ = 1 for the additive shared threshold signature

      _c_(i)_ = _l_(i)_ for the Shamir shared threshold signature

3.3.  Stateless computation of final share

   One of the chief drawbacks to the algorithm described above is that
   it requires signers to perform two steps with state carried over from
   the first to the second to avoid reuse of the value _r_(i)_. This
   raises particular concern for implementations such as signature
   services or HSMs where maintaining state imposes a significant cost.

   Fortunately, it is possible to modify the algorithm so that the final
   signer does not need to maintain state between steps:

   0.  All the signers except the final signer _F_ generate their value
       _r_(i)_ and submit the corresponding value _R_(i)_ to the dealer

   1.  Dealer calculates the value _R_ - _R_(F)_ and sends it to the
       final signer together with the all the other parameters required
       to calculate _k_ and the final signer's key multiplier
       coefficient _c_(F)_.

   2.  The final signer generates its value _r_(F)_

   3.  The final signer calculates the value _R_(F)_ from which the
       values _R_ and _k_ can now be determined.

   4.  The final signer calculates its key share contribution _S_(F) =
       rF + kcFsF mod L._

   5.  The final signer returns the values _S_(F)_ and _R_ to the
       dealer.

   6.  The dealer reports the value R to the other signers and continues
       the signature process as before.

   While this approach to stateless computation of the signature
   contributions is limited to the final share, this is sufficient to
   cover the overwhelming majority of real-world applications where _n_
   = _t_ = 2.




Hallam-Baker               Expires 6 May 2021                  [Page 10]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   Note that the final signer MAY calculate its value _r_(F)_
   deterministically provided that the parameters _R_ - _R_(F)_ and
   _c_(F)_ are used in its determination.  Other signers MUST NOT use a
   deterministic means of generating their value _r_(i)_ since the
   information known to them at the time this parameter is generated is
   not sufficient to fix the value of _R_.

3.3.1.  Side channel resistance

   The use of Kocher side channel resistance as described in
   [draft-hallambaker-threshold] entails randomly splitting the private
   key into two shares and performing the private key operation
   separately on each share to avoid repeated operations using the same
   private key value at the cost of performing each operation twice.

   This additional overhead MAY be eliminated when threshold approaches
   are used by applying blinding factors whose sum is zero to each of
   the threshold shares.

   For example, if generation of the threshold signature is divided
   between an application program A and an HSM B using the final share
   approach to avoid maintaining state in the HSM, we might generate a
   blinding factor thus:

   0.  A generates a random nonce _n_(A)_ and sends it to B with the
       other parameters required to generate the signature.

   1.  B generates a random nonce _n_(B)_

   2.  B calculates the blinding factor _x_ by calculating
       _H_(_n_(A,)nB) where H is a strong cryptographic digest function
       and converting the result to an integer in the range 1 x L._

   3.  B calculates the signature parameters as before except that the
       threshold signature contribution is now _S_(B) = rB + k(cBsB + x)
       mod L._

   4.  B returns the nonce _n_(B)_ to A with the other parameters.

   5.  A calculates the blinding factor _x_ using the same approach as B

   6.  A calculates the signature parameters as before except that the
       threshold signature contribution is now _S_(A) = rA + k(cAsA - x)
       mod L._

   This approach MAY be extended to the case that _t_ > 2 by
   substituting a Key Derivation Function (e.g.  [RFC5860]) for the
   digest function.



Hallam-Baker               Expires 6 May 2021                  [Page 11]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


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.  Calculation of r values

   The method of constructing the values _r_(i)_ MUST ensure that each
   is unique and unguessable both to external parties, the signers and
   the dealer.  The deterministic method specified in [RFC8032] cannot
   be applied to generation of the values r_(i) as it allows the dealer
   to cause signers to reveal their key shares by requesting multiple
   signature contributions for the same message but with different
   values of _k_. In particular, requesting signature contributions for
   the same message:

   With different Lagrange coefficients.

   With a false value of _R_

   To avoid these attacks, the value r_(i) is generated using a secure
   random number generator.  This approach requires the signer to ensure
   that values are never reused requiring that the signing API maintain
   state between the first and second rounds of the algorithm.




Hallam-Baker               Expires 6 May 2021                  [Page 12]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   While there are many approaches to deterministic generation of r_(i)
   that appear to be sound, closer inspection has demonstrated these to
   be vulnerable to rogue key and rogue contribution attacks.

3.4.2.  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
   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.3.  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.4.  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.






Hallam-Baker               Expires 6 May 2021                  [Page 13]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   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.

   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.  Ed2519 Signature

   The means by which threshold shares are created is described in
   [draft-hallambaker-threshold].

   The dealer selects the signers who are to construct the signature.
   Each signer then computes the value R_(i):

   0.  Randomly generate an integer r_(i) such that 1 r_(i) L.

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



Hallam-Baker               Expires 6 May 2021                  [Page 14]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   2.  Transmit the value R_(i) to the dealer

   3.  At some later point, the dealer MAY complete the signature by
       returning the values F, C, A and R as specified in [RFC8032]
       together with the key multiplier coefficient c_(i).  The signers
       MAY then complete their signature contributions:

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

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

   6.  Return the values R_(i), S_(i) to the dealer .

   The dealer then completes the signature by:

   0.  Computing the composite value S = S_(1) + S_(2) + ... + S_(n)

   1.  Verifying that the signature R, S is valid.

   2.  Publishing the signature.

5.  Ed448 Signature

   The means by which threshold shares are created is described in
   [draft-hallambaker-threshold].

   The dealer selects the signers who are to construct the signature.
   Each signer then computes the value R_(i):

   0.  Randomly generate an integer r_(i) such that 1 r_(i) L.

   1.  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 dealer

   0.  At some later point, the dealer MAY complete the signature by
       returning the values F, C, A and R as specified in [RFC8032]
       together with the key multiplier coefficient c_(i).  The signers
       MAY then complete the signature contributions:

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





Hallam-Baker               Expires 6 May 2021                  [Page 15]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


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

   3.  Return the values R_(i), S_(i) to the dealer.

   The dealer then completes the signature by:

   0.  Computing the composite value S = S_(1) + S_(2) + ... + S_(n)

   1.  Verifying that the signature R, S is valid.

   2.  Publishing the signature.

6.  Test Vectors

6.1.  Direct Threshold Signature Ed25519

   The signers are Alice and Bob's Threshold Signature Service 'Bob'.
   Each creates a key pair:
































Hallam-Baker               Expires 6 May 2021                  [Page 16]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   ED25519Alice's Key (ED25519)
       UDF:            ZAAA-GTSI-GXED-255X-XALI-CEXS-XKEY
       Scalar:         312191303806394376947696888962276115420485359001
           34467943432016761653342335248
       Encoded Private
     10 AE C0 C2  16 65 9B 4F  7C 9D DE 82  3E 49 7F D4
     9B 14 BB F8  2D 9F 0C 11  24 D7 15 E3  43 79 57 20
       X:              -13697699435406080999251131063344049965140553452
           752305353714819106646919347160064793506327635954342719144289
           2305566686088586980395284289746495530409889930
       Y:              278793875610616080844162800185864399625503938157
           569374174700414845758479331294424147393776831767266487579098
           7675375777043504113387553916769515911310193558
       Encoded Public
     45 16 53 7C  26 50 CF DA  F1 A4 DF 4C  45 DC 3D 95
     4E B6 8E EB  A6 5A 27 D6  CD 5B 43 C5  F4 06 53 ED
   ED25519Bob's Key (ED25519)
       UDF:            ZAAA-GTSI-G2ED-255X-XBOB-XSXK-EY
       Scalar:         567212843891509414800308620158891720685508995620
           72140666211075925337851277632
       Encoded Private
     E5 CD 34 01  FD 8C 0E 27  81 4B 11 DD  12 68 50 A1
     4B 5A D5 E1  E1 41 D7 68  5F 51 ED B4  3A 84 58 5C
       X:              -13809282472298084436735987888897423507149580966
           952791761446670884044433963975178482398144657564565223270588
           5322459642470946347570575475534141406285323257
       Y:              263684226342871984706317411760423095947068088366
           393546798602378437432707482089806653755881399592963068751759
           9645362525866308283171284327931970404321458677
       Encoded Public
     F1 5F C0 78  F8 32 49 2C  D9 64 CC 2B  CF 90 5C 4F
     23 EA BB F8  38 99 C5 FE  F3 AA 67 BE  AB EC D2 5E

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

















Hallam-Baker               Expires 6 May 2021                  [Page 17]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   Aggregate Key = Alice + Bob ()
       UDF:            TBS
       Scalar:         109634784180323260712231215560085272031403914964
           7717337619681427565742601012
       Encoded Private
     34 33 AB 10  9A 09 A9 61  65 8B 3A EC  58 21 FB 2D
     0D 45 74 49  45 BA E2 CF  A8 98 C2 94  C9 82 6C 02
       X:              -83837675294300852842901121613445594296352372347
           711317409367737761568353629718805151940195325485285476438422
           923698718220652243749390297055882388709313280
       Y:              160553422944358144751060009820735322036903773802
           361117046457476895165059738086663330972263850675453249990301
           0398473811263196653225446124160025082144761534
       Encoded Public
     48 1A 27 66  06 AF 4E 3C  20 A4 02 CD  8A 13 46 99
     02 B7 75 F8  AC D4 7E 89  68 FB 68 EB  D8 EF 4A C7

   To sign the text "This is a test", Alice first generates her value r
   and multiplies it by the base point to obtain the value R_(a):

   Alice:
       r_a:            304554767184319354570910632330847275245170925807
           471005852065308719163006873
   R_a =
     4D D3 35 87  4D D2 A9 35  79 CF 33 11  4E 3C 4C 86
     A3 46 83 F8  77 2B 69 B9  BE 8A D0 03  5B 07 1B 3D

   Alice passes her value R_(A) to Bob along with the other parameters
   required to calculate i.  Bob then calculates his value R_(A) and
   multiplies it by the base point to obtain the value R_(b):

   Bob:
       r_b:            211453017009495036941255861540216441186480571963
           4308458833747992420728606380
   R_b =
     9E 92 BB 50  CD DA 6A 97  70 83 54 82  4A C5 A2 5E
     CF 0C 53 65  19 55 74 E0  66 F7 49 0B  F1 9E 42 C1

   Bob can now calculate the composite value R = R_(a) + R_(b) and thus
   the value k.

   R =
     6D 04 0A 15  D3 26 95 7E  60 4B 31 B9  40 03 34 24
     C1 E2 94 CE  4C 2D 67 AC  23 F9 09 EB  01 35 27 BC
       k:              141815370378674010309754096097287620917810351837
           8705827473796209228380712742





Hallam-Baker               Expires 6 May 2021                  [Page 18]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   Bob calculates his signature scalar contribution and returns the
   value to Alice:

   Bob:
       S_b:            536363782415883723339410938370364298390876250983
           1717008575694722457748759583

   Alice can now calculate her signature scalar contribution and thus
   the signature scalar S.

   Alice:
       S_a:            268700124091647466934677864874812484315783329013
           4699034602004495702143596514
       S:              813633487743049688767701469408773586209479440586
           508437175748279874438105108

   Alice checks to see that the signature verifies:

   S.B = R + kA =
       X:              303888032885010422619559054491601097433934565460
           00461769461185182044799973523
       Y:              242312166466765598632540958273647355363821360549
           75658447998613064394185428840

6.2.  Direct Threshold Signature Ed448

   The signers are Alice and Bob's Threshold Signature Service 'Bob'.
   Each creates a key pair:























Hallam-Baker               Expires 6 May 2021                  [Page 19]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   ED448Alice's Key (ED448)
       UDF:            ZAAA-ITSI-GXED-44XA-LICE-XSXK-EY
       Scalar:         672286477331130983513039743350616227864346753924
           962787860729757222511999618443513569403793186398096717924945
           854846544396984088344823264
       Encoded Private
     6F 85 B1 91  9A 37 06 A6  B2 15 79 AD  5B 69 16 6A
     5A CD C8 17  D4 14 1F 68  DA 97 C5 B4  44 79 CE EA
     3C 17 7B E1  29 44 70 DF  41 C8 98 38  1E 7C 9B 3B
     03 63 6F 85  E8 39 31 91
       X:              526046019655043632868470952286947529492283092344
           122476077151423645243648974512182548405702873560533846673262
           767064019365470830861106049
       Y:              145374550785380850812934424757986866673485237047
           938554544492694946608060986459495807055455048208713991919477
           720250115717234689256856152
       Encoded Public
     59 55 F4 7A  66 08 91 35  F8 15 63 F4  90 91 7F 38
     12 E3 49 22  51 F8 BC 4A  41 C9 44 59  5A 64 9B 40
     0B C5 7E 53  48 0F 32 12  90 32 69 38  47 28 94 BB
     99 D1 16 6F  2D D5 3D 4F  80
   ED448Bob's Key (ED448)
       UDF:            ZAAA-ITSI-G2ED-44XB-OBXS-XKEY
       Scalar:         455052626698262385397736547727159423941520792904
           908612603542850909167215987713902322619933929404455741806848
           064294945283113799683261212
       Encoded Private
     CA 15 22 BD  F4 0F 9E 0A  EC A7 61 79  BE 9E E3 38
     BF 93 D3 5B  B3 E6 FC F0  A7 5B 7C F0  E7 B5 89 F6
     2E F6 D1 0E  72 49 4D DF  34 5E 2F 7C  9E 42 1D 85
     AB AB 30 BD  68 C6 3E 35
       X:              752024108200272710832187535557164455078689734595
           171189993383259892607253027500878543439908750525763880661232
           171322059854852522782265
       Y:              619329873102159676791326142073166790594683111409
           729383584199833441028484525583699421181422168190856074786324
           020492214873796495570056511
       Encoded Public
     76 2B FC F8  AC 96 79 DE  1C 72 07 65  DD 49 5B 28
     C7 04 CB A8  A5 96 3D D9  9E 23 FA 05  83 15 33 95
     85 82 F8 CF  A3 7A 2F 24  F8 EB D6 AE  20 0A 25 D0
     44 1A F9 C0  86 D7 87 B7  00

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







Hallam-Baker               Expires 6 May 2021                  [Page 20]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   Aggregate Key = Alice + Bob ()
       UDF:            TBS
       Scalar:         370810175859830330867905792457688502754055057988
           943100420373093608031918369199015948491953656482966798700316
           64591515851455352870185802
       Encoded Private
     4A AB 7A BB  2D 95 72 75  B1 3A 1D 22  24 17 76 2D
     A1 D5 55 94  67 35 8C E7  A1 A0 ED 0C  E7 88 FF 9F
     6E 2F 70 80  89 F5 01 2A  C0 AD 4C 4E  7B 90 68 6C
     F4 53 BA 32  9B 70 0F 0D
       X:              583249553407699999284154112964835446252412293188
           857058051552519639906663406776316984154017062023869075790536
           30514579317017660114474427
       Y:              518040437562811181169413740718290938351269168888
           257124107164689245721852001077758864406412789756149699111633
           051823234569886260996269341
       Encoded Public
     34 70 8D 08  DE 63 0B A6  49 2A 33 D8  B7 15 A9 84
     A4 87 F6 B6  C7 4B 1C AE  5A 1F 7C 4B  12 70 FB CF
     5A A9 3C 20  31 BA 9A 53  A0 FE 2A 43  24 97 06 F8
     DA 40 0D 88  E3 D9 DE 2E  00

   To sign the text "This is a test", Alice first generates her value r
   and multiplies it by the base point to obtain the value R_(a):

   Alice:
       r_a:            177274411620382331885613075298112943809338383162
           174753240420771790910425395072244220798681166866026098695507
           899343208324484682831848544
   R_a =
     EC 4E A5 8E  BE 3E DC C4  AA DC 67 65  D9 0D B1 24
     82 97 7E 57  83 4C BC CA  D0 68 98 72  B8 1A F2 61
     E2 CC 2C AF  AE F3 A9 8A  16 DF F1 1E  91 EC E2 FC
     3C 09 DD 25  AB 6E 7D 02  00

   Alice passes her value R_(A) to Bob along with the other parameters
   required to calculate i.  Bob then calculates his value R_(A) and
   multiplies it by the base point to obtain the value R_(b):

   Bob:
       r_b:            914384096261894497392108217856312041404007433725
           737987383860198449871749775140845071471047786135423317371867
           85115509488719418941845277
   R_b =
     7E 8C 1C B1  EA 5F 9E 58  F4 E1 4C AB  9D CF C9 4B
     42 8E 01 F4  B4 27 AA 74  D8 66 E8 5B  D5 8C 23 10
     31 A7 99 FC  69 3D 4A 81  56 9B 31 07  A4 7C 3B 83
     9D 79 6B 12  08 D0 2C CC  80



Hallam-Baker               Expires 6 May 2021                  [Page 21]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   Bob can now calculate the composite value R = R_(a) + R_(b) and thus
   the value k.

   R =
     AE 82 1A 7D  A9 B6 35 7A  3E CF 58 95  9E 97 3A 45
     62 77 E5 DB  F6 B5 B7 5F  5A 27 A0 29  0A 4D D4 2C
     9F 39 97 BB  A3 55 DC C8  BF 02 C1 8F  CE 8E 92 D9
     97 38 19 6B  73 07 19 FE  00
       k:              120812996308912938173796275547209139305812356493
           218326541177300961108122972500434047109753132978603955927000
           049579948492518627324723657

   Bob calculates his signature scalar contribution and returns the
   value to Alice:

   Bob:
       S_b:            131642872805495450312819108720996394951179966909
           422047047106195752645599694599197550402234644818088495417690
           338344590538474713569000455

   Alice can now calculate her signature scalar contribution and thus
   the signature scalar S.

   Alice:
       S_a:            135660088492295551401234992018778138767930165450
           263985669170229118586124164862063605687569508563259045492355
           878328728103423148386029682
       S:              855932802238892790767231487677734001306997921878
           565176459038750760857198979216754398940488616889715775997525
           07581656337124106095380358

   Alice checks to see that the signature verifies:

   S.B = R + kA =
       X:              225696302738968030426017676274023389357161605713
           77841610835599611770420843463
       Y:              366869559370146495596698412318900310141515842791
           80057095036770676314039224332

6.3.  Shamir Threshold Signature Ed25519

   The administrator creates the composite key pair









Hallam-Baker               Expires 6 May 2021                  [Page 22]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   ED25519Aggregate Key (ED25519)
       UDF:            ZAAA-GTSI-GQED-255X-XAGG-REGA-TEXK-EY
       Scalar:         367238470592488326468789252109412889361910680229
           03089760692844779165588879504
       Encoded Private
     FE 48 94 1F  EB 3D 28 E1  61 81 E2 1E  E1 CF F2 1E
     1E 70 91 30  DF 98 9F 1C  34 EB BB 74  C5 C8 07 EB
       X:              143576564277195758046684172284175869008525477709
           640743490221115123376609940386394888392330104965579307772627
           313244177612005636942740116142030215202393600
       Y:              844838272625277895849027219595751726665225134917
           547580682441821283235675507225396641352769322822815561632929
           543097074319051436285787045255908364074589900
       Encoded Public
     DF E8 0A 2B  E9 6C 53 C0  AB 9B BC BC  39 95 9A 61
     9C 33 2E 22  24 A7 F7 F2  21 06 AC 6D  01 5D 0B E2

   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 =    367238470592488326468789252109412889361910680229030897606928
               44779165588879504
   a1 =    338318986010852412366041291642398977925879116179901190258252
               3043521639876163

   The key share values for the participants are

   xa =    1
   ya =    392200903269604570067340531215030751116427738780256363326561
               3131259957500722

   xb =    2
   yb =    681933154723076103606316655313030495659521902216679298461852
               36496143125896

   xc =    3
   yc =    345138317558083173402104458195529282882474335202067983242870
               8280017783002059

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

   The Lagrange coefficients are:







Hallam-Baker               Expires 6 May 2021                  [Page 23]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   la =    361850278866613110698659328152149712042855817968995380300097
               5469142727125496
   lc =    361850278866613110698659328152149712042855817968995380300097
               5469142727125494

   Alice and Carol select their values ra, rc

   ra =    183324669043432475889177343290874841197580255869543278119963
               6861783584446189
   Ra =
     54 9B F7 DF  F9 4E FA 95  DE D8 27 4E  0D AD A4 81
     4B D7 1F CA  21 B4 B2 7D  D6 06 4F 59  28 41 87 92

   rc =    161475617387612449161820030097871350703159449773365674965881
               1083650872383824
   Rc =
     95 25 84 AA  B3 F7 39 14  10 67 E8 45  21 68 67 76
     11 73 88 28  D6 50 71 0F  D4 21 67 12  98 CC 80 C7

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

   R =
     22 B8 67 CA  63 65 00 7D  AD 85 96 83  FD 86 CB 92
     88 E7 E7 73  F9 3E 48 8D  AE 7E 43 E3  2D AC 5F 7F

   The value k is

   k =     300461162806835024067835386157211645931753120888211250552921
               1847964183554048

   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 =    588301354904406855101010796822546126674641608170384544989841
               9696889936251083
   sc =    189281120087571523997607099054385070601618650367961388678662
               1329133835624465

   The signature contributions can now be calulated:

   Sa =    128238145780800590303153436041482532412837879827391619588852
               5270458485017264
   Sc =    425392829290723185011341307483608802636424146029130066221513
               8481933637068796

   The dealer calculates the composite value S = S_(a) + S_(b)




Hallam-Baker               Expires 6 May 2021                  [Page 24]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   S =     553630975071523775314494743525091335049262025856521685810366
               3752392122086060

   The dealer checks to see that the signature verifies:

   S.B = R + kA =
       X:              386656916198500913898974718482142916932478347228
           53747339220827400653000735042
       X:              272627300420736046999889168909581852465293124122
           69338237353604076047710443564

6.4.  Shamir Threshold Signature Ed448

   The administrator creates the composite key pair

   ED448Aggregate Key (ED448)
       UDF:            ZAAA-ITSI-GQED-44XA-GGRE-GATE-XKEY
       Scalar:         723088510822916843359337925516642493307623385482
           113107480846498794254549074097051759295396782499503452909258
           978468506553055366989547456
       Encoded Private
     59 DC 8A 5F  5E AF 8C FA  96 19 F8 EE  78 13 00 12
     33 0E 12 80  2D 25 E6 EF  E8 E2 56 B5  83 6A 0C CF
     DC 11 96 A5  A5 D1 39 AA  34 25 0B 52  ED 9F 38 92
     5D 9F 7B BC  B9 BC 86 45
       X:              600163199260212879671026282440221570752543874569
           276531213297382365938924845597497264583528185273760383031589
           25167107013312482098672476
       Y:              568007995844826855892481230051783440873263817862
           016100095069663100696528804467952219402043387612562057320585
           561865068046226655443122582
       Encoded Public
     ED C3 90 99  38 0B 8F CD  60 29 24 04  6C DE 52 33
     A2 07 3E 56  8D 27 B5 B9  21 60 CF E9  E7 9D D6 4A
     11 47 20 E6  9D FE 75 C7  04 14 70 18  B4 52 10 83
     D0 EC 98 BD  F5 E6 E3 D5  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 =    723088510822916843359337925516642493307623385482113107480846
               49879425454907409705175929539678249950345290925897846850
               6553055366989547456
   a1 =    253947292459661473537056525563228503335644586909535883819036
               29593189848969312285942082195525418378983878506351793852
               012228645407360825




Hallam-Baker               Expires 6 May 2021                  [Page 25]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   The key share values for the participants are

   xa =    1
   ya =    216445157732761001637197701849608092875464834857486355812599
               29206860382197250994836594571141148378583546590493895709
               346188988958309165

   xb =    2
   yb =    470392450192422475174254227412836596211109421767022239631635
               58800050231166563280778676766666566757567425096845689561
               358417634365669990

   xc =    3
   yc =    724339742652083948711310752976065099546754008676558123450671
               88393240080135875566720758962191985136551303603197483413
               370646279773030815

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

   The Lagrange coefficients are:

   la =    908548405369508613186654759860005667942051700859147575351862
               74897573001980769792858097877645846187981655146854545831
               152386877929824891
   lc =    908548405369508613186654759860005667942051700859147575351862
               74897573001980769792858097877645846187981655146854545831
               152386877929824889

   Alice and Carol select their values ra, rc

   ra =    597061760142011172791892795402895896258128262343360777519356
               25449868368724094466154383697912358541824000038036669052
               993742082445345445
   Ra =
     35 E5 61 55  78 E7 27 24  55 2D C9 76  4B 49 2B 46
     16 E3 FA 97  2F 9A E6 47  1B 22 CD 2D  54 F5 1A 1C
     7A A7 67 B0  CE 65 84 05  39 33 0E A6  33 5E 67 BD
     58 CA ED 7E  F3 EE DD 59  00

   rc =    134782448747121628062621888359149856538463227176060814858572
               40759552504564125328966600869858667833252205589918638910
               3286110005426517374
   Rc =
     3C 7B 81 57  A9 C9 23 90  E2 1D 82 42  7B 0C D9 88
     E7 E5 98 81  DB 52 76 E3  77 67 E8 34  DC D7 DC 81
     20 B6 3A 6F  EC E8 0C D9  0E BC C5 5A  A0 E6 91 D5
     D9 14 0B 60  C2 A4 D0 A8  80



Hallam-Baker               Expires 6 May 2021                  [Page 26]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


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

   R =
     00 27 F8 F7  A7 39 F7 AE  B6 8F E4 0F  A8 4E 3A 71
     45 87 6A 1E  C4 C3 29 52  CC 8A C7 6C  36 47 4B A6
     04 F8 55 03  7B 49 86 87  E4 91 AB 73  E0 AF 3F 12
     AB 7F 09 2D  4E 06 4A 71  00

   The value k is

   k =     111997156629233344141251678175691985810414419806912701822160
               03679477455027316936425566511876628316232490805931954430
               9467825781335347270

   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 =    123321614196865011564245131263441780725524895314537710907076
               16870786357527664628511298973435756875585697503259538939
               5171670361367288637
   sc =    546378534043466638830999383371973118168674696520868513626526
               80700952961912832009497718396549853619706003345255804124
               467063738043309482

   The signature contributions can now be calulated:

   Sa =    458780069801903308724659679047126206540023727016859370284301
               27448209487257982695731719827860225173821194895861101407
               212569594681924953
   Sc =    401983114222685811776093088236307108408769238787937252473320
               58598217288865359359764076141664751937484813828720687591
               206436379246811336

   The dealer calculates the composite value S = S_(a) + S_(b)

   S =     860763184024589120500752767283433314948792965804796622757621
               86046426776123342055495795969524977111306008724581788998
               419005973928736289

   The dealer checks to see that the signature verifies:

   S.B = R + kA =
       X:              565863868058207644748379075787643375969163605886
           69329263413068616160478393570
       X:              150478297775841135131577263700053908124463098444
           5517859016637728894764938481




Hallam-Baker               Expires 6 May 2021                  [Page 27]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


7.  Security Considerations

   All the security considerations of [RFC7748], [RFC8032] and
   [draft-hallambaker-threshold] apply and are hereby incorporated by
   reference.

7.1.  Rogue Key attack

   The rogue key attack described in [draft-hallambaker-threshold] is of
   particular concern to generation of threshold signatures.

   If _A_ and _B_ are public keys, the intrinsic degree of trust in the
   composite keypair _A_ + _B_ is that of the lesser of _A_ and _B_.

7.2.  Disclosure or reuse of the value r

   As in any Schnorr signature scheme, compromise of the value _r_
   results in compromise of the private key.  The base signature
   specification [RFC8032] describes a deterministic construction of _r_
   that ensures confidentiality and uniqueness for a given value of _k_.

   As described above, this approach is not applicable to the generation
   of values of _r_(i)_ to compute threshold signature contributions.
   Accordingly the requirements of [RFC4086] regarding requirements for
   randomness MUST be observed.

   Implementations MUST NOT use a deterministic generation of the value
   _r_(i)_ for any threshold contribution except for calculating the
   final contribution when all the other parameters required to
   calculate _k_ are known.

7.3.  Resource exhaustion attack

   Implementation of the general two stage signing algorithm requires
   that signers track generation and use of the values _r_(i)_ to avoid
   reuse for different values of _R_(i)_. Implementations MUST ensure
   that exhaustion of this resource by one party does not cause other
   parties to be denied service.

7.4.  Signature Uniqueness

   Signatures generated in strict conformance with [RFC8032] are
   guaranteed to be unique such that signing the same document with the
   same key will always result in the same signature value.

   The signature modes described in this document are computationally
   indistinguishable from those created in accordance with [RFC8032] but
   are not unique.



Hallam-Baker               Expires 6 May 2021                  [Page 28]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   Implementations MUST not use threshold signatures in applications
   where signature values are used in place of cryptographic digests as
   unique content identifiers.

8.  IANA Considerations

   This document requires no IANA actions.

9.  Acknowledgements

   [TBS]

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-10, 27 July 2020,
              <https://tools.ietf.org/html/draft-hallambaker-mesh-udf-
              10>.

   [draft-hallambaker-threshold]
              Hallam-Baker, P., "Threshold Modes in Elliptic Curves",
              Work in Progress, Internet-Draft, draft-hallambaker-
              threshold-03, 3 September 2020,
              <https://tools.ietf.org/html/draft-hallambaker-threshold-
              03>.

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

   [RFC4086]  Eastlake 3rd, D., Schiller, J., and S. Crocker,
              "Randomness Requirements for Security", BCP 106, RFC 4086,
              DOI 10.17487/RFC4086, June 2005,
              <https://www.rfc-editor.org/rfc/rfc4086>.

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

11.  Informative References



Hallam-Baker               Expires 6 May 2021                  [Page 29]


Internet-Draft   Threshold Signatures in Elliptic Curves   November 2020


   [draft-hallambaker-mesh-developer]
              Hallam-Baker, P., "Mathematical Mesh: Reference
              Implementation", Work in Progress, Internet-Draft, draft-
              hallambaker-mesh-developer-10, 27 July 2020,
              <https://tools.ietf.org/html/draft-hallambaker-mesh-
              developer-10>.

   [Komlo]    Komlo, C. and I. Goldberg, "FROST: Flexible Round-
              Optimized Schnorr Threshold Signatures", 2020.

   [RFC5860]  Vigoureux, M., Ward, D., and M. Betts, "Requirements for
              Operations, Administration, and Maintenance (OAM) in MPLS
              Transport Networks", RFC 5860, DOI 10.17487/RFC5860, May
              2010, <https://www.rfc-editor.org/rfc/rfc5860>.

   [Shamir79] Shamir, A., "How to share a secret.", 1979.



































Hallam-Baker               Expires 6 May 2021                  [Page 30]