Internet-Draft | Threshold Signatures in Elliptic Curves | November 2020 |
Hallam-Baker | Expires 6 May 2021 | [Page] |
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/Discussion of this draft should take place on the CFRG mailing list (cfrg@irtf.org), which is archived at .¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 6 May 2021.¶
Copyright (c) 2020 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.¶
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:¶
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.¶
A single signature created using a single private key stored in an encrypted form whose use requires participation of multiple key decryption shares.¶
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¶
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.¶
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.¶
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.¶
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).¶
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.¶
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.¶
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.¶
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].¶
The implementation status of the reference code base is described in the companion document [draft-hallambaker-mesh-developer].¶
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:¶
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¶
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 = (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.¶
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:¶
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.¶
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.¶
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.¶
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.¶
A threshold signature scheme that allows the participants to 'bring their own key' may be vulnerable to a rogue key attack in which a signer is able to select the value of the aggregate public signature key by selecting a malicious public signature key value.¶
The scheme described in this document is a threshold signature scheme and does not support this feature. Consequently, this attack is not relevant. It is described here for illustrative purposes only.¶
This particular attack only applies when the individual signers create their own signature shares. It is not a concern when the signature shares are created by splitting a master signature private key.¶
Consider the case where the aggregate public key signature is calculated from the sum of public signature key share values presented by the signers:¶
A = A_{1} + A_{2} + ... + A_{n}¶
If the public key values are presented in turn, the last signer presenting their key share can force the selection of any value of A that they choose by selecting A_{n} = A_{m} - (A_{1} + A_{2} + ... + A_{n-1})¶
The attacker can thus gain control of the aggregate signature key by choosing A_{m} = s_{m}.B where s_{m} is a secret scalar known only to the attacker. But does so at the cost of not knowing the value s_{n} and so the signer cannot participate in the signature protocol.¶
This attack allows the attacker and the attacker alone to create signatures which are validated under the aggregate signature key.¶
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.¶
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}:¶
The dealer then completes the signature by:¶
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}:¶
Transmit the value R_{i} to the dealer¶
The dealer then completes the signature by:¶
The signers are Alice and Bob's Threshold Signature Service 'Bob'. Each creates a key pair:¶
ED25519Alice's Key (ED25519) UDF: ZAAA-GTSI-GXED-255X-XALI-CEXS-XKEY Scalar: 312191303806394376947696888962276115420485359001 34467943432016761653342335248 Encoded Private 10 AE C0 C2 16 65 9B 4F 7C 9D DE 82 3E 49 7F D4 9B 14 BB F8 2D 9F 0C 11 24 D7 15 E3 43 79 57 20 X: -13697699435406080999251131063344049965140553452 752305353714819106646919347160064793506327635954342719144289 2305566686088586980395284289746495530409889930 Y: 278793875610616080844162800185864399625503938157 569374174700414845758479331294424147393776831767266487579098 7675375777043504113387553916769515911310193558 Encoded Public 45 16 53 7C 26 50 CF DA F1 A4 DF 4C 45 DC 3D 95 4E B6 8E EB A6 5A 27 D6 CD 5B 43 C5 F4 06 53 ED ED25519Bob's Key (ED25519) UDF: ZAAA-GTSI-G2ED-255X-XBOB-XSXK-EY Scalar: 567212843891509414800308620158891720685508995620 72140666211075925337851277632 Encoded Private E5 CD 34 01 FD 8C 0E 27 81 4B 11 DD 12 68 50 A1 4B 5A D5 E1 E1 41 D7 68 5F 51 ED B4 3A 84 58 5C X: -13809282472298084436735987888897423507149580966 952791761446670884044433963975178482398144657564565223270588 5322459642470946347570575475534141406285323257 Y: 263684226342871984706317411760423095947068088366 393546798602378437432707482089806653755881399592963068751759 9645362525866308283171284327931970404321458677 Encoded Public F1 5F C0 78 F8 32 49 2C D9 64 CC 2B CF 90 5C 4F 23 EA BB F8 38 99 C5 FE F3 AA 67 BE AB EC D2 5E¶
The composite Signature Key A = A_{a} + A_{b}¶
Aggregate Key = Alice + Bob () UDF: TBS Scalar: 109634784180323260712231215560085272031403914964 7717337619681427565742601012 Encoded Private 34 33 AB 10 9A 09 A9 61 65 8B 3A EC 58 21 FB 2D 0D 45 74 49 45 BA E2 CF A8 98 C2 94 C9 82 6C 02 X: -83837675294300852842901121613445594296352372347 711317409367737761568353629718805151940195325485285476438422 923698718220652243749390297055882388709313280 Y: 160553422944358144751060009820735322036903773802 361117046457476895165059738086663330972263850675453249990301 0398473811263196653225446124160025082144761534 Encoded Public 48 1A 27 66 06 AF 4E 3C 20 A4 02 CD 8A 13 46 99 02 B7 75 F8 AC D4 7E 89 68 FB 68 EB D8 EF 4A C7¶
To sign the text "This is a test", Alice first generates her value r and multiplies it by the base point to obtain the value R_{a}:¶
Alice: r_a: 304554767184319354570910632330847275245170925807 471005852065308719163006873 R_a = 4D D3 35 87 4D D2 A9 35 79 CF 33 11 4E 3C 4C 86 A3 46 83 F8 77 2B 69 B9 BE 8A D0 03 5B 07 1B 3D¶
Alice passes her value R_{A} to Bob along with the other parameters required to calculate i. Bob then calculates his value R_{A} and multiplies it by the base point to obtain the value R_{b}:¶
Bob: r_b: 211453017009495036941255861540216441186480571963 4308458833747992420728606380 R_b = 9E 92 BB 50 CD DA 6A 97 70 83 54 82 4A C5 A2 5E CF 0C 53 65 19 55 74 E0 66 F7 49 0B F1 9E 42 C1¶
Bob can now calculate the composite value R = R_{a} + R_{b} and thus the value k.¶
R = 6D 04 0A 15 D3 26 95 7E 60 4B 31 B9 40 03 34 24 C1 E2 94 CE 4C 2D 67 AC 23 F9 09 EB 01 35 27 BC k: 141815370378674010309754096097287620917810351837 8705827473796209228380712742¶
Bob calculates his signature scalar contribution and returns the value to Alice:¶
Bob: S_b: 536363782415883723339410938370364298390876250983 1717008575694722457748759583¶
Alice can now calculate her signature scalar contribution and thus the signature scalar S.¶
Alice: S_a: 268700124091647466934677864874812484315783329013 4699034602004495702143596514 S: 813633487743049688767701469408773586209479440586 508437175748279874438105108¶
Alice checks to see that the signature verifies:¶
S.B = R + kA = X: 303888032885010422619559054491601097433934565460 00461769461185182044799973523 Y: 242312166466765598632540958273647355363821360549 75658447998613064394185428840¶
The signers are Alice and Bob's Threshold Signature Service 'Bob'. Each creates a key pair:¶
ED448Alice's Key (ED448) UDF: ZAAA-ITSI-GXED-44XA-LICE-XSXK-EY Scalar: 672286477331130983513039743350616227864346753924 962787860729757222511999618443513569403793186398096717924945 854846544396984088344823264 Encoded Private 6F 85 B1 91 9A 37 06 A6 B2 15 79 AD 5B 69 16 6A 5A CD C8 17 D4 14 1F 68 DA 97 C5 B4 44 79 CE EA 3C 17 7B E1 29 44 70 DF 41 C8 98 38 1E 7C 9B 3B 03 63 6F 85 E8 39 31 91 X: 526046019655043632868470952286947529492283092344 122476077151423645243648974512182548405702873560533846673262 767064019365470830861106049 Y: 145374550785380850812934424757986866673485237047 938554544492694946608060986459495807055455048208713991919477 720250115717234689256856152 Encoded Public 59 55 F4 7A 66 08 91 35 F8 15 63 F4 90 91 7F 38 12 E3 49 22 51 F8 BC 4A 41 C9 44 59 5A 64 9B 40 0B C5 7E 53 48 0F 32 12 90 32 69 38 47 28 94 BB 99 D1 16 6F 2D D5 3D 4F 80 ED448Bob's Key (ED448) UDF: ZAAA-ITSI-G2ED-44XB-OBXS-XKEY Scalar: 455052626698262385397736547727159423941520792904 908612603542850909167215987713902322619933929404455741806848 064294945283113799683261212 Encoded Private CA 15 22 BD F4 0F 9E 0A EC A7 61 79 BE 9E E3 38 BF 93 D3 5B B3 E6 FC F0 A7 5B 7C F0 E7 B5 89 F6 2E F6 D1 0E 72 49 4D DF 34 5E 2F 7C 9E 42 1D 85 AB AB 30 BD 68 C6 3E 35 X: 752024108200272710832187535557164455078689734595 171189993383259892607253027500878543439908750525763880661232 171322059854852522782265 Y: 619329873102159676791326142073166790594683111409 729383584199833441028484525583699421181422168190856074786324 020492214873796495570056511 Encoded Public 76 2B FC F8 AC 96 79 DE 1C 72 07 65 DD 49 5B 28 C7 04 CB A8 A5 96 3D D9 9E 23 FA 05 83 15 33 95 85 82 F8 CF A3 7A 2F 24 F8 EB D6 AE 20 0A 25 D0 44 1A F9 C0 86 D7 87 B7 00¶
The composite Signature Key A = A_{a} + A_{b}¶
Aggregate Key = Alice + Bob () UDF: TBS Scalar: 370810175859830330867905792457688502754055057988 943100420373093608031918369199015948491953656482966798700316 64591515851455352870185802 Encoded Private 4A AB 7A BB 2D 95 72 75 B1 3A 1D 22 24 17 76 2D A1 D5 55 94 67 35 8C E7 A1 A0 ED 0C E7 88 FF 9F 6E 2F 70 80 89 F5 01 2A C0 AD 4C 4E 7B 90 68 6C F4 53 BA 32 9B 70 0F 0D X: 583249553407699999284154112964835446252412293188 857058051552519639906663406776316984154017062023869075790536 30514579317017660114474427 Y: 518040437562811181169413740718290938351269168888 257124107164689245721852001077758864406412789756149699111633 051823234569886260996269341 Encoded Public 34 70 8D 08 DE 63 0B A6 49 2A 33 D8 B7 15 A9 84 A4 87 F6 B6 C7 4B 1C AE 5A 1F 7C 4B 12 70 FB CF 5A A9 3C 20 31 BA 9A 53 A0 FE 2A 43 24 97 06 F8 DA 40 0D 88 E3 D9 DE 2E 00¶
To sign the text "This is a test", Alice first generates her value r and multiplies it by the base point to obtain the value R_{a}:¶
Alice: r_a: 177274411620382331885613075298112943809338383162 174753240420771790910425395072244220798681166866026098695507 899343208324484682831848544 R_a = EC 4E A5 8E BE 3E DC C4 AA DC 67 65 D9 0D B1 24 82 97 7E 57 83 4C BC CA D0 68 98 72 B8 1A F2 61 E2 CC 2C AF AE F3 A9 8A 16 DF F1 1E 91 EC E2 FC 3C 09 DD 25 AB 6E 7D 02 00¶
Alice passes her value R_{A} to Bob along with the other parameters required to calculate i. Bob then calculates his value R_{A} and multiplies it by the base point to obtain the value R_{b}:¶
Bob: r_b: 914384096261894497392108217856312041404007433725 737987383860198449871749775140845071471047786135423317371867 85115509488719418941845277 R_b = 7E 8C 1C B1 EA 5F 9E 58 F4 E1 4C AB 9D CF C9 4B 42 8E 01 F4 B4 27 AA 74 D8 66 E8 5B D5 8C 23 10 31 A7 99 FC 69 3D 4A 81 56 9B 31 07 A4 7C 3B 83 9D 79 6B 12 08 D0 2C CC 80¶
Bob can now calculate the composite value R = R_{a} + R_{b} and thus the value k.¶
R = AE 82 1A 7D A9 B6 35 7A 3E CF 58 95 9E 97 3A 45 62 77 E5 DB F6 B5 B7 5F 5A 27 A0 29 0A 4D D4 2C 9F 39 97 BB A3 55 DC C8 BF 02 C1 8F CE 8E 92 D9 97 38 19 6B 73 07 19 FE 00 k: 120812996308912938173796275547209139305812356493 218326541177300961108122972500434047109753132978603955927000 049579948492518627324723657¶
Bob calculates his signature scalar contribution and returns the value to Alice:¶
Bob: S_b: 131642872805495450312819108720996394951179966909 422047047106195752645599694599197550402234644818088495417690 338344590538474713569000455¶
Alice can now calculate her signature scalar contribution and thus the signature scalar S.¶
Alice: S_a: 135660088492295551401234992018778138767930165450 263985669170229118586124164862063605687569508563259045492355 878328728103423148386029682 S: 855932802238892790767231487677734001306997921878 565176459038750760857198979216754398940488616889715775997525 07581656337124106095380358¶
Alice checks to see that the signature verifies:¶
S.B = R + kA = X: 225696302738968030426017676274023389357161605713 77841610835599611770420843463 Y: 366869559370146495596698412318900310141515842791 80057095036770676314039224332¶
The administrator creates the composite key pair¶
ED25519Aggregate Key (ED25519) UDF: ZAAA-GTSI-GQED-255X-XAGG-REGA-TEXK-EY Scalar: 367238470592488326468789252109412889361910680229 03089760692844779165588879504 Encoded Private FE 48 94 1F EB 3D 28 E1 61 81 E2 1E E1 CF F2 1E 1E 70 91 30 DF 98 9F 1C 34 EB BB 74 C5 C8 07 EB X: 143576564277195758046684172284175869008525477709 640743490221115123376609940386394888392330104965579307772627 313244177612005636942740116142030215202393600 Y: 844838272625277895849027219595751726665225134917 547580682441821283235675507225396641352769322822815561632929 543097074319051436285787045255908364074589900 Encoded Public DF E8 0A 2B E9 6C 53 C0 AB 9B BC BC 39 95 9A 61 9C 33 2E 22 24 A7 F7 F2 21 06 AC 6D 01 5D 0B E2¶
Three key shares are required for Alice, Bob and Carol with a threshold of two. The parameters of the Shamir Secret Sharing polynomial are:¶
a0 = 367238470592488326468789252109412889361910680229030897606928 44779165588879504 a1 = 338318986010852412366041291642398977925879116179901190258252 3043521639876163¶
The key share values for the participants are¶
xa = 1 ya = 392200903269604570067340531215030751116427738780256363326561 3131259957500722 xb = 2 yb = 681933154723076103606316655313030495659521902216679298461852 36496143125896 xc = 3 yc = 345138317558083173402104458195529282882474335202067983242870 8280017783002059¶
Alice and Carol are selected to sign the message "This is another test"¶
The Lagrange coefficients are:¶
la = 361850278866613110698659328152149712042855817968995380300097 5469142727125496 lc = 361850278866613110698659328152149712042855817968995380300097 5469142727125494¶
Alice and Carol select their values ra, rc¶
ra = 183324669043432475889177343290874841197580255869543278119963 6861783584446189 Ra = 54 9B F7 DF F9 4E FA 95 DE D8 27 4E 0D AD A4 81 4B D7 1F CA 21 B4 B2 7D D6 06 4F 59 28 41 87 92 rc = 161475617387612449161820030097871350703159449773365674965881 1083650872383824 Rc = 95 25 84 AA B3 F7 39 14 10 67 E8 45 21 68 67 76 11 73 88 28 D6 50 71 0F D4 21 67 12 98 CC 80 C7¶
The composite value R = R_{a} + R_{c}¶
R = 22 B8 67 CA 63 65 00 7D AD 85 96 83 FD 86 CB 92 88 E7 E7 73 F9 3E 48 8D AE 7E 43 E3 2D AC 5F 7F¶
The value k is¶
k = 300461162806835024067835386157211645931753120888211250552921 1847964183554048¶
The values R and k (or the document to be signed) and the Lagrange coefficients are passed to Alice and Carol who use them to calculate their secret scalar values:¶
sa = 588301354904406855101010796822546126674641608170384544989841 9696889936251083 sc = 189281120087571523997607099054385070601618650367961388678662 1329133835624465¶
The signature contributions can now be calulated:¶
Sa = 128238145780800590303153436041482532412837879827391619588852 5270458485017264 Sc = 425392829290723185011341307483608802636424146029130066221513 8481933637068796¶
The dealer calculates the composite value S = S_{a} + S_{b}¶
S = 553630975071523775314494743525091335049262025856521685810366 3752392122086060¶
The dealer checks to see that the signature verifies:¶
S.B = R + kA = X: 386656916198500913898974718482142916932478347228 53747339220827400653000735042 X: 272627300420736046999889168909581852465293124122 69338237353604076047710443564¶
The administrator creates the composite key pair¶
ED448Aggregate Key (ED448) UDF: ZAAA-ITSI-GQED-44XA-GGRE-GATE-XKEY Scalar: 723088510822916843359337925516642493307623385482 113107480846498794254549074097051759295396782499503452909258 978468506553055366989547456 Encoded Private 59 DC 8A 5F 5E AF 8C FA 96 19 F8 EE 78 13 00 12 33 0E 12 80 2D 25 E6 EF E8 E2 56 B5 83 6A 0C CF DC 11 96 A5 A5 D1 39 AA 34 25 0B 52 ED 9F 38 92 5D 9F 7B BC B9 BC 86 45 X: 600163199260212879671026282440221570752543874569 276531213297382365938924845597497264583528185273760383031589 25167107013312482098672476 Y: 568007995844826855892481230051783440873263817862 016100095069663100696528804467952219402043387612562057320585 561865068046226655443122582 Encoded Public ED C3 90 99 38 0B 8F CD 60 29 24 04 6C DE 52 33 A2 07 3E 56 8D 27 B5 B9 21 60 CF E9 E7 9D D6 4A 11 47 20 E6 9D FE 75 C7 04 14 70 18 B4 52 10 83 D0 EC 98 BD F5 E6 E3 D5 80¶
Three key shares are required for Alice, Bob and Carol with a threshold of two. The parameters of the Shamir Secret Sharing polynomial are:¶
a0 = 723088510822916843359337925516642493307623385482113107480846 49879425454907409705175929539678249950345290925897846850 6553055366989547456 a1 = 253947292459661473537056525563228503335644586909535883819036 29593189848969312285942082195525418378983878506351793852 012228645407360825¶
The key share values for the participants are¶
xa = 1 ya = 216445157732761001637197701849608092875464834857486355812599 29206860382197250994836594571141148378583546590493895709 346188988958309165 xb = 2 yb = 470392450192422475174254227412836596211109421767022239631635 58800050231166563280778676766666566757567425096845689561 358417634365669990 xc = 3 yc = 724339742652083948711310752976065099546754008676558123450671 88393240080135875566720758962191985136551303603197483413 370646279773030815¶
Alice and Carol are selected to sign the message "This is another test"¶
The Lagrange coefficients are:¶
la = 908548405369508613186654759860005667942051700859147575351862 74897573001980769792858097877645846187981655146854545831 152386877929824891 lc = 908548405369508613186654759860005667942051700859147575351862 74897573001980769792858097877645846187981655146854545831 152386877929824889¶
Alice and Carol select their values ra, rc¶
ra = 597061760142011172791892795402895896258128262343360777519356 25449868368724094466154383697912358541824000038036669052 993742082445345445 Ra = 35 E5 61 55 78 E7 27 24 55 2D C9 76 4B 49 2B 46 16 E3 FA 97 2F 9A E6 47 1B 22 CD 2D 54 F5 1A 1C 7A A7 67 B0 CE 65 84 05 39 33 0E A6 33 5E 67 BD 58 CA ED 7E F3 EE DD 59 00 rc = 134782448747121628062621888359149856538463227176060814858572 40759552504564125328966600869858667833252205589918638910 3286110005426517374 Rc = 3C 7B 81 57 A9 C9 23 90 E2 1D 82 42 7B 0C D9 88 E7 E5 98 81 DB 52 76 E3 77 67 E8 34 DC D7 DC 81 20 B6 3A 6F EC E8 0C D9 0E BC C5 5A A0 E6 91 D5 D9 14 0B 60 C2 A4 D0 A8 80¶
The composite value R = R_{a} + R_{c}¶
R = 00 27 F8 F7 A7 39 F7 AE B6 8F E4 0F A8 4E 3A 71 45 87 6A 1E C4 C3 29 52 CC 8A C7 6C 36 47 4B A6 04 F8 55 03 7B 49 86 87 E4 91 AB 73 E0 AF 3F 12 AB 7F 09 2D 4E 06 4A 71 00¶
The value k is¶
k = 111997156629233344141251678175691985810414419806912701822160 03679477455027316936425566511876628316232490805931954430 9467825781335347270¶
The values R and k (or the document to be signed) and the Lagrange coefficients are passed to Alice and Carol who use them to calculate their secret scalar values:¶
sa = 123321614196865011564245131263441780725524895314537710907076 16870786357527664628511298973435756875585697503259538939 5171670361367288637 sc = 546378534043466638830999383371973118168674696520868513626526 80700952961912832009497718396549853619706003345255804124 467063738043309482¶
The signature contributions can now be calulated:¶
Sa = 458780069801903308724659679047126206540023727016859370284301 27448209487257982695731719827860225173821194895861101407 212569594681924953 Sc = 401983114222685811776093088236307108408769238787937252473320 58598217288865359359764076141664751937484813828720687591 206436379246811336¶
The dealer calculates the composite value S = S_{a} + S_{b}¶
S = 860763184024589120500752767283433314948792965804796622757621 86046426776123342055495795969524977111306008724581788998 419005973928736289¶
The dealer checks to see that the signature verifies:¶
S.B = R + kA = X: 565863868058207644748379075787643375969163605886 69329263413068616160478393570 X: 150478297775841135131577263700053908124463098444 5517859016637728894764938481¶
All the security considerations of [RFC7748], [RFC8032] and [draft-hallambaker-threshold] apply and are hereby incorporated by reference.¶
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.¶
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.¶
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.¶
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.¶
This document requires no IANA actions.¶
[TBS]¶