InternetDraft  Threshold Signatures in Elliptic Curves  March 2020 
HallamBaker  Expires 10 September 2020  [Page] 
 Workgroup:
 Network Working Group
 InternetDraft:
 drafthallambakerthresholdsigs
 Published:
 Intended Status:
 Informational
 Expires:
Threshold Signatures in Elliptic Curves
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 nondeterministic. 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/Discussion of this draft should take place on the CFRG mailing list (cfrg@irtf.org), which is archived at .¶
Status of This Memo
This InternetDraft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
InternetDrafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as InternetDrafts. The list of current InternetDrafts is at https://datatracker.ietf.org/drafts/current/.¶
InternetDrafts 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 InternetDrafts as reference material or to cite them other than as "work in progress."¶
This InternetDraft will expire on 10 September 2020.¶
Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/licenseinfo) 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.¶
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 multisignatures, 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 multisignatures or threshold signatures to be inherently superior, it is more useful to regard both as two points on a continuum of choices:¶
 Multisignatures

Multiple digital signatures on the same document. Multisignatures 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.¶
 Multiparty 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 [drafthallambakerthreshold] 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.¶
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 [drafthallambakerthreshold].¶
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 multisignatures.¶
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 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.4. Implementation Status
The implementation status of the reference code base is described in the companion document [drafthallambakermeshdeveloper].¶
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 nondeterministic quorate threshold scheme produces values of R and S that will be different each time the document is signed.¶
Recall that a digital signature as specified by [RFC8032] consists of a pair of values S, R calculated as follows:¶
R = r.B¶
S = r + k.s mod L¶
 Where

B is the base point of the elliptic curve.¶
r is an unique, unpredictable integer value such that 0 r L¶
k is the result of applying a message digest function determined by the curve (Ed25519, Ed448) to a set of parameters known to the verifier which include the values R, A and PH(M).¶
A is the public key of the signer, A = s.B¶
PH(M) is the prehash function of the message value.¶
s is the secret scalar value¶
L is the order of the elliptic curve group.¶
To verify the signature, the verifier checks that:¶
S.B = R + k.A¶
This equality must hold for a valid signature since:¶
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 = (Sr).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.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.¶
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.¶
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_{n1})¶
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 adhoc 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 [drafthallambakerthreshold].¶
The dealer selects the signers who are to construct the signature. Each signer then computes the value R_{i}:¶
 Randomly generate an integer r_{i} such that 1 r_{i} L.¶
 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¶
 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:¶
 Compute SHA512(dom2(F, C)  R  A  PH(M)), and interpret the 64octet digest as a littleendian integer k.¶
 Compute S_{i} = (r_{i} + kc_{i}s_{i}) mod L. For efficiency, again reduce k modulo L first.¶
 Return the values R_{i}, S_{i} to the dealer .¶
The dealer then completes the signature by:¶
5. Ed448 Signature
The means by which threshold shares are created is described in [drafthallambakerthreshold].¶
The dealer selects the signers who are to construct the signature. Each signer then computes the value R_{i}:¶
 Randomly generate an integer r_{i} such that 1 r_{i} L.¶
 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¶
 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:¶
 Compute SHAKE256(dom4(F, C)  R  A  PH(M), 114), and interpret the 114octet digest as a littleendian integer k.¶
 Compute S_{i} = (r_{i} + kc_{i}s_{i}) mod L. For efficiency, again reduce k modulo L first.¶
 Return the values R_{i}, S_{i} to the dealer.¶
The dealer then completes the signature by:¶
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:¶
ED25519Alice's Key (ED25519) UDF: ZAAAGTSIGXED255XXALICEXSXKEY 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: ZAAAGTSIG2ED255XXBOBXSXKEY 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}¶
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 = 47498736868184230171598682949552850028048129926454476046383202 22101432831360 R_a = 37 4D BC B2 FC 26 43 69 DA B7 DF 78 F7 05 63 1D C4 96 FB FB D6 CC 6A 9E 92 ED E7 35 93 44 B8 14¶
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 = 52485056662860498129500187267044856221580824276836907703860095 4226327269184 R_b = AB A1 A8 28 11 6E FC A0 E9 8B CF 53 A2 4C AF F8 66 59 69 4B 2F 37 93 77 92 3A 70 95 33 DE 5B 54¶
Bob can now calculate the composite value R = R_{a} + R_{b} and thus the value k.¶
R = 5B 68 76 8C CA 23 E6 84 36 92 76 F1 9E FF 08 8F 0A 16 A9 55 E3 96 9C 84 36 28 89 DB 06 16 43 44 k = 2386567530061545624821866403866306492890802298065266303263411446 38069188344¶
Bob calculates his signature scalar contribution and returns the value to Alice:¶
Bob: S_b = 28944981827334439860137457106479900995796126061421325490732808 17601718529025¶
Alice can now calculate her signature scalar contribution and thus the signature scalar S.¶
Alice: S_a = 42757354096062105044904298703340896803929542552166792901005683 43184517117786 S = 7170233592339654490504175580982079779972566861358811839173849160 786235646811¶
Alice checks to see that the signature verifies:¶
S.B = R + kA = X: 40361643976948744971992641065784582623361456745859092512349846 75625733276535 Y: 41192378513331957483774498173296750751876504986403840969777850 360997558579289¶
6.2. Direct Threshold Signature Ed448
The signers are Alice and Bob's Threshold Signature Service 'Bob'. Each creates a key pair:¶
ED448Alice's Key (ED448) UDF: ZAAAITSIGXED44XALICEXSXKEY 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: ZAAAITSIG2ED44XBOBXSXKEY 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}¶
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 = 68686103432614286085087961100697733989779035076023642515818127 98858367044290553184740969706908768491109520568381137474912463623 0094998 R_a = 84 D1 68 50 1E BB 9D 40 17 52 C5 D2 96 41 DE FC 22 D9 04 02 82 27 1B 32 CD 1D 8C 53 85 AB 40 79 F5 00 C2 4C 89 A6 71 0A 39 08 A6 98 4C 2A FE FD B9 F7 66 FC E9 F2 20 B9 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 = 76096557183484521564781984661044762292570684233728343619181213 42816465520852868086783053490696058232580309131924136177891398775 9613091 R_b = F3 60 25 C5 13 CE AA A9 B2 7E 9D 05 5B B1 F5 6B 4F 5B A5 EC 49 3F 39 A4 B5 C3 3C 7F 80 17 44 5B 02 83 FD 12 06 A2 DF E8 C6 46 1D 2A 6C 8E 75 70 02 53 71 3F 95 C2 71 A8 00¶
Bob can now calculate the composite value R = R_{a} + R_{b} and thus the value k.¶
R = 25 F2 BA FD D1 BB 3F 38 7B 4F 26 63 47 9A 78 81 4F CB 1F 82 8D F9 84 D4 34 96 E1 5A 4A 52 46 2C 13 EF 67 37 E0 61 13 9F B2 1F 7E C5 B9 56 7F B6 CA 88 D7 0B CC BC 96 C5 00 k = 1280456290623708148598382410642762981433750669722496871781111755 77910741520269875312421999840786826452062625868870120134096187323 572465¶
Bob calculates his signature scalar contribution and returns the value to Alice:¶
Bob: S_b = 13468720239873188337021798218509333541110080817756031277945581 40664081463680336638329881442786750747115016847691428033880365372 48950911¶
Alice can now calculate her signature scalar contribution and thus the signature scalar S.¶
Alice: S_a = 11878333834477344997625309702086496132606331016796170754366862 41133668758758146277756495968716749041239572075324760597254347275 98536495 S = 7176085966960361070914012723395716314875377817369250525275188838 46290182823087058924419858586576028721485985925272008086975089878 37627¶
Alice checks to see that the signature verifies:¶
S.B = R + kA = X: 16291004486439090147776612791895755846785064919509905636229908 328194692798396 Y: 46841527536088411435030533441004631079380726947860208328057908 29635735834402¶
6.3. Shamir Threshold Signature Ed25519
The administrator creates the composite key pair¶
ED25519Aggregate Key (ED25519) UDF: ZAAAGTSIGQED255XXAGGREGATEXKEY 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 = 4447543804183276703367140352869026105461853047473514285943821414 241349264676¶
The key share values for the participants are¶
xa = 1 ya = 3741579482988170765278279250490187507889572786185132393071818643 89698982558 xb = 2 yb = 4821701752482093779894968277918044856250810326092027525251003278 631048247234 xc = 3 yc = 2032239979333108269288922067744076720855547014185634205192873754 586943260921¶
Alice and Carol are selected to sign the message "This is another test"¶
The Lagrange coefficients are:¶
la = 3618502788666131106986593281521497120428558179689953803000975469 142727125496 lc = 3618502788666131106986593281521497120428558179689953803000975469 142727125494¶
Alice and Carol select their values ra, rc¶
ra = 5377248352669516780549162073457874087773506582785629831437934867 461127075879 Ra = 2F 0E 76 87 F3 98 84 41 03 29 5F 5A 84 7D 62 34 A3 9B 64 8C 34 11 99 F1 D5 A9 63 0E 8E 3D 6C C9 rc = 4232465617601402201287633784079511069602658258584839658166776648 89765437047 Rc = 53 7C 5B 73 DE 10 64 82 3C CF CF 19 5F E8 83 24 A0 14 A3 F2 FF 7E 4D 0D 42 42 8E B3 03 66 49 04¶
The composite value R = R_{a} + R_{c}¶
R = 5E BA 21 F2 87 4E C8 4E B8 4B E9 5C 1E 3A B2 67 B8 D0 E3 B3 98 C8 DB E0 E6 50 35 8D 47 9B C1 E1¶
The value k is¶
k = 31647328596154272207177743411362878636270581278391351236822318404 2871610589¶
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 = 5612369224482256147917418875735281261834359179277698589607727965 84548473837; sc = 2602382798999576972342132247649458760000784672597136700404538591 849255495034¶
The signature contributions can now be calulated:¶
Sa = 6873614337238287985974631938614575791975512646788133685349814447 956390424246 Sc = 6734965213168676845758127805874268408589146808656626354387236455 007092488600¶
The dealer calculates the composite value S = S_{a} + S_{b}¶
S = 6371573973074702617759573181445849959707543096064852433735099964 678028661857¶
The dealer checks to see that the signature verifies:¶
S.B = R + kA = X: 50976148565709102066754003035356376378566475226930883450768310 75625019906058 Y: 74629887867177957343114045996705864971381351024041289421281109 60605559633693¶
6.4. Shamir Threshold Signature Ed448
The administrator creates the composite key pair¶
ED448Aggregate Key (ED448) UDF: ZAAAITSIGQED44XAGGREGATEXKEY 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 = 3934291191212650584059669841203896874838912563882890929786754329 01065050103930671683138406271792350963735688973370364434513108789 92904¶
The key share values for the participants are¶
xa = 1 ya = 3118475254618553241339722078876528141267932728756118294017944444 35183096299031399695530728818078200859172750635470321098006758306 3279 xb = 2 yb = 4246138716674505908193642049091549688965705836758502759188548773 44583359733833811652691479153600171049652964036917396544313784620 56183 xc = 3 yc = 8180429907887156492253311890295446563804618400641393688975303102 45648409837764483335829885425392522013388653010287760978826893410 49087¶
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 = 1610705867304076392921723072340177274788014288395871190735371844 45304821479265411365593663429368194644596000340187951474891649791 38278 Ra = CF 97 83 F4 16 2D EF A1 85 95 8F 65 68 BC 59 56 94 9F 51 61 A7 F9 95 27 81 E6 83 7F 0A E6 16 C0 50 8D 8A D5 B6 47 3C 64 E0 34 1B AB F3 BF 89 96 41 5D A8 29 06 04 F9 D3 00 rc = 1513721922038322665004883340036457345550315134561588659560214983 90578815745979201541151452164958584639864068264575123975657731927 908051 Rc = 7A 5A E9 4E 9B E9 9E 66 C1 E2 CE 3A B5 CD 73 FA 4C C7 9E E9 C3 59 37 46 11 55 62 6A DC 69 8D 7F 63 20 CF B0 30 6D 77 5E B4 5F 09 B3 8A ED C6 36 64 8F 6B 70 02 DE AB 45 00¶
The composite value R = R_{a} + R_{c}¶
R = D0 51 EC 22 5C 8A 25 9E E7 B6 0B 1E 26 54 0F 51 4C 65 1C B5 24 B1 89 91 FA 63 32 39 89 89 24 9B 03 3E E6 83 1A 74 FA 79 0D E5 90 D7 C2 7C 3B FF 22 D5 B2 7F B7 14 C8 F0 80¶
The value k is¶
k = 11205778835971090763459400118127617086725238194171737531994098751 92020469089993225609677938158558606382862723600565685005808743888 1311¶
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 = 9553255341887869118067505910431535900610706917904893497621319156 41007484252552638535308385781173609945427381140778859688569793044 19808; sc = 4995269099751507885739891653452333397518207808270778909030975938 52905814888815686913063833745765618809857142040314431034455332593 00346¶
The signature contributions can now be calulated:¶
Sa = 1288724802012784524546710951030879127642885816514372129177355341 52388852607084448690299630591486640562077067211721300969711457389 734384 Sc = 9245427182572705582371845728508254342708120847149751739704864321 05098990035212645834079206651328626851538428963929848345208375317 71245¶
The dealer calculates the composite value S = S_{a} + S_{b}¶
S = 3961707095310378564105860041616932260295944995110521524441162756 77527476490661275575117959649271272839206163990226234994585390618 55850¶
The dealer checks to see that the signature verifies:¶
S.B = R + kA = X: 89820587157297640914878146420868301420919058721019003413415111 40349053172466 Y: 29679650828270530327946891692133348611591938177520550739646498 568569373309365¶
7. Security Considerations
All the security considerations of [RFC7748], [RFC8032] and [drafthallambakerthreshold] apply and are hereby incorporated by reference.¶
7.1. Rogue Key attack
The rogue key attack described in [drafthallambakerthreshold] 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.¶
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
 [drafthallambakermeshudf]
 HallamBaker, P., "Mathematical Mesh 3.0 Part II: Uniform Data Fingerprint.", Work in Progress, InternetDraft, drafthallambakermeshudf08, , <https://tools.ietf.org/html/drafthallambakermeshudf08>.
 [drafthallambakerthreshold]
 HallamBaker, P., "Threshold Key Generation and Decryption in Ed25519 and Ed448", Work in Progress, InternetDraft, drafthallambakerthreshold00, , <https://tools.ietf.org/html/drafthallambakerthreshold00>.
 [RFC2119]
 Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfceditor.org/rfc/rfc2119>.
 [RFC4086]
 Eastlake 3rd, D., Schiller, J., and S. Crocker, "Randomness Requirements for Security", BCP 106, RFC 4086, DOI 10.17487/RFC4086, , <https://www.rfceditor.org/rfc/rfc4086>.
 [RFC7748]
 Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, , <https://www.rfceditor.org/rfc/rfc7748>.
 [RFC8032]
 Josefsson, S. and I. Liusvaara, "EdwardsCurve Digital Signature Algorithm (EdDSA)", RFC 8032, DOI 10.17487/RFC8032, , <https://www.rfceditor.org/rfc/rfc8032>.
11. Informative References
 [drafthallambakermeshdeveloper]
 HallamBaker, P., "Mathematical Mesh: Reference Implementation", Work in Progress, InternetDraft, drafthallambakermeshdeveloper09, , <https://tools.ietf.org/html/drafthallambakermeshdeveloper09>.
 [Komlo]
 Komlo, C. and I. Goldberg, "FROST: Flexible RoundOptimized Schnorr Threshold Signatures", .
 [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, , <https://www.rfceditor.org/rfc/rfc5860>.
 [Shamir79]
 Shamir, A., "How to share a secret.", .