US10903991B1 — Systems and methods for generating signatures (Part 1 of 2)
Document text
Research, not advice. Part of the Bitcoin research archive (October 2026). Claims labelled unverified, contested or fringe are reported, not endorsed; statuses of bills and rules are as of the date checked. Government, court and patent records are public domain; the research notes are CC BY 4.0.
US010903991B1
( 12 ) United States Patent ( 10) Patent No .: US 10,903,991 B1
Craige et al . (45) Date of Patent : Jan. 26 , 2021
( 54 ) SYSTEMS AND METHODS FOR ( 56 ) References Cited
GENERATING SIGNATURES
U.S. PATENT DOCUMENTS
( 71 ) Applicant: Coinbase , Inc. , San Francisco, CA (US ) 5,884,274 A 3/1999 Walker et al .
6,125,186 A 9/2000 Saito et al .
( 72 ) Inventors: Jake Craige , San Francisco, CA (US ); 6,952,683 B1 10/2005 Gerhard
Jesse Posner , San Francisco, CA (US ) ; 6,959,394 B1 10/2005 Brickell et al .
Adam Everspaugh, San Francisco, CA 7,644,037 B1 1/2010 Ostrovsky
(US ) 7,689,500 B2 3/2010 Cottrell
7,689,550 B2 3/2010 Lee et al .
7,970,823 B2 6/2011 Moeller et al .
( 73 ) Assignee : Coinbase , Inc. , San Francisco, CA (US ) 8,055,575 B2 11/2011 Grody et al .
8,111,648 B2 2/2012 Gandham
( * ) Notice : Subject to any disclaimer, the term of this 8,117,648 B2 2/2012 Slaton et al .
patent is extended or adjusted under 35 8,606,703 B1 12/2013 Dorsey et al .
9/2014 Gilboy
U.S.C. 154 ( b ) by 0 days. 8,839,386 B2
8,855,318 B1 10/2014 Patnala et al .
9,071,429 B1 6/2015 Roth et al .
( 21 ) Appl. No .: 16 /983,216 9,135,787 B1 9/2015 Russell et al .
9,224,262 B2 12/2015 Fine et al .
(22 ) Filed : Aug. 3 , 2020 (Continued )
Related U.S. Application Data FOREIGN PATENT DOCUMENTS
( 60 ) Provisional application No. 62/ 946,912 , filed on Dec. EP 2634738 A1 9/2013
11 , 2019 , provisional application No. 62/ 881,711 , JP 2007109002 A 4/2007
filed on Aug. 1 , 2019 , provisional application No. WO 2014190323 A1 11/2014
62/ 881,729 , filed on Aug. 1 , 2019 .
OTHER PUBLICATIONS
( 51 ) Int. CI.
H04L 29/06 ( 2006.01 ) “ BlockchainCreate ” , http://blockchain.info:80/wallet/faq, dated Jan.
H04L 9/08 (2006.01 ) 9 , 2012 , (5 pages) .
H04L 9/32 ( 2006.01 ) (Continued )
( 52 ) U.S. CI .
CPC H04L 9/085 ( 2013.01 ) ; H04L 9/0825 Primary Examiner — Harunur Rashid
( 2013.01 ) ; H04L 9/0861 ( 2013.01 ) ; H04L ( 74 ) Attorney, Agent, or Firm Jeffrey Schox ; Diana Lin
9/3252 ( 2013.01 ) ; H04L 9/3255 ( 2013.01 ) ;
H04L 2209/46 ( 2013.01 ) ( 57 ) ABSTRACT
( 58 ) Field of Classification Search System and method for digitally signing messages using
CPC HO4L 9/085 ; HO4L 9/0825 ; H04L 9/0861 ; multi-party computation .
HO4L 9/3252 ; HO4L 9/3255
See application file for complete search history. 18 Claims , 11 Drawing Sheets
Generate a message signing
private key S2110
Generate signing secrets $ 220
Process a signing request $ 230 Receive a signing request for a
message S231
Accessing stored signing secrets
S232
Providing the respective signing Receiving the message and
secret to each of a set of signing secrets for the participant
participant systems S233 +
Decrypting the signing secret
S310
Receiving additional signing data Accessing additional signing data
shares generated by other
participants S410
( e.g., nonce shares) generated by Generating additional signing data
other participants S234
$ 330
Decrypting the participant's
signing secret S420 Generating a signature based on Splitting the additional signing
the additional signing data $ 235 data into shares S340
Receiving the participant's
additional signing data shares Encrypting each additional signing
S440 data share to a different
Providing the generated signature participant S350
Decrypting the participant's S236
additional signing data shares
S450
1
Aggregating the decrypted
additional signing data shares
3460
Generating a partial signature
based on the aggregated
additional signing data shares and
decrypted signing secret S470
US 10,903,991 B1
Page 2
( 56 ) References Cited 2016/0034896 A1
2016/0085955 A1
2/2016 O'Brien et al .
3/2016 Lerner
U.S. PATENT DOCUMENTS 2016/0086418 Al 3/2016 Smolen et al .
2016/0171570 A1 6/2016 Dogin et al .
9,495,668 B1 11/2016 Juels 2016/0203572 Al
2016/0261411 A1
7/2016 McConaghy et al.
9/2016 Yau et al .
9,892,460 B1 2/2018 Winklevoss et al .
10,068,228 B1 9/2018 Winklevoss et al . 2016/0277398 A1 9/2016 Gregg et al .
10,180,912 B1 1/2019 Franklin et al . 2016/0321654 Al 11/2016 Lesavich et al .
10,256,983 B1 4/2019 Bauer et al . 2016/0380767 Al 12/2016 Hayashi et al .
10,469,309 B1 11/2019 Gupta et al . 2017/0063531 A1 3/2017 Sullivan
10,586,057 B2
3/2020 Keselman et al. 2017/0083718 Al 3/2017 Peddada et al .
10,733,291 B1 * 8/2020 McLeod H04L 9/14 2017/0161439 A1 6/2017 Raduchel et al .
2001/0034605 A1 10/2001 Hoffman 2018/0075453 A1 3/2018 Durvasula et al .
2001/0050990 A1 12/2001 Sudia 2018/0191503 A1 7/2018 Alwar et al .
2002/0023053 Al 2/2002 Szoc et al . 2018/0248704 A1 8/2018 Coode et al .
2002/0116611 A1 8/2002 Zhou et al . 2018/0367316 Al 12/2018 Cheng et al .
2003/0048906 A1 3/2003 Vora et al . 2019/0236245 A1 8/2019 Desarzens et al .
2005/0138374 Al 6/2005 Zheng et al . 2019/0288840 A1 9/2019 Gallancy et al .
2006/0168663 Al 7/2006 Viljoen et al . 2020/0036707 A1 * 1/2020 Callahan HO4L 9/3231
2007/0223706 A1 * 9/2007 Gantman H04L 9/085 2020/0084027 A1 * 3/2020 Duchon H04L 9/0825
380/286
2008/0091586 Al 4/2008 Cottrell OTHER PUBLICATIONS
2008/0263363 A1 10/2008 Jueneman et al .
2009/0037405 Al 2/2009 Lee et al . “ How to sell Lindens ” dated Mar. 6 , 2013 (Year: 2013 ) .
2009/0144810 Al 6/2009 Gilboy “ Send bitcoins to an unknown recipient ” , Feb. 13 , 2011 , down
2009/0205036 A1 8/2009 Slaton et al .
2009/0254750 A1 10/2009 Bono et al . loaded from https://bitcointalk.org/index.php?topic=3427.0 , ( Year:
2010/0054458 Al 3/2010 Schneider 2011 ) .
2010/0175061 Al 7/2010 Maeda et al . " Send Bitcoins to Email Addresses ! ” , Jan. 9 , 2012 , downloaded
2010/0235588 Al 9/2010 Maeda et al . from https://web.archive.org/web/20120109084110/http://www .
2011/0071958 Al 3/2011 Grody et al . bitcoinmail.com/, merged and attached as PDF file, ( Year: 2012 ) .
2011/0087582 A1 4/2011 Pak et al .
2011/0106675 A1 5/2011 Perlman “ Transaction Fees (“ Transaction fees and negative balances ””” ,
2011/0202755 A1 8/2011 Orsini et al . downloaded from https://bitcointalk.org/index.php?topic=6856.0 dated
2011/0251941 A1 10/2011 Dunwoody Apr. 30 -May 1 , 2011 , ( Year:2011 ), ( 3 pages ) .
2012/0136782 A1 5/2012 Norman et al . “ Wholesale Payment Systems : Interbank Payment and Messaging
2012/0150750 A1 6/2012 Law et al . System , Fedwire and Clearing House Interbank Payment Systems
2012/0239556 A1 9/2012 Magruder et al . ( CHIPS ) ”, http://www.ffiec.gov/ffiecinfobase/booklets/Wholesale/
2013/0010966 A1 1/2013 Li et al .
02.html, Dec. 16 , 2005 , ( 3 pages ) .
2013/0065670 A1 3/2013 Michaelson et al .
2013/0166455 Al 6/2013 Feigelson “ You Can Now Send Bitcoins over Email with Tip Bot ” , Feb. 26 ,
2013/0191632 A1 7/2013 Spector et al . 2014 , downloaded from https://www.coindesk.com/can-now-send
2013/0246261 A1 9/2013 Purves et al . bitcoins - email -tip - bot , ( Year 2014 ) .
2013/0290710 Al 10/2013 Broder et al. International Search Report and Written Opinion for PCT Applica
2013/0339738 A1 12/2013 Shaw tion No. PCT /US2019 /027857 dated Jul. 15 , 2019 .
2013/0343546 Al 12/2013 Shibutani et al . Ouaddah et al . “ FairAccess: a new Blockchain -based access control
2014/0019352 A1 1/2014 Shrivastava
2014/0025473 A1 1/2014 Cohen framework for the 1-20 Internet of Things. ” In : Security and
2014/0052617 Al 2/2014 Chawla et al . Communication Networks . Feb. 19 , 2017 .
2014/0057599 Al 2/2014 Hazari “ A plea to exchanges lets do 2 factor right !" Bitcoin Forum ,
2014/0082749 Al 3/2014 Holland et al . download from https://bitcointalk.org/index.php?topic=109424.0%
2014/0108223 Al 4/2014 Xiao E2 % 80 % 93 % 20Stephen %20Gomick%20NOV % 205 % 20 % 2712 %
2014/0156512 A1 6/2014 Rahman et al . 20at % 2016 : 56 (posted Sep. 14 , 2012 ) , ( 10 pages ), Mar. 1 , 2018
2014/0172633 A1 6/2014 Dogin et al . 00 :00 :00.0
2014/0229739 A1 8/2014 Roth et al . “ Bitcoin Explained Like You're Five Part 3 — Cryptography ” , http : //
2014/0274327 Al 9/2014 Fine et al . chrispacia.wordpress.com/2013/09/07/bitcoin-cryptography-digital
2014/0279436 A1 9/2014 Dorsey et al . signatures -explained /,2013 , ( 21 pages ), Feb. 9 , 2018 00 : 00 : 00.0 .
2014/0289118 A1 9/2014 Kassemi et al .
2014/0297537 A1 10/2014 Kassemi et al . “ Bitcoin Explained Like You’re Five , Part 4 —Securing Your Wal
2014/0304171 A1 10/2014 Mertens et al . let ” , https://chrispacia.wordpress.com/2013/09/29/bitcoin-explained
2015/0033301 Al 1/2015 Pianese et al . like-youre - five - part- 4 - securing -your -wallet/, dated Sep. 29 , 2013 )
2015/0039444 A1 2/2015 Hardin et al . ( Year: 2013 ) , ( 15 pages ) ., Mar. 1 , 2018 00 : 00 : 00.0 .
2015/0050987 Al 2/2015 Huang et al . " Computer Arch ” , http://www.math.uaa.alaska.edu/-afkjm/cs101/
2015/0120569 Al 4/2015 Belshe et al . handouts / ComputerArch.pdf, dated Sep. 10 , 2009 , ( 16 pages ) . , Feb.
2015/0127495 A1 5/2015 Houri 9 , 2018 00 : 00 : 00.0 .
2015/0170112 A1 6/2015 Decastro “ NIST ” , Archived NIST Technical Series Publication, dated Jul.
2015/0178693 Al 6/2015 Solis 2012 , sp 800-57_part1_rev3_general.pdf, ( 148 pages ) . , Mar. 1 ,
2015/0209678 Al 7/2015 Edwards et al. 2018 00 : 00 : 00.0 .
2015/0220928 A1 8/2015 Allen “ Off -the- chain transactions ” , downloaded from http :// gavintech.
2015/0227897 A1 8/2015 Loera blogspot.com/2012/07/off-chain-transactions.html, dated Jul. 3 , 2012
2015/0228004 Al 8/2015 Bednarek et al .
2015/0262139 Al 9/2015 Shtylman ( Year : 2012 ) , (4 pages ), Feb. 9 , 2018 00 :00 :00.0 .
2015/0262171 Al 9/2015 Langschaedel et al . “ Securing your wallet” , downloaded from https://bitcoin.org/en/
2015/0262173 A1 9/2015 Durbin et al . secure -your -wallet (post from2013 ), (4 pages ), Mar. 1 , 2018 00:00:00 .
2015/0287026 A1 10/2015 Yang et al . 0.
2015/0294308 A1 10/2015 Pauker et al . Beal , Alex , “ Backing Up Sensitive Data With Secret Sharing ” ,
2015/0302401 Al 10/2015 Metral downloaded from https:www.usrsb.in/secret-sharing-backup.html,
2015/0310424 A1 10/2015 Myers dated Feb. 23 , 2013 ) ( Year: 2013 ) , ( 8pages ) , Feb. 9 , 2018 00:00:00 .
2015/0365283 A1 12/2015 Ronca et al . 0.
US 10,903,991 B1
Page 3
( 56 ) References Cited 2006 , Proceedings pp . 207-228 , ( Lecture Notes in Computer Sci
ence ; vol . 3958 ) , https://cr.yp.to/ecdh/curve25519-20060209.pdf.
OTHER PUBLICATIONS Berstein , Daniel J. , et al . , “ High -speed high -security signatures ” ,
“ Blockchain — How do off chain transactions work ? ” downloaded
Journal of Cryptographic Engineering vol . 2 , pp . 77-89 ( 2012 ) ,
from https://bitcoin.stackexchange.com/questions/123530/how-do Published : Aug. 14 , 2012 .
Bradbury, Danny, “ BitGo Safe Aims to Secure Bitcoin Wallets with
off -chain - transactions -work , year 2013 . Multi-Signature Transactions ” , CoinDesk , The Voice of Digital
Dion Derek A. , “ I'll gladly trade you two bits on Tuesday for a byte Currency, http://web.archive.org/web/20140108021304/http://www .
today: Bitcoin , regulating fraud in the e - conomy of Hacker -cash ” , coindesk.com/, published Dec. 19 , 2013 .
Journal of Law , Technology & Policy, vol . 2013 , pp . 165-201 , Oct. Breitner, Joachim , et al., “ Biased Nonce Sense : Lattice Attacks
20 , 2017 00 : 00 : 00.0 .
Douget , Joshua J. , “ The Nature of the Form : Legal and Regulatory against Weak ECDSA Signatures in Cryptocurrencies ” , Financial
issues surrounding the Bitcoin digital currency system ” , Louisiana Cryptography and Data Security, pp . 3-20 , DOI : 10.1007/978-3
Law Review , vol . 73 , No. 1 Summer 2013 , pp . 1118-1153 , Feb. 9 , 030-32101-7_1 , Sep. 2019 .
2018 00 : 00 : 00.0 . Davis, Don , “ Defective Sign & Encrypt in S/ MIME , PKCS #7 ,
" GitHub for SelectCoin code ” , https://github.com/trottier/original MOSS , PEM , PGP, and XML ” , The Proceedings of the 2001
bitcoin /blob /master / src/main.cpp , lines 2410-2510 , lated Apr. 4 , UNSENIX Annual Technical Conference, Jun . 25-30 , 2001 , Boston ,
2013 . Massachusetts, USA , pp . 65-78 of the Proceedings.
“ How Bitcoin Works” , downloaded from https://www.forbes.com/ Gennaro , Rosario , et al., “ Revisiting the Distributed Key Genera
sites /investopedia /2013 /08 /01 /how -bitcoin -works /# 284bd94a17ff, dated tion for Discrete - Log Based Cryptosystems” , https://pdfs.
Aug. 1 , 2013 , attached as PDF file . ( Year: 2013 ) . semanticscholar.org/642b/d1bbc86c7750cef9fa770e9e4ba86bd49eb9 .
" Inputs.io FAQ ” , https://inputs.io/faq, 2013 . pdf, 2003 .
International Search Report and Written Opinion of the ISA dated Krawczyk, H. , et al . , “ HMAC - based Extract -and -Expand Key
Dec. 18 , 2019 for PCT /US19 / 52371. Derivation Function (HKDF ) ", Internet Engineering Task Force
Meiklejohn Sarah ; et al . , “ A fistful of bitcoins : Characterizing ( IETF ) , May 2010 , https://tools.ietf.org/html/rfc5869.
Payments among men with no names ” , 2013 , ( 8 pages ) , Oct. 20 , Lee , Leland , et al., “ Alternative Signatures Schemes ”, Medium ,
2017 00 : 00 : 00.0 . Feb. 12 , 2019 , https://medium.com/blockchain-at-berkeley/alternative
“ Multi -Party Threshold Signature Scheme” , https://github.com/ signatures - schemes -14a563d9d562.
binance - chain /tss - lib # readme. Marlinspike, Moxie , et al . , “ The X3DH Key Agreement Protocol ” ,
“ NPL4, Importing Bitcoin from a paper wallet into Electrum ” , Signal, Revision 1 , Nov. 4 , 2016 .
https://thecleverest.com/, dated Mar. 12 , 2014 . Merkel, Dirk , “ Bitcoin for beginners, Part 2 : Bitcoin as a technol
“ Proactive secret sharing ” , Wikipedia , https://en.wikipedia.org/wiki/ ogy and network ” , Javaworld , Dec. 6 , 2011 .
Proactive_secret_sharing. Neuman , Nick , “ KeySplit - Tackling the hard parts of being your
“ Strongcoin—The safest Bitcoin e -wallet on the planet ” , https:// own bank ” , https://medium.com/©nickneuman/keysplit-private-key
www.javaworld.com/article/2078467/bitcoin-for-beginners part security - for -cryptocurrency -owners -d1653ea9631d , Feb. 24 , 2018 .
2 --bitcoin -as - a -technology - and -network.html, year 2013 . Pedersen , Torben Pryds , “ Non - Interactive and Information
Wallace Benjamin , “ The rise and fall ofbitcoin " , Magazine, WIRED , Theoretic Secure Verifiable Secret Sharing ” , Advances in Cryptol
https://www.wired.com/2011/11/mf_bitcoin/all/1., Nov. 23. 2011 , ogy , CRYPTO '91 , LNCS 576 , pp . 129-140 , 1992 .
pp . 1-17 , Oct. 20 , 2017 00 : 00 : 00.0 . Shamir, Adi , “ How to Share a Secret” , Communications of the
“ What is the coin selection algorithm ” , downloaded from https: // ACM , Nov. 1979 , vol . 22 , No. 11 .
web.archive.org/web/20130228073524/https://bitcoin.stackexchange. Stinson , Douglas , et al . , “ Provably Secure Distributed Schnorr
com / questions/ 1077 /what - is - the-coin - selection - algorithm dated Feb. Signatures and a (t , n ) Threshold Scheme for Implicit Certificates ” ,
27 , 2014 . Australasian Conference on Information Security and Privacy ACISP
Bernstein , Daniel J. , “ Curve25519 : new Differentiations -Hellman 2001 : Information Security and Privacy pp . 417-434 .
speed records” , 9th International Conference on Practice and Theory
in Public -Key Cryptography, New York NY, USA , Apr. 24-26 , * cited by examiner
U.S. Patent Jan. 26 , 2021 Sheet 1 of 11 US 10,903,991 B1
Participant Participant Participant
System System System
114a 114b 114c
Signing
Issuer System
System 112
1
111
API
System
113
Signing System 110
External
Blockchain (s) System
104
FIGURE 1
U.S. Patent Jan. 26 , 2021 Sheet 2 of 11 US 10,903,991 B1
200
Generate a message signing private key S210
Generate signing secrets S220
Process a signing request S230
--- -- -
1
Perform proactive secret sharing S240
--
FIGURE 2A
U.S. Patent Jan. 26 , 2021 Sheet 3 of 11 US 10,903,991 B1
S210
Convert the message signing private key into an expanded private key S211
Generate a signature verification key S212
S220
FIGURE 2B
Split the message signing key into shares S221
Generate authentication keys S222
I Generate encryption keys S223
Generate integrity key S224
Encrypt the shares S225
Store signing secrets S226
FIGURE 2C
S230
Receive the signing request S231
Access stored signing secrets for the signing request S232
Providing the stored signing secrets to participant systems S233
Access additional signing data S234
Generate a signature for the signing request by using the stored signing secrets S235
Provide the generated signature S236
FIGURE 2D
U.S. Patent Jan. 26 , 2021 Sheet 4 of 11 US 10,903,991 B1
S234
1
Decrypting a signing secret S310
|
1
Verifying validity of the decrypted signing secret S320
1
Generating additional signing data S330
_
|
Splitting the additional signing data into additional signing data shares S340
1 Encrypting the additional signing data shares S350
'
L
Storing the additional signing data shares S360
I
FIGURE 3
U.S. Patent Jan. 26 , 2021 Sheet 5 of 11 US 10,903,991 B1
S235
Accessing participant encrypted signing secret S410
í
Decrypting participant signing secret S420
-- 1
-
Verifying validity of decrypted participant signing secret S430
-
Accessing encrypted additional sighing data shares S440
-
0 Decrypting additional signing data shares S450
1 --
Aggregating decrypted additional signing data shares S460
_
-
Generating a partial signature S470
1
1
Providing the partial signature S480
FIGURE 4
U.S. Patent Jan. 26 , 2021 Sheet 6 of 11 US 10,903,991 B1
Input Device 581
DisplayDevice 591
Bus 501
ROM 504
Memory522 MS5teod0riau5gme OS530 Ap5lic1ati3ons D5eriv1iecr4es
Procesor 503N
Procesor 503B NDetvwiocrke 511
Procesor 503A FIG5URE
Procesing Un599it
Hardware D5ev0ice
U.S. Patent Jan. 26 , 2021 Sheet 7 of 11 US 10,903,991 B1
Key Allocation Flow
Client Server
Signed ( AllocateKeyRequest , deltaPrivkey ) S210
KeyAllocatedTo ( deltaPubkey )
Futher requests to authorize access to
the key by verifying they are signed
with the sale deltaprivkey .
Client Server
FIGURE 6
Signing Flow
ClientSage Librarian CSS CSr } Serversage
CreateSig S231
Request key Shares ( if needed ) S232
Sumit Key Shares
Request Nonce Shares S233
Submit Nonce S234
Wait for Quorum , .
finalize Nonce
Request Sig Shares S235
Submit Sig
Wait for quorum .
Finalize sig
Signature
S236
ClientSage Librarian CSS ( 57 ] Serversage
FIGURE 7
U.S. Patent Jan. 26 , 2021 Sheet 8 of 11 US 10,903,991 B1
sthoarage PK ...
Cn
1
+
,
Ci
S2 6
Lstocragle psapretic(c)ifpainct psaprteicCity+1()ipfanitci psapretic()Coifpianct
S2 5 epsnrchirykeyatovprted epsnrchirvtokeyaprted
Eyn
participantparticipantparticipanti S2 23
authkey1pub eknepubcyr1
epsnrchirPKK,ubauthkeyivtoacrpted
auth
pub
PKka
,
+
1
encr proof
keyi )
auth
type
1
+
,
(
PK
pub
PKK
keyi
,
PKK
pub
proof
PK
(
)
type
auth
keyi pub PKK
,
PKK
encr
keyn
auth )
auth
,
type
(
pub
proof
PK
keyn
PKKGS2 4
FIG8URE
shareeyvat
:)
k
pri( 1
)
+
key
ki
(
share
private )vkey
kn
sharet
pri(
aicsnetroe)cPKKG(,keygwithgenimraoiteyd Public
Key
(
)
PK
:
pdleasintreoxty
S2 1
expanded prikeyv1ate
esk
)
(
I |
pdleasitnreoxyt
S210 prikeyvate )
(
sk
U.S. Patent Jan. 26 , 2021 Sheet 9 of 11 US 10,903,991 B1
1 1 local secure storagei
1 S231 to
1. message 1 participant i
signing service request for share 1
be signed ( m ) (signed with aki) auth keyi : private (aki), public ( AK)
client S235 Pi encr keyi : private (eki), public (EKI)
19. signed message 18. combine integrity key: PKKG
Si... St into s 2. ci , PK , m
(m , s )
S233 participant others
AK1 , ... AKN
1
3. type, PK , PKK , Aki
1 Ci
S310 ki
AK1 , ... AKO
9. Ci , PK , m
S410 request PK , m verify share validity (proof , PK)
S320 ki
4. generate noncei (ri , Ri)
8. S330 .
sender : Pi 5. generate nonce shares ( p1 , ... Pn)
recipients: P1 ... Pn
1
bit ,
PK
bin
S340 (101, Pn)
6. encrypt nonce shares to each participant
1 S350 p1 AKI , EK1 , AK1 b1
1
local secure storagei AKI , EK , AK ;
1
1
participanti Pn
AKI, EK , AKN bn
aki, AK ;
eki, EK?
PKKG Pi 7. encrypted nonce shares (b1 , ... bn)
participant others S360
AK1, ... AKN
PK
type ??
10 .
PKka , aki,, ek
ki
S420 1
1
12. S440
verify share validity b1j ; btj
Aki, aki, eki S430 PK , m
13. decrypt encrypted nonce shares
b1j pli S450
17. Si, participanti
S480
buj Pt?
14. aggregate nonce shares 15. aggregate nonce public keys
S460
PK, m
S470 FIGURE 9
16. create partial signature ( si)
U.S. Patent Jan. 26 , 2021 Sheet 10 of 11 US 10,903,991 B1
Participant System Message
114 Signing
Server 112
Update additional signing data shares S241
Generate and store encrypted zero - value shares S242
Additional signing data shares and zero - value shares
Match and
combine
shares
S244
Encrypt
combined
shares
S245 Store encrypted combined shares S246
Replace old
additional signing data shares with
encrypted combined shares S247
FIGURE 10
U.S. Patent Jan. 26 , 2021 Sheet 11 of 11 US 10,903,991 B1
Generate a message signing
private key S210
Generate signing secrets S220
Process a signing request S230 Receive a signing request for a
message S231
Accessing stored signing secrets
S232
Providing the respective signing Receiving the message and
secret to each of a set of signing secrets for the participant
participant systems S233
Decrypting the signing secret
S310
Receiving additional signing data Accessing additional signing data
shares generated by other ( e.g., nonce shares) generated by
participants S410 other participants S234 Generating additional signing data
S330
Decrypting the participant's
signing secret S420 Generating a signature based on Splitting the additional signing
the additional signing data S235 data into shares S340
Receiving the participant's
additional signing data shares Encrypting each additional signing
S440 data share to a different
Providing the generated signature participant S350
Decrypting the participant's S236
additional signing data shares
S450
1
Aggregating the decrypted
additional signing data shares
S460 1
1 FIGURE 11
Generating a partial signature
based on the aggregated
additional signing data shares and
decrypted signing secret S470
US 10,903,991 B1
1 2
SYSTEMS AND METHODS FOR 1. Overview .
GENERATING SIGNATURES The method for distributed signature generation functions
to restrict information about a private key, such that the
CROSS - REFERENCE TO RELATED private key does not need to exist in the clear outside of key
APPLICATIONS 5 generation . The system and method enables cryptographic
This application claims priority to U.S. Provisional Appli ing signature generation with t of n participants without requir
the signing private key to be in the clear (e.g. , recon
cation No. 62 / 881,729 , filed 1 Aug. 2019 , U.S. Provisional stituted ) for signing.
Application No. 62 / 881,711 , filed 1 Aug. 2019 , and U.S. All or portions of the method can be performed by a
Provisional Application No. 62 / 946,912 , filed 11 Dec. 2019 ,
which are
reference.
each incorporated herein in its entirety by this 10 remote computing
combination thereofsystem
, and /or, any
a local
other participant system
suitable system ,a
. Com
munications between systems can be : signed (e.g. , with a
TECHNICAL FIELD private key of an asymmetric key pair, with a symmetric
key ), encrypted, and / or otherwise authenticated and /or
This invention relates generally to the cryptocurrency 15 secured In
.
some variations, a quorum of signers (t of n ) must
field , and more specifically to a new and useful system and
method for generating signatures. collaborate to produce a valid signature, and no malicious
group of adversaries can gain useful information about the
BACKGROUND private key without access to at least t signers and key -share
20 ciphertext. In some variations, asynchronous signing is
Several cryptocurrency protocols requiring signing of provided, where signers can be offline by default, and come
transactions for operations related to management of a online only when there is an action to take . Variations
cryptocurrency protocol. Such transactions are typically leverage a trusted key generation and key - share issuance
separate from transactions for transfer of cryptocurrency ceremony to distribute secrets to signers, as well as an online
assets . Ordinarily, a private key is used to sign such trans- 25 centralized server to manage protocol state . In some varia
actions . However, accessing and using such a private key for tions , signing -keys ( e.g. , private keys ) are generated in an
transaction signing can increase the likelihood of the private off - line key generation ceremony.
key being accessed by an unauthorized entity. In some variations, a signing system (e.g. , 110 shown in
There is a need in the computer networking field to create FIG . 1 ) is used to sign transactions. In some variations the
a new and useful systems and methods for secure signing of 30 signing system includes at least one of: an application
transactions . This disclosure provides such new and useful programming interface (API) system ( e.g. , 113 ) ; an issuer
systems and methods. system (e.g. , 111 ) ; a message signing system (e.g. , 112 ) ; and
at least one participant system (e.g. , 114a - c ) .
BRIEF DESCRIPTION OF THE FIGURES In some variations, the method (e.g. , 200 shown in FIG .
35 2A) includes at least one of: generating a private key ( e.g. ,
FIG . 1 is schematic representations of a system , in accor- S210 ) ; generating signing secrets by using the generated
dance with variations . private key ( e.g. , S220 ) ; and processing a signing request by
FIGS . 2A - D are representations of a method , in accor- using the stored signing secrets (e.g. , S230 ) . In some imple
dance with variations . mentations, at least one component of the signing system
FIG . 3 is a representation of a method , in accordance with 40 ( e.g., no) performs at least a portion of the method (e.g. ,
variations. 200 ) .
FIG . 4 is a representation of a method , in accordance with In one example , the method can include : at an issuer
variations. system , generating a signing key (message signing key ),
FIG . 5 is a representation of a system , in accordance with splitting the signing key into secret shares encrypted to
variations. 45 different participants, and uploading the encrypted secret
FIG . 6 is a representation of an exemplary key allocation shares to a message signing system . To sign a message , the
flow , in accordance with variations. method can include : with a first quorum of participants ,
FIG . 7 is a representation of an exemplary signing flow , generating a nonce for a message to be signed ( e.g. , using a
in accordance with variations. distributed key generation method ) based on the respective
FIG . 8 is a representation of a key generation flow for a 50 secretshares,splitting the nonce into nonce shares encrypted
single message signing key and participant set , in accor- to different participants, and uploading the encrypted nonce
dance with variations . shares to the message signing system ; and at each of a
FIG . 9 is a representation of a message signing flow for second quorum of participants, generating a partial signature
a single message , using a single message signing key, in from the nonce shares encrypted to the respective partici
accordance with variations . 55 pant, and uploading the partial signature to the message
FIG . 10 is a representation of a proactive secret sharing, signing system ; the partial signatures are then aggregated
in accordance with variations . into a signature that verifies under the aggregate public key
FIG . 11 is a flowchart representation of an example of the (PK) (e.g. , by a participant, the message signing system ,
method . etc. ) , wherein the message can be signed with the signature
60 and optionally sent to the respective blockchain network .
DESCRIPTION OF THE PREFERRED Each participant of the first quorum can generate the nonce ,
EMBODIMENTS a partial nonce , or other datum that is subsequently split ,
encrypted, and uploaded . Generating the partial signature
The following description of embodiments is not intended can include, at each participant of the second quorum :
to limit the claims to these embodiments, but rather to enable 65 downloading and decrypting the nonce shares that are
any person skilled in the art to make and use embodiments encrypted to them ; downloading and decrypting the signing
described herein . key shares that are encrypted to them ; optionally verifying
US 10,903,991 B1
3 4
the validity of all encrypted data ; combining the decrypted aggregated with other partial signatures ( generated in the
nonce shares into a single nonce share ; and creating the same manner) to generate a valid signature.
partial signature using the key and nonce share. This Additional benefits can be provided by the systems and
example can be coordinated by the message signing system , methods disclosed herein .
which can function as shared data storage and state machine 5 3. The System .
signature generation method is preferably performed
coordinator, and can be blind to the private signing key
and / or nonce values . with a signing system 110 , but can alternatively be per
In a second example, the method includes generating a preferably formed with a different system . The signing system 110
functions to facilitate message signing. In a first
nsigning
splittingkeyconstruction
sk and splitting sk into key shares using a t of
;at each participant system of a first 10 variation , the signingtransactions
system 110 functions to sign messages
quorum of at least t participants, generating a noncer; based (signing e.g. , cryptocurrency ). In a second variation, the
on randomness and a key share and splitting the nonce into eration for a message . For example, the signing system gen
system 110 functions to coordinate signature
110
nonce shares using the same t of n splitting construction; at can function as a shared data storage, as a state machine
each participant system of a second quorum of at least t coordinator, to verify the authorization key signatures of the
participants, retrieving a key share and nonce shares of the 15 participants requesting or sending data, or perform other
at least t nonces (from the first quorum ), generating an functionalities. The signing system is preferably blind ( e.g. ,
aggregate nonce , and generating a partial signature based on has no knowledge of, cannot access ) the message signing
a message , the key share, and the aggregate nonce ; and key (private signing key ) and / or nonce values , but can
reconstructing a signature for the message based on the at 20 pate
least t partial signatures.
alternatively
.
function as a participant or otherwise partici
2. Benefits. The message is preferably a blockchain message , com
This method can confer several benefits over conventional patible and verifiable with the respective blockchain that the
systems and methods. signed message is sent to , but can alternatively be a datum
First , messages ( e.g. , cryptocurrency transactions) can be 25 or other message . The message can be : a transaction mes
signed without exposing a private key of a cryptocurrency sage , a governance message ( e.g. , for staking , delegating ,
wallet. Instead , the private key is split into shares, the shares voting , etc. ) , and / or other message . The message can be
are used to generate partial signatures, and the partial generated by : a platform , a dApp ( distributed application ),
signatures are combined to generate a signature for the an exchange, a client, and / or any other suitable system . The
message . The systems generating the partial signatures do 30 message can be associated with a signature verification key
not need access to the complete private key, and the system PK , an address generated from PK , and / or any other suitable
combining the partial signatures does not need to access address or message signing key identifier.
either the shares of the private key or the complete private The signing system 110 is preferably used with a set of
key to generate a full signature for the message . keys, which can be used for authorization or verification,
Second, messages can be signed by using on - line systems. 35 encryption, signing, or otherwise used . Examples of keys
Since the complete private key is not needed to sign the used with the signing system 110 include : a message signing
message , signing can be performed by on - line systems that public key (PK) ( signature verification key ) used to verify
have access to shares of the private key, or partial signatures. the final signature (e.g. , generated from the signing private
There is no need to reconstruct the private key in a secure , key, paired with the signing private key ( sk) ) ; a message
off -line environment to perform signing. This further 40 signing private key ( sk) ; a keygen integrity key ( PKKG ) or
enables the private keys to be reused for multiple signatures. public -private keypair ( PKKG , skko, respectively ), which
Third , security can be improved by distributing the sign- can be used by participant systems to validate encrypted key
ing process among a plurality of systems , rather than entrust- shares as being provided by a known key generation system
ing signing to a single trusted system . (e.g. , the Issuer System 111 ) or process; a server authenti
Fourth , variants of the system and method enable valid 45 cation key ( AKS) or public -private keypair ( AK , aks,
signature generation without message signing key recon- respectively ), wherein AK , can be used by participants to
struction . In variants leveraging Shamir's Secret Sharing verify that they are communicating with the correct message
( SSS ) to split the message signing key, shares generated signing system 112 ; a participant authentication key ( AKP )
using SSS can be linearly combined to reconstruct the or public -private keypair ( AKP , ak p , respectively, for par
message signing key as long as t of n shares are available . 50 ticipant i ) , wherein the public keyAK pi can be used for
This allows any participant to construct a valid signature as authenticating participant systems with the server and other
long as t of n partial signatures, generated using the same participants; a participant encryption key ( ENKP ) or public
message ( m ), but different message signing key shares, are private keypair (ENK Pi, enkpi, respectively or ENC Pie encPis
available . For signing protocols that require one or more respectively, for participant i ) , wherein the public key
pieces of additional signing data ( e.g. , a nonce ), the addi- 55 ENKp; can be used by other participants to encrypt data to
tional signing data can be collectively generated, particu- the receiving participant; one or more ephemeral issuer keys
larly when one or more participants each determine respec- (EK ,) used to encrypt the shares of the signing private key
tive additional signing data from a respective private key ( sk) to each participant system ; one or more participant
share and / or the message ( e.g. , by generating the data using ephemeral keys ( EKP) created by the participant systems
a random value , hashing the private key share and the 60 when encrypting data to another participant; and/ or other
message , etc. ). Furthermore , when an additional signing data keys.
itself is split using SSS ( e.g. , with the same t of n configu- The message signing key (e.g. , public and /or private ) can
ration ), its shards are also linearly combinable with shards of be a key that conforms to any suitable message signing
additional signing data generated using a different message format or protocol. Examples of cryptocurrency signature
signing key share , such that a partial signature generated 65 schemes that the signing key and / or resultant signature can
using shards from multiple additional signing data ( each be compatible with include: DSA signature schemes ,
generated from a different message signing key share) can be ECDSA signature schemes, EdDSA signature schemes ( e.g. ,
US 10,903,991 B1
5 6
Ed25519 , Ed448 , etc. ), pairing -based schemes ( e.g. , BLS ) , include: an application programming interface (API ) system
Schnorr, RSA , ring signatures, and / or any other suitable 113 ; at least one participant system 114 ( examples 114a - c) .
cryptocurrency signature scheme ( e.g. , public key algo- In variants, the issuer system 111 functions as a secure key
rithm ). When the cryptocurrency signature scheme requires generation system (e.g. , for generating one or more of a
additional signing data in addition to the private key and the 5 message signing key pair authentication key pair, encryption
message ( e.g. , a nonce) , the additional signing data is key pair, etc. ) . The issuer system is preferably a centralized
generated. The signing system 110 can be compatible with processing system ( e.g. , a remote computing system , a cloud
one or more cryptocurrency signature schemes. When the system , a server system , etc. ) , but can alternatively be a
signing system 110 is compatible with a single cryptocur distributed computing system . The issuer system can be an
rency signature scheme, a system can include a different 10 networks offline system
.
that is secured from public communication
signing system 110 implementation for each cryptocurrency In some variations, the issuer system 111 performs one or
signature scheme. In some variations , the message signing more
private key is a sequence of randomly generated bytes . In nativelyoffline key generation processes . Additionally, or alter
, the issuer system 111 can perform one or more
some variations, S210 includes fetching 32 bytes of random online key generation processes. In some variations, the
data from a cryptographically secure random data source . 15 issuer system 111 functions to generate a signing private key
In some variations, keys PKKG : EK , EKp are ephemeral during an offline key generation ceremony . In some varia
keys. In some variations, key PK is an Ed25519 key. In some tions , during the key generation ceremony, the issuer system
variations, keys PKKG , EK , AKP, ENKp, EK p , and AK , are in also generates a plurality of participant keys. In some
NIST-P256 keys. 20 variations, the issuer system 111 provides the participant
In one variation , a platform account ( e.g. , institution , keys to the participant systems 114a - c ( or to users of the
individual, etc.) can be associated with a participant group participant systems ). Alternatively, the participant keys can
including n or more participant key sets (e.g. , wherein a be generated before the key generation ceremony, wherein
participant key set can include : AK Pakpi, ENKpi, enkp; for the participant keys are provided to the key generation
participant i ) , held by participants affiliated with the plat- 25 ceremony for use .
form account (e.g. , institution employees ). The participant The issuer system 111 can generate (e.g. , in one or more
group ( and /or platform account) can be associated with one keygen ceremonies ) one or more of the keys discussed
or more message signing keys , wherein t of n participants above . Alternatively, the keys can be generated by a different
from the participant group can cooperatively sign messages system . In some variations, the issuer system 111 provides
verifiable to the public message signing key (PK) . Each 30 each key AKp, ENK , to a respective participant system
message signing key can be associated with a keygen (e.g. , 114a - c) . In some variations , the issuer system 111
integrity key ( PKKG ), which is associated with ( and /or provides key AK , to the message signing system 112 .
dentifies) the keygen ceremony that generated the respec- In some variations, the message signing system 112
tive message signing key. functions to coordinate and maintain a protocol state and
All or a portion of the keys can be generated by : the issuer 35 keep track of data that is provided to participant systems for
system , the participants , and / or otherwise generated . When generation of a signature . The message signing system 112
all keys are generated by a single system (e.g. , issuer can : identify the participants associated with a public sign
system ), the keys are preferably distributed to the partici- ing key (PK) , identify the encrypted signing key shards
pants (e.g. , users ). The keys are preferably generated offline associated with the public signing key (c ; ) , receive encrypted
( e.g. , in a system isolated from the Internet or other com- 40 nonce shares from the first quorum of participants, distribute
munication networks ), but can alternatively be generated the encrypted nonce shares that are encrypted to a requesting
online . Key distribution preferably occurs offline (e.g. , an participant, aggregate the partial signatures, sign the mes
HSM with the keys are physically or manually delivered to sage or distribute the partial signatures to a participant for
the participant ), but can alternatively occur online ( e.g. , message signing, authenticate every message received from
transferred over a secure communication channel). The 45 a participant, and /or perform other processes . The message
plaintext version of the keys are preferably destroyed after signing system is preferably a centralized system controlled
key storage, but can alternatively be otherwise retained . The by a platform or centralized service, but can alternatively be
keys can be generated contemporaneously ( e.g. , during the a distributed system or other system .
same ceremony ), or asynchronously (e.g. , during different The application programming interface ( API ) system 113
ceremonies ). In a first example, all keys are generated during 50 functions to receive predetermined calls to the signing
the same ceremony. In a second example , the message system 110 , which can subsequently be sent to and fulfilled
signing keys for a set of participants are generated after the by the issuer system , message signing system 112 , partici
participants' authentication and encryption keys are gener- pant system ( s ) 114 , and / or other system . Examples of calls
ated . However, the keys can be otherwise generated. include: key generation requests, message signing requests ,
The signing system 110 preferably interfaces with one or 55 and / or other requests .
more blockchain networks ( e.g. , via one or more blockchain The signing system 110 preferably interfaces with a set of
nodes hosted by the signing system 110 or a connected participant systems. Alternatively, the signing system 110
system ). The blockchain networks are preferably compatible can include the participant systems . Each participant system
with the message signing protocol ( s) supported by the 114a - c functions to perform at least one process for gener
signing system 110 , but can alternatively be incompatible. 60 ating a signature.
Examples of blockchain networks include UXTO -model A participant system is preferably remote computing
protocols (e.g. , Bitcoin , etc. ); account -model protocols ( e.g. , devices associated with ( e.g. , controlled by ) a participant ,
Ethereum , ERC20 tokens, such as USDC , Litecoin , etc. ) ; but can alternatively be local and / or otherwise related to the
and / or other protocols . signing system no . Examples of participant systems include :
The signing system 110 preferably includes at least one 65 hardware security modules (HSMs ) , secure cryptoprocessor
of: an issuer system 111 ; and a message signing system 112 . chips, laptops, smartphones , mobile devices, tablets, smart
In variants , the message signing system 110 can optionally watches, desktop computers, servers and /or other computing
US 10,903,991 B1
7 8
system . The participant system can include including a In some variations, the storage device includes the
processing system and memory (e.g. , storing the partici- machine - executable instructions for performing at least a
pant's private keys and other participants ' public keys ). In portion of the method 200 described herein .
some implementations, at least one participant system is a In some variations, at least one component of the system
device ( e.g. , an Internet connected mobile device) has a 5 performs at least a portion of the method 200 described
persistent network connection (e.g. , to the Internet ), and herein .
optionally includes a notification module that functions to 4. Method .
receive asynchronous notifications (e.g. , notifications for
authorization input, etc. ) . In some implementations, at least 200.FIGS . 2A - D are flowchart representations of a method
In some variations , the method 200 includes at least one
one participant
network system
connection (e.g. ,isto athedevice
Internetwith
) ( e.g.an, aintermittent
laptop that 10 by
of using
generating
the
a private key
generated
S210key; generating
private S220 ;
signing
and
secretsa
processing
is only connected to the network when the laptop is powered signing request by using the stored signing secrets S230 . In
on and not in a sleep mode ).
The participants ( e.g. , users , individual accounts, etc. ) are some implementations, at least one component of the sign
preferably part of a participant group, wherein the partici- 15 ing system no performs at least a portion of the method 200.
pant set is associated with a platform account (e.g. , associ All or portions of the method can be performed automati
ated with an entity ). A given participant can be associated cally ( e.g. , without user input ), manually, in response to user
with one or more participant groups . input (e.g. , user approval, user connection of the respective
Each participant system can store a participant key set , participant system to a network , etc. ), or otherwise per
which can include: a participant authentication key (AK Pi, 20 formed .
akpi, respectively , for participant i ) and a participant encryp- The method can leverage verifiable secret sharing in one
tion key (ENK Pi, enkpi, respectively or ENC Pi, enc pis or more steps of the method . VSS can function to provide a
respectively, for participant i ) , but can additionally or alter- proof (VSS ) alongside a secret share ( e.g. , of the message
natively be associated with other keys. The participant signing key, of a nonce) that allows the recipient to verify it
system can optionally store the public keys for the message 25 was honestly generated , and that the sender or system
signing system ( e.g. , server , central system ), the issuer, generating the proof knew the secret that was shared . In
and /or other systems. variants, the VSS can serve as a knowledge of secret key
In some variations, participant systems include participant proof (KOSK) that the system generating the proof knows
systems managed by humans and participant systems man- the discrete log of the public key it is creating the proof for .
aged by server ( s) of the signing system no . In some varia- 30 In one example, the signing secret sharing proof is a set of
tions , server -managed participant systems are used to commitments to coefficients of a sharing polynomial used to
improve security. By using server -managed participant sys- split the message signing key into shares, and is generated
tems , humans managing human -managed participant sys with {VaG } je [t]. To verify the proof, the verifier ( e.g. ,
tems do not need to be trusted . Users of server -managed receiver) with the share ( s : ) ( e.g . , of the message signing key
participant systems can prevent an attack where a malicious 35 k; or nonce ) checks the equality of the following :
set of t human participants collude in an attempt to recon
struct the signing private key. In some variations, a threshold
of human -managed participant systems and server -managed 1-1
participant systems are required to be compromised for an
attack to be successful.
S: G = }= 0 V ;.id
40
Ž
In some variations, one or more of the components of the
system are implemented as a hardware device ( e.g. , 500 for t participants , and / or verifies that the provided PK equals
shown in FIG . 5 ) that includes one or more of a processor the free -coefficient commitment Vk,o in
( e.g. , 503a - n ) , a display device ( e.g. , 591 ) , a memory ( e.g. , The method can leverage mutual authentication in one or
522) , a read only memory (ROM) (e.g. , 504) , a storage 45 more steps of the method. In variants, the receiver and
device (e.g. , 505 ) , an audible output device, an input device sender (e.g. , participants and server ) are able to mutually
( e.g. , 581 ) , an output device, and a communication interface authenticate each other by signing the request and response
( e.g. , 511 ) . In some variations, one or more components payloads with the respective authentication keys (e.g. , with
included in hardware device are communicatively coupled akp, or aks, respectively ). In a specific example, participants
via a bus (e.g. , 501 ) . In some variations , one or more 50 making a request to the server must sign the full payload
components included in the hardware device are communi- with their participant authentication key, wherein the server
catively coupled to an external system via the communica- must verify the signature is valid and belongs to a known
tion interface . participant before proceeding. In this example , response
Processors can include one or more of a CPU ( central payloads from the server must be signed with the server
processing unit ), GPU ( graphics processing unit), NPU 55 authentication key, wherein the participant must verify the
( neural processing unit ), and any other suitable processing signature is valid and matches the known server authenti
system that functions to execute machine-readable instruc- cation key before proceeding. Similarly, recipient partici
tions . In variants , at least one of a processor and a memory pants must verify that the sending participant's signature is
can be included in a processing unit ( e.g. , 599 ) . valid before proceeding. However, the messages can be
The communication interface functions to communicate 60 otherwise authenticated.
data between the hardware device and another device via a The method can leverage Authenticated Key Exchange
network (e.g. , a private network, a public network , the ( AKE ) and / or Authenticated Encryption with Associated
Internet, and the like ). Data (AEAD ) in one or more steps of the method ( e.g. , for
The storage devices can include machine - executable all communication between two parties ). This can enable
instructions ( and optionally data ) for one or more of an 65 secret data ( e.g. , nonce , other signing secrets ) to be shared
operating system 530 , applications 513 , and device drivers with participants such that only the sender and receiver
514 . know the plaintext content and can verify the participant
US 10,903,991 B1
9 10
who created it . In a specific example, this can be accom- (e.g. , an on - line process , such as using a threshold signing
plished by deriving a shared secret with AKE and encrypting method ) to generate the message signing private key. How
the shared secret with AEAD . However, this can be other- ever, the message signing private key can be generated in
wise accomplished . any suitable manner .
In an example, AKE can include, for sender P ; and 5 In some variations, the private key is converted into an
recipient P ;: expanded private key ( epk ) ( S211 ) . In some implementa
DHI= DHAK PENKP;) tions , the expanded private key is an expanded private key
DH2= DH (EK P?,AKP;) of a key pair for an Ed25519 signature . Alternatively, the
DH3 = DH ( EKP; ENKP;) private key can be a private key of a key pair for any suitable
secret encryption key = KDF (DH1||DH2 ||DH3) 10 type of signature. In some variations, converting the private
where secret encryption key is a symmetric key used to key into an expanded private key includes hashing the
encrypt the message. The recipient can independently derive private key with SHA512 and extracting the first 32 bytes of
the secret encryption key ( e.g. , using the same method, with the hash output as a digest ; and changing some bits of the
their information ), and decrypt ciphertext received from the digest, wherein the changed digest is the expanded private
sender. In this example, (AK PEKP:) can be participant i’s 15 key. However, keys generated at S210 can conform to any
authentication key and a random ephemeral key for the suitable format or protocol .
message , respectively, and (AK PIEKP:) can be participant In some implementations, S210 includes generating a
j's authentication key and encryption key, respectively. signature verification key ( S212 ) . In some implementations,
DH1 , DH2 , and DH3 can be generically represented as the signature verification key is a public key (PK) of a key
DH ( PK1 , PK2 ) , where PK1 and PK2 are generic placehold- 20 pair that includes the message signing private key (sk ), and
ers . DH (PK1 , PK2 ) can represent the shared secret from an the public key is used to verify a signature generated by
Elliptic - Curve Diffie -Hellman ( ECDH ) function between using the message signing private key.
the keys ( PK1 , sk2) and ( PK2 , skl ) for (public , private ) key In some implementations, the expanded private key (gen
pairs ( PK1 , skl ) and ( PK2 , sk2 ) and wherein KDF ( k ) erated at S211 ) is used to derive the signature verification
computes a specified number of output bytes from HKDF 25 key (e.g. , PK) . In some implementations, deriving the sig
( Hash- based Key Derivation Function ) which accepts an nature verification key includes performing scalar multipli
arbitrary sized byte sequence as input , and wherein wherein cation on the expanded private key. In some implementa
EK ;Pi . is an ephemeral key of the sending system . However, tions , the scalar multiplication is performed by using a base
any other suitable key exchange method can be used . point according to the following equations: dG = Y , wherein
Alternatively, one - time keys and / or signed pre -keys can be 30 d is the expanded private key, G is the base point, and Y is
used . The keys can be static ( e.g. , not regularly rotated , the public key (PK) . However, the signature verification key
which minimizes the number of keys a participant needs to can be otherwise generated.
track and reduces the need retain large amounts of keys , S210 can be performed in response a key allocation
re -encrypting old data to new keys, and / or burning previ- request (e.g. , as shown in FIG . 6 ) , when key generation is
ously -encrypted data on rotation ), but can alternatively be 35 requested, at a predetermined time,or at any other suitable
rotated ( e.g. , using proactive secret sharing or another time . Each instance of S210 is preferably performed for a
method ). specific participant group , wherein the participant identities
When AEAD is used, the ciphertext can include cleartext (e.g. , participant key sets ) and splitting - reconstruction con
associated data . The associated data can include the public figuration (e.g. , t and n for a t of n signing quorum ; SSS
authentication keys for simple identification of who the 40 parameters; etc. ) are known before or generated during the
message relates to . The associated data can optionally key generation ceremony. In variations, S210 includes
include information about the message contents ( e.g. , selecting a participant group that includes n participants. The
ciphertext type, such as an identifier for a nonce , different participant group can be selected at any suitable time ( e.g. ,
identifier for a signing key, etc .; protocol versioning ), and /or before or after receiving a key allocation request). In some
other information . For example, the symmetric secret key 45 implementations, a participant group is selected based on
generated using AKE can be used to encrypt the message : one or more of user input, configuration information , or in
Encrypt ( sk , message, AKP://AKP;). any suitable manner. In some implementations, a participant
The method can leverage a distributed signing data gen- group is identified based on a platform account ( e.g. , asso
eration protocol ( e.g. , a distributed signature generation ciated with the key allocation request). However, S210 can
protocol, a distributed key generation protocol, a distributed 50 be otherwise performed based on any other suitable data.
nonce generation protocol , etc. ) in one or more steps ( e.g. , In some variations, as shown in FIG . 6 , a client system
additional data generation ). This can include : sending shares (e.g. , external system 104 shown in FIG . 1 ) , sends a request
of secret data ( e.g. , message signing key, nonce ) to other to a system (e.g. , issuer 111 , message signing system 112 ) to
participants , wherein the other participants perform a com- allocate a message signing private key for a user account
putation , shards and encrypts the result to the other n 55 associated with the client system (e.g. , a cold storage sys
participants, and returns the encrypted shards. For example, tem) . In some implementations, the key allocation request is
this can include having each participant generate a nonce signed by a private authentication key of the client system
and create shares of it to send to other participants. (e.g. , 104 ) . In some variations, in response, the system
Throughout the method , cleartext versions of some or all associates a message signing private key with the client
secret data (e.g. , message signing key, message signing key 60 system's authentication public key corresponding to the
shares, nonce , etc.) can be deleted after encryption or authentication private key. In some variations, the system
otherwise managed. can optionally provide the client system with a notification
Generating a private key S210 functions to generate a that the message signing keys have been assigned to the
message signing private key ( sk) . In a first variation, the authentication public key, provide the client system with the
issuer system 111 performs S210 (e.g. , in a secure , offline 65 message signing public key, and / or provide any other suit
key generation ceremony ). In a second variation , one or able response . In some variations, further requests to autho
more systems perform a distributed key generation process rize use of the allocated message signing private key are
US 10,903,991 B1
11 12
authenticated by verifying that the request is signed with the In some variations, generating an integrity key S224
client system's authentication private key. However, any includes generating a key generation ( keygen ) integrity key.
other suitable process can be used for key allocation . In variants , this keygen integrity key can be used to verify
The method can optionally include generating communi- the identify of the system ( or systems ) that generate the
cation keys (e.g. , authentication keys, encryption keys , 5 message signing key (or key shares ). In a first example, the
integrity key, etc.) (e.g. , at S222 , S223 , and S224 ) used to keygen integrity key identifies the issuer system 111 as the
securely provide the signing secrets ( and additional signing Insource of the message signing private key ( and key shares).
a second example, the keygen integrity key identifies
data ) to participants ( via participant systems 114 - c ) , and
used to securely provide additional signing data and partial 10 participants
emony that
used during a distributed key generation cer
for generation of the message signing private
signatures to the message signing message signing system key ( and key shares ). In variants, the signing secrets are
112. In variants, the generated communication keys gener considered valid if the corresponding ciphertext decrypts
ated are used to provide secure broadcast communication using the keygen integrity key. In some implementations,
between participant systems, and the message signing mes S224 includes generating a key generation integrity key pair
sage signing system 112 (and optionally the issuer system 15 that includes a public keygen integrity key (PKxG) and a
111 ) . In some implementations, at least a portion of the private keygen integrity key ( skxG ). The keygen integrity
communication keys are generated during generation of key can be generated before or during the key generation
signing secrets S220 . However, the communication keys can ceremony (e.g. , and used to encrypt the message signing key
be generated at any suitable time (e.g. , before receiving a shares during the key generation ceremony ), or be generated
message signing request, after receiving a message signing 20 after.
request but before splitting the message signing key into Generating the signing secrets S220 functions to generate
shares , after splitting the message signing key into shares , signing key shards, each encrypted to a specific participant.
etc. ) . In some implementations, the issuer system 111 gen- In a first variation , the issuer system 111 performs S220 . In
erates at least a portion of the communication keys ( e.g. , all a second variation , one or more systems perform a distrib
or some ) . However, any suitable system ( or combination of 25 uted process ( e.g. , an online process ) to generate the signing
systems ) can generate the communication keys (e.g. , at secrets. However, the message signing secrets can be gen
S222 , S223 , and S224 ) . erated in any suitable manner.
The communication keys can be securely distributed to Generating signing secrets can include: splitting the mes
one or more of the message signing system 112 and partici- sage signing key S221 and encrypting the shares S225 , but
pant systems 114a - c in any suitable manner. In some varia- 30 can additionally or alternatively include any other suitable
tions , at least a portion of the generated communication keys process.
( e.g. , private keys or corresponding public/private key pairs ) S220 can include S221 , which functions to split the
are injected into one or more HSM (Hardware Security message signing key. In a first variant, splitting the message
Module ) devices. Such HSM devices can then be commu- signing key includes splitting the message signing private
nicatively coupled (or electrically coupled ) to a respective 35 key ( sk ) generated at S210 . In a second variant, splitting the
participant system (or the message signing system 112 ) . message signing key includes splitting the expanded private
Additionally, or alternatively, one or more communication key ( epk ) generated at S211 .
keys can be encrypted with an import key to later be In some variations, the message signing key is split into
imported into the destination system ( e.g. , participant sys- n shares or shards (k? , kn ), wherein t of the n shares are
tem , message signing system) . 40 required to recover the message signing key. In variants, the
In variants, the generating communication keys includes number n is a predefined number (e.g. , a configurable
one or more of generating authentication keys , generating number, a hardcoded number, etc. ). Additionally, or alter
encryption keys, and generating an integrity key. natively, the number n can be specified in a key allocation
In some implementations, generating authentication keys request ( e.g. , as shown in FIG . 6 ) or otherwise determined .
S222 includes generating public and private key pairs . In 45 The message signing key can be split using Shamir's Secret
some implementations, S222 includes generating a server Sharing ( SSS ) or another secret sharing algorithm . In a
authentication key pair that includes a public authentication specific example, the Shamir’s Secret Sharing process is
key (AK ,) and a private authentication key (ak ) for the performed over a finite field modulo a number ( Zq) , wherein
message signing system 112. In some variations, the server's the modulus is an order (q) of the base point ( G) of the
public authentication key (AK ,) and private authentication 50 elliptic curve used to generate the public key (PK) . How
key (aks) are provided to the message signing system 112 . ever, the message signing key can be split in any suitable
In some implementations, S222 includes generating a par manner.
ticipant authentication key pair that includes a public In some implementations, S221 includes generating sign
authentication key ( AK ) and a private authentication key ing secret sharing proof for the message signing key shares .
( ak ,) for each participant system p (e.g. , 114a -c) . In some 55 The signing secret sharing proof is a set of data that is used
variations, each authentication key pair that includes the to verify that a message signing key share is actually a share
participant system public authentication key (AK , ) and the of the message signing key. By using the signing secret
private authentication key (ak ) is provided to the associated sharing proof, a recipient of a signing secret ( generated at
participant system p ( e.g. , 114a - c ). S220 ) can verify that the share is a valid share for the
In some variations, generating participant encryption keys 60 message signing private key. The proof is preferably gen
S223 includes generating a participant encryption key pair erated using VSS , but can alternatively be generated using
that includes a public encryption key ( ENK ,) and a private any other suitable proof algorithm . The proof is preferably
encryption key (enk ) for each participant system p ( e.g. , generated using the message signing key ( sk) or the
114a - c ) . In some variations, each participant encryption key expanded signing key ( epk ), but can alternatively be gen
pair that includes the participant system public encryption 65 erated using any other suitable data .
key ( ENK , ) and the private encryption key ( enk ,) is pro- The proof can be generated concurrently, before, or after
vided to the associated participant system p (e.g. , 114a - c ) . message signing key splitting using the same or different
US 10,903,991 B1
13 14
instance of the message signing key. In one example, the (PKxG ) ( e.g. , as the sender's authentication key ) to generate
signing key ( sk or epk ) is split into t of n shares and VSS an encrypted private key share ( c ; ) . In some variations, each
proofwith ((k ;, ... , km ) V ) = VSS ( epk , t , n) , with the secret share is encrypted to a specific participant. In some varia
signing proof represented as : V = { V ;= a G } jeld tions , each share is encrypted to a specific set of participants,
In some implementations, the Verifiable Secret Sharing 5 wherein encrypting a share to a set of participants includes
process is performed over a finite field modulo a number encrypting the share to each participant in the set of m
( Za ) , wherein the modulus is an order (q) of the base point participants (thereby generating m encrypted versions of the
( G ) of the elliptic curve used to generate the public key ( PK) . same share ). The shares can optionally be encrypted based
In some implementations, the Verifiable Secret Sharing on additional information, such as an identifier for a key
(VSS ) process is a Pedersen's Verifiable Secret Sharing 10 share ( e.g. , ciphertext type ) , the public key of the keygen
process. In some implementations, the Verifiable Secret integrity key, the participant’s public authentication key, the
Sharing (VSS ) process is any suitable type of secret sharing signing public key, the VSS proof, and /or any other suitable
process. additional information . The additional information can
In some implementations, the shares ( k ;, . kn ) are optionally be used to verify or identify the encrypted private
encoded in big -endian bytes as as s ; = y :||X ; where y uses a 15 key share .
fixed - bit length encoding ranging from [ 0 , q ) and x is a In some implementations, encrypting the shares includes :
single byte which ranges from [ 1 , n + 1 ] , wherein “ x |ly ” for each share ( s :) , encrypting the share by using a public
represents the concatenation of byte sequences x and y, and authentication key ( e.g , PKxG ) ( e.g. , the keygen integrity
wherein q is the order of the base point (G) of the elliptic key ) of the sending system sending the share ( e.g. , the issuer
curve used to generate the public key (PK) . However, the 20 participant
system 111 )receiving
, a publicthe
authentication key (e.g , AKpi) of the
share ( e.g. , a participant pi associ
shares can be encoded in any suitable manner.
Encrypting the shares S225 functions to encrypt each ated with the share ), a public encryption key (e.g. , ENKpi)
message signing key share to a specific participant. The of the participant, and optionally an a public ephemeral
shares can be encrypted to a participant in a 1 : 1 , 1 : m , or m : 1 encryption key ( e.g., EK ,) generated by the sending system .
shares :participants relationship , or any other suitable rela- 25 In an example, the aforementioned keys are used to generate
tionship . In some variations, encrypting the shares at S225 an encryption key ( e.g. , a symmetric key ) shared between
includes encrypting the shares (k?, ... , kn) generated at the sending system and the respective participant. In an
S221 to generate encrypted shares (C1 , Cn ). Each example , each share is preferably encrypted to a specific
encrypted share c ; is preferably encrypted to a different participant using AKE and AEAD , but can be encrypted in
participant ( e.g. , wherein the participant group includes n 30 any other suitable manner .
participants ), but can alternatively be encrypted to a partici- In a specific example , generating an encryption key
pant shared with another encrypted share. shared between the sending system and the respective par
Encrypting the shares S225 can include: identifying a ticipant includes deriving the encryption key by performing
participant to encrypt to , determining the participant key set an Elliptic - Curve Diffie -Hellman ( ECDH ) process by using
( or public keys thereof) associated with the identified par- 35 the public keygen integrity key ( PKKG) as the issuer system
ticipant, and encrypting the message signing key share using 111's public key and by using the public authentication key
the participant key set . ( AK ) generated for the participant system at S222 .
The participants can be identified in any suitable manner. In some implementations, generating an encryption key
In some implementations, participants are identified based shared between the sending system and the respective par
on one or more of configuration , hardcoded data, or data 40 ticipant is performed as follows:
received via a key allocation request (e.g. , the key allocation DH1 = DH (PKKGENKP)
request shown in FIG . 6 ) . DH2= DH (EK , AK )
In variants , identifying participants includes identifying DH3= DH ( EK ,,ENKp)
participant systems ( e.g. , 114a - c) for each identified partici- shared encryption key =KDF (DH1||DH2||DH3)
pant system . Identifying a participant system can include 45 In some implementations, PKKG , ENKP, EK , and AK ,
identifying one or more of the following for each participant are all public keys known to both the sending system and the
system : a message signing application endpoint identifier respective participant, whereas the private keys correspond
( e.g. , an application level identifier that identifies a process ing to each of PKKG and EK , are known only to the sending
running on a participant system ), a physical layer network system , and the private keys corresponding to each of ENKps
address (e.g. , a MAC address ), a network layer address (e.g. , 50 and AK , are known only to the participant ( and optionally
an IP address ), a port number ( e.g. , a TCP port number ), a the system that generates the private keys corresponding to
session identifier, a communication link identifier ( for a each of ENK ,, and AK ) .
persistent communication link ), a security token , a partici- In some implementations, the sending system (e.g. , 111 )
pant identifier (e.g. , user name, login credentials, etc. ) , an calculates DH1 by using ENK , and the private key corre
account identifier, and the like . However, participant sys- 55 sponding to PKKG, and the participant system for the par
tems and participants can otherwise be identified . ticipant p , calculates DH1 by using PKKG and the private key
The participant key set can be : retrieved from storage of ENK ,
( e.g. , local storage , remote storage ) , received from the In some implementations, the sending system calculates
participant, or otherwise determined. DH2 by using AK , and the private key corresponding to
In variants, the participant key set includes at least one of 60 EK , and the participant system for the participant p , calcu
a participant system public authentication key ( AK ) a lates DH2 by using EK , and the private key of AK ..
public encryption key (ENK .) for each identified partici- In some implementations, the sending system calculates
pant. DH3 by using ENK , and the private key corresponding to
In some implementations, encrypting the shares includes: EK ;, and the participant system for the participant p , calcu
for each share, encrypting the share to a participant i using 65 lates DH3 by using EK , and the private key of ENK ,.
the participant's public authentication key, the participant's In some implementations, encrypting the shares includes :
public encryption key, the public keygen integrity key for each share (k; ) , encrypting the share k; as described
US 10,903,991 B1
15 16
herein to generate the share ciphertext (C ; ) , and combining the partial signature. For example, if the public authentica
the resultant encrypted share c ; with the associated data ( e.g. , tion key AKpi is associated with index i at the message
wherein the associated data can be provided as cleartext). In signing system 112 , and the partial signature ( s ) provided by
this variation , the associated data can be included as part of participant p , is signed by using the associated private
the encryption process, or be appended after k; encryption . 5 authentication key akpi, then the message signing system can
In some implementations, encrypting the shares includes : identify the partial signature ( s:) as being the in partial
for each share (k;), combining the share k , with associated signature , by verifying the signature with the public authen
data, and encrypting the combined data ( as described herein ) tication key AK
to generate an encrypted share c ;: In variants, the signing secrets (cy ) ( generated at S220 and
In some implementations , encrypting the shares includes : 10 stored at $226) can be updated to improve security . For
for each share ( k ; ), encrypting the share k? under the shared example, to protect against a threat that several of the
encryption key (e.g. , generated as described herein ) to
generate an encrypted share c ; (e.g. , share ciphertext c ;) and participant
secrets can
systems have been compromised, the signing
be updated such that any information that an
combining the encrypted share with associated data . attacker obtains from a compromised system will no longer
In some implementations, the associated data includes the 15
public keygen integrity key ( PKKG ) and the participant's be useful for message signing . In some variations, to protect
authentication key AK ,. In some implementations, the asso reagainst such attacks, the signing secrets can be updated ( e.g. ,
-encrypted to new participant keys ; reconstructed, re -split,
ciated data includes the signature verification key PK . In
some implementations, the associated data includes the and re -encrypted; funds transferred to another PK , etc. ) . The
signing secret sharing proof (e.g. , the VSS proof û gener- 20 signing secrets (C:) can be updated periodically, in response
ated at S221 ) . In some implementations, the associated data to detection of a threat, in response to a command , or in
includes a participant broadcast round identifier that identi- response to any suitable trigger or event .
fies the secret share as being broadcast to each participant in Updating the signing secrets can include accessing (or
at least a first broadcast round . restoring ) the message signing private key generated at
In a specific example, the shares (of the private message 25 S210 , and re -splitting the message signing private key into
signing key ) can be encrypted using : shares as described herein for S221 . The shares can be
C = AES (3DH ( PKKG ,AKPP is ENK PIS ki, ciphertext encrypted to a set of participants (as described herein for
type ||PKxG||AK |||PK ||V ) S225 ) . The set of participants can be the pervious set of
However, c ; can be otherwise generated. participants. Alternatively, the shares can be encrypted to a
In variants, the signing secrets generated at S220 (e.g. , the 30 different set of participants (e.g. , a set of participants that
encrypted shares c , encrypted at S225 , and optionally the excludes participants that are believed to have been com
associated data ) are stored at S226 . In some variations, the promised ). Once encrypted , the encrypted updated shares
sending system ( e.g. , the issuer system 111 ) stores the can be stored at the messaging signing system 112 ( as
encrypted signing secrets ( signing key share ciphertext) (c ; ) described herein for S226 ) . The old signing secrets can be
( and optionally the associated data ) in association with the 35 deleted at the message signing system 112 , deprecated, or
signature verification key PK generated at S212 . Addition- otherwise excluded from message signing operations. In this
ally or alternatively, the signing secret ( c ; ) can be stored in manner, the data needed to perform message signing can be
association with the respective participant ( p :). In some updated such that compromised data can be invalidated ,
variations, the sending system stores the encrypted signing without rotating the message signing private key. In this
secrets ( cy ) at the message signing system 112 , or in storage 40 manner , message signing private key can still be used
accessible by the message signing system 112. In some without being rotated . Alternatively, the signing secrets (c ; )
variations, the sending system stores the encrypted signing can be re -encrypted using new participant keys assigned to
secrets ( cy ) at a respective participant system Pi . The ency- the participants of the respective participant group . How
pted signing secrets ( c ; ) are preferably stored online ( e.g. , in ever , the signing secrets (c , ) can be otherwise updated .
Internet- or externally -connected storage ), but can alterna- 45 In variants, the participants can perform proactive secret
tively be stored offline (e.g. , in cold storage , etc.) in geo- sharing to protect against security threats ( e.g. , at S240 ) ,
graphically distributed storage , or otherwise stored . without requiring access to the message signing private key.
In some variations, the sending system stores information In some variations, the issuer system 111 performs at least
at the message signing system 112 that associates a partici- a portion of S221 - S226 . In some variations , the participant's
pant system i with a particular share ( c ; ) . For example, each 50 local system (e.g. , user device, HSM , etc. ) performs at least
encrypted message signing key share ( c; ) can be stored at the a portion of S221 - S226 .
message signing system 112 in association with the public FIG . 8 is an example of a key generation flow for a single
authentication key AK , associated with the key share ( c ; ) . message signing key and participant set, in accordance with
Additionally, or alternatively, the message signing system variations. As shown in FIG . 8 , the expanded private key
112 can store information identifying each participant sys- 55 ( esk ) is split ( S210 ) , authentication keys ( S222 ) and encryp
tem with the associated message signing key share ( c ; ) . tion keys ( S223 ) are generated for a plurality of participant
However, message signing key shares ( c ; ) can be associated systems , the private key shares are encrypted to specific
with participants and / or participant systems 114a - c in any participants ( S225 ) , and the encrypted private key shares are
suitable manner, such that during message signing the stored ( S226 ) . The private key shares can optionally be
message signing system 112 can broadcast the message 60 encrypted to (or otherwise associated with ) the key genera
signing key shares ( c :) to the appropriate participant systems tion ceremony instance via an integrity key for the key
( e.g. , during the first broadcast round ). In variants, the generation ceremony.
message signing system 112 can store information associ- Processing a signing request by using the stored signing
ating an index with each participant, such that the message secrets S230 functions to cooperatively generate a signature
signing system 112 can identify the index i of a partial 65 for a message in a distributed manner . FIG . 7 is a represen
signature received from a participant system by based on the tation of an exemplary signing flow , in accordance with
authenticated identity of the participant system that provides variations . FIG . 9 is a representation of a message signing
US 10,903,991 B1
17 18
flow for a single message , using a single split (or sharded ) and all signing secrets stored by the message signing system
message signing key, in accordance with variations. 112 are associated with the single verification key PK . In
As shown in FIG . 11 , processing the signing request S230 some implementations, the message signing system 112
can include one or more of: receiving a signing request for stores signing secrets for a plurality of signature verification
a message S231 ; accessing stored signing secrets S232 ; 5 keys ( PK) , the signing system 112 stores signing secrets in
providing the respective signing secret to each of a set of association with a respective verification key PK ; accessing
participant systems S233 ; accessing additional signing data the stored signing secrets includes accessing the signing
( e.g. , nonce shares) generated by other participants S234 ; secrets stored in association with a signature verification key
generating a signature based on the additional signing data PK identified in the signing request.
( e.g. , encrypted to the receiving participant) $ 235 , and 10 S232 functions to access signing secrets for the signing
providing the generated signature S236 . request received at S231 . In some variations , each signing
Additionally or alternatively, processing the signing secret c ; is encrypted to a participant Pi , and for each signing
request S230 can include : optionally receiving a signing secret c ; the server stores participant information for the
notification ; requesting the message and the encrypted sign- related participant system ( e.g. , 114a - c ) with the signing
ing secrets encrypted to the participant; decrypting the 15 secret ci . In some implementations, the message signing
encrypted signing secret S310 ; optionally verifying the system 112 uses the stored participant information to pro
validity of the signing secret and aborting if validation fails vide each signing secret c ; to the participant system of the
S320 ; generating additional signing data S330 ; splitting the respective participant Pi :
additional signing data into additional signing data shares In some variations , S233 includes, for each signing secret
S340 ; encrypting each additional signing data share to a 20 corresponding to the signing request, providing the signing
different participant ( e.g. , of the participant group ) S350 ; secret c ; to respective participant system p ; along with the
and storing the additional signing data shares S360 ( e.g. , at signature verification key PK and the message m associated
the message signing system 112 ) as shown in FIG . 3 . with the signing request. In some implementations, the
Processing the signing request S230 can additionally or message signing system 112 provides each signing secret c ;
alternatively include : after a first quorum of additional 25 to the respective participant system in a payload signed with
signing data has been reached, at a participant system of the the server's private authentication key ( aks) ( generated at
participant group: accessing the participant's the encrypted S222 ) . In some implementations, providing the signing
signing secretc, ( S410 ) ; decrypting the participant's secrets to the participant systems at S233 is a first broadcast
encrypted signing secret c ; ( S420 ) ; verifying the validity of round (e.g. , signing round) in the signing process that
the signing secret ( aborting if validation fails) ( S430 ) ; 30 includes a plurality of broadcast communication rounds for
accessing the additional signing data shares bij encrypted to sending data from the message signing system to the par
the participant system p ; by the one or more other participant ticipant systems .
systems Pi ( S440 ) ; decrypting each encrypted additional In some variations, the signing secret sharing proof ( e.g. ,
signing data share by, ( S450 ) ; aggregating the decrypted VSS proof) for the signing secret is provided to the partici
additional signing data shares ( e.g. , nonce,j) ( S460 ) ; gener- 35 pant system along with the signing secret. In some varia
ating a partial signature by using the decrypted additional tions , the additional information for the signing secret is
signing data shares (nonce ;;) ( S470 ) ; and optionally provid- provided to the participant system along with the signing
ing the partial signature ( e.g. , to the message signing system secret. In some variations, the index i for the signing secret
112 ) ( S480 ) , as shown in FIG . 4 , wherein a threshold is provided to the participant system along with the signing
number of partial signatures are aggregated into a valid 40 secret.
signature in S235 . Participant systems 114a receiving signing secrets at S233
However, the signing request can be otherwise processed . can include : participant systems managed by humans, and
All or a portion of S230 can be performed by the message participant systems managed by server ( s) of the signing
signing system 112 (e.g. , S231-236 ) , a participant system system 110 ( e.g. , server participants; system servers func
( e.g. , S310 - S360 , S410 - S480 ) , and / or any other suitable 45 tioning as participants and holding participant authentication
system . keys and / or participant encryption keys ; etc. ) , and / or par
Receiving the signing request S231 functions to receive a ticipant systems managed by any other suitable entity or
request to sign a message (m) . The signing request can be system . The server participants can be : centralized , distrib
received by the message signing system 112 , a participant uted, or otherwise related . In some variations , a total number
system 114 , and / or any other suitable system . The signing 50 of human -managed participant systems (h) is selected ; a
request can be received from an external system (e.g. , 104 ) minimum number of required human -managed participant
via the API system 113 , from a client of the message signing systems ( q) is selected ( wherein h >=q) ; a number of server
system 112 , be generated by the message signing system managed participant systems ( s ) is calculated based on h and
112 , or received from any other suitable endpoint. The q ; a minimum number of shares ( t) to reconstruct the
external system can be a digital wallet , a cold storage 55 message signing private key is calculated based on q and s ;
computing system (CSS ) , or any suitable type of system . and the total number of shares ( n ) is calculated based on h
The signing request can include or identify: a message m to and s .
be signed, the signature verification key (PK) (e.g. , such that In some variations, s is calculated as follows: s = h - q + 1.
the request is a request for a signed message that can be In some variations, t is calculated as follows: t=q + s .
verified by the signature verification key (PK) ) , the block- 60 In some variations, n is calculated as follows: n = h + s .
chain that the message should be sent to , an expiration time , However, s , t , and n can be otherwise determined . Vari
other metadata ( e.g. , message source , message generation ants of the system and method using server participants can
time , etc. ) , and / or any other suitable information . automatically determine: the number of server participants,
S232 functions to access stored encrypted signing secrets shares required to reconstruct, and the total number of shares
( c ) that are associated with the signing request. In some 65 required ( e.g. , based on the number of human participants
implementations, the message signing system 112 stores and user -specified or automatically determined quorum );
signing secrets for a single signature verification key PK , and can optionally automatically split the message signing
US 10,903,991 B1
19 20
key ( e.g. , in S220 ) and / or generate authentication and Decrypting a signing secret S310 can include deriving the
encryption keys for the human and server participants based shared encryption key used at step S225 (e.g. , using AKE )
on the automatically determined values above . and using the derived encryption key to decrypt the signing
S234 functions to access additional signing data generated secret. In some variations, the decrypted signing secret
by at least t of n participants. The additional signing data is 5 includes a message signing key share generated at S221 . In
preferably data related to a nonce (e.g. , a nonce share ), but some variations , S310 includes accessing the key share
can alternatively be related to a cryptographic seed or any secret sharing proof generated at S221 , and using the key
other suitable additional signing data required by the signing share secret sharing proof to verify the decrypted signing
protocol. In variants, one or more participant systems gen secret (e.g. , to verify that the share is in fact a share of the
erates a portion of the additional signing data (e.g. , an 10 message signing private key ). In some variations, the
additional signing share ) by using information sent to the
participants by the message signing system 112 in the decrypted signing secret includes the additional information
for the signing secret.
current broadcast round (e.g. , the encrypted share c ;, the In some variations, deriving the shared encryption key
decrypted share s? , the signature verification key , the key includes: calculating
share secret sharing proof, the message to be signed, etc. ). 15 data source accessibleDH1to bytheusing PKKG (stored
participant systemin) aand
trusted
the
Participant systems can generate the additional signing data private key of ENK , ( which is securely stored for the
in response to user input ( e.g. , input identifying user autho participant system ); calculating DH2 by using EK , ( stored in
rization ), or automatically (without requiring user input to a trusted data source accessible to the participant system)
authorize generation of the additional data ). and the private
In some variations, a participant system for participant p : 20 participant systemkey);ofcalculating
AK , (whichDH3is securely
by usingstored
EK, and for the
the
generates additional signing data (e.g. , a nonce share ) by
using the signing secret ci , signature verification key PK , private key of ENK ,; generating a byte sequence by con
and the message m provided by the server 111 at S233 . In as a result DH1
catenating | DHŽ | DH3 ; and deriving the encryption key
of KDF (DH1||DH2||DH3 ).
variants , a random nonce seed is also used to generate the In some variations, key share secret sharing proof is a
additional signing data
perform nonce generation .
. Any set of t of n participants can 25 VSS proof, and verifying the validity of the signing secret
( S320 ) includes verifying the VSS proof (
In some implementations, a participant system for par V = { V ;=a,G } jelu {a ,G , a,G ... , _,G }) for the decrypted
ticipant Pi generates additional signing data by using a signing secret. In some variations, each Vj of the VSS proof
signed payload received from the message signing system
112. The signed payload is signed by the message signing 30 thea sharing
system's private authentication key ( ak ) (generated at
is commitment value , used
polynomial and each a ;, is thethe
for splitting j -thmessage
coefficientsignof
ing key into shares and G is the base point of the elliptic
S222 ) and includes the signing secret ci , signature verifica curve used to generate the signature verification key. In
tion key and the message m (and optionally the addi some variations, verifying the validity includes verifying the
tional information and / or a key share secret sharing proof ). signing secret k by checking the equality for je [ t ] :
In some implementations, the participant system for P ; 35
verifies that the payload's signature is valid by using the
server's public authentication key (AK ) ( generated at
S222 ) . If the signature is invalid , P ; aborts the message kk ;; GG ==
signing process . j=0
Generating the additional signing data can include at least 40 V ;. j = ( a.G.1°) + (a1G.it ) + ... + (Qz-1G .; -1)
one of, by a participant system p ;: decrypting the encrypted
signing secret c ; ( S310 ) ; optionally verifying the validity of
the signing secret ( aborting if validation fails) ( S320 ) ; wherein values for a , G , a ,G ... , 24-1G are provided by
generating additional signing data ( S330 ) ; splitting the addi- the VSS proof, and wherein i is the index of the signing
tional signing data into additional signing data shares 45 secret that is associated with the participant system ( e.g. , by
( S340 ) ; encrypting the additional signing data shares ( S350 ) ; information stored at the message signing system 112 , and
and storing the additional signing data shares ( S360 ) , as optionally provided by the message signing system 112 to
shown in FIG . 3. However, additional signing data can be the participant system) . In some variations, verifying the
otherwise determined . In some implementations, storing the validity includes verifying that the signature verification key
additional signing data shares ( S360 ) includes storing the 50 PK equals the free - coefficient commitment Vjo in V ;.
encrypted nonce shares bij at the message signing system In a first variation, generating additional signing data
112. In some variations, steps S310 - S360 are performed by ( S330 ) includes : generating a random number (e.g. , a
a participant system 114. This process is preferably per- nonce) .
formed by at least t participant systems ( e.g. , concurrently, In a second variation , generating additional signing data
within a predetermined time threshold ), but can alternatively 55 ( S330 ) includes : generating the data by performing a dis
be performed by less . However, S310 - S360 can otherwise be tributed key generation process .
performed. In a third variation , generating additional signing data
Decrypting a signing secret S310 with a participant sys- ( S330 ) includes : generating the additional signing data
tem for p ; can include decrypting the encrypted signing based on the signing secret k; and / or the signing secret with
secret by using the private authentication key (akpi ) for the 60 additional info . In a specific example , the additional signing
public authentication key (AKpi ) associated with the data is generated by : generating a random nonce seed ( e.g. ,
encrypted signing secret (e.g. , identified by the associated a 32 -bit nonce seed , generated using ri< $ { 0, 1 } 32 ) , and
data for the signing secret ). In variants , participant system calculating the nonce :
for p ; uses one or more of the participant Pi's private signing r; =HKDF ( signing secret||nonce seed , broadcast round
key ( enkpi), the public keygen integrity key PKxg , and /or a 65 identifier||PK ||m )
public issuer ephemeral key ( EK ) to decrypt the encrypted wherein the broadcast round identifier (e.g. , “ 2 ” ) can be
signing secret. different from the message signing key broadcast round
US 10,903,991 B1
21 22
identifier ( e.g. , “ 1 ° ). In variants, the broadcast round iden- Pi generating the additional signing data share derives a
tifier identifies the broadcast round in which the generated shared encryption key for encrypting the data to a participant
additional signing data is broadcasted from the message system P , by : calculating DH1 by using the private key of
signing system to other participant systems. AKpi (the authentication key of participant system P;) and
In some variations , generating additional signing data 5 ENK ,; (the public encryption key for participant system P ;);
( S330 ) includes : generating a nonce public key pair that calculating DH2 by using the private key of EKi (the
includes a generated nonce and a nonce public key R. In ephemeral key for participant system P ;) and AKpj ( the
some implementations, generating the nonce public key R
includes performing scalar multiplication of the nonce nonce authentication key of participant system P ;); calculating
by the base point G used to generate the signature verifica- 10 a byte sequence private
DH3 by using the
by
key of EKp and ENK / generating
concatenating DH1||DH2||DH3; and
tion key ( at S212 ) (e.g. , R = nonceG ). deriving the encryption key as a result of KDF
In some variations, generating additional signing data (DH1 | DH2 | DH3 ) .
( S330 ) includes: generating a random number, and multi
plying the random number by one of two challenges to ingIn data some implementations, encrypting the additional sign
shares includes : for each share ( e.g. , nonce; ) ,
produce a nonce . 15
In some variations, a subset of participants (of the set of tion encrypting the share ( e.g. , nonce ;) with the shared encryp
participants ) each generate a different additional signing key ( e.g. , generated at S350 ) , and combining the
data ( e.g. , based on the decrypted key share k?, based on the resultant encrypted share b ; with the associated data ( e.g. ,
message m , etc. ) , wherein the respective additional signing wherein the associated data can be provided as cleartext). In
data share ( r;) is encrypted to each participant ( pj) of the set 20 this variation , the associated data can be included as part of
of participants to generate an encrypted additional signing the encryption process , or be appended after encryption .
data share ( b ;) for each participant of the set of participants In some implementations, encrypting the additional sign
(b1 , ... bn ) , associated with the respective additional signing ing data shares includes : for each additional signing data
data share . In variants, the additional signing data is gener- share (e.g. , nonce ;), combining the share ( e.g. , nonce ;) with
ated based on a secure distributed key generation protocol 25 associated data, and encrypting the combined data under the
( e.g. , such that the additional signing data generated by shared encryption key (e.g. , generated at S350 ) to generate
different participants within the same participant set are an encrypted share b ;
related ), but can be generated using any other suitable In some implementations, encrypting the shares includes :
method . The additional signing data can be : randomly for each share ( e.g. , nonce ;), encrypting the ( e.g. , nonce;)
generated, generated using a Monte Carlo method ( e.g. , LDS 30 under the shared encryption key (e.g. , generated at S350 ) to
method ), deterministically generated , or otherwise gener- generate an encrypted share bj . , and combining the
ated . encrypted share with associated data .
In some variations, the additional signing data (e.g. , r; ) is The associated data can include: the ciphertext type ( e.g. ,
split into shares (e.g. , nonce shares ). The additional signing nonce) , AKpi (the authentication key of participant system
data is preferably split using the same t of n configuration as 35 P ; ) and AKpj (the authentication key of participant system
that used for message signing key splitting (e.g. , wherein the 13 ) , the signature verification key PK , the message m , the
splitting configuration can be predetermined or sent to the signing secret sharing proof generated at S340 , and /or any
participants ), but can be otherwise split . For example , split- other suitable information .
ting the additional signing data into shares ( S340 ) includes Each encrypted share bij is generated by the participant
splitting the additional signing data into n shares (e.g. , 40 system p; for each participant system p ;. In one example, the
noncei, ... , noncen ), wherein t of the n shares are required encrypted nonce share is generated using :
to recover the message signing key (as described herein for b = AES (3DH (AK Pi AKP , EKP;), l'ij 2||AKp:||
S221 ) . In some variations, splitting the additional signing AK ||PK ||MV)
data into shares ( S340 ) includes generating a signing secret In some implementations, storing the additional signing
sharing proof that can be used to verify that the shares are 45 data shares ( S360 ) includes storing the encrypted additional
in fact shares of the additional signing data. In variants, the signing data shares bij at the message signing system 112
proof is a VSS proof generated by a VSS process used to (e.g. , sending the additional signing data shares bil ... bin
split the additional signing data into n shares (noncej , to the message signing system 112 for storage ). All shares
noncen ) (as described above , such as for S221 ) . are preferably uploaded ( e.g. , including the share encrypted
In some variations, encrypting the additional signing data 50 to the generating participant (bii ) ; alternatively , only shares
shares ( S350 ) includes: for each participant system for a encrypted to other participants are uploaded .
participant Pi , encrypting the associated additional signing In some implementations, the server S112 stores each
data share (e.g. , nonce;) to participant P ;. In some imple- encrypted nonce shares bij in association with the corre
mentations, encrypting the shares includes: for each share sponding message m and signature verification key PK .
(P :) , encrypting the share by using a public authentication 55 In some implementations, S360 includes the participant
key ( e.g. , AKP:) of the sending system sending the share system Pi signing a payload that includes the additional
( e.g. , participant P ; ) , a public authentication key ( e.g. , AKP;) signing data shares, the signed payload being signed by the
of the participant receiving the share, a public encryption participant system's private authentication key ( akpi ) (gen
key (e.g. , ENKPj) of the receiving participant, and optionally erated at S222 ) . In some implementations, the message
a public ephemeral encryption key (e.g. , EKP:) generated by 60 signing system 112 verifies that the payload's signature is
the sending participant P.;. In an example, the aforemen- valid by using the participant system p ; ' s public authenti
tioned keys are used to generate an encryption key ( e.g. , a cation key ( AKpi) ( generated at S222 ) .
symmetric key ) shared between the sending participant and In some implementations, after accessing ( and optionally
the respective participant. authenticating ) additional signing data shares generated by a
In some implementations, encrypting the shares includes : 65 threshold number (e.g. , t , quorum ) of participants ( at S234
for each share ( p :), encrypting the share by using a shared shown in FIG . 2D ) , a broadcast round begins ( e.g. , second
encryption key. In some variations, the participant system broadcast round ).
US 10,903,991 B1
23 24
Reverting to FIG . 2D , generating a signature S235 func- decrypting the participant's the encrypted signing secret c ;
tions to generate a signature for the signing request ( received ( S420 ) ; verifying the validity of the signing secret ( aborting
at S231 ) by using the stored signing secrets . if validation fails ) ( S430 ) ; accessing the additional signing
In some variations, the signature is an Ed25519 signature . data shares bij encrypted to the participant system p ; by the
In some implementations, the signature is a signature in 5 participant system p ; and each of the other participants Pi
accordance with an EdDSA signature scheme . In some ( S440 ) ; decrypting each encrypted additional signing data
implementations, the signature is parameterized to SHA - 512 share bij ( S450 ) ; aggregating the decrypted additional sign
and Curve 25519. However, the signature can be any suit- ing data shares (e.g. , nonce ; j) ( S460 ) ; generating a partial
able type of signature, including, but not limited to , a signature by using the decrypted additional signing data
Boneh -Lynn -Shacham (BLS ) signature, a Schnorr signature, 10 shares ( nonce ;j) ( S470 ) ; and providing the partial signature
and the like . ( e.g. , to the message signing system 112 ) ( S480 ) , as shown
In some variations, S235 includes two or more participant in FIG . 4. In some variations, steps S410 - S480 are per
systems producing partial signatures for the message iden- formed by a participant system 114. This process is prefer
tified in the signing request. In some implementations, since ably performed by at least t participant systems ( e.g. , con
the message signing private key is split into n shares, t of 15 currently, within a predetermined time threshold ), but can
which are needed for signing, at least t participant systems alternatively be performed by less . The t participant systems
must produce partial signatures. The set of participant sys- generating the partial signatures can be the same as or
tems that provide partial signatures for the message signing different from the participant systems generating the nonce .
can be a different set of participant systems that generate a Decrypting the participant's encrypted signing secret c ;
nonce at S330 . 20 (S420) includes decrypting the encrypted signing secret c ;
In a first variation , generating partial signatures is per- (e.g. , using AKE ; as described herein for S310 ; etc. ).
formed after a first broadcast round (e.g. , a first round in Verifying the validity of the signing secret ( aborting if
which the encrypted signing secrets are broadcasted by the validation fails) ( S430 ) includes : verifying the validity of the
message signing system to each participant system) . In a signing secret (e.g. , using VSS ; as described herein for
second variation , generating partial signatures is performed 25 S320 ; etc.).
after two or more broadcast rounds. In each broadcast round Accessing the additional signing data shares b ;; encrypted
prior to the partial signature generation round , one or more to the participant system P; by the participant system 13
participant systems receive data from the message signing ( S440 ) functions to fetch at least t additional signing data
system 112 , generates data (e.g. , using the data provided by shares ( e.g. , nonce share ciphertexts, encrypted nonce
the message signing system 112 in the current round, or in 30 shares ), each generated by a different participant ( e.g. ,
previous rounds ) , and provided the data generated by the inclusive or exclusive of the instantaneous participant P ; ) .
participant system in that round to the message signing The additional signing data shares can be retrieved from the
system . This data can then be broadcasted by the message message signing system 112 , from the other participants ,
signing system 112 to all the other participant systems in the and / orany other suitable source . The additional signing data
signature generation round, or in a further data generation 35 shares can be retrieved or received: after signing secret
round . In variants, the number of rounds can be based on validation ; in response to a request to the message signing
security constraints, signature protocol requirements, usabil- system ; with the encrypted signing secret; and / or at any
ity constraints, efficiency constraints, and network connec- other suitable time .
tivity constraints, and any other suitable type of constraint. Decrypting each encrypted additional signing data share
In some variations, S235 includes the message signing 40 bij ( S450) with a participant system for P; includes decrypt
system 112 initiating a second broadcast round by providing ing the encrypted additional signing data share by using the
to each participant system p ;: the message to be signed m ; private authentication key ( akpi) for the public authentica
the signature verification key ( PK) ; their respective tion key (AK pi) associated with the encrypted signing secret
encrypted signing secret ci ; and the encrypted additional (e.g. , identified by the associated data for the signing secret ).
signing data shares bij encrypted to the participant pi (by the 45 The participant system for Pi can additionally or alterna
participant system for p ; and each of the other participants tively use one or more of the participant P ; ' s private encryp
P ;). Alternatively, the second broadcast round can be initi- tion key ( enkpi), the public authentication key (AK P;) asso
ated by a participant or another system . In some implemen- ciated with the participant generating the encrypted data, and
tations , at S235 the message signing system 112 provides the a public participant ephemeral key (EK ) ( associated with
message m , the signature verification key ( PK) , and their 50 the participant generating the encrypted data ) to decrypt the
respective encrypted signing secret c ; to the participant encrypted data at S450 .
system for Pi in a payload signed by the message signing Decrypting additional signing data share bij can include
system's private authentication key (ak) ( generated at deriving the shared encryption key used at step S350 and
S222 ) . In some implementations, each participant system using the derived encryption key to decrypt the encrypted
verifies that the payload's signature is valid by using the 55 additional signing data share bij. The shared encryption key
server's public authentication key ( AK ) ( generated at S222 ) can be derived based on b ;;'s associated data (e.g.,ciphertext
( S410 shown in FIG . 4 ) . In some variations, the encrypted type, AK sender, AK recipient, PK , m , proof, etc. ), and / or other
additional signing data shares bij are included in the signed data .
payload . In some variations, the encrypted additional signing data
In some variations, generation of a partial signature by a 60 share bij includes the additional signing data share (e.g. ,
participant system for P ; can be performed in response to nonce; ) generated at S340 . In some variations, the signing
user input ( e.g. , input identifying user authorization ), or secret sharing proof generated at S340 is provided with the
automatically (without requiring user input to authorize encrypted additional signing data share bij.
generation of the a partial signature ). In some variations, deriving the shared encryption key
In some variations, generation of a partial signature by a 65 used at S350 includes : calculating DH1 by using AKpj (the
participant system for p ; includes at least one of: accessing public authentication key of participant system p ;) and the
the participant's the encrypted signing secret c ; ( S410 ) ; private key of ENKpi (the encryption key of the participant
US 10,903,991 B1
25 26
system p :) ; calculating DH2 by using EK pi (the public additional signing data generated in S330 , but can alterna
ephemeral key of the participant system p ; ) and the private tively be the same . Aggregating the additional signing data
key of AKi( the authentication key of the participant system shares (e.g. , decrypted nonce shares) can include calculating
P ; ) ; calculating DH3 by using EKpj and the private key of 5 the aggregated signing data shares according to :
ENKpii generating a byte sequence by concatenating
DH1 | DH2 | DH3 ; and deriving the shared encryption key as 1-1
a result of KDF (DH1|DH2 |DH3 ).
In some variations, S450 includes , for each additional P: = p ;(mod )
signing data share (e.g. , nonce; j), verifying the validity of the
additional signing data share by verifying the signing secret 10
sharing proof included along side the decrypted nonce . This where p , is the aggregated additional signing datum for P ,
is preferably performed after additional signing data share ( e.g., aggregated nonce ) , and p , is the additional signing data
decryption, but can alternatively occur before. In variants , share from each P , that was encrypted to P ;. However, the
the signing secret sharing proof is a VSS proof 15 aggregated additional signing datum can be otherwise deter
(V = {V = G }ke[ ={a,G , G . . . , ,- G } ) . In some mined
implementations, each Vk of the VSS proof is a commitment
.
Aggregating the decrypted additional signing data shares
value , and each ak, is the k - th coefficient of the sharing can optionally include aggregating the public keys of the
polynomial used for splitting the additional signing data additional signing data shares. In one example, this includes
(thee.g.elliptic
, noncecurve
;) into used
sharesto(nonce ;) and G is the base point of
generate the nonce public key.In 20 aggregating the nonce share public keys R. Ina specific
some variations, verifying the validity includes verifying the example, R can be determined using:
additional signing data share by checking the equality for
KE [ t ] : 1-1
25 R = ER;
ML
noncei; G =
k =0
where Rj is the public key for the additional signing data
Vk • i* = (a ,G.;º) + (a1G .; ') + ... + ( Qz- 16.14-1 ) share from each P ;. In a specific example, S460 can output
30 the tuple ( k?, Ôi , R , PK) , which can be used for partial
signature generation.
wherein values for a G , a , G ... , 87-1G are provided by Generating the partial signature S470 functions to gener
the VSS proof, and wherein i is the index of the additional ate pieces of the signature that are invalid in isolation but
signing data share ( e.g., nonce ;) that is associated with the become valid under PK ( e.g. , for m) once a threshold of
participant system (e.g. , by information stored at the mes- 35 partial signatures ( e.g. , t partial signatures) are combined .
sage signing system 112 , and optionally provided by the S470 is preferably performed by participant system P :, but
message signing system 112 to the participant system ). can be generated by other systems . The partial signature is
Verifying the validity can optionally include verifying that preferably generated based on the aggregated additional
there are no duplicate VSS proofs. signing datum ( e.g. , the aggregated nonce ), the public aggre
In some variations, verifying the validity includes the 40 gated additional signing data key ( R ), PK , the message , the
participant system P , verifying that t additional signing data decrypted signing secret ( e.g. , decrypted signing key share
shares (e.g. , t nonce share ciphertexts) have been provided k; ) , and / or other data . The partial signature is preferably
to the participant system Pi . generated after the aggregated additional signing datum is
In some variations, verifying the validity includes veri- generated ( e.g. , immediately after, after a delay ), but can
fying that there are no two additional signing data shares 45 alternatively be generated: after the other participants have
have the same sender public authentication key ( AKpj) (e.g. , generated their respective aggregated additional signing
each share should be from a different participant system , anddatum , after a predetermined event occurrence , and / or at any
if authentication information indicates that one participant suitable time . In a specific example, each participant Pi
system generated two or more of the receive nonce shares , within the second participant set ( e.g. , each participant of t
then the process should be aborted ). 50 participants, part of the second quorum , part of the second
In some variations, verifying the validity includes veri- broadcast round ) calculates si : = ? ; + SHA512 ( R || PK ||m )-k ;
fying that all additional signing data shares have the par- (mod q) , wherein q is the order of the base point G used to
ticipant system's public authentication key (AKP ) as the generate the signature verification key PK , and determines
recipient authentication key (meaning that all received addi- the partial signature as 07 : =R | $ ;, wherein the partial signa
tional signing data shares were intended for the participant 55 ture (s :) can be uploaded to the message signing system 112
system p ). with an identifier for P ;. However, the partial signatures can
In some variations, if any verification step fails, the be otherwise generated .
process is aborted . On the other hand , if verification is In variants, several broadcast rounds are performed to
successful, the verified and decrypted additional signing generate a signature , and in each round the message signing
data shares ( one from a different participant system) are 60 system 112 broadcasts information to each participant sys
aggregated at S460 . tem . In some implementations, after at least a predetermined
Aggregating the decrypted additional signing data shares number (e.g. , t , the number of partial signatures required to
(e.g., nonce ;) (S460 ) functions to generate an aggregated generate a signature ) of participants return additional sign
additional signing datum for partial signing . The aggregated ing data to the message signing system 112 , the message
additional signing datum is preferably specific to Pi , but can 65 signing system initiates another broadcast round ( e.g. , to
alternatively be shared between participants. The aggregated receive further additional signing data from the participant
additional signing datum is preferably different from the systems , or to receive partial signatures from the participant
US 10,903,991 B1
27 28
systems ) . In some implementations, additional signing data In variants, the message signing system 112 initiates
generated in at least one of the broadcast rounds is used to proactive secret sharing by sending each participant system
generate the partial signatures. a request to update their additional signing data shares S241 .
In variants, the participant system Pi generates a partial The update request can be signed by using the authentication
signature S470 by signing the message (to be signed) by 5 private key of the message signing system .
using the signing secret decrypted at S310 and the aggre In some variations, in response to the update request, a
gated additional signing data shares (e.g. , nonce shares participant system ( e.g. , 114a - c) splits a zero (0 ) value into
nonce ) n shares ( zero - value shares ), encrypts the zero - value shares
At S480, the participant system P , provides the generated to each of the participants, and stores the zero - value shares
partial signature to the message signing system 112. In 10 atmentations
the message signing system 112 (S242) . In some imple
, the zero values are split as described herein for
variants, the participant system P , provides the partial sig S340 , encrypted as described herein for S350 , and stored as
nature in a signed payload that is signed by the participant described herein for S360 .
system's private authentication key (akpi) (generated at In response to the zero -value shares from at least a
S222 )
. In some implementations , the message signing sys- 15 threshold number of participants (e.g. , t participants ), the
tem 112 verifies that the payload's signature is valid by using message signing system 112 provides each participant sys
the participant system Pi's public authentication key (AK ) tem with the encrypted additional signing data shares and
( generated at S222 ) . In some variations, the signed payload the encrypted zero - value shares ( from each participant) at
also includes the aggregated nonce public key R. S243 .
Generating a signature based on the additional signing 20 The encrypted zero - value shares and the encrypted addi
data S235 functions to generate a valid signature out of the tional signing data shares are decrypted , as described herein
partial signatures. S235 can include aggregating the t partial for S450 . Each zero - value share is matched with a corre
signatures received from the participant systems , which sponding additional signing data share (e.g. , according to the
functions to generate a signature that verifies under signing participant that generated the share ), and the two shares are
public key PK . S235 can be performed by the message 25 combined (e.g. , added ) S244 . The combined shares are
signing system 112 (e.g. , wherein the message signing encrypted to each of the participants S245 , and stored at the
system 235 receives partial signatures from t participant message signing system 112 S246 . In some implementa
systems ) , by a participant system , and/ or any other system . tions , combined shares are encrypted as described herein for
In some variations , aggregating the t partial signatures S350 , and stored as described herein for S360 . In some
includes aggregating the partial signatures together as 30 implementations, the message signing system 112 replaces
Shamir Shares . In some variations, the message signing the old additional signing data shares with the encrypted
system 112 stores information associating each message combined shares S247 . Since valid aggregated zero - value
signing key share index i with a participant system , and the shares sum to zero , the aggregated value of the updated
key share index i is used to aggregate the partial signatures additional signing data shares does not change. However, if
using the Shamir Sharing reconstruction process as shown 35 a malicious system does not have zero - value shares, then the
below : malicious system will not be able to produce a valid partial
signature (e.g. , a partial signature that can be combined with
other partial signatures to form a valid full signature ).
1-1
However, proactive secret sharing can otherwise be per
S = 40 formed .
i=0 Embodiments of the system and /or method can include
1-1 every combination and permutation of the various system
Si components and the various method processes , wherein one
j = 0,5 or more instances of the method and / or processes described
x ; = r + c.sk
45 herein can be performed asynchronously ( e.g. , sequentially ),
X ; –x; concurrently ( e.g. , in parallel ), or in any other suitable order
by and / or using one or more instances of the systems ,
elements , and / or entities described herein .
In some variations, the aggregate partial signature s , along As a person skilled in the art will recognize from the
with nonce pubkey R , is a valid signature for the public key 50 previous detailed description and from the figures and
PK . In some variations, the message signing system 112 claims , modifications and changes can be made to the
verifies the signature ( R, s ) with message m and PK and preferred embodiments of the invention without departing
verifies that the nonce value R has not been previously used . from the scope of this invention defined in the following
Prior to aggregation , the message signing system 112 can claims .
optionally verify that each partial signature uses the same R 55
value . We claim :
S236 functions to provide the generated signature ( and /or 1. A method for digitally signing messages comprising:
signed message ) to at least one system (e.g. , the external with a secure key generation system , securely providing
system 104 , a blockchain network associated with the mes- encrypted message signing key shares and a key share
sage , etc. ) as a response to the signing request. 60 secret sharing proof to a message signing system ;
In variants, the method 200 includes performing proactive with the message signing system , in a first broadcast
secret sharing S240 to improve security ( e.g. , as shown in round, securely providing to each of a plurality of
FIG . 10 ) . In some variations, performing proactive secret participant systems a message to be signed, the key
sharing includes each participant updating the additional share secret sharing proof, and the encrypted message
signing data shares generated by the participant and replac- 65 signing key share that is encrypted to a message signing
ing the existing additional signing data shares ( stored at the participant of the participant system , wherein each
message signing system 112 ) with the updated shares . participant system for a first set of message signing
US 10,903,991 B1
29 30
participants generates encrypted additional signing data 6. The method of claim 3 , further comprising: with the
shares based on the encrypted message signing key secure key generation system : for each participant in the
share, comprising : participant group ,
decrypting and validating the encrypted message sign- generating a shared symmetric key by using :
ing key share for the participant system , 5 a private authentication key of the secure key generation
generating a nonce seed , and system ,
generating a nonce by using the nonce seed and the the a
participant's encryption public key,
private ephemeral encryption key of the secure key gen
validated and decrypted message signing key share eration system , and
for the participant system ;
with the message signing system , from each participant 10 theencrypting
participant's authentication public key; and
the participant's message signing key share
system for the first set of message signing participants: with the generated shared symmetric key.
securely receiving the encrypted additional signing
data share and a corresponding signing secret sharing eration system is an offline1 , system
7. The method of claim wherein the secure key gen
that is secured from
proof;
with the message signing system , in response to receiving participant system is a mobile devicewherein
15 public communication networks , and at least one
with a persistent
encrypted additional signing data shares from a thresh connection to a public communication network .
old number of participant systems : in a subsequent 8. The method of claim 7 , wherein the message signing
broadcast round, securely providing to each of the system receives the encrypted additional signing data shares
plurality of participant systems the message , the key 20 and the partial signatures in response to at least one autho
share secret sharing proof, each signing secret sharing rization input received from a participant via a user inter
proof, the encrypted message signing key share face .
encrypted to the participant of the participant system , 9. The method of claim 1 , wherein the full signature is an
and each encrypted additional signing data share ED25519 signature, and wherein the encrypted additional
encrypted to the participant; 25 signing data shares are encrypted shares of a nonce .
with the message signing system , from each participant 10. The method of claim 1 , wherein the full signature is
system for a second set of the message signing partici- one of a Boneh - Lynn - Shacham (BLS ) signature, and a
pants : securely receiving a partial signature ; and Schnorr signature.
with the message signing system , in response to receiving 11. The method of claim 1 , wherein the key share secret
partial signatures from the threshold number of partici- 30 sharing proof is a Verifiable Secret Sharing (VSS ) proof, and
pant systems, generating a full signature for the mes- wherein the signing secret sharing proof is a VSS proof.
sage by aggregating the received partial signatures. 12. A method for digitally signing messages comprising:
2. The method of claim 1 , further comprising, with the with a secure key generation system , securely providing
secure key generation system : encrypted message signing key shares to a message
generating a message signing key pair, a plurality of 35 signing system ;
participant authentication key pairs , and a plurality of with the message signing system , in a first broadcast
participant encryption key pairs , each key pair includ- round, securely providing to each of a plurality of
ing a private key and a corresponding public key; participant systems a message to be signed, and the
securely providing at least authentication private keys of encrypted message signing key share that is encrypted
participant authentication key pairs and encryption 40 to a message signing participant of the participant
private keys of participant encryption key pairs to system ;
respective participant systems, with each participant system for a first set of message
splitting a message signing private key of the message signing participants:
signing key pair into a plurality of message signing key generating encrypted additional signing data shares based on
shares and generating the key share secret sharing proof 45 the encrypted message signing key share, comprising:
for the message signing