Threshold Signatures in Elliptic Curves
draft-hallambaker-threshold-sigs-04
The information below is for an old version of the document.
| Document | Type |
This is an older version of an Internet-Draft whose latest revision state is "Expired".
|
|
|---|---|---|---|
| Author | Phillip Hallam-Baker | ||
| Last updated | 2020-09-03 (Latest revision 2020-07-28) | ||
| RFC stream | (None) | ||
| Formats | |||
| Additional resources | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-hallambaker-threshold-sigs-04
Network Working Group P. M. Hallam-Baker
Internet-Draft ThresholdSecrets.com
Intended status: Informational September 4, 2020
Expires: March 8, 2021
Threshold Signatures in Elliptic Curves
draft-hallambaker-threshold-sigs-04
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 March 8, 2021.
Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved.
Hallam-Baker Expires March 8, 2021 [Page 1]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 2]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 3]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 4]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 5]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 6]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 7]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 8]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 9]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 10]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 11]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 12]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 13]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 14]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 15]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 16]
Internet-Draft Threshold Signatures in Elliptic Curves September 2020
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 composite Signature Key A = A_(a) + A_(b)
Hallam-Baker Expires March 8, 2021 [Page 17]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 first generates her value r
and multiplies it by the base point to obtain the value R_(a):
Alice:
r_a = 39481530989500570659081556772521617337911026343586730199076077
22114057563970
R_a =
97 4A 15 AC C8 05 21 91 87 B7 1F C1 2F AB C4 00
6E 52 85 09 54 04 00 5E 30 62 99 F5 62 A5 2F 7E
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 = 53794602633571448603419732447329315217287976777312087913574775
08723470105822
R_b =
8E 48 01 72 91 74 D0 C9 36 44 EA 7B 8A D2 50 0D
F2 4B F9 2C 53 B7 AF 2D 91 06 81 79 3D 28 43 DD
Bob can now calculate the composite value R = R_(a) + R_(b) and thus
the value k.
R =
55 1A 67 0A D2 8C F6 74 FD A7 0E BE 4D AA A8 8F
E6 AB 98 61 7B 7D 04 D4 F2 05 0A 71 D3 81 59 AF
k = 2421363997835522134020668429031063921379440688711932467881614021
504091928861
Hallam-Baker Expires March 8, 2021 [Page 18]
Internet-Draft Threshold Signatures in Elliptic Curves September 2020
Bob calculates his signature scalar contribution and returns the
value to Alice:
Bob:
S_b = 16218971061984715973738168270294546698092320250831576357174059
25399123547360
Alice can now calculate her signature scalar contribution and thus
the signature scalar S.
Alice:
S_a = 48633098250297226038262755114982589781022109179929876390922466
96122249236384
S = 6485206931228194201200092338527713647911442943076145274809652621
521372783744
Alice checks to see that the signature verifies:
S.B = R + kA =
X: 31970754396382072160768904923868016501704809130751339430468771
226924902729588
Y: 42652466254796906167986746499263519020730974689311471235758253
40736275086949
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 March 8, 2021 [Page 19]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 composite Signature Key A = A_(a) + A_(b)
Hallam-Baker Expires March 8, 2021 [Page 20]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 first generates her value r
and multiplies it by the base point to obtain the value R_(a):
Alice:
r_a = 12579897228229965435145658294327712989795531501893232106499892
89681302839491331449888721535664675983310277410977228241931824542
50578091
R_a =
25 81 8E 72 12 06 2B 9F C2 90 9F 9E 16 55 51 16
A1 53 24 FD C3 29 82 A5 3E DC 0E 69 5C C7 FF 7E
71 60 4E 21 CB 71 59 84 68 9B 1F 59 E1 56 F0 FD
4A 80 67 9C 99 2D C9 A8 80
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 = 94475541305183315492441638684696640787219219352824613903602377
05284653346212377761617015793185322655995130417461462487958500972
3713102
R_b =
AF 91 A2 24 B1 B3 5E F4 F3 2C A5 06 45 A7 90 23
28 68 4A 3E E8 8D D7 B2 40 12 55 85 20 BF 53 82
86 97 9A 3D 84 40 D5 A3 4E E6 A6 D2 2E 80 1A DC
40 32 04 DF AB 09 E1 FE 80
Hallam-Baker Expires March 8, 2021 [Page 21]
Internet-Draft Threshold Signatures in Elliptic Curves September 2020
Bob can now calculate the composite value R = R_(a) + R_(b) and thus
the value k.
R =
FB 04 F2 8A 1D 26 6D AF 0F C5 27 3C 19 4C 9F 30
D7 B8 CB B3 73 F2 EC 7C 0C 41 ED D5 AB B6 50 A9
C9 AD 45 50 34 A6 24 83 50 91 0A 9A 56 EC 59 D9
15 34 81 7A 5D 40 96 F4 80
k = 1114611014063501116613867141529424596251655496753131787628559383
37364120817354370936515245042197321114567413248741160748378478790
681471
Bob calculates his signature scalar contribution and returns the
value to Alice:
Bob:
S_b = 16039476917135265334527230911158039502139318338070597455056095
64681863169906962950761847223946073430255036087562611717818559618
1028696
Alice can now calculate her signature scalar contribution and thus
the signature scalar S.
Alice:
S_a = 21026356483062916567544814937806998370021341112531790514607516
15676503362950349198935476068933071440579133782644266606317107429
0101794
S = 3706583340019818190207204584896503787216065945060238796966361180
35836653285731214969732329287914487083416987020687832413566704711
30490
Alice checks to see that the signature verifies:
S.B = R + kA =
X: 13430030555801715651108391534497698605996566164478554520490263
44715275527428
Y: 23294518891760930618220409397109930286557491844791521429604956
720890326572862
6.3. Shamir Threshold Signature Ed25519
The administrator creates the composite key pair
Hallam-Baker Expires March 8, 2021 [Page 22]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 = 1642892179747526362125411177719513794207741359956661956935408266
531254199801
The key share values for the participants are
xa = 1
ya = 4806511901195328949259285312942500680391961950481568516300719654
965058168672
xb = 2
yb = 6449404080942855311384696490662014474599703310438230473236127921
496312368473
xc = 3
yc = 8552906833581194595369211053385340279503283110149848241695852497
42112317285
Alice and Carol are selected to sign the message "This is another
test"
The Lagrange coefficients are:
Hallam-Baker Expires March 8, 2021 [Page 23]
Internet-Draft Threshold Signatures in Elliptic Curves September 2020
la = 3618502788666131106986593281521497120428558179689953803000975469
142727125496
lc = 3618502788666131106986593281521497120428558179689953803000975469
142727125494
Alice and Carol select their values ra, rc
ra = 4582163519135697954212356121831281867610872330474418182918654552
719487887500
Ra =
2A E0 F9 8B D2 85 C5 61 5D 14 D8 BF EA E9 96 D3
1A E2 0B 37 8A 7C 5C FE 90 6C DF 36 70 D0 BC 90
rc = 3679566825305648240874136350616349919194440179398151235437522804
353602423864
Rc =
3D 0B 8B D5 B4 5A 93 B0 3E B0 24 CE 42 AD F7 FF
4D 43 6C 09 1C 07 0A F9 76 9C F5 D2 59 E2 B7 9A
The composite value R = R_(a) + R_(c)
R =
B7 93 54 14 DD AC A5 94 00 3D 09 EB 60 E6 91 18
9A AF 60 07 DA CA E5 83 7E 1F 3E 6A C4 49 DF A3
The value k is
k = 40993397091938598651697285820684701229880737187373552994300226559
88467436177
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 = 7209767851792993423888927969413751020587942925722352774451079482
447587253008;
sc = 3190857446987071377218132728852230106453394024182461390916182844
271670966852
The signature contributions can now be calulated:
Sa = 3328989745507326292266821261476737658921447882205957270253608502
484638974498
Sc = 5932746180467179638638850117242322706693329974834825884925701595
858986229620
The dealer calculates the composite value S = S_(a) + S_(b)
Hallam-Baker Expires March 8, 2021 [Page 24]
Internet-Draft Threshold Signatures in Elliptic Curves September 2020
S = 2024730348642243716932484815676066124757661497660875549177359160
058170953129
The dealer checks to see that the signature verifies:
S.B = R + kA =
X: 13666591543765071964834317735790194069963726165121686955487832
105142108752977
Y: 20775966697642032279966691396030726941085308409030793184460185
676304105925271
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: 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 = 5089046065641972153127358795828409601581098276054157542072680505
39683337837216003977228732536078674802149039736292653681850024283
019712
a1 = 1550999901841386151901998425672690051264689056286441960494229439
42535003917136508299604076339687566636344266479521172051858028847
271091
Hallam-Baker Expires March 8, 2021 [Page 25]
Internet-Draft Threshold Signatures in Elliptic Curves September 2020
The key share values for the participants are
xa = 1
ya = 1188755535266306625909428662341065645193477127185714050455733450
96780329869733755128245543000689113548562425088538838819386785551
341466
xb = 2
yb = 9226586263686755514381175682937443605740627817538608602462373924
41693298253306777116538640486843042215963978589683485664710585389
62778
xc = 3
yc = 6565617174710444769668064742464230759546484363220076700367413339
15583297809276002950621850966794948946303706293978583135553315265
84090
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 = 1496695989301362163168579893078939576055478053582077987842188159
81572439136632201150848887159722470726697626221876540830488497692
099942
Ra =
8F C2 62 01 43 39 35 2F 15 1C 97 BD D6 29 92 ED
C2 DF E7 56 0B 49 37 E4 F7 BA 7A 5D BA 45 1C 39
EE 23 EF FE F3 CB 5B ED 33 AB A8 D9 97 0D B4 9C
70 C1 02 A2 71 08 20 F8 80
rc = 1315259132332389080097729070288895479376412145635234566561260348
85686598945854770737828828936179895865317203017520659128509983064
478834
Rc =
B0 37 9E BC 5A 50 0E DC 19 56 7D 1A 4E 6F 92 63
33 C2 82 5C 77 45 2E A7 79 54 7A A2 FB FE F4 F8
90 CE D1 5C 04 A0 7C EB 87 D2 BA E5 57 CF 3F 45
FA FD 27 7E 10 29 91 AC 80
Hallam-Baker Expires March 8, 2021 [Page 26]
Internet-Draft Threshold Signatures in Elliptic Curves September 2020
The composite value R = R_(a) + R_(c)
R =
02 F1 FC 76 4F 34 A6 74 39 CB AF D3 96 DF C2 6F
F8 D2 8C C7 28 C8 36 F1 DE 9A E7 CE 9A DE C6 79
90 9E 2F 2A E8 14 E0 14 CD 06 8B 30 F1 61 EA C0
89 11 7C 85 33 F2 8A 08 00
The value k is
k = 24349522678580469525531601305349874786441698191777297108871400571
64322563268580245413433284674218785382878420998275959014579479614
7935
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 = 1783133302899459938864142993511598467790215690778571075683600176
45170494804600632692368314501033670322843637632808258229080178327
012199;
sc = 1488815952003494987889906282596799797906779183557291315685354830
99366839071075785568664662743352628515995108394392733147996090096
357734
The signature contributions can now be calulated:
Sa = 1813098642235159385577750965787902646262662182590690423179327447
87548599871305490942337029804015073122558685157994421699467930005
403407
Sc = 1786732187196626949822274127967658987330014322486999403584441819
61287645876306473101042347188778074681315014827243713964951294010
546032
The dealer calculates the composite value S = S_(a) + S_(b)
S = 1782734018692769109026715574035550297708573103359394676060043769
53690241786072378327183621701100771840563406276146473359645468156
299660
The dealer checks to see that the signature verifies:
S.B = R + kA =
X: 22269164075823155982206235662550890548495096320747189740776580
698080912420099
Y: 22192519940337997518518077627365944525840303920321484782585911
563432903433924
Hallam-Baker Expires March 8, 2021 [Page 27]
Internet-Draft Threshold Signatures in Elliptic Curves September 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 March 8, 2021 [Page 28]
Internet-Draft Threshold Signatures in Elliptic Curves September 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, July 27, 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-02, March 9, 2020, <https://tools.ietf.org/html/
draft-hallambaker-threshold-02>.
[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 March 8, 2021 [Page 29]
Internet-Draft Threshold Signatures in Elliptic Curves September 2020
[draft-hallambaker-mesh-developer]
Hallam-Baker, P., "Mathematical Mesh: Reference
Implementation", Work in Progress, Internet-Draft, draft-
hallambaker-mesh-developer-10, July 27, 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 March 8, 2021 [Page 30]