idnits 2.17.1 draft-hallambaker-threshold-sigs-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Authors' Addresses Section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 621 has weird spacing: '... where a_(0)...' == Line 630 has weird spacing: '... where p_(1)...' -- The document date (5 January 2020) is 1544 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Obsolete informational reference (is this intentional?): RFC 2314 (Obsoleted by RFC 2986) Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group P. M. Hallam-Baker 3 Internet-Draft Venture Cryptography. 4 Intended status: Informational 5 January 2020 5 Expires: 8 July 2020 7 Threshold Signatures Using Ed25519 and Ed448 8 draft-hallambaker-threshold-sigs-00 10 Abstract 12 A Threshold signature scheme is described. The signatures created 13 are computationally indistinguishable from those produced using the 14 Ed25519 and Ed448 curves as specified in RFC8032 except in that they 15 are non-deterministic. Threshold signatures are a form of digital 16 signature whose creation requires two or more parties to interact but 17 does not disclose the number or identities of the parties involved. 19 Status of This Memo 21 This Internet-Draft is submitted in full conformance with the 22 provisions of BCP 78 and BCP 79. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF). Note that other groups may also distribute 26 working documents as Internet-Drafts. The list of current Internet- 27 Drafts is at https://datatracker.ietf.org/drafts/current/. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 This Internet-Draft will expire on 8 July 2020. 36 Copyright Notice 38 Copyright (c) 2020 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 43 license-info) in effect on the date of publication of this document. 44 Please review these documents carefully, as they describe your rights 45 and restrictions with respect to this document. 47 Table of Contents 49 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 50 2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 4 51 2.1. Requirements Language . . . . . . . . . . . . . . . . . . 4 52 2.2. Defined Terms . . . . . . . . . . . . . . . . . . . . . . 4 53 2.3. Related Specifications . . . . . . . . . . . . . . . . . 4 54 2.4. Implementation Status . . . . . . . . . . . . . . . . . . 4 55 3. Threshold Signature Construction . . . . . . . . . . . . . . 4 56 3.1. Threshold signature . . . . . . . . . . . . . . . . . . . 6 57 3.2. Ed2519 Signature . . . . . . . . . . . . . . . . . . . . 8 58 3.3. Ed448 Signature . . . . . . . . . . . . . . . . . . . . . 9 59 3.4. Security Analysis . . . . . . . . . . . . . . . . . . . . 10 60 3.4.1. Replay Attack . . . . . . . . . . . . . . . . . . . . 10 61 3.4.2. Malicious Contribution Attack . . . . . . . . . . . . 11 62 3.4.3. Rogue Key Attack . . . . . . . . . . . . . . . . . . 11 63 4. Unanimous Signature . . . . . . . . . . . . . . . . . . . . . 12 64 4.1. Using threshold key generation . . . . . . . . . . . . . 12 65 4.2. Using key splitting . . . . . . . . . . . . . . . . . . . 13 66 5. Quorate Signature . . . . . . . . . . . . . . . . . . . . . . 13 67 5.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 13 68 5.2. Calculating the secret scalar value . . . . . . . . . . . 14 69 6. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 15 70 6.1. Unanimous Threshold Signature Ed25519 . . . . . . . . . . 15 71 6.2. Unanimous Threshold Signature Ed448 . . . . . . . . . . . 17 72 6.3. Quorate Threshold Signature Ed25519 . . . . . . . . . . . 20 73 6.4. Quorate Threshold Signature Ed448 . . . . . . . . . . . . 23 74 7. Security Considerations . . . . . . . . . . . . . . . . . . . 25 75 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 76 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25 77 10. Normative References . . . . . . . . . . . . . . . . . . . . 26 78 11. Informative References . . . . . . . . . . . . . . . . . . . 26 80 1. Introduction 82 Threshold encryption and key generation provide compelling advantages 83 over single private key approaches because splitting the private key 84 permits the use of that key to be divided between two or more roles. 86 All existing digital signatures allow the signer role to be divided 87 between multiple parties by attaching multiple signatures to the 88 signed document. This approach, known as multi-signatures is 89 distinguished from a threshold signature scheme in that the identity 90 and roles of the individual signers is exposed. In a threshold 91 signature scheme, the creation of a single signature requires the 92 participation of multiple signers and the signature itself does not 93 reveal the means by which it was constructed. 95 Rather than considering multi-signatures or threshold signatures to 96 be inherently superior, it is more useful to regard both as two 97 points on a continuum of choices: 99 Multi-signatures Multiple digital signatures on the same document. 100 Multi-signatures are simple to create and provide the verifier 101 with more information but require the acceptance criteria to be 102 specified independently of the signature itself. This requires 103 that the application logic or PKI provide some means of describing 104 the criteria to be applied. 106 Multi-party key release A single signature created using a single 107 private key stored in an encrypted form whose use requires 108 participation of multiple key decryption shares. 110 Threshold signatures A single signature created using multiple 111 signature key shares. Signature creation may be subject to 112 complex criteria such as requiring an (n,t) quorum of signers but 113 these criteria are fixed at the time the signature is created 115 Aggregate Signatures A single signature created using multiple 116 signature key shares such that validation of the aggregate 117 signature serves to validate the participation of each of the 118 individual signers. 120 This document describes a scheme that creates threshold signatures 121 that are computationally indistinguishable from those produced 122 according to the algorithm specified in [RFC8032]. The scheme does 123 not support the creation of aggregate signatures. 125 Two versions of the algorithm are presented. Both versions allow a 126 creation of a signature to be divided between a set of n signers such 127 that a minimum of t signers are required to create a signature. The 128 first version of the algorithm (unanimous signature) requires that 129 every member of the set of signers participate in the signing process 130 (i.e. n=t). The second version (quorate signature) allows a 131 signature to be created by a subset of the authorized signers. 133 The unanimous signature scheme allows key shares to be generated by 134 either dividing a master key or using threshold key generation to 135 construct the master key from two or more key contributions as 136 described in [draft-hallambaker-threshold]. 138 The quorate signature scheme requires that the signature key shares 139 be derived from a master signature key using Shamir secret sharing. 140 The process of key share generation is thus fundamentally one of 141 dividing a master key. 143 If required, division of the signing key administration roles may be 144 achieved by using threshold key generation to construct the master 145 key and performing the key splitting process separately for each 146 contribution. 148 2. Definitions 150 This section presents the related specifications and standard, the 151 terms that are used as terms of art within the documents and the 152 terms used as requirements language. 154 2.1. Requirements Language 156 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 157 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 158 document are to be interpreted as described in [RFC2119]. 160 2.2. Defined Terms 162 See [draft-hallambaker-threshold]. 164 2.3. Related Specifications 166 This document extends the approach described in 167 [draft-hallambaker-threshold] to support threshold signatures. The 168 use of Lagrange polynomials to resolve Shamir Secret Shares is 169 currently described in the Uniform Data Fingerprint specification 170 [draft-hallambaker-mesh-udf]. It is expected that these three 171 documents will eventually form the basis for two CFRG proposals. 173 2.4. Implementation Status 175 The implementation status of the reference code base is described in 176 the companion document [draft-hallambaker-mesh-developer]. 178 3. Threshold Signature Construction 180 The threshold signatures created according to the algorithms 181 described in this document are compatible with but not identical to 182 the signatures created according to the scheme described in 183 [RFC8032]. In particular: 185 * The signature verification algorithm is unchanged. 187 * The unanimous threshold scheme produces values of R and S that are 188 deterministic but different from the values that would be obtained 189 by using the aggregate private key to sign the same document. 191 * The deterministic quorate threshold scheme produces values of R 192 and S that are deterministic for a given set of signers but will 193 change for a different set of signers or if the aggregate private 194 key was used to sign the same document. 196 * ?The non-deterministic quorate threshold scheme produces values of 197 R and S that will be different each time the document is signed. 199 Recall that a digital signature as specified by [RFC8032] consists of 200 a pair of values S, R calculated as follows: 202 R = r.B 204 S = r + k.s mod L 206 Where B is the base point of the elliptic curve. 208 r is an unique, unpredictable integer value such that 0 r L 210 k is the result of applying a message digest function determined 211 by the curve (Ed25519, Ed448) to a set of parameters known to the 212 verifier which include the values R, A and PH(M). 214 A is the public key of the signer, A = s.B 216 PH(M) is the prehash function of the message value. 218 s is the secret scalar value 220 L is the order of the elliptic curve group. 222 To verify the signature, the verifier calculates: 224 S.B = R + k.A 226 Therefore: 228 S.B = (r + k.s).B = r.B +k.(s.B) = R + k.A 230 The value r plays a critical role in the signature scheme as it 231 serves to prevent disclosure of the secret scalar. If the value r is 232 known, s can be calculated as s = (S-r).k^(-1) mod L. It is 233 therefore essential that the value r be unguessable. 235 Furthermore, if the same value of r is used to sign two different 236 documents, this results two signatures with the same value R and 237 different values of k and S. Thus 238 S_(1) = r + k_(1).s mod L 240 S_(2) = r + k2.s mod L 242 s = (S_(1) - S_(2))(k_(1) - k_(2))^(-1) mod L 244 The method of constructing r specified in [RFC8032] ensures that the 245 value r is unique and unguessable provided that the private key from 246 which the secret scalar value is derived is kept secret. 248 The use of a deterministic means of generating the value r permits 249 auditing of hardware and software implementations to determine if the 250 correct means of constructing r is used by importing a known private 251 key and verifying that the expected values of R are produced when a 252 set of documents is signed. 254 The threshold schemes described in this document have been designed 255 to preserve the ability to audit the means of constructing the values 256 of r for each individual key share even though the sum of these 257 values and hence the value R will vary according to the number of 258 signature shares used. 260 3.1. Threshold signature 262 A threshold signature R, S is constructed by summing a set of 263 signature contributions from two or more signers. Each signer _i_ 264 provides a contribution as follows: 266 A_(i) = s_(i).B 268 R_(i) = r_(i).B 270 S_(i) = r_(i) + k.s_(i) mod L 272 Where s_(i) and r_(i) are the secret scalar and unguessable value for 273 the individual signer. 275 The contributions of signers {1, 2, ... n} are then combined as 276 follows: 278 R = R_(1) + R_(2) + ... + R_(n) 280 S = S_(1) + S_(2) + ... + S_(n) 282 A = s.B 284 Where s = (s_(1) + s_(2) + ... + s_(n)) mod L 285 The threshold signature is verified in the same manner as before: 287 S.B = R + k.A 289 Substituting for S.B we get: 291 = (S_(1) + S_(2) + ... + S_(n)).B 293 = S_(1).B + S_(2).B + ... + S_(n).B 295 = (r_(1) + k.s_(1)).B + (r_(2) + k.s_(2)).B + ... + (r_(n) + 296 k.s_(n)).B 298 = (r_(1).B + k.s_(1).B) + (r_(2).B + k.s_(2).B) + ... + (r_(n).B + 299 k.s_(n).B) 301 = (R1 + k.A1) + (R1 + k.A1) + ... + (Rn + k.An) 303 Substituting for R + k.A we get: 305 = R_(1) + R_(2) + ... + R_(n) + k.(A_(1) + A_(2) + ... + A_(n)) 307 = R_(1) + R_(2) + ... + R_(n) + k.A_(1) + k.A_(2) + ... + k.A_(n) 309 = (R_(1) + k.A_(1)) + (R_(1) + k.A_(1)) + ... + (R_(n) + k.A_(n)) 311 As expected, the operation of threshold signature makes use of the 312 same approach as threshold key generation and threshold decryption as 313 described in [draft-hallambaker-threshold]. As with threshold 314 decryption it is not necessary for each key share holder to have a 315 public key corresponding to their key share. All that is required is 316 that the sum of the secret scalar values used in calculation of the 317 signature modulo the group order be the value of the aggregate secret 318 scalar corresponding to the aggregate secret key. 320 While verification of [RFC8032] signatures is unchanged, the use of 321 threshold signatures requires a different approach to signing. In 322 particular, the fact that the value k is bound to the value R means 323 that the participants in the threshold signature scheme must agree on 324 the value R before the value k can be calculated. Since k is 325 required to calculate the signature contributions S_(i) can be 326 calculated, it is thus necessary to calculate the values R_(i) and 327 S_(i) in separate phases. The process of using a threshold signature 328 to sign a document thus has the following stages orchestrated by a 329 coordinator as follows: 331 0. The coordinator determines the values F, C and PH(M) as specified 332 in [RFC8032] and transmits them to the signers {1, 2, ... n}. 334 1. Each signer generates a random value r_(i) such that 1 r_(i) L, 335 calculates the value R_(i) = r_(i).B and returns R to the 336 coordinator. 338 2. The coordinator calculates the value R = R_(1) + R_(2) + ... + 339 R_(n) and transmits R and A to the signers {1, 2, ... n}. 341 3. Each signer uses the suppled data to determine the value k and 342 hence S_(i) = r_(i) + k.s_(i) mod L and transmits it to the 343 coordinator. 345 4. The coordinator calculates the value S = S_(1) + S_(2) + ... + 346 S_(n) and verifies that the resulting signature R, S verifies 347 according to the mechanism specified in [RFC8032]. If the 348 signature is correct, the coordinator publishes it. Otherwise, 349 the coordinator MAY identify the signer(s) that provided 350 incorrect contributions by verifying the values R_(i) and S_(i) 351 for each. 353 For clarity, the coordinator role is presented here as being 354 implemented by a single party. 356 3.2. Ed2519 Signature 358 The process for creating an Ed25519 signature contribution is as 359 follows 361 0. Determine the value of the secret scalar value s_(i) according 362 to the means used to construct the secret shares. 364 1. Generate a random integer r_(i) such that 1 r_(i) L 366 2. Compute the point R_(i) = r_(i)B. For efficiency, do this by 367 first reducing r_(i) modulo L, the group order of B. Let the 368 string R_(i) be the encoding of this point. 370 3. Transmit the value R_(i) to the coordinator 372 4. Note that the construction of prefix is chosen so as to 373 guarantee that the use of a different message value M or secret 374 scalar value s_(i) will result in a different value of prefix 375 and thus ensure a different choice of the value r_(i). 377 5. At some later point, the coordinator MAY complete the signature 378 by returning the values F, C, A and R as specified in [RFC8032]. 379 The signer MAY then complete the signature contribution as 380 follows: 382 6. Compute SHA512(dom2(F, C) || R || A || PH(M)), and interpret the 383 64-octet digest as a little-endian integer k. 385 7. Compute S_(i) = (r_(i) + k * s_(i)) mod L. For efficiency, 386 again reduce k modulo L first. 388 8. Return the values R_(i), S_(i) to the coordinator. 390 9. The coordinator assembles the signature values R = S = S_(1) + 391 S_(2) + ... + S_(n) 393 10. The coordinator verifies that the signature R, S is valid. 395 3.3. Ed448 Signature 397 The process for creating an Ed448 signature contribution is as 398 follows 400 0. Determine the value of the secret scalar value s_(i) according to 401 the means used to construct the secret shares. 403 1. Generate a random integer r_(i) such that 1 r_(i) L 405 2. Compute the point R_(i) = r_(i)B. For efficiency, do this by 406 first reducing r_(i) modulo L, the group order of B. Let the 407 string R_(i) be the encoding of this point. 409 Transmit the value R_(i) to the coordinator 411 At some later point, the coordinator MAY complete the signature by 412 returning the values F, C, A and R as specified in [RFC8032]. The 413 signer MAY then complete the signature contribution as follows: 415 0. Compute SHAKE256(dom4(F, C) || R || A || PH(M), 114), and 416 interpret the 114-octet digest as a little-endian integer k. 418 1. Compute S_(i) = (r_(i) + k * s_(i)) mod L. For efficiency, again 419 reduce k modulo L first. 421 2. Return the values R_(i), S_(i) to the coordinator. 423 3. The coordinator assembles the signature values R = S = S_(1) + 424 S_(2) + ... + S_(n) 426 4. The coordinator verifies that the signature R, S is valid. 428 Note that the process of generating the signature contribution is 429 deterministic for a given secret scalar value but the signature 430 computed MAY be deterministic or non-deterministic according to the 431 desired signature properties. 433 3.4. Security Analysis 435 We consider a successful breach of the threshold signature scheme to 436 be any attack that allows the attacker to create a valid signature 437 for any message without the participation of the required threshold 438 of signers. 440 Potential breaches include: 442 * Disclosure of the signature key or signature key share. 444 * Modification of signature data relating to message M to allow 445 creation of a signature for message M'. 447 * Ability of one of the signers to choose the value of the aggregate 448 public key. 450 * Access control attacks inducing a signer to create a signature 451 contribution that was not properly authenticated or authorized. 453 We regard attacks on the access control channel to be out of scope 454 for the threshold signature algorithm, though they are certainly a 455 concern for any system in which a threshold signature algorithm is 456 employed. 458 We do not consider the ability of a signer to cause creation of an 459 invalid signature to represent a breach. 461 3.4.1. Replay Attack 463 The most serious concern in the implementation of any Schnorr type 464 signature scheme is the need to ensure that the value r_(i) is never 465 revealed to any other party and is never used to create signatures 466 for two different values of k.s_(i). 468 Ensuring this does not occur imposes significant design constraints 469 as creating a correct signature contribution requires that the signer 470 use the same value of r_(i) to construct its value or R_(i) and 471 S_(i). 473 For example, a HSM device may be required to perform multiple 474 signature operations simultaneously. Since the storage capabilities 475 of an HSM device are typically constrained, it is tempting to attempt 476 to avoid the need to track the value of r_(i) within the device 477 itself using an appropriately authenticated and encrypted opaque 478 state token. Such mechanisms provide the HSM with the value of r_(i) 479 but do not and cannot provide protection against a replay attack in 480 which the same state token is presented with a request to sign 481 different values of k. 483 3.4.2. Malicious Contribution Attack 485 In a malicious contribution attack, one or more parties present a 486 signature contribution that does not meet the criteria R_(i) = 487 r_(i).B and S_(i) = r_(i) + ks_(i). 489 Such an attack is not considered to be a breach as it merely causes 490 the signature process to fail. 492 3.4.3. Rogue Key Attack 494 A threshold signature scheme that allows the participants to 'bring 495 their own key' may be vulnerable to a rogue key attack in which a 496 signer is able to select the value of the aggregate public signature 497 key by selecting a malicious public signature key value. 499 The scheme described in this document is a threshold signature scheme 500 and does not support this feature. Consequently, this attack is not 501 relevant. It is described here for illustrative purposes only. 503 This particular attack only applies when the individual signers 504 create their own signature shares. It is not a concern when the 505 signature shares are created by splitting a master signature private 506 key. 508 Consider the case where the aggregate public key signature is 509 calculated from the sum of public signature key share values 510 presented by the signers: 512 A = A_(1) + A_(2) + ... + A_(n) 514 If the public key values are presented in turn, the last signer 515 presenting their key share can force the selection of any value of A 516 that they choose by selecting A_(n) = A_(m) - (A_(1) + A_(2) + ... + 517 A_(n-1)) 519 The attacker can thus gain control of the aggregate signature key by 520 choosing A_(m) = s_(m).B where s_(m) is a secret scalar known only to 521 the attacker. But does so at the cost of not knowing the value s_(n) 522 and so the signer cannot participate in the signature protocol. 524 This attack allows the attacker and the attacker alone to create 525 signatures which are validated under the aggregate signature key. 527 The attack is a consequence of the mistaken assumption that a 528 signature created under the signature key A_(1) + A_(2) + ... + A_(n) 529 provides evidence of the individual participation of the 530 corresponding key holders without separate validation of the 531 aggregate key. 533 Enabling the use of threshold signature techniques by ad-hoc groups 534 of signers using their existing signature keys as signature key 535 shares presents serious technical challenges that are outside the 536 scope of this specification. 538 4. Unanimous Signature 540 A unanimous threshold signature is a signature created by a set of 541 two or more signers that requires the participation of every member 542 of the set. The key shares used by the signers MAY be generated by 543 either: 545 * Each key share holder generating their own unique key share and 546 combining them. 548 * Generating a master signature key and dividing it. 550 Both approaches are described in [draft-hallambaker-threshold]. 552 4.1. Using threshold key generation 554 To create a threshold signature key share using threshold key 555 generation, each signer generates a pair {A_(i), s_(i)} and transmits 556 the public component to the coordinator. 558 The coordinator calculates the aggregate public key A = A_(1) + A_(2) 559 + ... + A_(n) 561 = s_(1).B + s_(2).B + ... + s_(n).B 563 = ((s_(1) + s_(2) + ... + s_(n)) mod L).B 565 = s.B 567 Where s = s_(1) + s_(2) + ... + s_(n)) mod L 569 The coordinator MUST require and verify proof of possession of the 570 private key component s_(i) to defeat rogue key attacks of the type 571 described in Section 3.4.3. 573 For example, the coordinator MAY require each signer to create a test 574 signature for their individual signature key share or to participate 575 in creating a test signature under the aggregate signature key. Such 576 a test signature MAY be a Certificate Signing Request as specified in 577 [RFC2314]. 579 Relying parties MUST NOT accept signatures purporting to be aggregate 580 signatures under ad-hoc collections of public keys as proof of the 581 involvement of the signers. 583 4.2. Using key splitting 585 To divide a keypair {A, p} into n parts, we begin by generating n-1 586 key pairs according to the method described in [RFC8032]. 588 To calculate the final secret scalar share s_(n) we begin by 589 calculating the secret scalar value s corresponding to the master 590 private key p and the key shares s_(1), s_(2), ..., s_(n-1). The 591 final secret scalar is given by: 593 s_(n) = s - s_(1), s_(2), ..., s_(n-1) 595 Since the final secret scalar is not derived from a private key by 596 means of a digest, it is not possible to use [RFC8032] format to 597 store keys. The format described in [draft-hallambaker-threshold] is 598 used instead. 600 5. Quorate Signature 602 Constructing the set of secret scalar key shares using the Shamir 603 secret sharing scheme allows a signature scheme in which the 604 threshold of signers t required to create a signature is smaller than 605 the number of key shares n. 607 5.1. Key Generation 609 The key generation process begins with the generation of a master 610 signature key {A, p}. The private key p is used to calculate the 611 secret scalar value s according to the procedure specified in 612 Section 4.1 above. 614 The secret scalar is then divided as follows. 616 First, we construct a polynomial of degree t in the modular field L, 617 where L is the order of the curve sub-group: 619 f(x) = a_(0) + a_(1).x + a_(2).x^(2) + ... a_(t).x^(t) mod L 621 where a_(0) = s 622 a_(1) ... a_(t) are randomly chosen integers in the range 1 a_(i) 623 L 625 The values of the key shares are the values _f_(x_(1)), _f_(x_(2)), 626 ... ,_f_(x_(n)). That is 628 p_(i) = _f_(x_(i)) 630 where p_(1) ... p_(n) are the private key shares 632 x_(1) ... x_(n) are distinct integers in the range 1 x_(i) L 634 The means of constructing distinct values x_(1) ... x_(n) is left to 635 the implementation. It is not necessary for these values to be 636 secret. 638 As with the final secret scalar value above, it is not possible to 639 use [RFC8032] format to store keys. The format described in 640 [draft-hallambaker-threshold] is used instead. 642 5.2. Calculating the secret scalar value 644 The value of the secret scalar value used to create a signature 645 depends on the specific choice of signature shares used to construct 646 it. Since the numbering of the key shares is arbitrary, we choose 647 the set of signers {1, 2, ... , t}. 649 Lagrange polynomials are used to compute a set of coeficients l_(1), 650 l_(2), ... l_(t) such that 652 s = a_(0) = l_(1)p_(1) + l_(2)p_(2) + ... + l_(t)p_(t) 654 The value of the secret scalars s_(1) + s_(2) + ... + s_(n) are thus 655 given by 657 s_(i) = l_(i)p_(i) 659 The coordinator identifies the signers to participate in the 660 signature event and uses the set of x coordinates corresponding to 661 their key shares to calculate the corresponding Lagrange coefficient 662 li for each as described in [draft-hallambaker-mesh-udf]. 664 [Note: The discussion of Shamir Secret Sharing should probably be 665 moved from its current location in [draft-hallambaker-mesh-udf] to 666 either this document or the base document 667 [draft-hallambaker-threshold]. Which document is better suited will 668 depend on whether it is decided to implement (n,k) threshold 669 signatures and/or key escrow of elliptic curve scalar secrets.] 671 6. Test Vectors 673 6.1. Unanimous Threshold Signature Ed25519 675 The signers are Alice and Bob. Each creates a key pair: 677 ED25519Alice's Key (ED25519) 678 UDF: ZAAA-GTSI-GXED-255X-XALI-CEXS-XKEY 679 Scalar: 56271244081186130980636545017945156580516101894352492 680 459594967614223399428880 681 Encoded Private 682 33 40 0E 22 D8 67 17 F4 8A 9F 6A 46 61 B4 0E AD 683 8C D0 DD C3 79 CD 85 BD 95 5C 90 B9 6C CB 8C 23 684 X: 11116793672970427161790264469280294507189044728140547954071022 685 7976454124042406369344932655633664630560242213431409139866940 686 284702002648469365756492647970 687 Y: 61655404171611396573021808119108664749574235125343680206454285 688 6299141386615046548323087409388548650272224487089895079970526 689 0143544115364878870129761259200 690 Encoded Public 691 E2 AB 8F 37 62 C8 7B F9 E9 BC 59 0C 2E 99 A5 58 692 0C C3 19 D5 CD DA 53 DF 3E C1 F0 C0 FE D3 55 5E 693 ED25519Bob's Key (ED25519) 694 UDF: ZAAA-GTSI-G2ED-255X-XBOB-XSXK-EY 695 Scalar: 54940772670153459146152925564198105262971485730889818 696 986727608573229799020168 697 Encoded Private 698 68 9A 68 92 8A 06 17 84 35 3C B7 08 F8 56 00 3F 699 BA 31 8C 42 B0 42 FE 2D 18 F2 7F AB CD 10 49 F1 700 X: 14271495069349838216379540196263140964032393512903842206168182 701 5518850827098876289800868735522232908519794251130907125878675 702 6343411484065706313568410880015 703 Y: 28094328948004112428189466223757440886388684291254605355859923 704 6240968229706795825282419594219442074647093851302547452470435 705 9438513477629978601366725015573 706 Encoded Public 707 32 E5 8D 5E 66 B2 F9 E9 14 79 08 71 96 3B 9A 75 708 A2 31 59 4B 8E ED 18 EF BD FF 11 D4 47 2A 8C F4 710 The Aggregate Signature Key A = A_(a) + A_(b) 711 Aggregate Key = Alice + Bob () 712 UDF: TBS 713 Scalar: 26569330913556569171916721364983482306308422345436973 714 56293312113171384684213 715 Encoded Private 716 B5 CE 0E B3 9C CF 18 99 CF 8D 4C BB AE 81 79 1F 717 CE 13 AA 3E 63 59 5B AC 8D 2C EB A4 55 C5 DF 05 718 X: 67872685043898469012456949773240814121645904736114813455820339 719 8688906486811443744733724675994181258029547346985079901494367 720 752381127781166234556148580090 721 Y: 36481740058369645484420180976004932062085375941522344052907594 722 0118552792158551197107484892204562290802810655253510302448455 723 4128548992118101415797909250954 724 Encoded Public 725 29 65 63 86 4F FB 10 8D BA 7A 0A 68 04 6D 00 DA 726 9B 1D C3 A4 AF BA 95 B4 5D 27 B4 35 00 2F DF 32 728 To sign the text "This is a test", Alice and Bob first generate their 729 values r which they multiply by the base point to obtain the value 730 R_(i): 732 Alice: 733 r_a = 63604859197442869293148706887422539627692219221403898700132668 734 2121229168067 735 R_a = System.Byte[] 737 Bob: 738 r_a = 90588289213224300609691011367428583037027596393781713986313426 739 4309321564224 740 R_a = System.Byte[] 742 The aggregate value R = R_(a) + R_(b) 744 R = 745 FB 4A B1 B4 53 C4 90 54 C4 F3 FD 00 87 AE EF 3D 746 33 CE 2B 5B F2 88 DB 13 FD F7 28 67 26 EE 07 1F 748 The value k is calculated 750 k = 4033579620745134235581641900982768938545463892767267607223155591 751 591374371726 753 Alice and Bob both calculate their signature scalar contribution: 755 Alice: 756 S_a = 66555407144639732988508254705363964829787697756754631094914457 757 8662199168944 759 Bob: 760 S_b = 14755481297036888929325321941188765612781723011853930571004511 761 25046339648114 763 The coordinator calculates the aggregate value S = S_(a) + S_(b) 765 S = 2141102201150086222817614741172516209576049278752939368049595703 766 708538817058 768 The coordinator checks to see that the signature verifies: 770 S.B = R + kA = 771 X: 20168784599297644264752251999842912626695351875278949808545814 772 238064903547119 773 Y: 17798208503807446200181400098695224792791795831502230059016274 774 558554804974562 776 6.2. Unanimous Threshold Signature Ed448 778 The signers are Alice and Bob. Each creates a key pair: 780 ED448Alice's Key (ED448) 781 UDF: ZAAA-ITSI-GXED-44XA-LICE-XSXK-EY 782 Scalar: 63495803583658817688110446314786076976347236361354035 783 5597788771064742993095132758589292255654895141583596922516472 784 738879360490167934280 785 Encoded Private 786 A0 53 4C 93 3C 34 00 76 AE 5D B5 4A C2 71 5F 43 787 E1 D6 63 2C 5C 56 53 C8 98 A0 8F 03 FF F5 22 96 788 91 45 8C 2B CF E3 FD 7E 2A 9E 0B D6 F4 CC 66 61 789 43 62 72 7B 34 B4 79 92 790 X: 24743197509267833262111449556527285120868167712209919570838426 791 3466168536901525943558973091346360088759980994772668117646359 792 614426660579 793 Y: 21342899120576770537664462049685258390853729788303428349051130 794 8752175233505795318243164692156369495328007220135137156078814 795 081547431302 796 Encoded Public 797 0A 3B F3 27 E7 E1 67 63 2C 59 E2 1C D1 84 C7 83 798 E8 1E D1 68 9F 32 A1 16 99 00 5C DA 29 B9 6C 08 799 E4 15 57 7E E5 63 C2 32 08 23 41 68 5F 49 1F FF 800 BC 4D CD 3A 4E A6 85 49 00 801 ED448Bob's Key (ED448) 802 UDF: ZAAA-ITSI-G2ED-44XB-OBXS-XKEY 803 Scalar: 72649803773199751564998543891898904839718409312910780 804 0262041941160989643727331987658132182181970054245587322070535 805 846720571414845714224 806 Encoded Private 807 BC 53 B4 74 3E A7 A7 FA 9F 05 9A BC 8C 22 26 15 808 A1 4E BB 10 0E B5 59 6B DE 9C 1B E9 F2 3C 65 42 809 E7 B4 47 18 60 AC 18 A6 D2 78 B8 BC CE F5 F4 28 810 B2 3A FF 08 61 EF 6B 7C 811 X: 58235851934808640621920816872959059172692411187640950432203039 812 8116748997750134460231406698091317008063030408798536634284207 813 667468558264 814 Y: 34390767697909283892495761259186538632120422458392131201372282 815 6056455656591826216381185634080685718154852726725624178995827 816 091591132128 817 Encoded Public 818 93 63 5A 45 2D 4C 94 32 45 23 CD E2 A8 46 E4 78 819 A0 80 59 DA 36 CB 6B 0C 06 64 6F BE 51 AB C0 BF 820 1E DB A8 3F 2B 3B 80 0F BF 00 E6 78 DD E0 83 E9 821 AC 20 02 55 87 07 39 38 00 823 The Aggregate Signature Key A = A_(a) + A_(b) 824 Aggregate Key = Alice + Bob () 825 UDF: TBS 826 Scalar: 89488306051273634069773238262841883041784075539841550 827 3672228636597106090916876462340541507950185640860121886233669 828 49466515613996100051 829 Encoded Private 830 D3 29 DD AB F6 0D 99 8B 75 65 B8 06 36 C9 3A 2C 831 D4 08 C3 9B 7C F9 77 8C 68 29 0E 3D 5D C7 3E 00 832 92 8B DC AE 26 FB 16 39 CD 25 1B 23 4A 5A 05 61 833 1D 5C C4 70 0A C9 84 1F 834 X: 17985659098670117617173315763082238685735647626871251468000984 835 2080317111091696183607307614171726960576308774975742249260532 836 199160570999 837 Y: 31506323224859159594386181995639405170623657273945727288760063 838 1624406694682617334725040181287905351066763414658543828623841 839 509161975864 840 Encoded Public 841 9B 3E DF 49 55 40 9F 7B EA 0B AA 40 B7 3D 15 82 842 60 9F 7C 40 CF 67 DE 56 56 0D 03 87 63 3B 15 F2 843 45 33 FE 48 BD 2D A0 A2 8B CC 74 DA 94 0F 39 00 844 AC 39 CB 0A 9F A4 EB B0 00 846 To sign the text "This is a test", Alice and Bob first generate their 847 values r which they multiply by the base point to obtain the value 848 R_(i): 850 Alice: 851 r_a = 73759418290054794861373572858566288781619358129342401750774507 852 86228048858000588481919454774928817062768941685761418007593280530 853 2999804 854 R_a = System.Byte[] 856 Bob: 857 r_a = 46237963278513215322396148050034865586946889704122042348536832 858 25811783723521941968309643248450810747601167927994249458319388189 859 6018677 860 R_a = System.Byte[] 862 The aggregate value R = R_(a) + R_(b) 864 R = 865 A0 FF BC 4A 92 40 39 FE A3 E2 98 19 8A CB 60 54 866 65 E1 EF C5 3E E2 AA 54 8D 27 78 CB F8 34 DC E2 867 9C DF A0 D7 F1 D2 7F EA 33 A2 A7 07 76 29 A1 7C 868 EB D4 97 F1 A3 CE 0B 61 80 870 The value k is calculated 871 k = 4253302316461679481082434282193340085469714728082631996749509171 872 36528863341161130189337827407821840447093029569242109238035123293 873 90659 875 Alice and Bob both calculate their signature scalar contribution: 877 Alice: 878 S_a = 98531765382438321188310203252700171214078910507928709174117939 879 03719918811956876581076180944672089155783210289818359855928311296 880 3570131 882 Bob: 883 S_b = 10826185029558642533243398893637670455024435365016467182849367 884 92853602994592020853268312315426021226313042112304897550405147626 885 03231952 887 The coordinator calculates the aggregate value S = S_(a) + S_(b) 889 S = 2508393460412302388341324021707574217591292398626386593223906852 890 74134836172312654213972856976306382258260204195816912950241197071 891 52304 893 The coordinator checks to see that the signature verifies: 895 S.B = R + kA = 896 X: 87229317542997013818252634997777965098763712747235444768375375 897 25263195569863 898 Y: 48426719549368988040047207185774675871089544448034802040243984 899 177418779288237 901 6.3. Quorate Threshold Signature Ed25519 903 The administrator creates the aggregate key pair 904 ED25519Aggregate Key (ED25519) 905 UDF: ZAAA-GTSI-GQED-255X-XAGG-REGA-TEXK-EY 906 Scalar: 39348647608109113656999806950437958090469802387424444 907 589375066079861075223816 908 Encoded Private 909 37 39 5E 7A 8B A5 A0 19 46 4B 58 22 EA 24 A5 71 910 45 2C 2A AC 7A 3E FB CA CE 3F D4 12 9A BA EB 70 911 X: 14198837758377867455716504277518729070915183249890461230792115 912 9904969716778427995951234766002164511738587575257530388758374 913 7824906047250057721855068523970 914 Y: 20211025649802071998810413948266748565975140520947927724517956 915 2067625505077751598018629551746824533726709810990193455662385 916 6152736116303441031851305458040 917 Encoded Public 918 6E 13 79 B4 39 DA 97 9C 5A 34 CE 79 CD 1B 50 DF 919 A0 76 AD 49 81 6D 52 59 A4 2C DB CE 44 FF 3E F5 921 Three key shares are required for Alice, Bob and Carol with a 922 threshold of two. The parameters of the Shamir Secret Sharing 923 polynomial are: 925 a0 = 3934864760810911365699980695043795809046980238742444458937506607 926 9861075223816 927 a1 = 6478235074936669232922546709062853526800747723284435893560379998 928 498854036401 930 The key share values for the participants are 932 xa = 1 933 ya = 2404849219052209606083234281242846172127851954429434846923740448 934 647203754283 936 xb = 2 937 yb = 1646078716656616625032594427262705458071483318333963134482169508 938 860603539695 940 xc = 3 941 yc = 8873082142610236439819545732825647440151146822384914220405985690 942 74003325107 944 Alice and Carol are selected to sign the message "This is another 945 test" 947 The Lagrange coefficients are: 949 la = 3618502788666131106986593281521497120428558179689953803000975469 950 142727125496 951 lc = 3618502788666131106986593281521497120428558179689953803000975469 952 142727125494 954 Alice and Carol select their values ra, rc 956 ra = 5467990291185231529722642292282910677180928186673090898286725351 957 703148584114 958 Ra = System.Byte[] 960 rc = 3842295179874978910349644562407562715869337917437976620141371939 961 137906271828 962 Rc = System.Byte[] 964 The aggregate value R = R_(a) + R_(c) 966 R = 967 B1 23 76 E0 38 C5 15 2A B4 0F AB E2 FA 0C AC 81 968 D0 34 28 B7 13 14 75 A2 29 08 3C C0 62 3B 97 2D 970 The value k is 972 k = 24387631527158770388984723649123275410144206977564237560989138844 973 76357243053 975 The values R and k (or the document to be signed) and the Lagrange 976 coefficients are passed to Alice and Carol who use them to calculate 977 their secret scalar values: 979 sa = 7225776617244445516111444703385766378620336111334106073386586142 980 113532756919; 981 sc = 3174848681535619284995615994880214748421000838570708091980676184 982 605725462941 984 The signature contributions can now be calulated: 986 Sa = 5258509372798138258048339062398668871787395474915394506826958407 987 016143211994 988 Sc = 2369087102951219635858054121785113036716245524183189984191118268 989 317926650670 991 The coordinator calculates the aggregate value S = S_(a) + S_(b) 993 S = 3905908984170956799332066211407876676465246397186768850161257370 994 48615611675 996 The coordinator checks to see that the signature verifies: 998 S.B = R + kA = 999 X: 44137199296357774791154193859950611817340233105447413062332736 1000 902705770844448 1001 Y: 29688538012678578878269116100526571773188243259702429043049505 1002 096610475369173 1004 6.4. Quorate Threshold Signature Ed448 1006 The administrator creates the aggregate key pair 1008 ED448Aggregate Key (ED448) 1009 UDF: ZAAA-ITSI-GQED-44XA-GGRE-GATE-XKEY 1010 Scalar: 50890460656419721531273587958284096015810982760541575 1011 4207268050539683337837216003977228732536078674802149039736292 1012 653681850024283019712 1013 Encoded Private 1014 78 22 7E 3B 89 95 80 5D 04 19 DC 27 F1 7F 9B E4 1015 86 2B 0B DD 55 64 EE 04 19 49 4D DE B9 04 3B 9E 1016 8B 7D DC EC EC 8F DD 1D E7 88 86 FD 11 FD 78 EF 1017 1A 8B 84 8F 77 00 73 65 1018 X: 44109173355278142669484438370724914685176368933547176239809629 1019 7503768465595321590690311221269514682222687386378631457535068 1020 446135118173 1021 Y: 53219402718535721212460981200104434180077825188675868294070079 1022 5084662920552823356888138706016038637934794839496624474125511 1023 419755284720 1024 Encoded Public 1025 43 61 20 A0 B1 DF AA BD 6B 55 00 97 A3 BE CB B8 1026 09 57 20 88 16 69 E4 B9 E1 7E 9C 13 C0 41 5B CB 1027 4D 3E E4 99 2E 2D 48 89 1C C0 FB 26 58 C2 DD 5C 1028 C1 DC 17 82 D7 A0 43 EE 80 1030 Three key shares are required for Alice, Bob and Carol with a 1031 threshold of two. The parameters of the Shamir Secret Sharing 1032 polynomial are: 1034 a0 = 0 1035 a1 = 3230310441090132544881502506497842088200690521964525360879407271 1036 94765745753141655224661941966620396823169163035586912417623145586 1037 91569 1039 The key share values for the participants are 1040 xa = 1 1041 ya = 3230310441090132544881502506497842088200690521964525360879407271 1042 94765745753141655224661941966620396823169163035586912417623145586 1043 91569 1045 xb = 2 1046 yb = 6460620882180265089763005012995684176401381043929050721758814543 1047 89531491506283310449323883933240793646338326071173824835246291173 1048 83138 1050 xc = 3 1051 yc = 9690931323270397634644507519493526264602071565893576082638221815 1052 84297237259424965673985825899861190469507489106760737252869436760 1053 74707 1055 Alice and Carol are selected to sign the message "This is another 1056 test" 1058 The Lagrange coefficients are: 1060 la = 9085484053695086131866547598600056679420517008591475753518627489 1061 75730019807697928580978776458461879816551468545458311523868779298 1062 24891 1063 lc = 9085484053695086131866547598600056679420517008591475753518627489 1064 75730019807697928580978776458461879816551468545458311523868779298 1065 24889 1067 Alice and Carol select their values ra, rc 1069 ra = 9916409373832855445680225409665819204694890272466243758088723611 1070 70412660541692764122871086733859409013013307204388508168153245726 1071 71888 1072 Ra = System.Byte[] 1074 rc = 1073609511703983208477950323599584281909008734279687416788909134 1075 22950735978683478421395579947183492087041733558644230420650276766 1076 461770 1077 Rc = System.Byte[] 1079 The aggregate value R = R_(a) + R_(c) 1081 R = 1082 30 A1 B3 17 69 AB 99 0E 57 5E 0B A5 2E 51 72 C0 1083 BA 31 35 39 51 7C 83 B8 22 01 9F 85 45 93 9B 54 1084 19 A2 FA FD 34 7A CA 88 7D 05 52 A6 21 5C E0 B7 1085 69 62 F4 94 6C 15 C3 11 80 1087 The value k is 1088 k = 10235373755332719753132453070965244233375545860969817073088585850 1089 34984308611997081872546544930901042673608404328479261067005777756 1090 07973 1092 The values R and k (or the document to be signed) and the Lagrange 1093 coefficients are passed to Alice and Carol who use them to calculate 1094 their secret scalar values: 1096 sa = 1393094971533028494918880135834681981172155279153826379483773839 1097 76787863843741041141797168940839247505130521309883868015030349767 1098 862243; 1099 sc = 4240018392059887314544293838853293547119481225644687712199516581 1100 83581401177985445743985863508531284581797723992077942897434060917 1101 87536 1103 The signature contributions can now be calulated: 1105 Sa = 1176422144911387757819650694682546452875900733977789124175969611 1106 96064995455877990887534924392638074098909532952322658866770310075 1107 667839 1108 Sc = 1261695317878032144403764439936251221873899581791569343175257655 1109 85463382113907822175563223482227224266776195506309879565242141085 1110 378620 1112 The coordinator calculates the aggregate value S = S_(a) + S_(b) 1114 S = 6210206520504026758501056148987863388656969140510633166475017698 1115 63823736082462273469023925831729224023754347495408761272386953013 1116 96680 1118 The coordinator checks to see that the signature verifies: 1120 S.B = R + kA = 1121 X: 41458922531347602467333936260245029252955857925674064823925020 1122 498684283758735 1123 Y: 46892836594134893138380416498249507660693894634845371281694628 1124 683354340901899 1126 7. Security Considerations 1128 TBS. 1130 8. IANA Considerations 1132 This document requires no IANA actions. 1134 9. Acknowledgements 1135 10. Normative References 1137 [draft-hallambaker-mesh-udf] 1138 Hallam-Baker, P., "Mathematical Mesh 3.0 Part II: Uniform 1139 Data Fingerprint.", Work in Progress, Internet-Draft, 1140 draft-hallambaker-mesh-udf-07, 18 October 2019, 1141 . 1144 [draft-hallambaker-threshold] 1145 "[Reference Not Found!]". 1147 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1148 Requirement Levels", BCP 14, RFC 2119, 1149 DOI 10.17487/RFC2119, March 1997, 1150 . 1152 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 1153 Signature Algorithm (EdDSA)", RFC 8032, 1154 DOI 10.17487/RFC8032, January 2017, 1155 . 1157 11. Informative References 1159 [draft-hallambaker-mesh-developer] 1160 Hallam-Baker, P., "Mathematical Mesh: Reference 1161 Implementation", Work in Progress, Internet-Draft, draft- 1162 hallambaker-mesh-developer-09, 23 October 2019, 1163 . 1166 [RFC2314] Kaliski, B., "PKCS #10: Certification Request Syntax 1167 Version 1.5", RFC 2314, DOI 10.17487/RFC2314, March 1998, 1168 .