WO2015160839A1

WO2015160839A1 - A method for secure and resilient distributed generation of elliptic curve digital signature algorithm (ecdsa) based digital signatures with proactive security

Info

Publication number: WO2015160839A1
Application number: PCT/US2015/025804
Authority: WO
Inventors: Karim El Defrawy; Joshua D. LAMPKINS
Original assignee: HRL Laboratories LLC
Current assignee: HRL Laboratories LLC
Priority date: 2014-04-17
Filing date: 2015-04-14
Publication date: 2015-10-22
Anticipated expiration: 2016-10-17
Also published as: CN106664205B; EP3132560A1; EP3132560A4; CN106664205A

Abstract

Described is system for generation of elliptic curve digital signature algorithm (ECDSA) based digital signatures. A. Secret-Share protocol is initialized between a client and a set of servers to share a set of shares of a private key s among the set of servers. The set of servers initializes a protocol to generate a digital signature on a message using the set of shares of the private key s without reconstructing or revealing the private key A. The set of servers periodically initialises a Secret-Redistribute protocol on each share of the private key A- to re- randomize the set of shares. A Secret-Open protocol is initialized to reveal the private key s to an intended recipient, wherein the private key A is used to compute the digital signature.

Description

[00013 A METHOD FOR SECURE AND RESILIENT DISTRIBUTED

GENERATION OF ELLIPTIC CURVE DIGITAL SIGNATURE ALGORITHM (ECDSA) BASED DIGI TAL SIGNATURES WITH

PROACTIVE SECURITY

[0002] CROSS-REFERENCE TO RELATED APPLICATIONS

[0003] This is a Non-Provisional Application of U.S. Provisional Patent

Application No. 61/981,1.91, filed April 17, 2014, entitled,. "A Method for Secure and Resilient Distributed Generatio of Elliptic Curve Digital Signature Algorithm (ECDSA Based Digital Signatures with Proactive Security,⁵ ' the entirety of which is hereby incorporated by reference.

[0004] BACKGROUND OF INVENTION

[0005] (1) Field of Invention

[0006] The present invention relates to a system for generating Elliptic Curve Digital Signature Algorithm (ECDSA) based digital signatures and, more particularly, to a system for generating ECDSA based digital signatures in a distributed maimer.

[0007] (2) Description of Related Art

[0008] Digital signatures are essential to the operation of secure distributed

systems, and authentication and access control. Elliptic Curve Digital Signature Algorithm (ECDSA) based digital signatures, for example, are used to ensure i ntegrity of transmitted data online, can be used for authentication of data and entities online, and are also used, in a variety of digital currency and financial transactions.

[0009] There are a few previous approaches which, describe generati on of digital signatures for secure systems. In Literature Reference No. 15 of the List of Incorporated Literature References, the protocols and algorithms consider onl passive adversaries and do not provide proactive security.

l Passive adversaries are only able to spy on corrupted nodes as opposed to malicious adversaries, which are able to spy on corrapted nodes and cause them to send arbitrary messages as the adversary desires. Proactive security enables the storing of information in a secure, distributed fashion in a hostile environment. In Literature Reference No. 8, the protocols and algorithms consider a threshold of nlZ for malicious adversaries and do not provide proactive security,

[00010] Thus, a continuing need exi sts for a set. of protocols to proactivize the computation and storage of digital signatures with a higher threshold of servers that can be corrupted or compromised while still maintaining confidentiality and correctness of the digital signature.

[0001 1 ] SUMMARY OF THE INVENTION

[00012] The present invention relates to a system for generating Elliptic Curve Digital Signature Algorithm (ECDSA) based digital signatures and, more particularly, to a system for generating ECDSA based digital signatures in a distributed manner. The system comprises one or more processors and a memory having instructions such that when the msir ctions are executed, the one or more processors perform multiple operations. A Secret-Share protocol is initialized between a client C and a set of /? servers, wherein the client C shares a set of shares of a private key s among the set of » servers. The set of n servers initializes a protocol to generate a digital signature on a message m using the set of shares of the private key s' without reconstructing or reveal ng the private ke $. The set of n servers periodically initializes a Secret-Redistribute protocol on each s hare of the private ke .« to re-randomize the set of shares. [00013] In another aspect, a Secret-Open protocol is initialized to reveal the private key s to an intended recipient, wherein the private key _*v is used to compute the digital signature,

[0001 ] In another aspect, in order .for an adversary to retrieve the private key s_t the adversary must compromise a plurality of servers in the set of « servers.

[00015] In another aspec t, a threshold t of up to nil of the set of // servers can be completely corrupted while the confidentiality of the private key s and correctness of the digital signature remain uoconipromised.

[00016] In another aspect, if a majority of the set of shares of the private key s is not corrupted, then the set of n servers jointly restore any corrupted shares.

[00017] in another aspect, corrupted servers are restored to an uiicorrapted state.

[00018] In another aspect, the present invention also comprises a method for causing a processor to perform the operations described herein.

[00019] Finally, in yet another aspect, the present invention also comprises a computer program product comprising computer-readable instructions stored on a non-transitory computer-readable medium that are executable by a computer having a processor for causing the processor to perform the operations described herein.

[00020] BRIEF DESCRIPTION OF THE DRAWINGS [00021] The objects, features and advantages of the present invention will be apparent from the following detailed descriptions of the various aspects of the itvveBtion in conjunction with reference to the following drawings, where:

[00022] FIG. t is a block diagram depicting the components of a system for generating Elliptic Curve Digital Signature Algorithm (ECDSA) based digital signatures according to the principles of the present invention;

[00023] FIG. 2 is an illustration of a computer program product according to the principles of the present invention;

[00024] FIG. 3 is an illustration of a client uploading shares of a private key 5 to a set of servers accordi g to the principles of the present in venti n;

[00025] FIG. 4 is an illustration of the set of servers generating signatures on messages using their shares of the private key ,v without revealing the private key s according to the principles of the present invention;

[00026] FIG. 5 is an illus tratio of the set of servers periodically performing a .Proactive-Refresh protocol to correct any shares thai ma have been corrupted according to the principles of the present invention; and

[00027] FIG. 6 is a flow diagram illustrating distributed generation of elliptic curve digital signature algorithm (ECDSA) based digital signatures with proacti ve security according to the principles of the present invention.

[00028] DETAILED DESCRIPTION

[00029] The present invention relates to a system for generating Elliptic Curve Digital Signature Algorithm (ECDSA) based digital signatures and, more particularly, to a system for generating ECDSA based digital signatures in a distributed manner. The following description is presented to enable one of ordinary skill in the art to make and use the invention and to incorporate it in the context of particular applications. Various modifications, as well as a variety of uses in different applications will be readily apparent to those skilled in the art. and the general principles defined herein may be applied to a wide range of aspects. Thus, the present invention is not intended to be limited to the aspects presented, but is to be accorded the widest scope consistent with the principles and novel features disclosed herein. [00030] In the following detailed description, numerous specific details are set forth in order to provide a more thorough understanding of the present invention. However, it will be apparent to one skilled in the art that the present invention may be practiced without necessarily being limited to these specific details. In other instances, well-known structures and devices are shown in block diagram form, rather than in detail, in order to avoid obscuring the present invention.

[00031 ] The reader's attention is directed to all papers and documents which are filed concurrently with this specification and which are open to public inspection with this specification, and the contents of all such papers and documents are incorporated herein by reference. All the features disclosed in this specification, (including any accompanying claims, abstract, and drawings) may be replaced by alternative features serving the same, equivalent or similar purpose, unless expressly stated otherwise. 11ms, unless expressly stated otherwise, each feature disclosed is one example only of a generic series of equivalent or similar features.

[00032] Furthermore, any element in a claim that does not explicitly state "means for" performing a specified function, or "step for" perforating specific function, is not to be interpreted as a "means" or "step" clause as specified in 35 U.S.C. Section 1 12, Paragraph 6. In particular, the use of "step of or "act of in the claims herein is not intended to invoke the provisions of 35 U.S.C. 1 12, Paragraph 6.

[00033] Please note, if used, the labels left, right, front, back, top, bottom, forward, reverse, clockwise and counter-clockwise have been used for convenience purposes only and are not intended to imply any particular fixed direction. Instead, they are used to reflect relative locations and or directions between various portions of an object. As such, as the present invention is changed, the above labels may change their orientation.

[00034] Before describing the invention in detail, first a list of cited literature references used in the description is provided. Next, a description, of various principal aspects of the present invention is provided. Finally, specific details of the present in vention are provided to give an

understanding of the specific aspects.

[00035] (! ) List of Incorporated Literature References

[00036] The following references are incorporated and cited throughout this application. For clarity and convenience, the references are listed herein as a central resource for the reader. The following references are hereby incorporated by reference as though fully included herein. The references are cited in the application by referring to the corresponding literature reference number, as follows;

1. D. Beaver, Efficient multiparty protocols using circuit randomization. In CRYPTO '91, L CS 576, pp. 420 -432, 1991.

2, Eli Ben-Sasson, Serge Fehr, and Rafail Ostrovsky. Near-linear unconditionally-secure multiparty computation with a dishonest minority. Cryptology ePrint Archive, Report 201 1/629, 201 1. Zuzana Beeriiova-Trubmiova and Martin Hirt. Efficient multiparty computation with dispute control In TCC, pages 305-328, 2006.

Ivan Damgard and Jesper Buns Nielsen. Scalable and

unconditionally secure multiparty computation, in CRYPTO.

pages 572-590, 2007.

Federal Information Processing Standards Publication. The Digital Signature Standard (DSS) (FIPS 386-4).

P. Feldman. A Practical Scheme for on- interactive Verifiable Secret Sharing. In Proc, Of the 2Sth IEEE Symposium on the Foundations of Computer Science, pages 427-437, 1 87.

Steven Goldfeder, Joseph Bonneau, Edward W. Felten, Joshua A . Kroil, Arvind Narayanan, "Securing Bitcoin Wallets via Threshold Signatures".

Ibrahim, M.H.; Ali, LA.; Ibrahim, LL; El-Sawi, A. H,, A robust threshold elliptic curve digital signature providing a new verifiable secret sharing scheme. Circuits and Systems, 2003 IEEE 46th Midwest Symposium on , vol.1 , no., pp.276,280 Vol. 1, 30-30 Dec. 2003.

Amir Herzberg, Stanislaw Jarecki, Hugo Krawczyk, and Moti Yung. Proactive secret sharing or: Bow to cope with perpetual leakage, in CRYPTO, pages 339-352, 1995.

Don Johnson, Alfred Menezes, Scott Vansione, The Elliptic Curve Digital Signature Algorithm (ECDSA), In International Journal of information Security, Volume 1 , Issue 1 , pages 36-63, 2001.

Rafail Ostrovskv and Moti Yung. How to withstand mobile virus attacks, in Proceedings of the tenth annual ACM symposium o Principles of distributed computing, pages 51 -59. ACM Press,

1 91.

Torben P. Pedersen. Non-interactive and formation-iheoretic secure verifiable secret sharing, in CRYPTO, volume 576 of Lecture Notes in Computer Science, pages 129- -140. Springer, 1991.

13. David Schultz. Mobile Proactive Secret Sharing. PhD thesis, Massachusetts Institute of Technology, 2007.

14. Adi Shamir. How to share a secret. Commun. ACM, 22(1 1):612 - 613, 1 79.

15. Hao Wang, Zhongfu Wu, Xin Tan. A New Secure Authentication Scheme Based Threshold ECDSA For Wireless Sensor Network, in Security and Management, pages^'129-133, 2006.

16. Working Draft, American National Standard X9.62- 1998 Public Key Cryptography For The Financial Services Industry: The

Elliptic Curve Digital Signature Algorithm (ECDSA), pgs. 7-13, 1998. [00037] (2) Principal Aspects

[00038] The present invention has three "principal" aspects. The first is a system for generating Elliptic Curve Digital Signature Algorithm

(ECDSA) based digital signatures and, more particularly, to a system for generating; ECDS A based digital signatures in a distributed manner. The system is typically in the form of a computer system operating software or in the form of a "hard-coded" instruction set. This system may be incorporated into a wide variety of devices that provide different functionalities. The second principal aspect is a method, typically in the form of software, operated using a data processing system (computer). The third principal aspect is a computer progra product. The computer program product generally represents computer-readable instructions stored on a non-transitory computer-readable medium such as an optical storage device, e.g., a compact disc (CD) or digital versatile disc (DVD), or a magnetic storage device such as a floppy disk or magnetic tape. Other, non-limiting examples of computer-readable media include hard disks, read-only memory (ROM), and flash-type memories- These aspects will be described in more detail below.

[00039] A block diagram depicting an example of a system (i.e.. computer system 100) of the present in vention is provided in FIG. 1. The computer system 100 is configured to perform calculations, processes, operations, and/or functions associated with a program or algorithm. In one aspect, certain processes and steps discussed herein are realized as a series of instructions (e.g., software program) that reside within computer readable memory units and are executed by one or more processors of the computer system 100. When executed, the instructions cause the computer system 100 to perform specific actions and exhibit specific behavior, such as described herein.

[00040] The computer system 100 may include an address/data bus 102 that is configured to communicate information. Additionally, one or more data processing units, such as a processor 104 (or processors), are coupled with the address/data bus 102. The processor 104 is configured to process information and instructions. In an aspect, the processor 1 4 is a

microprocessor. Alternatively, the processor 104 may be a different type of processor such as a parallel processor, or a field programmable gate array.

[0004.1 ] The computer system 1 0 is configured to utilize one or more data storage unite. The computer system 100 may include a volatile memory unit 10 (e.g., random access memory ("RAM"), static RAM, dynamic RAM, etc) coupled with the address/data bus 102, wherein a volatile memory unit 106 is configured to store mformation and instructions for the processor 1 4. The computer system 100 further may include a non- volatile memory unit 108 (e.g., read-only memory ("ROM"),

programmable ROM ("PROM"), erasable programmable ROM ("EPROM" ), electrically erasable programmable ROM "EEPROM"), Hash memory, etc,} coupled with the address/data bus 102, wherein the nonvolatile memory unit 108 is configured to store static information and instructions for the processor 104. Alternatively, the compoier system 100 may execute instructions retrieved irom an online data storage unit such as in "Cloud" computing- in an aspect, the computer system 100 also may include one or more interfaces, such as an interface 1 1.0, coupled with the address/data bus 102. The one or more interfaces are configured to enable the computer system 100 to interface with other electronic devices and computer systems. The communication interfaces implemented by the one or more interfaces may include wireline (e.g., serial cables, modems, network adaptors, etc.) and/or wireless (e.g., wireless modems, wireless network adaptors, etc) communication technology. In one aspect, the computer system 100 may include an input device 112 coupled with the address/data bus 102, wherein the input device 1 12 is configured to communicate information and command selections to the processor 100. In accordance with one aspect, the input device 1.12 is an alphanumeric input device, such as a keyboard, that may include alphanumeric and/or function keys. Alternatively, the input device 12 may be an input device other than an alphanumeric input device. In an aspect, the computer system 100 may include a cursor control device 114 coupled with the address/data bus 102, wherein the cursor control device .1 14 is configured to communicate user input information and/or command selections to the processor j 00. la an aspect, the cursor control device 114 is implemented using a device such as a mouse, a track-ball, a track-pad, an optical tracking device, or a touch screen. The foregoing

.notwithstanding, in an aspect, the cursor control device 1 14 is directed and/or activated via input from the input device 1 12, such as in response to the use of special keys and key sequence commands associated with the input device 1 12. In an alternative aspect, the cursor control device 1 14 is configured to be directed or guided by voice commands.

[00043] In an aspect, the computer system 1 0 further may include one or more optional computer usable data storage devices, such as a storage device 1 16, coupled with the address/data bus 102. The storage device 1 16 is configured to store information and/or computer executable instructions. In one aspect, the storage device 1 16 is a storage device such as a magnetic or optical disk drive (e.g., hard disk, drive ("HDD"), floppy diskette, compact disk read only memory ( "CD-ROM" ), digital versatile disk ("DVD")). Pursuant to one aspect, a display device I IS is coupled with the address/data bus 102, wherein the display device 1 18 is ■configured to display video and/or graphics. In an aspect, the display device 1 .1 S may include a cathode ray tube ("CRT"), liquid crystal display ("LCD"), field emission display ("FED"), plasma display, or any other display device suitable for displaying video and/or graphic images and alphanumeric characters recognizable to a user. 00044] The computer system 100 presented herein is an example computing environment in accordance with an aspect. However, the non-limiting example of the computer system 300 is not strictly limited to being a computer system. For example, an aspect provides that the computer system 100 represents a type of data processing analysis that may be used in accordance with various aspects described herein. Moreover, other computing systems may also be implemented. Indeed, the spirit and scope of the present technology is not limited to any single data processing environment. Thus, in an aspect, one or more operations of various aspects of the present technology are controlled or implemented using computer-executable instructions, such as program modules, being executed by a computer, in one implementation, such program modules include routines, programs, objects, compooents and/or date structures that are configured to perform particular tasks or implement particular abstract data types. In addition, an aspect provides that one or more aspects of the present technology are implemented by utilizing one or more distributed computing environments, such as where tasks are perforated by remote processing de vices thai are linked through a communications network, or such as where various program modules are located in both local and remote computer-storage media including memory-storage devices.

[00045] An illustrative diagram of a computer program product, (i.e.. storage device) embodying the present invention is depicted in FIG. 2. The computer program product is depicted as floppy disk 200 or an optical disk 202 such as a CD or DVD. However, as .mentioned previously, the computer program product generally represents computer-readable instructions stored on any compatible non-transitory computer-readable medium. The term "instructions" as used with respect to this invention generally indicates a set of opera tions to be performed on a computer, and may represent pieces of a whole program or indi vidual, separable, software modules. Non-limiting examples of "instruction" include computer program code (source or object code) and "hard-coded" electronics (i.e. computer operations coded into a computer chip). The "instruction'^" is stored on any non-transitory computer-readable medium, such as in the memory of a computer or on a flopp disk, a CD-ROM, and a flash drive. In either event, the instructions are encoded on a non- transitory computer-readab I e medi um.

[00046] (3) Specific Details of the invention

[00047] Described is a system that allows a group of servers to digitally sign messages on behalf of a cl ien t. Messages are signed using the Elliptic Curve Digital Signature Algorithm (ECDSA). The ECDSA is described in Literature Reference No. 6. ECDSA signatures are generated using a private key, and signatures are verified using a corresponding public ke The signature on a message m using private key s is denoted as ECDSA_,s (m). The algorithm is such that anyone holding the public key can easily verify that ECDS A ji (m) is a signature on message m, but no one can generate ECDSA .v (»} without knowing Λ\

[00048] A client 300 (computer hardware or software) first uploads shares of his/her private key s to a set of servers 302 using secret sharing

algorithm, as shown in FIG. 3. This is done such that an adversary can learn the private key -? only if he/she learns a majority of the shares. The server's 302 can then use their shares to joint ly generate signatures 400 on messages 402 without, reconstructing or revealing the private key, as depicted in FIG. 4. As shown in FIG. 5. over the course of the protocol some of the shares in the sets of shares 500 may become corrupted (forming corrupted shares 502), either due to accidental faults or malicious behavior. Thus, the servers 302 periodically perform a Proactive-Refresh protocol 504 to correct an shares that may have been corrupted. So long as the majority of shares 500 of any gi ven private key are not corrupted, this will allow the servers 302 to jointly restore corrupted shares 502 to a uncorrupted state.

[00049] Described are algorithms and protocols that allow a set of» servers to generate ECDSA based digital signatures in a distributed manner with the following security and resil ience guarantees. A threshold (?) of up to nil (i.e. , t < tf/2), of the n servers can be maliciously and completely corrupted or compromised, and the confidentiality of the private key used to generate the signature will not be compromised. Furthermore, the correctness of the generated signature will not be compromised.

Correctness of a digital signature is defined in Literature Refer ence No, 10. [00050] Additionally, the distributed (secret shared) pri vate key used to generate the ECDSA signature is periodically refreshed to ensure long

term security against mobile adversaries (i.e., the protocols impiement

proactive security guarantees). Proactive security is also guaranteed

against malicious adversaries, not only passive or semi-honest ones.

Malicious adversaries are able to spy on corrupted nodes and cause them

to send arbitrary messages as the adversary desires. For the purposes of

the present invention, proactive security means that the system is secure in

the presence of a mobile adversary which may eventually corrupt all of the nodes (or servers), although no more than a threshold number may be

corrupt at any given time. Each of these aspects will be described in

further detail bel w.

[00051 ] (3.1 ) Preliminaries

[00052] Below is a table of symbols used in the protocols described herein.

Table of Symbols

\ p j The set of servers currently on-line and engaged

I in the protocol.

i ff i The number of servers currently engaged in the i protocol.

j i The maximum number of servers that a malicious

I party can corrupt per stage without revealing the i secret. This is called the threshold of corruption.

C I The client on behalf of whom the servers store the

i private key.

■V i The private key used to sign messages.

\d j The degree of the polyno mi al used to share the

j secret. Corr \ The set of servers known by every server to be

1 corrupt. g, h 1 Group elements used for Pedersen commitments.

S where g is an. element of order q in an elliptic

1 curve and h is an element for which no servers i know \ogg(h). ] Let » de ote the number of servers, and. denote the set of servers by

p = i- The private keys are redistributed (i.e., refreshed)

periodically. The period between adjacent redistributions is called a stage.

Also, the period befor the first redistribution is a stage, and the period

after the last redistribution is a stage. Let / denote the threshold of

corruption (i.e., the maximum number of servers an adversary may corrupt

during the current stage). The adversary may adaptiveiy corrupt and de- corrupt servers at will, so long as the number of corruptions per stage does not exceed the threshold. Any server that is corrupt during a secret

redistribution is considered to be corrupt in both adjacent stages, ft is

required that t < /z/2 at each stage . Let Corr denote the set of servers that

are known by everyone to be corrupt; it is initially assumed that Corr ^~ 0. ] Assume a synchronous network model with a secure broadcast

channel. Point-to-point communications will not be used in the protocol

descriptions, although any implementation of the protocols would likely

emulate a broadcast channel over point-to-point channels using a

broadcast protocol. Secure erasure is also assumed, meaning that each

server can erase its data in such way thai if the adversary later corrupts

that server, the adversary cannot feasibly learn any information on what 00055] Ilie secret sharing scheme used in the system according to the principles of the present, invention is based cm Shamir's secret sharing scheme (see Literature Reference No. 14 for a description of Shamir's secret sharing scheme) in which the shares of a. secret (the private key in the ECDSA case described here) are points on a polynomial, the constant terra of the polynomial being the secret. Denote by 4 the degree of the polynomial used to distribute the secret. Therefore, knowing any d^'H points on the polynomial allows one to interpolate the secret, but knowing d or fewer points does not reveal any information about the secret. For the polynomials t at store the private keys, set tl - / is set,

00056] Secrets will be shared using Pedersen commitments (which are

described in Literature Reference No. 12) and, in some instances, Feldman commitments (which are described in Literature Reference No. 6). To that end, let q be a large prime, and let g be an element of order q over some elliptic curve such that the discrete logarithm assumption holds for g) (where <g> is the group generated by g). Furthermore, let h e (g) such that no server 302 knows the discrete logarithm of h. That is, no server 302 knows k E Zq such that kg ^:::: h. If one wants to share a secret with polynomial U 6 Zq [x^~] (i.e., (0) is the secret), then an auxiliary polynomial V Zq [x] is also created. Letting OCi denote the evaluation point of Pj , each server P{ receives his share UCCi of the secret, together with VCi[. Let Ufa denote the coefficient of X k in U_x

(and similarly for V^). Then, when the secret is shared, the values

+ Vfch - called Pedersen commitments - are broadcast for each k.

This means that η{βι) + v(a-i)h are also public knowledge (as they can be computed from the U .Q ~f~ V^ h). This allows servers to verify that the shares they received are consistent with the commitments broadcast by the dealer. Feldraaa commitments are the same as Pedersen commitments, except that the auxiliary polynomial is zero.

[00057] it is assumed that each server has a public key encryption scheme, and the encryption of MESSAGE for server Pf is denoted

ENCp . (MESSAGE) . Each server also has a public key signature scheme, and P_j/s signature on MESSAGE is denoted as SIGp, (MESSAGE), RAND is used to denote an arbitrary random value.

[00058] (3.2) System Overview

[00059] The system operates as follows, as shown in. FIG. 6. The client C

distributes a sharing of his/her private key s among the servers by

executing a Secrei-Share protocol 600 t, C, s,P U {C}, Corr) with the servers. After this initial setup has been done, the servers may run instances of a Robt4Si-Sig-Gen protocol (Robusi-Sigtimw protocol 602 in FIG, 6} (t, P, Corr, [s], m) or a Oient-Sig-Gen protocol

(I, P, Corr, C, [s], m) to generate a signature on message m. The question, of which messages will be signed at what time may be determined by interaction with the client, or may occur according to some pre-deter ined schedule, or any trigger or signal from another trusted system.

[00060] The servers periodically run a. Secrei-Redistrihuie protocol 604

(t, P, Corr, [$}) on each sharing [s] of a private key in order to re- randomize the sharmgs, thereby preserving pri vacy of the stored values and ensuring long-term confidentiality. The redistribution will be

performed according to some predetermined schedule (e.g.. every night at midnight} or in response to any ootside or inside trusted signal or trigger (e.g., in response to a command by a system administrator). The present invention provides the protocols and algorithms to perform such a redistribution; when and why the redistribution is performed can be determined by various other means and ali could be seamlessly integrated with the system according to the principles of the present invention.

[00061 ] The servers 302 periodic lly perform the Proactive-Refresh protocol 504 to correct any shares that may have been corrupted. Finally, a Secret- Open protocol 606 is initialized to reveal the pri vate key s to an intended recipient, wherein the private key s is used to compute the digital signature.

[00062] (3.3) The Robust Signature Generation Protocol

[00063] Below is a description of the signing algorithm of the standard

ECDSA signature scheme (i.e., thai which is computed on. a single server and where the private key s is not shared among multiple servers). The standard ECDSA signature scheme is described in Literature Reference Nos. 5 and 10.

[00064] To generate a signature on message m, the signer has to perform the following, as described in Literature Reference Nos, 5 and 1 :

1. Compute e - SHA- l (m) and convert to a integer using the

approach in. Literature Reference No. 16.

2. Select a random integer k such that i< k < - 1.

3. Compute (%i, 3 l) ~~ k, g.

4. Convert x to an integer using the approach in Literature Referenc No. 16. Compute r— mod i/. If r - 0, return to step 2.

5. Compute Z™ k (β + Sr) mod q,. If z ^::: 0, return to step 2.

6. The signature over a message m using the key s is the pair (t∑)

(j,Q., ECDSA (?7i) = (r, z). [00065] The following protocol allows the servers to generate an ECDSA signature from a sharing of a private key wi thout reconstructing and revealing the private key. The protocol uses subprotocols that axe defined below.

0066] (33.1 ) Robusf-$ig-G (t, P, Corr, [s], m)

[00067] To generate a signature on message m (knoxvn to all the » servers) with private key s, perform the following:

1. Each server computes e ~ SNA- 1 (m) and converts e to an integer using the approach in Literature Reference No. 16.

2. The n servers execute GenPoly (£, P, Corr, 1, d) to generate a sharing of a secret random value [vj with Pedersen commitments, and in parallel the servers execute the Feldman version of GenPaly

(t, P, Corr, l,d) to generate a sharing of a secret random vaiite [k] with Feldman commitments.

3. Let ( _j , 3¾ ) denote Lg which is the commitment to the constant coefficient of the sharing of [k] generated in the invocation of the GenPoly protocol (which is known to each server). Convert X< to an integer using the approach in Literature Reference No. 16. 4. Set Γ = ^mod q. Ifr - 0 go to step 2.

5. The servers compute [vk] <~ Multiply(t_> PXorr, \v], [&]).

6. The servers run Secret-Open (t, P, {vk}) to reveal vk. If vk ~ 0. then go to step 2.

7. The servers locally compute [k^{" 1}} = (vfc)^_1[v]mod q. 8. The servers compute

[w] <- Multiply it _t P, Corr, [s], [fc^{" 1}]).

9. The servers locally compute [z] ^~ [ c^"1]^ + [w]r so that the shared value is Z— k^{" 1}^ + rs)mod q. .10. The servers ran Sec i-Opim (£, P, [z]) to reveal 2. Ifz^■■»■ 0 go to step

■j

11. The final ECDSA signature under the shared private key $ is;

ECDSA_s{rn) ~ {r, z).

[00068] The communication complexity of the Robusi-Sig-Gen protocol is

O ( l^) (measured as the number of broadcast field elements), it takes

35 rounds of communication (excepi with negligible probability). The following Cii ni-Sig-Gen protocol is similar to the Robust-Sig-Gert protocol in that it aiiows the servers to generate an ECDSA signature using a sharing of the private key. it differs in that the client C (on behalf of whom the servers are storing the private key) interacts with the servers, allowing for increased efficiency.

[00069] (33,2) Oietti-Sig-Gen t, P, Corr, C, [s], m)

[00070] To generate a signature for client€ on message m with private key Λ\ perform the following:

1. The client C computes e SHA~l(m) and converts e to an integer using the approach in Literature Reference No. 16,

2. The client broadcasts e to the servers.

3. The client selects 3 random values a, b, and k≠ 0 from Z_q and

computes k^"1 and c - ab. The client chooses these values so that the values r and z defined in steps 6 and 1 1 (respectively) are both nonzero.

4. The client and the servers execute 4 instances of the Secret-Share protocol (t, C,s, P U {C}, Cmr) to generate sharings of , b_< e, and k ¹. If me client is found to be corrupt during execution, the protocol terminates.

5. The client broadcasts k* Q =^· (λ'χ, Convert X to an integer •using the approach in Literature Reference No. 16, 6. Set ?^* — mod . C(. If r -- Q, the protocol terminates.

7. The servers locally compute [a] ~ [s] + [ ] and [ ?] = [fc^{- 1}] +

[ft]-

8. The servers invoke the Secret-Open protocol (t, P, [a]) and the Secret- Open protocol (t, P, [/?]) in paraHel.

9. The servers locally compute [w] <- α/ί— — ?[«.] +

10. The servers locally compute z — [fe~ ^l] f? + [w] , so that the shared value is Z = k^→(e ~h r ) ϊϊϊθά q.

11. The servers run the Secret-Open protocol (t, P, [z]) to reveal 2. If 2 ~ 0, the protocol terminates.

12. The final ECDSA signature under the shared key w is:

ECDSA_s(m)— (r, z).

[00071] The communication complexity of the Cfient~$ig~Gen protocol is 0 n). If the client is uncorrupted, it takes 7 rounds of communication.

[00072] (3.4) Secret Sharing, Redistribution, and Opening

[00073] Modified versions of the Secret-Share protocol, the GenPoiy protocol, the Secret-Red 'trikute protocol, and the Secret-Open protocol, from U.S.

Patent Application No. 14/207,321. which is hereby incorporated by reference as though fully set. forth herein, were used. These will.

implement basic tasks pertaining to secret sharing. For completeness, the details of those protocols are outlined below.

[00074] A sharing of a secret $ is denoted by [sj. Note that the servers can perform affine operations on secrets locally by performing the

corresponding operations on their shares. For instance, suppose secrets

S ^} , ... , S^{K J} have been shared and the servers want to compute a sharing of r— CL^ + a^S^ for some publicly known

Writing server Pj 's share of s(j) as S^, Pi cars compute his share T( of r as 7^* _j ^™ Q,^ + ∑if— 1 cally, this operati Since

Pedersen commitments are used, these operations also have to be

performed for the auxiliary polynomial, and corresponding operations must be performed on the commitments to each polynomial. 00 7S] (3.4.1) Secret Sharing

[00076] The following protocol allows a dealer Pp to share a secret using

Pedersen commitments. Also described is a variant of the protocol that uses Feidman commitment, which is equivalent to a Pedersen

commitment in which the auxiliary polynomial is zero. Whenever this protocol (or the CenPoly protocol below) is invoked, it is assumed the

Pedersen version is used, unless it is explicitly stated that the Feidman version is used.

[00077] Secret-Share (t, P_D , S, P, COTV)

1. Share/Commitment Distribution

1.1 PQ picks a random degree d— 1 polynomial u(x) and sets ll(x) = S + XU(x) = UQ + u_t (x) + ·^■· + UdX^ P also picks a random degree d polynomial

V{x) = V₀ + V_tX H h V_dX_d . If this is the Feidman version of the protocol, it is required that v be the all-zero polynomial .1.2 p computes€^ ~~ g 4" Il for each £^™ 0, ... , d and broadcasts

VSSp_D

« ** » SIG_PD (VSS_PD).

Error Detection

2.1 Each P COTT decrypts the message sent by _# to find U( i), V{a-i) and verifies that Zi(fl¾)# +

if this is the Fe man version of the protocol, Pi also verifies that ϊ?(#ΐ) ^™ ®

2.2 Any P| §£ COTT who detected a fault in step 2.1 broadcasts ACC_P = (t, a CWSe, D, RAND) and

2.3 For each properly signed accusation (from server P_j) made in step 2.2, ^ broadcasts

(D_f defense, i, [U(G¾), v(c*i)], RANDi), where RAN D is the randomness that was used to encrypt, the message for Pj i step 1.2.

2.4 Each server checks to see if the defenses broadcast in step 2.3 are correct (i.e., the defense was weii-fermed, the pair encrypts to the same message broadcast in step 1 ,2 when the given randomness is used, and the pair passes the checks in step 2. i). For each accusation that was rebutted with a correct defense, the accuser is added to Corr. If any accusation was not correctly rebutted, P_Q is added to Corr, if Ρβ is not found to be corrupt, the protocol terminates successfully.

[00078] The communication complexity of the Secret-Share protocol is (Xn) field elements, it takes three rounds of communication. Multiple instances of the Secret-Share protocol can be run in parallel without affecting the round complexity. Note that the protocol does not necessarily terminate successfully if the dealer is corrupt.

[00070] (3.4.2) Generating Random Polynomials

[00080] Let Fbe a Vandermoncle matrix with » rows and n— t columns, and let M = V⁷. Suppose that A- is an ^-dimensional vec tor with n— t of its coordinates having a uniformly random distribution and the other / coordinates having an arbitrary distribution independent of the n - t coordinates, it was shown in Literature Reference No. 4 that under these assumptions, all the coordinates of Mx have a uniformly random distribution, it is assumed that there is a publicly known M, fixed for each stage of the protocol.

[00081] Described below is a protocol for creating £ random polynomials with Pedersen commitments in parallel As with the Secret-Share protocol, also described is a Feldman version. This protocol generates polynomials of degree D. Note that one may ha e D≠ d.

[00082] GenPoiy (t, P, Corr, £, D)

1. Proposal Distribution 1.1 ί" ^™ li/(n ~~ i)]is defined. Each server P COTY

w th degQ ^} - degy ^k) - D, Qj^k) (x) -

G[^_Q " £^ .^ H~ ^{* * *} +€[^_j X is written (and die coefficients for are similarly y_f- ^'■ ^' ), It this is the Feldman version of the, protocol, it is required that each "^* is the all-zero polynomial.

1.2 Each server Pj- COYT computes 6^ = ^_j ^ Then

Pj broadcasts

vss_Pi

and siGp_i ( sSp_i ) «

1.3 Each server that did not produce a properly signed message in the previous step is added to Corr.

Error Detection

2. 1 Each server P ¾: COTT checks for each pair

received in the previous step that Qf adg

o/e¾. if this is the Feldrogn version of the protocol, Pf also checks

If Pi detected an error in the previous step with the pair

IQ ^} ΰ> Ym ^} («I )I broadcasts ACCp. =

)i, CCUSe, m, fc) and SIG_Pi(ACCp_c P_t broadcasts an accusation no more than once for each P_m, although there may be more than one accusation per k . if P[ was accused (with a properly signed accusation) in the previous step, he broadcasts his (purported) pair of values along with the randomness RAND i,m,k ^{sat was} used to encrypt it in step 1.2;

(i, defense, m [Q ^k)(a_m)_t >¾^(fc)(ir_m)] , RAND_{i ni k}.

2.4 Each server checks to see if the defenses broadcast in step 2.3 are correct (i.e., the defense was well-formed, the pair encrypts to the same message broadcast in step 1.2 when the given randomness is used, and the pair passes the checks in step 2.1 ). For each accusation that was rebutted with a correct defense, the accuser is added to Corr. For each accusation that was not correctly rebutted, the accused server is added to Corr.

3. Local Share Manipulation For each Pf C OTT and each k, Q: is defined to be the all- zero polynomial. Each batch k of n polynomials will he converted into a batch of n— t polynomials as follows:

[00083] The y^^' is similarly used to construct the auxiliary polynomials for the R ^S Each server locally computes the Petersen (or Fektman) commitments for these polynomials, lire output is the set of shares of g with the shares of the corresponding auxiliary

polynomials.

[00084] The communication complexity of GenPoly O (^Ή^) ~~

O in + Π-²) field elements (assuming that D = (n)). It takes three rounds of communication. Note that niiiltiple instances of the GenPoly protocol can be invoked in parallel, even if the degrees of the generated polynomials are different.

[00085] (3.4.3) Secret Redistribution

[00086] The following protocol allows the servers to redistribute a secret This re-randomizes the sharing, so that old shares cannot he combined with new shares to Seam the secret (thus providing security against mobile

adversaries). In addition, it allows servers to correct shares they hold that, may have been altered by an adversary

[00087] Secret-Redislrih ie (t, P, Corr, [s]) It is assumed thai the secret s as been correctly shared with

polynomial u and auxiliary polynomial v (both of degree d) and that the

Pedersen commitmeots for these polynomials are known to all servers in P,

I . Polynomial Generation

invoke GenPofy (t, P, Corr, n + 1, d— 1) in parallel to generate 0 and of degree d ~~ 1 with auxiliary polynomials γ and i jjO) respectively. The k^tn coefficient of O is and similarly for γ,

2. Commitment ^'Transfer

2.1 Each Pi COTT broadcasts the commitments for the old secret sharing polynomial (i.e., COMp, =

2.2 Each P( determines the correct values for the commitments broadcast in the previous step by siding with, the majority; Pj updates its commitments accordingly.

3. Share Transfer and interpolation

3.1 Each i computes 6i — ^'li(CTj) + +

SiGp VSSp-X The idea is thai for P.% the servers .mask u w th the polynomial X (Xj^R^X, and similarly for v,

3.2 Each Pj checks whether the values broadcast in step 3.1 are correct given the publicly known Pedersen

commitments. That is, Pj cheeks if

3.3 The new sharing polynomial s defined to be it' x)—

u(x) + xQ(x)_> arid similarly the new auxiliary polynomial. is i?^f (x) = v(x) + xy(x). Since ( — Uj)R^X evaluates to zero at X = C£j , can deduce li'(ii ) from the points on It' x) + (x— « )i?^(x) sent to him by the servers (and similarly for v'(c )). So each Pj uses all the shares that passed the check in step 3.2 to interpolate his new

as well as v'{cCj). The servers compute the commitments to if and v' using publicly known commitments to «_» Q, v, and γ.

Data Eras are

Each P erases their shares of«_? 0, v, and y, and each J?^ and

along with the corresponding commitmenis, and sets Corr^:::0. [00089] The communication complexity of the Secret-Redistribute protocol is O (fl^) field elements. It takes 6 .rounds of communication.

[00090] (3.4.4) Secret Opening

[0009.1 ] The following protocol allows the servers to open a secret that has been shared with Pedersen commitments.

[00092] Secret-Open (t, P, [s])

[00093] it is assumed that the secret a has been shared with polynomial a and auxiliary polynomial, v ( both of degree d). If the k^tn coefficient of u is t¾( d . similarly for t?^), then it is assumed that the Pedersen commitments ™ · l?¾ h for each k ^:::: are publicly known.

1. Eac server P( broadcasts his shares SHp. = [li(c?j), v c i

2. Each server check for each pair of points

^ ') ^rece* ^¾d in the previous step that.

3. Each server uses all the points that passed the check in step 2 to interpolate the secret,? =¾(0).

[00094] The communication complexity of the Secret-Open protocol is 0(n) field elements. It takes one round of communication. Multiple instances of the Secret-Open protocol can be i nvoked in parallel whi le still taking only one round of communication.

[00095] (3,5) Multiplication [00096] Multiplication triples of shared secrets need to be generated in a verifiable manner. The protocol for generating multiplication triples i Literature Reterence No. 4 uses a degree d sharing of a random number r, together with a degree Id sharing of the same value. Using a 2d sharing would be problematic for the protocol according to the principles of the present invention, so instead two random sharings [r] and [$) are used, and when a degree 2d sharing of r is wanted, the servers locally compute

[00097] The following protocol Multiplication-Triple

(t, P, Corr, [a], [y {[r«], [s ], [f «], [s⁽ ]}"_al). which is a modified version of the protocol from U.S. Patent Application No. 14/207,483 (which is hereby incorporated by reference as though fully set forth herein) uses the sharings la], [yl {[r [s [f «], [s^C ]}^ to generate (correct) sharings [b] and [c] such that c — ah,

[00098] Multiplication-Triple

[00099] In what follows, the capital letter for the polynomial that shares the secret represented by the corresponding small letter (i.e., .4(0)™ d, J?^ 0) — etc.) is used. The auxiliary polynomials will, have overlines (e.g., the auxiliary polynomial for A is A). The following steps are performed in parallel for each server Pi «£ Corr.

1. Generating Multiplicands

P[ randomly chooses two values and then invokes

Secret-Share (t, P, COVV and Secret-Share (t, Pi, B^, P, COIT) in parallel. The polynomial used to share is denoted by (with auxiliary polynomial B^ , and the polynomial used to share h ^ is denoted by (with auxiliary polynomial B ). If P( is added to Coir in the

invocation of Secret-Share, then the following steps are not performed for P .

Opening Masked Products

2.1 Each server P lfc COTT broadcasts shares of

[α] [&^(ϊ:)] + [r ⁱ⁾] + ^d [s⁽ ] nd ¾·]. together with corresponding shares of auxiliary polynomials:

4- afsWfa),

Y(a_s)_t F(¾-).₍S/G_P/(%, ψ,-, F(¾), ?(«,).

The shares of fvj are not used until step 5.3. They are broadcast here simply to reduce round complexity.

2.2 Pf checks for each β broadcast in the previous step R®(aj)g + R ⁱ ( _j)h) + af {S {aj)g 4-

Recall that j can compute die Pedersen commitments to

5 Pj'$ shares of CL, , and usin the publicly known commitments.

2.3 For any pair (Bj_f φ ) that did not pass the check in the previous step, Pj broadcasts

lo (Pj, c se, Ρ,, £⁽ⁱ⁾(a/), 5⁽ⁱ (a_y), RAND_U) where

RANDf is the randomness used to encrypt ^*s shares i the invocation of Secret-Share in step 1.

2.4 if Pj broadcasts a correct accusation against ^, (i.e., the

15 values encrypt to the same message sent in the invocation of Secret-Share in step 1 when the given randomness is used, and these values do not correspond to the values

(0j, <f>j) broadcast in step 2.1) then / is added to Corr. if j broadcasts an incorrect accusation against Pj_y then f is

20 added to Corr.

3. Revealing Corrupt Servers' Shares

3.1 The servers invoke one instance of GenPoly

(£, P_} Corr, 3?i, d— | O7T j) {i.e., this step is not ran for each Pj, but rather once for all the Pj), This generates polynomials with auxiliary polynomials

The polynomials W_Q /V ^ , are defined by

W ^l)(x) = ^(x)n_PfeeCor (x - a_k) and

M°Wnp_AeC₀rr(JC ~ «kl E«eb server / _j broadcasts SH_j

+ R^w(a,),W¾^C0(¾)

+ S®(a_;)¾⁽ (_¾)

+ i(a), i¾⁽ⁱ⁾(%)

+ ί¾^ω(α,·) + S⁽ⁱ (a_;)]

and S/ . (5// 1 ) .

In parallel with the previous step, Pi broadcasts

CorSh_P. = { ⁽ (a_fc) _pfeeCorraiongwith SIG_P.(CorSh_Pf .

Each server checks for each pair broadcast i step 3.2 that it corresponds to the publicly known Pedersen commitments. The shares that pass the check are used to interpolate the shares of [a], [f^], and [s^] belonging to servers i Corr, and together with the shares broadcast hi the previous step, these are used to compute the corrupt servers' shares of ab® + r^.

4. Steps 2 and 3 are also performed to distribute and check shares of

[a] [5 ^iJ] + [f + X^d [S ^J. The two executions of these steps are to be performed in parallel,

5. Checking ^'Multiplication Triples

5.1 Each server interpolates = Ctb^ + and

£⁾⁽ = ab^ + from the shares of all servers not in Corr thai were broadcast in step 2.1 and the shares of servers in Corr that were computed in step 3.4.

5.2 Each server locally computes [c^] = —

[r^(l ] and |c^Ci)] = 5^ - ^].

5.3 The servers interpolate y from the shares broadcast in step 2.1 that correctly correspond to the commitments,

5.4 Invoke Secret-Open (t, P, [S ^W] + y[b ^]) to get

5.5 invoke Secret-Open (t, P, [c^] + [c^] -

S^(£ [a]) to get ^ = c^(l) + yc⁽ⁱ - S^a.

5.6 \ f Z^'^]≠ 0, then Pj is added to C On: ] [/ ] =∑[6^{( )}] and [c]™∑[c^{(i )}] are defined, where the sums are taken over all such that P (i C07^"T. The servers locally compute these sharings (along with their Pedersen commitments), and the multiplication triple is taken to be ([a], [b], [c]) with c^™ ab. [000101] The communication complexity of the Multiplication-Triple protocol is 0(n² ). it takes 1 I rounds of communication.

[000102] The following protocol computes a sharing ofxy given a sharing of.* and a sharing of v. It uses the Multiplication- Triple protocol as a subprotocol and employs Beaver's multiplication technique. Beaver's multiplication technique is described in Literature Reference No. 1.

Multiplication is used as a subprotocol in the Kohmi-Sig~Gert protocol.

[000103] Multiply (£, P, Corr, \x], \y})

L The servers invoke GenPofy (t, P, Corr, 2 + 4n, d) to generate 2+4» sharings of random values.

2. The servers invoke Multiplication-Triple using the 2-† 4« random sharings generated in the previous step as input; denote the output triple as ([a], [b], [c]) with c— ah,

3, The servers locally compute [ ] ~ [x] + [a] and [/?] ~ [y] + [b].

4, Invoke Secret-Open (t, P, [a]) and Secret-Open (t, P, [ ?]) in parallel,

5. The servers locally compute the output of the protocol as [xy]— β ~~ a[h} - β[α] + [c].

[000104] The communication complexity of the Multiply protocol is 0(?l²).

It takes 15 rounds of commtnucation.

105] Computing the ECDSA signatures in a distributed manner according to the principles of the present invention guarantees significantly increasing security, because it eliminates a single point, of

failure/compromise (i.e., a single server) as an adversary/attacker must compromise multiple servers in order to retrieve the private key used to compute the digital signature or affect its computation, in addition, such a compromise has to occur between two proactive refresh cycles, because all information obtained from servers in previous cycles will be irrelevant when a proactive refresh cycle is executed as new randomized shares of the keys are generated. These ne shares cannot be used with old ones to reconstruct the private key.

[000106] ECDSA Signatures, standardized in the FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION, FIPS PUB 186-4;

Digital Signature Standard (DSS) (see Literature Reference No. 5), are used to generate digital signatures which ensure integrity of transmitted data online, can be used for authentication of data and entities online, and are also used in a variety of digital currency and financial transactions (e.g., Bitcoin, Liiecoin, Ripple, and others digital currencies). The present invention, thus, has a large set of applications to wliich it could be applied.

[000107 ] For instance, companies can use the present invention to design and implement remote access to internet-enabled/connected vehicles, individuals who have access to the vehicle can do so without risk of compromise of their private keys, which can be stored in a distributed manner on a user's mobile device(s), security toke and/or backend servers. If a user's device or backend server, or the operator thereof, is compromised, the private key will not be revealed. Requiring a private key for authentication will guarantee that individuals without proper access will not be able to access the vehicle. I addition to the private key, a bionietric (e.g., fingerprint, palm vein scan) can also be stored in a distributed manner, and both an ECDSA -based digital signature and biomet ic data can be used for authentication.. [000108] Additionally, future connected vehicles may require Public Key

Certificates in their operation. Manufacturers will need to generate such certificates and load them into vehicles. Those certificates have to be signed by a manufacturer's private key (or multiple keys) which have to be stored securely. The system according to the principles of the present invention would allow a manufacturer and/or it's supplier to secure the private keys and compute such signatures in a distributed manner. The ability to efficiently perform distributed computations using secret shared private keys is a very important step to securing future infrastructure of connected vehicles. ] Further, companies can utilize the system described herein for facility access to extremely sensitive facilities. Such facilities may not wish to store lists of indi iduals who may access particular rooms, such as sensitive compartmented information facilities (SCIFs). The present invention will allow only authorized users to access such facilities without storing their entire identifying information and private key at the facility.

Claims

What is claimed is:

A system for generation of elliptic curve digital signature algorithm

(ECDSA.) based digital signatures, the system comprising:

one or more processors and a .non-transitory coraputer-readable medium having executable instructions encoded thereon such that when executed, the one or more processors perform operations of:

initializing a Secrei-Share protocol between a client C and a set of n servers, wherein the client C shares a set of shares of a private key s among the set of » servers;

initializing, by the set of » servers, a protocol to generate a digital signature on a message m using the set of shares of the private key s without reconstructing or revealing the private key s and

periodically initializing, by the set of « servers, a Secret- Redistribute protocol cm each share of the private key s to re-randomize the set of shares.

The system as set forth in Claim 1. wherein the one or more processors further perform an operation of initializing a Secret-Open protocol to reveal th private key $ to an intended recipient, wherein the private key s is used to compute the digital signature.

The system as set forth in Claim 2. wherein in order for an adversary to retrieve the private key s, the adversary must compromise a plurality of servers in the set of ?? servers.

The system, as set forth in 3, wherein a threshold i of up to nil of the set of n servers can be completely corrupted or compromised while the confidentiality of the private key s and correctness of the digital signature remain

uncoraproraised. The system as set. forth in Claim 4, wherein if a majority of the set of shares of the private key s is not corrupted, then the set of /? servers jointly restore any corrupted shares.

The system as set forth in Claim 5, wherein corrupted servers are restored to a imcorrupted state.

A computer-implemented method fo generation of elliptic curve digital signature algorithm (ECDSA) based digital signatures, comprising:

an act of causing one or more processors to execute instructions stored on a noa-transitoty memory such that upon, execution, the one or more processors perform operations of;

initializing a Secret-Share protocol between a client C and a set of n servers, wherein the client. C shares a set of shares of a private key $ among the set of n servers;

initializing, by the set of it servers, a protocol to generate a digital signature on a message m using the set of shares of the private key.* without reconstructing or revealing the private key s and

periodically initializing, by the set of« servers, & Secret- Retfistribnte protocol on each share of the private key ,v to re-randomize the set of shares.

The method as set forth in Clai 7, wherein the one or more processors further perform an operation of initializing a Secret-Open protocol to reveal the private key s to an intended recipient, wherein the private key s is used to compute the digital signature.

The method as set forth in Claira 8, wherein in order for an adversary to retrieve the private key s, the adversary must compromise a plurality of servers in the set of f? servers.

10. The method as set forth in C l aim 9, w herein a threshold t of up to n/2 of the set of H servers can be completely corrupted or compromised while the confidentiality of the private key 5 and correctness of the digital signature remain uncompromised.

1 1. The method as set forth in Claim 10, wherein if a majority of the set of shares of the pri vate key -v is not corrupted, then the set of « servers jointly restore any corrupted shares.

12. The method as set forth in Claim I L wherein corrupted servers are restored to an uncorrupted state.

13. A. computer program product for generation of el l iptic curve digital signature algorithm (ECDSA) based digital signatures, the computer program product comprising:

computer-readable instructions stored on a non-transitory computer- readable medium that are executable by a computer having one or more processors for causing the one or more processors to perform operations of:

initializing a Secret-Share protocol between a client C and a set of n servers, wherein the client C shares a set of shares of a private key* among the set of n servers;

initializing, by the set of n servers, a protocol to generate a digital signature on a message m using the set of shares of the private ke Λ^! without reconstructing or revealing the private key s; and

periodically initializing, by the set of n servers, a Secret- Redistribute protocol on each share of the private key s to re-randomize the set of shares. 1.4. The computer program product as set forth in Claim 13, further comprising instructions for causing the one or more processors to perform an operation of initializing a Secret-Open protocol to reveal the private key s io an intended recipient, wherein the private key s is used to compute the digital signature.

15. The computer program product as set forth io Claim 14, wherein in order for an adversary to retrieve the private key the adversary mast compromise a plurali ty of servers in the set of n servers.

16. The computer program product as set forth in Claim 15, wherein a threshold t of up to nil of the set. ofw servers can he completely ^'corrupted or

compromised while the confidentiality of the private key s mid correctness of the digital signature remain uncompromised.

17. The compi er program product as set forth in Claim 16, wherein if a majority of the set of shares of the private key ,v is not corrupted, then the set of n servers jointly restore any corrupted shares,

18. The computer program product as set forth in Claim 17, wherein corrupted servers are restored to an uncorrupted state.