IP Library › Granted Patent US 12,445,277
Granted Patent B2
US 12,445,277 · App. 18/275,372 · Granted Oct 14, 2025

Threshold key exchange

Inventor: Michaella Pettit (London, GB)
Assignee: nChain Licensing AG
H04L9/0861H04L9/0825H04L9/085
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,445,277
App. No.
18/275,372
Granted
Oct 14, 2025
Kind
B2
Abstract

A computer-implemented method of generating a shared cryptographic key based on at least one shared secret, wherein each participant belonging to a first group has a respective share of a first secret, the first secret having a first threshold and a corresponding first public key, wherein a second coordinator has a second public key corresponding to a second secret, wherein the second coordinator is configured to generate the same shared cryptographic key.

Claims (34)

1. A computer-implemented method of generating a shared cryptographic key based on at least one shared secret, wherein each participant belonging to a first group has a respective share of a first secret, the first secret having a first threshold number and a corresponding first public key, wherein a second coordinator has a second public key corresponding to a second secret, and wherein the method is performed by a first coordinator of the first group and comprises:

obtaining, from at least the first threshold number of participants of the first group, respective shares of the shared cryptographic key, where each respective share of the shared cryptographic key is based on i) a respective zeroth order coefficient of a respective private polynomial used to calculate the respective share of the first secret, and ii) the second public key; and

generating the shared cryptographic key based on the obtained respective shares of the cryptographic key, wherein the second coordinator is configured to generate the same shared cryptographic key.

2. The method of claim 1 , wherein the coordinator is one of said participants belonging to the first group.

3. The method of claim 1 , comprising:

obtaining the second public key; and

transmitting the second public key to each participant of the first group.

4. The method of claim 1 , comprising transmitting the first public key to second coordinator.

5. The method of claim 4 , comprising:

obtaining, from at least the first threshold number of participants of the first group, respective shares of the first public key, wherein each respective share of the first public key is based on the respective share of the first secret and a public key generator.

6. The method of claim 3 , wherein said obtaining of the second public key comprises receiving the second public key from the second coordinator.

7. The method of claim 1 , wherein said respective share of the shared cryptographic key is generated based on the respective zeroth order coefficient of a respective private polynomial used to calculate the respective share of the first secret, wherein said obtaining of the respective shares of the shared cryptographic key comprises obtaining a respective share of the shared cryptographic key from each of the first group of participants, and wherein said generating of the shared cryptographic key comprises performing point addition of the obtained respective shares of the shared cryptographic key.

8. The method of claim 1 , comprising encrypting a first message with the shared cryptographic key.

9. The method of claim 8 , comprising transmitting the encrypted first message to the second coordinator and/or to a different party.

10. The method of claim 8 , comprising:

generating a blockchain transaction, wherein the blockchain transaction comprises the encrypted message; and

making the blockchain transaction available to one or more nodes of a blockchain network.

11. The method of claim 1 , wherein the shared cryptographic key is a symmetric key, wherein a second message has been encrypted with the shared cryptographic key, and wherein the method comprises decrypting the second message using the shared cryptographic key.

12. The method of claim 1 , comprising:

obtaining a private key corresponding to the shared cryptographic key; and

generating a digital signature using the corresponding private key, and/or using the corresponding private key to decrypt a third message that has been encrypted with the shared cryptographic key.

13. The method of claim 12 , wherein a first blockchain transaction comprises an output locked to the shared cryptographic key, and wherein the method comprises generating a second blockchain transaction having an input that references the output of the first blockchain transaction and comprises the digital signature for unlocking said output.

14. The method of claim 1 , comprising generating one or more additional cryptographic keys based on the shared cryptographic key.

15. The method of claim 14 , wherein said generating of the one or more additional cryptographic keys comprises applying a hash function to the shared cryptographic key.

16. The method of claim 1 , wherein the second secret is a shared secret, wherein a second group comprises a plurality of participants, and wherein each participant of the second group has a respective share of a second secret, the second secret having a second threshold number.

17. The method of claim 16 , wherein each participant of the second group has a respective zeroth order coefficient of a respective private polynomial used to calculate the respective share of the second secret.

18. 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 run on the processing apparatus, the processing apparatus performs a method of generating a shared cryptographic key based on at least one shared secret, wherein each participant belonging to a first group has a respective share of a first secret, the first secret having a first threshold number and a corresponding first public key, wherein a second coordinator has a second public key corresponding to a second secret, and wherein the method is performed by a first coordinator of the first group and comprises:

obtaining, from at least the first threshold number of participants of the first group, respective shares of the shared cryptographic key, where each respective share of the shared cryptographic key is based on i) a respective zeroth order coefficient of a respective private polynomial used to calculate the respective share of the first secret, and ii) the second public key; and

generating the shared cryptographic key based on the obtained respective shares of the cryptographic key, wherein the second coordinator is configured to generate the same shared cryptographic key.

19. A computer program embodied on non-transitory computer-readable storage media and configured so as, when run on computer equipment, the computer equipment performs a method of generating a shared cryptographic key based on at least one shared secret, wherein each participant belonging to a first group has a respective share of a first secret, the first secret having a first threshold number and a corresponding first public key, wherein a second coordinator has a second public key corresponding to a second secret, and wherein the method is performed by a first coordinator of the first group and comprises:

obtaining, from at least the first threshold number of participants of the first group, respective shares of the shared cryptographic key, where each respective share of the shared cryptographic key is based on i) a respective zeroth order coefficient of a respective private polynomial used to calculate the respective share of the first secret, and ii) the second public key; and

generating the shared cryptographic key based on the obtained respective shares of the cryptographic key, wherein the second coordinator is configured to generate the same shared cryptographic key.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 1, 2023
From: PETTIT, MICHAELLA
To: NCHAIN LICENSING AG
Reel/Frame 064456/0506 →
Priority Claims (1)
GB 2101590 · Feb 5, 2021 · national
Continuity (1)
Related Publication 20240097894A1 · Mar 21, 2024
References Cited (107)
US 7246232B2 · Dutertre · 2007 [cited by examiner]
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 · 2022 [cited by examiner]
US 11563567B2 · Le Saint · 2023 [cited by examiner]
US 11973867B2 · Tysor et al. · 2024 [cited by applicant]
US 20020116611A1 · Zhou et al. · 2002 [cited by applicant]
US 20030009694A1 · Wenocur et al. · 2003 [cited by applicant]
US 20030059041A1 · Mackenzie et al. · 2003 [cited by applicant]
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 examiner]
US 20140325309A1 · Resch · 2014 [cited by applicant]
US 20150100781A1 · Yann et al. · 2015 [cited by applicant]
US 20150288525A1 · Camenisch et al. · 2015 [cited by applicant]
US 20170223008A1 · Camenisch et al. · 2017 [cited by applicant]
US 20170250972A1 · Ronda et al. · 2017 [cited by applicant]
US 20180060248A1 · Liu · 2018 [cited by examiner]
US 20180074889A1 · Resch et al. · 2018 [cited by applicant]
US 20180101697A1 · Rane · 2018 [cited by examiner]
US 20180183601A1 · Campgana · 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 examiner]
US 20190007205A1 · Corduan · 2019 [cited by examiner]
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 · 2020 [cited by examiner]
US 20200074450A1 · Fletcher et al. · 2020 [cited by applicant]
US 20200145231A1 · Trevethan · 2020 [cited by applicant]
US 20200153640A1 · Ranellucci · 2020 [cited by applicant]
US 20200169391A1 · Kapp et al. · 2020 [cited by applicant]
US 20200213099A1 · Wright · 2020 [cited by applicant]
US 20200213113A1 · Savanah et al. · 2020 [cited by applicant]
US 20200259638A1 · Carmignani et al. · 2020 [cited by applicant]
US 20200259651A1 · Mohassel et al. · 2020 [cited by applicant]
US 20200311678A1 · Fletcher et al. · 2020 [cited by applicant]
US 20200353167A1 · Vivek et al. · 2020 [cited by applicant]
US 20210049600A1 · Spector · 2021 [cited by applicant]
US 20210089676A1 · Ford et al. · 2021 [cited by applicant]
US 20210359843A1 · Li et al. · 2021 [cited by applicant]
US 20210377049A1 · Nix · 2021 [cited by applicant]
US 20220172180A1 · Komiyama · 2022 [cited by examiner]
US 20220182235A1 · Tysor et al. · 2022 [cited by applicant]
US 20220239509A1 · Jang et al. · 2022 [cited by applicant]
US 20220286276A1 · Li et al. · 2022 [cited by applicant]
US 20220311623A1 · Tomlinson · 2022 [cited by applicant]
US 20220321340A1 · Tsitrin · 2022 [cited by applicant]
US 20230361993A1 · Camenisch et al. · 2023 [cited by applicant]
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 2015160839 · 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 2019158209 · 2019 [cited by applicant]
WO 2019193452A1 · 2019 [cited by applicant]
WO 2019246206 · 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 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]
PCT/EP2022/050116 International Search Report and Written Opinion dated Apr. 26, 2022, 14 pages. [cited by applicant]
Joonsang Baek et al: “Simple and efficient threshold cryptosystem from the gap diffie-hellman group”, GLOBECOM '03. 2003-IEEE Global Telecommunications Conference. Conference Proceedings. San Francisco, CA, Dec. 1-5, 20… [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]
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.pdf,… [cited by applicant]
GB2101590.4 Combined Search and Examination Report dated Jul. 30, 2021, 7 pages. [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]
Damgard I., et al., “Fast Threshold ECDSA with Honest Majority”, Aug. 23, 2020, Computer Vision—ECCV2020: 16th European Conference, Proceedings; Part of the Lecture Notes in Computer Science, 35 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 M. “Shared Secrets and Threshold Signatures,” May 1, 2020, [retrieved on Jun. 14, 2021], pp. 1-23, Retrieved from the Internet: URL: https://nakasendoproject.org/Threshold-Signatures-whitepaper-nchain.pdf, sectio… [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]
Boldyreva A., et al., “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]
Camenisch J., et al., “Short Threshold Dynamic Group Signatures,” International conference on security and cryptography for networks Cham: Springer International Publishing, 2020, pp. 401-423. [cited by applicant]