IP Library › Granted Patent US 12,425,233
Granted Patent B2
US 12,425,233 · App. 18/288,555 · Granted Sep 23, 2025

Nested threshold signatures

Inventor: Michaella Pettit (London, GB)
Assignee: nChain Licensing AG
H04L9/3255H04L9/085H04L9/0869
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,425,233
App. No.
18/288,555
Granted
Sep 23, 2025
Kind
B2
Abstract

A computer-implemented method of requiring at least one of a sub-group of a group of participants to contribute to a threshold-optimal signature scheme, wherein the valid signature comprises a first signature component and a second signature component, wherein each participant has a respective private key share of a shared private key, a respective ephemeral private key share of a shared ephemeral private key, and the first signature component, wherein the shared private key can only be generated with at least a first threshold number of respective private key shares.

Claims (33)

1. A computer-implemented method of requiring at least one of a sub-group of a group of participants to contribute to a threshold-optimal signature scheme, wherein a valid signature comprises a first signature component and a second signature component, wherein each participant has a respective private key share of a shared private key, a respective ephemeral private key share of a shared ephemeral private key, and the first signature component, wherein the shared private key can only be generated with at least a first threshold number of respective private key shares, and wherein the method comprises, by a first participant belonging to the sub-group:

obtaining at least a second threshold number of respective shares of a message-independent component (MIC) of the second signature component, wherein each respective share of the MIC is generated by a respective participant based on a respective ephemeral private key share, a respective private key share and the first signature component, wherein the MIC can only be generated with at least the second threshold number of respective shares of the MIC, wherein a first share of the MIC is generated by the first participant, and wherein the respective shares of the MIC are available only to one or more participants of the sub-group;

generating the MIC based on the obtained second threshold number of respective shares; and

a) making the MIC available to a coordinator for generating the second signature component based on the MIC and the second threshold number of respective shares of a message-dependent component (MDC) of the second signature component, each respective share of the MDC being generated based on a respective ephemeral private key share and a hash of a message to be signed by the valid signature; and/or

b) splitting the MIC into a plurality of secondary MIC shares, wherein a third threshold number of the secondary MIC shares are required to generate the MIC; and distributing one or more respective secondary MIC shares to respective participants of the group for the third threshold number of participants for generating the MIC and making the MIC available to a coordinator for generating the second signature component.

2. The method of claim 1 , comprising:

generating a first share of the MDC; and

making the first share of the MDC available to the coordinator for generating the second component of the signature.

3. The method of claim 1 , wherein the first participant comprises the coordinator, and wherein the method comprises generating the second signature component.

4. The method of claim 1 , wherein the coordinator is a different one of the participants or a third party.

5. The method of claim 1 , wherein each participant has a respective blinding key share of a blinding key, wherein each respective share of the MIC is generated based on the respective blinding key share, and wherein each respective share of the MDC is based on the respective blinding key share.

6. The method of claim 5 , wherein the signature is an elliptic curve digital signature algorithm (ECDSA) signature, and wherein each share of the MIC is generated as λ i =k i −1 a i r+β i , where k i is a respective ephemeral private key share, a i is a respective private key share, β i is a respective blinding key share, and r is the first signature component, and wherein each share of the MDC is generated as s i =k i −1 e−β i , where r is the hash of the message.

7. The method of claim 1 , wherein the sub-group comprises a plurality of participants, and wherein a) comprises making the first share of the MIC available to one, some or all of the other participants in the sub-group.

8. The method of claim 1 , wherein the sub-group comprises a plurality of participants, and wherein each participant in the sub-group receives each respective share of the MIC from the other participants in the group of participants.

9. The method of claim 1 , wherein the sub-group consists of the first participant.

10. The method of claim 1 , wherein the message comprises at least part of a blockchain transaction.

11. The method of claim 1 , wherein a size of the group is N≥2t+1 and a size of the sub-group is N−(t+1), wherein t is the order of a polynomial used to derive the respective private key share of each participant, wherein 2t+1 is the first threshold number and t+1 is the second threshold number.

12. The method of claim 1 , wherein each participant generates the respective private key share, and the respective ephemeral private key share using a joint verifiable random secret sharing scheme (JVRSS).

13. The method of claim 5 , wherein each participant generates the respective blinding key share using JVRSS.

14. The method of claim 1 , wherein the method comprises said splitting of the MIC into the plurality of secondary MIC shares, and wherein said splitting of the MIC is performed using Shamir's secret sharing scheme.

15. The method of claim 1 , wherein the signature is an elliptic curve digital signature algorithm (ECDSA) signature.

16. Computer equipment, comprising:

memory comprising one or more memory units; and

processing apparatus comprising one or more processing units, wherein the memory stores code arranged to run on the processing apparatus, the code being configured so as when on the processing apparatus to perform a method of requiring at least one of a sub-group of a group of participants to contribute to a threshold-optimal signature scheme, wherein a valid signature comprises a first signature component and a second signature component, wherein each participant has a respective private key share of a shared private key, a respective ephemeral private key share of a shared ephemeral private key, and the first signature component, wherein the shared private key can only be generated with at least a first threshold number of respective private key shares, and wherein the method comprises, by a first participant belonging to the sub-group:

obtaining at least a second threshold number of respective shares of a message- independent component (MIC) of the second signature component, wherein each respective share of the MIC is generated by a respective participant based on a respective ephemeral private key share, a respective private key share and the first signature component, wherein the MIC can only be generated with at least the second threshold number of respective shares of the MIC, wherein a first share of the MIC is generated by the first participant, and wherein the respective shares of the MIC are available only to one or more participants of the sub-group;

generating the MIC based on the obtained second threshold number of respective shares; and

a) making the MIC available to a coordinator for generating the second signature component based on the MIC and the second threshold number of respective shares of a message-dependent component (MDC) of the second signature component, each respective share of the MDC being generated based on a respective ephemeral private key share and a hash of a message to be signed by the valid signature; and/or

b) splitting the MIC into a plurality of secondary MIC shares, wherein a third threshold number of the secondary MIC shares are required to generate the MIC; and distributing one or more respective secondary MIC shares to respective participants of the group for the third threshold number of participants for generating the MIC and making the MIC available to a coordinator for generating the second signature component.

17. A non-transitory computer readable medium, comprising a computer program configured so as, when run on computer equipment, the computer equipment performs a method of requiring at least one of a sub-group of a group of participants to contribute to a threshold-optimal signature scheme, wherein a valid signature comprises a first signature component and a second signature component, wherein each participant has a respective private key share of a shared private key, a respective ephemeral private key share of a shared ephemeral private key, and the first signature component, wherein the shared private key can only be generated with at least a first threshold number of respective private key shares, and wherein the method comprises, by a first participant belonging to the sub-group:

obtaining at least a second threshold number of respective shares of a message-independent component (MIC) of the second signature component, wherein each respective share of the MIC is generated by a respective participant based on a respective ephemeral private key share, a respective private key share and the first signature component, wherein the MIC can only be generated with at least the second threshold number of respective shares of the MIC, wherein a first share of the MIC is generated by the first participant, and wherein the respective shares of the MIC are available only to one or more participants of the sub-group;

generating the MIC based on the obtained second threshold number of respective shares; and

a) making the MIC available to a coordinator for generating the second signature component based on the MIC and the second threshold number of respective shares of a message-dependent component (MDC) of the second signature component, each respective share of the MDC being generated based on a respective ephemeral private key share and a hash of a message to be signed by the valid signature; and/or

b) splitting the MIC into a plurality of secondary MIC shares, wherein a third threshold number of the secondary MIC shares are required to generate the MIC; and distributing one or more respective secondary MIC shares to respective participants of the group for the third threshold number of participants for generating the MIC and making the MIC available to a coordinator for generating the second signature component.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 1, 2023
From: PETTIT, MICHAELLA
To: NCHAIN LICENSING AG
Reel/Frame 065421/0080 →
Priority Claims (1)
GB 2105992 · Apr 27, 2021 · national
Continuity (1)
Related Publication 20240214218A1 · Jun 27, 2024
References Cited (108)
US 7246232B2 · Dutertre · 2007 [cited by applicant]
US 8144874B2 · McGough · 2012 [cited by applicant]
US 9813244B1 · Triandopoulos et al. · 2017 [cited by applicant]
US 9894151B2 · Dhuse et al. · 2018 [cited by applicant]
US 10211981B2 · Camenisch et al. · 2019 [cited by applicant]
US 10511436B1 · Machani · 2019 [cited by applicant]
US 10764043B2 · Traynor et al. · 2020 [cited by applicant]
US 10903991B1 · Craige et al. · 2021 [cited by applicant]
US 11323267B1 · Griffin et al. · 2022 [cited by applicant]
US 11563567B2 · Le Saint · 2023 [cited by applicant]
US 11973867B2 · Tysor et al. · 2024 [cited by applicant]
US 12309196B2 · Pettit · 2025 [cited by applicant]
US 20020116611A1 · Zhou et al. · 2002 [cited by applicant]
US 20030009694A1 · Wenocur et al. · 2003 [cited by applicant]
US 20030059041A1 · MacKenzie · 2003 [cited by examiner]
US 20100037055A1 · Fazio et al. · 2010 [cited by applicant]
US 20110138192A1 · Kocher et al. · 2011 [cited by applicant]
US 20140164769A1 · D'Souza · 2014 [cited by applicant]
US 20140325309A1 · Resch et al. · 2014 [cited by applicant]
US 20150100781A1 · Yann et al. · 2015 [cited by applicant]
US 20150288525A1 · Camenisch · 2015 [cited by applicant]
US 20170223008A1 · Camenisch · 2017 [cited by applicant]
US 20170250972A1 · Ronda · 2017 [cited by applicant]
US 20180060248A1 · Liu et al. · 2018 [cited by applicant]
US 20180074889A1 · Resch · 2018 [cited by examiner]
US 20180101697A1 · Rane et al. · 2018 [cited by applicant]
US 20180183601A1 · Campagna · 2018 [cited by applicant]
US 20180212772A1 · Leavy et al. · 2018 [cited by applicant]
US 20180307573A1 · Abraham et al. · 2018 [cited by applicant]
US 20180349867A1 · Trieflinger · 2018 [cited by applicant]
US 20190007205A1 · Corduan et al. · 2019 [cited by applicant]
US 20190280864A1 · Cheng et al. · 2019 [cited by applicant]
US 20190370792A1 · Lam · 2019 [cited by applicant]
US 20190372759A1 · Rix · 2019 [cited by applicant]
US 20200044863A1 · Yadlin et al. · 2020 [cited by applicant]
US 20200074450A1 · Fletcher et al. · 2020 [cited by applicant]
US 20200145231A1 · Trevethan · 2020 [cited by applicant]
US 20200153640A1 · Ranellucci et al. · 2020 [cited by applicant]
US 20200169391A1 · Kapp · 2020 [cited by examiner]
US 20200213099A1 · Wright · 2020 [cited by applicant]
US 20200213113A1 · Savanah et al. · 2020 [cited by applicant]
US 20200259638A1 · Carmignani · 2020 [cited by applicant]
US 20200259651A1 · Mohassel · 2020 [cited by examiner]
US 20200311678A1 · Fletcher et al. · 2020 [cited by applicant]
US 20200353167A1 · Vivek et al. · 2020 [cited by applicant]
US 20210049600A1 · Spector et al. · 2021 [cited by applicant]
US 20210089676A1 · Ford et al. · 2021 [cited by applicant]
US 20210359843A1 · Li · 2021 [cited by examiner]
US 20210377049A1 · Nix · 2021 [cited by examiner]
US 20220172180A1 · Komiyama · 2022 [cited by applicant]
US 20220182235A1 · Tysor et al. · 2022 [cited by applicant]
US 20220239509A1 · Jang et al. · 2022 [cited by applicant]
US 20220286276A1 · Li · 2022 [cited by examiner]
US 20220311623A1 · Tomlinson et al. · 2022 [cited by applicant]
US 20220321340A1 · Tsitrin et al. · 2022 [cited by applicant]
US 20230361993A1 · Camenisch · 2023 [cited by examiner]
JP 2007124032A · 2007 [cited by applicant]
JP 2008199278A · 2008 [cited by applicant]
JP 2013513312A · 2013 [cited by applicant]
JP 2015194959A · 2015 [cited by applicant]
JP 2018005089A · 2018 [cited by applicant]
WO 9937052A1 · 1999 [cited by applicant]
WO 2015160839A1 · 2015 [cited by applicant]
WO 2017145010A1 · 2017 [cited by applicant]
WO 2018189656A1 · 2018 [cited by applicant]
WO 2019034951A1 · 2019 [cited by applicant]
WO 2019034986A1 · 2019 [cited by applicant]
WO 2019158209A1 · 2019 [cited by applicant]
WO 2019193452A1 · 2019 [cited by applicant]
WO 2019246206A1 · 2019 [cited by applicant]
WO 2020084418A1 · 2020 [cited by applicant]
WO 2021213959A1 · 2021 [cited by applicant]
WO 2021254702A1 · 2021 [cited by applicant]
WO 2023072502A1 · 2023 [cited by applicant]
Combined Search and Examination Report for Application No. GB2009062.7, mailed on Mar. 12, 2021, 10 pages. [cited by applicant]
Combined Search and Examination Report under Sections 17 and 18(3) for Application No. GB2011686.9, mailed on Apr. 22, 2021, 10 pages. [cited by applicant]
Combined Search and Examination Report under Sections 17 and 18(3) for Application No. GB2017103.9 mailed on Jun. 28, 2021,13 pages. [cited by applicant]
Fornaro D., “Elliptic Curve Hierarchical Deterministic Private Key Sequences: Bitcoin Standards and BestPractices,” Master Thesis, Apr. 19, 2018, retrieved from the URL: https://www.politesi.polimi.it/bitstream/10589/14… [cited by applicant]
Gennaro R., et al., “Robust Threshold DSS Signatures,” International Conference on the Theory and Applications of Cryptographic Techniques, 2001, vol. 164, pp. 54-84. [cited by applicant]
Goldfeder S., et al., “Securing Bitcoin Wallets via Threshold Signatures,” 2014, retrieved from the URL: https://www.cs.princeton.edu/stevenag/bitcoin_threshold_signatures.pdf, sections “Threshold ECDSA Signature Genera… [cited by applicant]
International Search Report and Written Opinion for Application No. PCT/EP2021/062941, mailed on Aug. 3, 2021, 14 pages. [cited by applicant]
International Search Report and Written Opinion for Application No. PCT/EP2021/076686 mailed on Feb. 14, 2022, 17 pages. [cited by applicant]
International Search Report and Written Opinion issued in International Application No. PCT/EP2021/067673, mailed on Sep. 28, 2021, 13 pages. [cited by applicant]
Luzio A.D., et al., “Arcula: A Secure Hierarchical Deterministic Wallet for Multi-asset Blockchains,” Section 2, Dec. 10, 2019, 33 pages. [cited by applicant]
Pramanik S., et al., “VPSS: A Verifiable Proactive Secret Sharing Scheme in Distributed Systems,” IEEE Military Communications Conference, Milcom, Oct. 13, 2003, vol. 2, pp. 826-831, XP010698401, DOI: 10.1109/MILCOM.200… [cited by applicant]
Combined Search and Examination Report under Sections 17 and 18(3) for Application No. GB2105992.8 mailed on Jan. 17, 2022, 9 pages. [cited by applicant]
International Search Report and Written Opinion for Application No. PCT/EP2022/058085 mailed on Jul. 26, 2022, 14 pages. [cited by applicant]
Pettit, Michaella, “Shared Secrets and Threshold Signatures Reference Document”, May 1, 2020 (May 1, 2020), pp. 1-23, XP055813628, Retrieved from the Internet: URL: https://nakasendoproject.org/Threshold-Signatures-whit… [cited by applicant]
Damgard Ivan et al: “Fast Threshold ECDSA with Honest Majority”, Aug. 23, 2020 (Aug. 23, 2020), Computer Vision—ECCV 2020: 16th European Conference, Glasgow, UK, Aug. 23-28, 2020: Proceedings; Part of the Lecture Notes … [cited by applicant]
Cachin Christian, “Security and Fault-tolerance in Distributed Systems —Distributed Cryptography”, Dec. 31, 2012 (Dec. 31, 2012), XP055903112, Retrieved from the Internet: URL: https://cachin.com/cc/sft12/ distcrypto.pd… [cited by applicant]
Denis Kolegov et al: “Towards Threshold Key Exchange Protocols”, arxiv.org, Cornell University Library, 201 Olin Library Cornell University Ithaca, NY 14853, Dec. 27, 2020 (Dec. 27, 2020), XP081849900, section 2.2. [cited by applicant]
GB2101590.4 Combined Search and Examination Report dated Jul. 30, 2021,7 pages. [cited by applicant]
Joonsang Baek et al: “Simple and efficient threshold cryptosystem from the gap diffie-hell man group”, GLOBECOM '03. 2003-IEEE Global Telecommunications Conference. Conference Proceedings. San Francisco, CA, Dec. 1-5, 2… [cited by applicant]
PCT/EP2022/050116 International Search Report and Written Opinion dated Apr. 26, 2022, 14 pages. [cited by applicant]
Combined Search and Examination Report under Sections 17 and 18(3) for Application No. GB2111440.0 mailed on Jan. 25, 2022, 6 pages. [cited by applicant]
Combined Search and Examination Report under Sections 17 and 18(3) for Application No. GB2111441.8 mailed on Jan. 25, 2022, 6 pages. [cited by applicant]
Combined Search Report under Sections 17 for Application No. GB2111442.6 mailed on Jan. 25, 2022, 4 pages. [cited by applicant]
Dikshit P., et al., “Efficient Weighted Threshold ECDSA for Securing Bitcoin Wallet,” 2017 ISEA Asia Security and Privacy (ISEASP), IEEE, Jan. 29, 2017, pp. 1-9, DOI: 10.1109/ISEASP.2017.7976994. [cited by applicant]
Ewa Syta et al: “Keeping Authorities “Honest or Bust” with Decentralized Witness Cosigning”, 2016 IEEE Symposium on Security and Privacy (SP), May 1, 2016 (May 1, 2016), pp. 526-545. [cited by applicant]
Gennaro R., et al, “Fast Multiparty Threshold ECDSA with Fast Trustless Setup,” Proceedings of the 2018 ACM SIGSAC Conference on Computerand Communications Security, Oct. 2018, pp. 1179-1194. [cited by applicant]
Gennaro R., et al., “Robust Threshold DSS Signatures,” International Conference on the Theory and Applications of Cryptographic Techniques, 1996, EUROCRYPT '96 pp. 354-371. [cited by applicant]
International Search Report and Written Opinion for Application No. PCT/EP2022/069246 mailed on Nov. 3, 2022, 15 pages. [cited by applicant]
International Search Report and Written Opinion for International Application No. PCT/EP2022/076636, mailed Jan. 20, 2023, 12 pages. [cited by applicant]
Wuille P., “BIP 32: Hierarchical Deterministic Wallets,” Github Bitcoin BIPs, Feb. 2012, 6 pages, Retrieved from the Internet: URL: https://en.bitcoin.it/wiki/BIP_0032, Retrieved on Aug. 24, 2020. [cited by applicant]
Hideyuki F., et al., “Updating Method of Distributed Data in Secret Sharing System,” Research Report of Computer Security (CSEC), Japan, Information Processing Society of Japan, May 15, 2014, vol. 2014-CSEC-65, No. 1, p… [cited by applicant]
Shingu T., et al., “Updating Method of Verifiable Distributed Data in the Secret Sharing Scheme,” Japan, Information Processing Society of Japan, Nov. 28, 2014, vol. 2014-CSEC-67, No. 5, pp. 1-6, 9 pages. [cited by applicant]
Camenisch, Jan, et al. “Short threshold dynamic group signatures.” International conference on security and cryptography for networks. Cham: Springer International Publishing, 2020 (Year: 2020). [cited by applicant]
Boldyreva, Alexandra. “Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme.” International Workshop on Public Key Cryptography. Berlin, Heidelberg: Springer … [cited by applicant]