EP0723348A2

Method and system for a public key cryptosystem having proactive, robust, and recoverable distributed threshold secret sharing

Abstract

A proactive threshold secret sharing cryptosystem using a set of servers. The cryptosystem is a threshold cryptosystem, in the sense that service is maintained if at least (k + 1) out of n servers are active and honest. The secret signature key is compromised only if the adversary breaks into at least (k + 1) servers. It is robust in the sense that the honest servers detect faulty ones and the service is not disrupted. It is recoverable, because if the adversary erases all the local information on the server it compromised, the information can be restored as soon as the server comes back to performing the correct protocol. The method and system has proactiveness, which means that in order to learn the secret, the adversary has to break into (k + 1) servers during the same round of the algorithm because the shares of the secret are periodically redistributed and rerandomized. The present invention uses a verifiable secret sharing mechanism to get the security requirements during the update between two rounds. The security of the scheme depends on the assumption of intractability of computing logarithms in a field of a big prime order and the ElGamal signature scheme.

EP0723348A2, drawing sheet 1 — Sheet 1 of 63

Term

Term ended

Projected expiry passed 15 December 2015, 10.8 years ago.

18 claims: 2 independent, 16 dependent

1
A method of public key cryptography having proactive, robust and recoverable distributed threshold secret sharing, comprising the steps of:initializing servers linked by a communications network to form keys;synchronizing said servers to operate in discrete rounds having ends;calculating updated keys at said ends of said rounds from messages broadcast on said communications network;verifying said updated keys to form a set of compromised servers;and recovering said set of compromised servers.
10
A data processing system for processing a public key cryptography scheme having proactive, robust and recoverable distributed threshold secret sharing, comprising:servers linked by a communications network;initialization means for initializing said servers to form keys associated with said servers;timing means for synchronizing operation of said servers into discrete rounds having ends;updating means for updating said keys at the end of each round of said discrete rounds to produce updated keys;verification means for verifying said updated keys to form a set of compromised servers;and recovery means for recovering said set of compromised servers.

Independent claims2

124 paragraphs in 5 sections, as filed

TECHNICAL FIELD OF THE INVENTION

0001The present invention relates to data processing systems and more particularly to data processing systems including cryptographic mechanisms for information security.

BACKGROUND OF THE INVENTION

0002Public key encryption systems are used to send and receive encrypted messages. Public key encryption systems are those in which a message is encrypted by performing a mathematical algorithm using a publicly available value, called the public key. Then, the recipient decrypts the message by performing an algorithm using a private value, called the private key. Public key encryption depends on choosing an encryption algorithm, E, and a decryption algorithm, D, such that deriving D, even given a complete description of E, would be effectively impossible. The three requirements of public key encryption are: <ol id="ol0001" ol-style=""><li>1. D(E(P)) = P , wherein P is the message;</li><li>2. It is exceedingly difficult to deduce D from E; and</li><li>3. E cannot be broken by attacking P.</li></ol>

0003Thus, the public key can be distributed freely. The private key, however, must be kept private by the entity that uses it. If an intruder accesses the memory content of the entity, the system security is broken. This holds true for all the original public key patents. In Key escrow systems and Micali's fair cryptosystems, the private key is split into many portions and each portion is held by a different entity. However, if with passing time an intruder is able to read each entity's memory, system security is broken.

Proactive Secret Sharing

0004To explain the concept of proactive secret sharing, the terminology of secret sharing schemes and their security characteristics must be explained.

Threshold, Robustness and Recoverability in Secret Sharing

0005Secret sharing was first introduced by <nplcit id="ncit0001" npl-type="s"><text>G.R. Blakley, Safeguarding Cryptographic Keys, AFIPS Con. Proc. (v. 48), 1979, pp. 313-317</text></nplcit> and <nplcit id="ncit0002" npl-type="s"><text>A. Shamir, How to Share a Secret, Commun. ACM, 22, 1979, pp. 612-613</text></nplcit>, which are both hereby incorporated by reference. In its most basic form, secret sharing is a way to divide a secret piece of information M among n participants, called share holders, so that together they will be able to reconstruct it. However, no group of (n - 1) share holders can learn anything about M. This mechanism is used to increase security whenever there is a need to safeguard a piece of information. The increase in security corresponds to being able to guard the secret from an adversary who can break into some servers, but not all of them.

0006Every secret sharing scheme has these conceptual phases: <ol id="ol0002" ol-style=""><li>(1) a dealing phase, when a dealer who knows the secret creates its shares and distributes them among the share holders;</li><li>(2) a storage phase, when the shares are maintained by the share holders; and</li><li>(3) a reconstruction phase, when the share holders reconstruct the secret from their shares.</li></ol>

0007The basic secret sharing described above is not very practical because if an adversary compromises a share holder and erases or modifies the secret share held by that holder, the secret M can never be reconstructed. Hence, the above scheme is secure against an adversary who can break into (n - 1) servers and learn their shares, but cannot erase or modify servers' memories or storage, cannot cause any server to crash and does not interfere either with the dealing of the shares or with the reconstruction of the secret.

0008Before the properties of secret sharing that make the basic scheme more secure, are defined or the different types of adversary's attacks on servers must be defined: <ul id="ul0001" list-style="bullet"><li>A server is compromised to the adversary if she breaks into it and learns all the secret information stored at this server: its secret share and keys used for communication.</li><li>The adversary freezes a server if she causes it to stop working. It is assumed, however, that as soon as the adversary is purged, the server can return to performing the correct protocol (i.e., no data is lost). Cutting the server's access to the network is an example of freezing a server. Shutting off the power or killing all the processes on the server also constitute freezing, if all the necessary data (variables and the algorithm code) is not erased or modified. A frozen server does not send or receive any messages; it is idle until human intervention brings it up again.</li><li>The adversary controls a server if she can change the protocol it performs and cause it to send messages that are incorrect with respect to the original protocol. From the other server's point of view, such a server is cheating or dishonest. Freezing is a trivial case of controlling.</li><li>The adversary disables a server when she manages to erase or modify the secret data that the server stores. Erasing the protocol code or erasing public keys of other servers makes it harder for the system management to bring this server back to life, but since this information is public, it can be reinstalled into the server without exposing any secret information to the system operators. It is the destruction of server's secret share that makes a qualitative difference between freezing and disabling.</li></ul>

0009The desirable properties of secret sharing schemes, which offer security against the above types of adversaries, are described below. The concern is with security during the storage and reconstruction phases while leaving the dealing phase as insecure as in the basic secret-sharing scheme described above. This concern can be contrasted with verifiable secret sharing schemes, which aim at increasing security during the dealing phase.

0010A secret sharing scheme is called a threshold scheme if only (k + 1) out of n servers need to cooperate to reconstruct the secret. This property makes the system secure against attackers who: <ul id="ul0002" list-style="bullet"><li>During the reconstruction phase freeze or disable up to k out of n servers. During the storage phase, the adversary can freeze more servers, and the threshold scheme will still be secure, provided that these servers are brought up before the reconstruction phase starts.</li><li>During the lifetime of the algorithm compromise k out of n servers. Compromising (k + 1) out of n servers allows the adversary to reconstruct the secret by herself.</li></ul>

0011The above two requirements can be met only if the threshold k is a strict minority, i.e., when 2k + 1 ≦ n.

0012A secret sharing scheme is called robust if the reconstruction phase is secure in the presence of up to k cheating servers. The threshold scheme by itself relies on the fact that when the attacker can disable or freeze, but cannot control the compromised servers, then there is no problem in picking the group of (k + 1) non-faulty servers to reconstruct the secret, because faulty means non-active. In short, robustness makes the threshold scheme secure against adversaries who during the reconstruction phase can disable or control no more than k servers in total.

0013A threshold secret sharing scheme is recoverable if the proper secret share can be restored to the server that lost it. This scheme assumes that a loss can happen during the storage phase only. Thus, the recovery mechanism will be carried out during the storage phase. The property of recovery in secret sharing is the object of the present invention. It makes the robust threshold scheme secure against adversaries who can disable or control no more than k out of n servers at any time during the storage phase. Whenever the system notices that some servers are disabled, the recovery phase starts and it will be successful assuming that it is so short that the adversary will not jump other servers during this phase.

0014Recovery is needed whenever the secret share is lost. But that can happen with or without the adversary learning this secret share. The share might be lost because an adversary with compromising and disabling capabilities broke into a server, learned its secret share and erased or modified it. But the share might be lost due to a power outage. One could argue that in the first case, the secret could just as well be restored publicly since the adversary knows it anyway. However, there might be more than one adversary, in which case, public recovery of a share spares the other adversaries some work. Also, since a mechanism to deal with the case of disability due to the power outage exists, it can be used in the case when one of the adversaries knows the secret. It is hard to know which case the security scheme is dealing with, so it is better to use one secure recovery mechanism whenever a secret share is lost.

Secret Recovery and Server Authentication

0015If the adversary has capability of erasing or modifying the local storage and memory of the compromised server, and she can also inject messages to the communication channels between the servers, a fully automatic recovery is impossible. A human being must reboot the server, start up the process performing the secret-sharing algorithm and reinstall some means of mutual authentication between this server and the others.

0016The issue of server authentication is rarely discussed in connection to secret sharing. However, server authentication is necessary to preserve the security of the recovery protocol in the presence of an adversary who can send messages to the servers from outside the group of servers that participate in secret sharing. The recovering server A must have some means of authenticating the servers B that try to reinstall its share. Also, the servers B must be sure that it is indeed A to whom they are giving the proper share. These goals can be reached with either secure links between A and B's or with pairs of secret/public decryption and signature keys between A and servers in B. However, if the server A lost its secret share, it could also lose all its other secret keys used for securing and authenticating its links with the other servers B. This means that human intervention in reinstalling means of authentication to a disabled server is necessary for recovery. This intervention will either consist of installing new server to server link security between A and servers B, or in reinstalling B's public authentication/encryption keys on A, letting A compute its new private keys and securely installing them on servers B. In the example of a proactive system, private/public keys are used for server to server communication, and hence the human intervention in the recovery mechanism will be of the second type.

Proactiveness

0017A new property of secret sharing schemes must be defined: proactiveness. Proactiveness increases security by restricting the rate with which the adversary can compromise servers. The storage phase of the proactive secret sharing scheme is composed of rounds divided by short update phases. The scheme is secure against the adversary who can compromise no more than k servers during the same round. Without proactiveness, the scheme is secure against the adversary who can compromise up to k during the whole storage phase, i.e., effectively during the lifetime of the algorithm. A proactive scheme is secure against the adversary who compromises all of the servers, provided she does not do it too quickly This property is achieved by a re-randomization of the secret shares held by the servers during the update phases. The update protocol is equivalent to re-dealing the secret without revealing it in the process. Formally, the update must achieve the following: <ol id="ol0003" ol-style=""><li>1. No group of k or fewer servers participating in the update protocol can learn anything about the new shares of other servers.</li><li>2. Knowing k out of n previous shares and k out of n new shares does not reveal any information about the secret share.</li></ol>

Proactiveness Versus Threshold, Robustness and Recovery

0018An adversary during the update phase protocol should be no stronger than during the reconstruction phase. Therefore, to proactivize a robust, recoverable threshold secret sharing scheme, the update phase must be secure against the adversary who can disable or control up to k servers.

0019Proactiveness and recoverability in secret sharing make the most sense when they are used together. Notice that without a recovery mechanism, the proactive secret sharing increases security against some types of attack but decreases it against others. Non-proactive secret sharing schemes are secure against adversaries who can control servers during the storage phase, simply because the servers do not do anything during that phase. During the storage phase in a proactive scheme, servers periodically update their shares. Therefore, if a server is frozen or controlled during an update phase it will not have a proper share in the next round, which is equivalent to the case of the adversary with disabling capabilities. Hence, a proactive scheme is secure against an attacker who can control up to k servers in one round only if it has a recovery mechanism. Also it is secure against an attacker who can control or disable up to k servers in one round.

SUMMARY OF THE INVENTION

0020It is an object of the present invention to provide a method of and system having a proactive, robust and recoverable distributed threshold secret sharing scheme.

0021It is another object of the present invention to provide a proactively secure key certification authority using the above scheme.

0022The foregoing and other objects are achieved by a method and system which provides a proactive threshold secret sharing cryptosystem using a set of servers. The proactive secret sharing cryptosystem is a distributed threshold cryptosystem, in the sense that service is maintained if at least (k + 1) out of n servers are active and honest. The secret signature key is compromised only if the adversary breaks into at least (k + 1) servers. It is robust in the sense that the honest servers detect faulty ones and the service is not disrupted, even when the servers infiltrated by the adversary are cheating. It is recoverable, because if the adversary erases all the local information on the server it compromised, the information can be restored as soon as the server comes back to performing the correct protocol. The method and system has proactiveness, which means that in order to learn the secret, the adversary has to break to (k + 1) servers during the same round of the algorithm because the shares of the secret are periodically redistributed and rerandomized. The present invention uses a verifiable secret sharing mechanism to get the security requirements during the update between two rounds. The present invention assumes that the servers are communicating through a broadcast medium, that they have fully synchronized, unbreakable local clocks and that they have local sources of true randomness. The security of the scheme depends on the assumption of intractability of computing logarithms in a field of a big prime order. It also depends on the security of the ElGamal signature scheme, which is used for server-to-server authentication.

0023The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

0024For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which: <ul id="ul0003" list-style="none"><li><figref idref="f0001">FIGURE 1</figref> is a diagram of a server console;</li><li><figref idref="f0002">FIGURE 2</figref> is a block diagram showing servers connecting to a communications channel;</li><li><figref idref="f0002">FIGURE 3</figref> is a flow chart showing a high-level view of the sequence of steps of a preferred embodiment of the present invention;</li><li><figref idref="f0003">FIGURE 4</figref> is a flow chart showing the sequence of steps of a preferred embodiment of the share update protocol of the present invention;</li><li><figref idref="f0004">FIGURE 5</figref> is a flow chart showing the sequence of steps in step 410 of <figref idref="f0003">FIGURE 4</figref>; and</li><li><figref idref="f0005 f0006">FIGURE 6</figref> is a flow chart showing the sequence of steps of a preferred embodiment of the share recovery protocol of the present invention.</li></ul>

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT OF THE INVENTION

0025The present invention is a proactive threshold secret sharing scheme with properties of robustness and recoverability. Disclosed are the model and goals of this scheme and the tools that it uses. Also disclosed is a Key Certification Authority system using the present invention. The security of the scheme depends on the assumption of intractability of computing logarithms in a field of a big prime order. It also depends on the security of the ElGamal signature scheme, which is used for server-to-server authentication. The EIGamal signature scheme is disclosed in <nplcit id="ncit0003" npl-type="s"><text>T EIGamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithm, IEEE Trans. on Informational Theory 31, p. 465, 1985</text></nplcit>, which is hereby incorporated by reference.

Model of the System and Assumptions About the Adversary

0026Assume a system of n servers A = {P1, P2, ... , Pn} that will proactively secret-share value x. Also, assume that the system is securely and properly initialized. The goal of the scheme is to prevent an adversary from learning x. At the same time, the adversary cannot prevent servers A from reconstructing x themselves when they need to. Given are specifications about servers A and the communication network they communicate with. Also specified are the interaction mechanisms between the servers A and the human management as well as the trust held by the management.

Model of Proactive Servers

0027A representative hardware configure of a server for practicing the present invention is depicted in <figref idref="f0001">Figure 1</figref>, which illustrates a typical hardware configuration of a workstation in accordance with the subject invention having central processing unit 10, such as a conventional microprocessor, and a number of other units interconnected via system bus 12. The workstation shown in <figref idref="f0001">Figure 1</figref> includes random access memory (RAM) 14, read only memory (ROM) 16, and input/output (I/O) adapter 18 for connecting peripheral devices such as disk units 20 and tape drives 40 to bus 12, user interface adapter 22 for connecting keyboard 24, mouse 26, speaker 28, microphone 32, and/or other user interface devices such as a touch screen device (not shown) to bus 12, communication adapter 34 for connecting the workstation to a communications network, and display adapter 36 for connecting bus 12 to display device 38.

0028<figref idref="f0002">Figure 2</figref> shows how servers A are connected via private links L to a common broadcast medium C, called the communication channel or communication network, which also connects them to the outside world. The broadcast medium has the property that whenever a message is sent to it from a link connecting it to some server, it instantly reaches all the other links connected to this medium. The present invention assumes the servers in A are equipped with secure and synchronized clocks (not shown), which do not change or fail even when the adversary controls or disables a server. These clocks divide the time between rounds and update phases. Because of synchronization, every server in A gets the signal to start the update phase at the same time. Also assumed is that every server in A has a source of true randomness (not shown). If the adversary compromises a server, she cannot predict the future random numbers generated on that server. Every server also has a figurative unbreakable box that contains a code with the algorithm described below for every server (not shown).

Adversary

0029The adversary's model of attacks on the servers A is an extension of a "mobile fault" model. <nplcit id="ncit0004" npl-type="s"><text>R. Ostrovsky & M. Yung, How to Withstand Mobile Virus Attacks, Proc. of the 10th ACM Symposium on the Principles in Distributed Computing, 1991, pp. 51-61</text></nplcit> and <nplcit id="ncit0005" npl-type="s"><text>R. Canetti & A. Herzberg, Crypto 94</text></nplcit>, both of which are hereby incorporated by reference. Let <maths id="math0001" num=""><math display="block"><msubsup><mi>k</mi><mn>1</mn><mrow><mo>(</mo><mo>′</mo></mrow></msubsup></math><img file="EP0723348A2_D0001.tif" /></maths> be the number of servers in A the adversary corrupts at any point during round t, and let <maths id="math0002" num=""><math display="block"><msubsup><mi>k</mi><mn>2</mn><mrow><mo>(</mo><mo>′</mo></mrow></msubsup></math><img file="EP0723348A2_D0002.tif" /></maths> be the number of additional servers whose links to the communication channel are under active attack by the adversary at any point during the round t. Then, our proactive secret-sharing scheme is secure against the adversary for whom (k1(t) + (k2(t) ≦ for every round t. To achieve this bound we need n ≧ 2k + 2 servers in A.

0030The scheme can easily be made secure against stronger adversaries. First, it is possible to achieve the same bound k on adversaries in the round with one less server, i.e., 2k + 1 ≦ n. Second, with changes to the synchronization mechanism, more attacks on the links can be allowed, because all such attacks are always detected by the system and the servers could halt the protocol until the management removes the adversary from the link.

0031Corrupting a server means any of the following: <ul id="ul0004" list-style="bullet"><li>Compromising it: Learning all the data it stores.</li><li>Controlling it: Making it faulty with respect to the specified protocol. This includes freezing the machine.</li><li>Disabling it: Modifying (or erasing) its data.</li></ul>

0032Additionally, the adversary always knows the data classified as public and it knows the algorithm M that each machine performs. For simplicity, the present invention treats "natural" power outages, data loss and other hardware failures as actions of the adversary. Therefore, every time a machine is faulty, assume that it is the adversary that corrupted it.

0033When a server is corrupted at any point during the update phase between two rounds, the server is corrupted for both of these rounds. The reason behind this way of counting corrupted servers is that it is impossible or at least very hard to differentiate between an adversary who moves from one server to another during the update phase and the adversary who just stays in both all throughout. This differentiation is not a realistic concern in this setting, where update phase is negligibly short when compared to the length of one round. Furthermore, the present invention treats the adversary who jumps from one server to another in the same way as if both of them are corrupted throughout the round.

0034Apart from attacking servers in A, the adversary can attack the communication network between them. Assume the adversary has its own server E that is connected via its link to the same communication channel C that connects servers A. Therefore, it can both listen to messages broadcasted on C and broadcast messages to C. However, when a message reaches the communication channel, the adversary cannot prevent it from reaching all the links connected to it. The adversary can also make an attack on the link connecting some server in A with the communication channel. If a link to server P ∈ A is under such attack, the adversary can block it both ways: it can Prevent P from hearing the messages that are broadcasted on C as well as it can stop the messages sent by P broadcasted on C. Formally, the adversary can see all the tapes of both links L and the communication channel C. Replacing the algorithm of some link L with adversary's algorithm constitutes an active attack on that link while tampering with the algorithm of C is forbidden in this model.

0035The present invention assumes that the adversary attacking the servers A and the links L is "removable", i.e., it can be removed when it is detected. However, server E is not "removable", it cannot be traced or cut from C.

Assumptions About the Human Management of the System

0036Every server in A has console 38 through which it can display information to the human management. Through console 38 the managers can reboot the server and perform a procedure for renewal of the authentication keys. The console program allows for entering data to the server. The management is trusted in the following ways: they will not tamper with the servers and they won't cheat in the protocol specified for them. In other words, the management is trusted to follow instructions on when and how to reboot a server and perform the reinstallation of authentication keys.

0037The human management is responsible for tracing down the adversary attacking on the links. Assume that whenever the management is instructed to check whether the link is under attack and remove the potential attacker, the procedure is always successful. Also assume that all the procedures of rebooting servers, reinstalling public authentication keys and removing adversaries from the links take less time then the length of a round.

The Secret Sharing Scheme

0038A preferred method of the proactive verifiable secret sharing scheme of the present invention is shown by the flow chart of <figref idref="f0002">Figure 3</figref>. <figref idref="f0003">Figure 4</figref> is a detailed flow chart of step 314 in <figref idref="f0002">Figure 3</figref>. Similarly, <figref idref="f0004">Figure 5</figref> is a detailed flow chart of step 410 in <figref idref="f0003">Figure 4</figref>.

Initialization

0039Step 310 is to initialize the servers. Let p be a prime number such that p = mq + 1, where q is also prime and m is a small integer like 2, 3 or 4. Let g be an element of Zp of order q, i.e., gq = 1 (mod p). The prime p is chosen to be secure for the EIGamal encryption and signature schemes. The secret value x belongs to Zq. Use a modification of Shamir's secret sharing over a finite field Zq as the threshold secret sharing scheme: There exists a (k + 1) degree polynomial f in Zq, such that f(0) = x (mod q) and every server Pi, i ∈ {1, n} has its secret share xi(1) = f(i) (mc. The index (1) denotes that these will be the values used in the first round.

0040Additionally, each server Pi has its private authentication and encryption key wi, a random number in Zq. The set of public counterparts to these keys {ri(1)}i∈ {1,n} where <maths id="math0003" num=""><math display="block"><msup><msub><mi>r</mi><mi>i</mi></msub><mfenced><mn>1</mn></mfenced></msup><mo>=</mo><msup><mi>g</mi><msup><msub><mi>w</mi><mi>i</mi></msub><mfenced><mn>1</mn></mfenced></msup></msup><mfenced><munder><mi>mod p</mi><mo>̲</mo></munder></mfenced></math><img file="EP0723348A2_D0003.tif" /></maths> is public and stored by every server in A. Additionally, every server needs a set of one-way hashes of all xi's for robustness in reconstruction of the secret. The present invention uses exponentiation as a one-way hash, and so every server stores a set {yi(1)}i∈{1,n}, where <maths id="math0004" num=""><math display="block"><msup><msub><mi>y</mi><mi>i</mi></msub><mfenced><mn>1</mn></mfenced></msup><mo>=</mo><msup><mi>g</mi><msup><msub><mi>x</mi><mi>i</mi></msub><mfenced><mn>1</mn></mfenced></msup></msup><mfenced separators=""><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced></math><img file="EP0723348A2_D0004.tif" /></maths>

0041As mentioned in the description of the model, the present invention assumes that the adversary is not present in any way (passively or actively) during the initialization stage. Consequently, this initialization can be done openly.

0042After the initialization, local clocks of servers in A start ticking. At this point, the operation of the servers is synchronized into discrete time periods or rounds (step 312). At the end of each round, an update phase is triggered (step 314). In the update phase servers A perform an update protocol and then there is a reserved time for management to perform optional (up to k of them) key reinstallation procedures followed by share reconstruction protocols. The update phase is long enough to encompass all of these, but it is assumed to be short in comparison to a round.

Update Protocol

0043To update the shares, as shown by step 314 and <figref idref="f0003">Figure 4</figref>, the present invention adapts a simplified version of the update protocol presented in R. Ostrovsky & M. Yung. When the secret x is stored as a value f (0) = x of a k degree polynomial f in Zq, it can be updated by adding it to a k degree random polynomial δ (•), where δ (0) = 0, so that ft+1(0) = f (t)(0) + δ (0) = x + 0 = x. Ostrovsky and Yung noticed that the linerarity of the operation of computing a polynomial at a point allows for a very simple update of the shares xi = f(i), namely: <maths id="math0005" num=""><math display="block"><msup><munder><mi mathvariant="normal">f</mi><mo>̲</mo></munder><munder><mfenced separators=""><mi mathvariant="normal">t</mi><mo>+</mo><mn mathvariant="normal">1</mn></mfenced><mo>̲</mo></munder></msup><mo>⁢</mo><mi mathvariant="normal">δ</mi><mfenced><mo>•</mo></mfenced><mo>←</mo><msup><munder><mi mathvariant="normal">f</mi><mo>̲</mo></munder><munder><mfenced><mi mathvariant="normal">t</mi></mfenced><mo>̲</mo></munder></msup><mfenced><mo>•</mo></mfenced><mo>+</mo><munder><mi mathvariant="normal">δ</mi><mo>̲</mo></munder><mfenced><mo>•</mo></mfenced><mo>⁢</mo><mfenced><munder><mi>mod q</mi><mo>̲</mo></munder></mfenced><mo>⇐</mo><mo>=</mo><mo>⇒</mo><msub><munder><mo>∀</mo><mo>̲</mo></munder><munder><mi mathvariant="normal">i</mi><mo>̲</mo></munder></msub><mo>⁢</mo><msup><munder><mi mathvariant="normal">f</mi><mo>̲</mo></munder><mrow><munder><mrow><mo>(</mo><mi mathvariant="normal">t</mi><mo>+</mo><mn mathvariant="normal">1</mn></mrow><mo>̲</mo></munder><mo>)</mo></mrow></msup><mo>⁢</mo><munder><mfenced><mi mathvariant="normal">i</mi></mfenced><mo>̲</mo></munder><mo>=</mo><msup><mi mathvariant="normal">f</mi><mfenced><munder><mi mathvariant="normal">t</mi><mo>̲</mo></munder></mfenced></msup><mfenced><mi mathvariant="normal">i</mi></mfenced><mo>+</mo><munder><mrow><mi mathvariant="normal">δ</mi><mfenced><mi mathvariant="normal">i</mi></mfenced><mo>⁢</mo><mfenced><mi>mod q</mi></mfenced></mrow><mo>̲</mo></munder></math><img file="EP0723348A2_D0005.tif" /></maths> In the present system, δ(•) = (f1(•) + f2(•) + ... + fn(•)) (mod q), each polynomial fi (•), fi (0) = 0, i ∈ {1,n} of degree (k + 1) is picked independently and at random by the ith server. The update protocol for each server Pi, i ∈ {1,n} is as follows: <ol id="ol0004" compact="compact" ol-style=""><li>1. Pi picks (k + 1)2 random numbers {fi j}j∈{1, (k+1)} from Zq. These numbers define a polynomial fi (z) = fi 1z1 + fi 2z2 + ... + fi (k+1)zk in Zq, whose free coefficient is zero and hence, fi (0) = 0.</li><li>2. For all other servers, Pj, Pi sends fi (j) (mod q) to Pj.</li><li>3. Pi computes its new share xi(t+1) ← xi(t) + (f1(i) + f2(i) + ... + fn(i)) (mod q) and erases all the variables it used except its current secret key xi(t+1).</li></ol>

0044To make this protocol secure against the adversary with controlling capabilities, the present invention uses the mechanism of verifiable secret sharing using one-way functions presented by <nplcit id="ncit0006" npl-type="s"><text>P. Feldman, A Practical Scheme for Non-Interactive Verifiable Secret Sharing, Proc. of the 28th IEEE Symposium on the Foundations of Computer Science, pp. 427-37, 1987</text></nplcit> and then discussed by <nplcit id="ncit0007" npl-type="s"><text>T P. Pedersen, Distributed Provers with Applications to Undeniable Signature, Eurocrypto '91, 1991</text></nplcit>, which are both hereby incorporated by reference. This particular verifiable secret sharing scheme is used because it is non-interactive, and its side effect is that it allows for update of the secret's exponents yi together with updating xi's.

0045The honest servers should unanimously mark their shares of updating polynomial fj produced by server Pi as "bad" in the following two cases: <ol id="ol0005" compact="compact" ol-style=""><li>1. If the shares fi(j) that Pj's receive are not values of any polynomial of degree (k + 1), or they are, but this polynomial fi is not a correct update polynomial because fi (0) ≠ 0.</li><li>2. If shares <maths id="math0006" num=""><math display="block"><msub><mfenced open="{" close="}"><msup><mi>g</mi><mrow><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>j</mi></mfenced></mrow></msup></mfenced><mrow><mi>j</mi><mo>∈</mo><mfenced open="{" close="}" separators=""><mn>1</mn><mo>⁢</mo><mi>n</mi></mfenced></mrow></msub><mo>,</mo></math><img file="EP0723348A2_D0006.tif" /></maths> used for updating public values yj do not correspond to the secret update shares {fi(j}j∈ {1,n} of fj.</li></ol>

0046The values wi/ri as private / public key counterparts are used for authentication of messages coming from Pi and encryption of messages destined for Pi with EIGamal encryption. When Pi encrypts m ∈ Zq for Pj, it sends Ejk[m] = (m(rj)k, gk) where k ∈ Zq is a random number and the exponents are computed in Zp. The receiver decrypts by using <maths id="math0007" num=""><math display="block"><munder><mrow><mi mathvariant="normal">m</mi><mo>=</mo><mi mathvariant="normal">m</mi></mrow><mo>̲</mo></munder><mo>⁢</mo><msup><mfenced><msub><munder><mi mathvariant="normal">r</mi><mo>̲</mo></munder><munder><mi mathvariant="normal">j</mi><mo>̲</mo></munder></msub></mfenced><munder><mi mathvariant="normal">k</mi><mo>̲</mo></munder></msup><mo>*</mo><msup><mfenced><msup><munder><mi mathvariant="normal">g</mi><mo>̲</mo></munder><munder><mi mathvariant="normal">k</mi><mo>̲</mo></munder></msup></mfenced><mfenced><msub><munder><mrow><mo>-</mo><mi mathvariant="normal">w</mi></mrow><mo>̲</mo></munder><munder><mi mathvariant="normal">i</mi><mo>̲</mo></munder></msub></mfenced></msup><mfenced><munder><mi>mod p</mi><mo>̲</mo></munder></mfenced><mn mathvariant="normal">.</mn></math><img file="EP0723348A2_D0007.tif" /></maths>

0047The signature operation uses a collision-free hash function h : N ↦ Zq. The signature of message m with key wi where Si [h(m)] = (r, s) is r = gk (mod p), s = k(-1)(h(m) - rwi) (mod q). This signature can be verified with the public counterpart <maths id="math0008" num=""><math display="block"><msub><munder><mi mathvariant="normal">r</mi><mo>̲</mo></munder><munder><mi mathvariant="normal">i</mi><mo>̲</mo></munder></msub><mo>=</mo><msup><munder><mi mathvariant="normal">g</mi><mo>̲</mo></munder><msub><munder><mi mathvariant="normal">w</mi><mo>̲</mo></munder><munder><mi mathvariant="normal">i</mi><mo>̲</mo></munder></msub></msup><mfenced><munder><mi>mod p</mi><mo>̲</mo></munder></mfenced></math><img file="EP0723348A2_D0008.tif" /></maths> of wi by checking the equation <maths id="math0009" num=""><math display="block"><msup><mi>g</mi><mrow><mi>h</mi><mfenced><mi>m</mi></mfenced></mrow></msup><mo>⁢</mo><mover><mo>=</mo><mo>?</mo></mover><mo>⁢</mo><msup><mi>r</mi><mi>s</mi></msup><mo>⁢</mo><msubsup><mi>r</mi><mi>i</mi><mi>r</mi></msubsup><mfenced><munder><mi>mod p</mi><mo>̲</mo></munder></mfenced><mn>.</mn></math><img file="EP0723348A2_D0009.tif" /></maths>

0048The hash function h must have a property that knowing m, Si [h(m)] one cannot produce any pair m', Si [h(m')] where m' ≠ m.

0049All through the update phase, the encryption and authentication is performed with values wi(t),j, where t is the round that has just ended. The adversary who comprised a server during this round will know the secret key this server uses to sign and decrypt during the update protocol.

The Full Update Protocol

0050The following steps detail the update protocol used by the servers in step 314: <ul id="ul0005" list-style="none" compact="compact"><li>At step 410, each server Pi picks (k+ 1) random numbers fi 1, fi 2, ... , fi (k+1) in Zq which define an updating polynomial fi(z)=fi 1z1 + fi 2z2 + ... + fi (k+1)zk+1 in Zq (step 510).</li></ul>

0051It forms (n - 1) shares uij = fi (j) (mod q), j ≠ i of this polynomial (step 512), and creates its message msgi : <maths id="math0010" num=""><math display="block"><mrow><mo>(</mo><msup><mi>g</mi><msub><mi>t</mi><mrow><mi mathvariant="italic">i</mi><mo>⁢</mo><mn mathvariant="italic">1</mn></mrow></msub></msup><mo>,</mo><msup><mi>g</mi><msub><mi>t</mi><mrow><mi mathvariant="italic">i</mi><mo>⁢</mo><mn mathvariant="italic">2</mn></mrow></msub></msup><mo>,</mo><mo>…</mo><mo>,</mo><msup><mi>g</mi><msub><mi>t</mi><mrow><mi mathvariant="italic">i</mi><mo>⁢</mo><mfenced separators=""><mi>k</mi><mo>+</mo><mn>1</mn></mfenced></mrow></msub></msup><mo>,</mo><msup><msub><mi>E</mi><mn>1</mn></msub><msub><mi>k</mi><mrow><mi mathvariant="italic">i</mi><mo>⁢</mo><mn mathvariant="italic">1</mn></mrow></msub></msup><mfenced open="[" close="]" separators=""><msub><mi mathvariant="italic">u</mi><mrow><mi>i</mi><mo>⁢</mo><mn mathvariant="italic">1</mn></mrow></msub><mo>⁢</mo><msup><msub><mi mathvariant="italic">E</mi><mn mathvariant="italic">2</mn></msub><msub><mi mathvariant="italic">k</mi><mrow><mi mathvariant="italic">i</mi><mo>⁢</mo><mn mathvariant="italic">2</mn></mrow></msub></msup></mfenced><mo>⁢</mo><mfenced open="[" close="]" separators=""><msub><mi mathvariant="italic">u</mi><mrow><mi>i</mi><mo>⁢</mo><mn mathvariant="italic">2</mn></mrow></msub><mo>…</mo><msup><msub><mi mathvariant="italic">E</mi><mfenced separators=""><mi>i</mi><mo>-</mo><mn>1</mn></mfenced></msub><msub><mi mathvariant="italic">k</mi><mrow><mi mathvariant="italic">i</mi><mo>⁢</mo><mfenced separators=""><mi>i</mi><mo>-</mo><mn>1</mn></mfenced></mrow></msub></msup></mfenced><mo>,</mo><mfenced open="[" close="]" separators=""><msub><mi mathvariant="italic">u</mi><mrow><mi mathvariant="italic">i</mi><mo>⁢</mo><mfenced separators=""><mi>i</mi><mo>-</mo><mn>1</mn></mfenced></mrow></msub><mo>⁢</mo><msup><msub><mi mathvariant="italic">E</mi><mfenced separators=""><mi>i</mi><mo>+</mo><mn>1</mn></mfenced></msub><msub><mi mathvariant="italic">k</mi><mrow><mi mathvariant="italic">i</mi><mo>⁢</mo><mfenced separators=""><mi>i</mi><mo>+</mo><mn>1</mn></mfenced></mrow></msub></msup></mfenced><mo>⁢</mo><mfenced open="[" close="]" separators=""><msub><mi mathvariant="italic">u</mi><mrow><mi mathvariant="italic">i</mi><mo>⁢</mo><mfenced separators=""><mi>i</mi><mo>+</mo><mn>1</mn></mfenced></mrow></msub><mo>…</mo><msup><msub><mi mathvariant="italic">E</mi><mi>n</mi></msub><msub><mi mathvariant="italic">k</mi><mi mathvariant="italic">in</mi></msub></msup></mfenced><mo>⁢</mo><mfenced open="[" close="]"><msub><mi>u</mi><mi mathvariant="italic">in</mi></msub></mfenced></mrow></math><img file="EP0723348A2_D0010.tif" /></maths> where all exponentials are computed in Zp (step 514). Additionally, each server Pi picks its new private key wi(t+1) as a random number in Zq (step 516), and computes its corresponding new public key: <maths id="math0011" num=""><math display="block"><msup><msub><mi>r</mi><mi>i</mi></msub><mfenced separators=""><mi>t</mi><mo>+</mo><mn>1</mn></mfenced></msup><mo>=</mo><msup><mi>g</mi><msup><msub><mi>w</mi><mi>i</mi></msub><mfenced separators=""><mi>t</mi><mo>+</mo><mn>1</mn></mfenced></msup></msup><mfenced><munder><mi>mod p</mi><mo>̲</mo></munder></mfenced></math><img file="EP0723348A2_D0011.tif" /></maths> (step 518). Pi then broadcasts a pair (msgi, ri(t+1)) signed with its old key wi(t) (steps 412 and 520).

0052At step 414, each server Pi considers the messages it received in the previous step. If for some j, it received no or more than one authenticated message of the form (msgj, rj(t+1)), it marks Pj as "bad". Let Bi be the set of indexes of servers not marked as "bad". Pi then decrypts the <maths id="math0012" num=""><math display="block"><msubsup><mi>E</mi><mi>i</mi><msub><mi>k</mi><mi mathvariant="italic">ji</mi></msub></msubsup><mfenced open="[" close="]"><msub><mi>u</mi><mi mathvariant="italic">ji</mi></msub></mfenced></math><img file="EP0723348A2_D0012.tif" /></maths> parts of messages msgj, j ∈ Bi. Then, for every j ≠ i, it verifies whether uji agrees with the coefficients given in the <maths id="math0013" num=""><math display="block"><mfenced separators=""><msup><mi>g</mi><msub><mi>f</mi><mrow><mi mathvariant="italic">j</mi><mo>⁢</mo><mn mathvariant="italic">1</mn></mrow></msub></msup><mo>⁢</mo><msup><mi>g</mi><msub><mi>f</mi><mrow><mi mathvariant="italic">j</mi><mo>⁢</mo><mn mathvariant="italic">2</mn></mrow></msub></msup><mo>…</mo><msup><mi>g</mi><msub><mi>f</mi><mrow><mi mathvariant="italic">j</mi><mo>⁢</mo><mfenced separators=""><mi>k</mi><mo>+</mo><mn>1</mn></mfenced></mrow></msub></msup></mfenced></math><img file="EP0723348A2_D0013.tif" /></maths> part of the message msgj: <maths id="math0014" num=""><math display="block"><msup><mi>g</mi><msub><mi>u</mi><mi mathvariant="italic">ji</mi></msub></msup><mo>⁢</mo><mover><mo>=</mo><mo>?</mo></mover><mo>⁢</mo><msup><mfenced><msup><mi>g</mi><msub><mi>f</mi><mi mathvariant="italic">ji</mi></msub></msup></mfenced><mi>i</mi></msup><mo>⁢</mo><msup><mfenced><msup><mi>g</mi><msub><mi>f</mi><mrow><mi mathvariant="italic">j</mi><mo>⁢</mo><mn mathvariant="italic">2</mn></mrow></msub></msup></mfenced><msup><mi>i</mi><mn>2</mn></msup></msup><mo>…</mo><msup><mfenced><msup><mi>g</mi><msub><mi>f</mi><mrow><mi>j</mi><mo>⁢</mo><mfenced separators=""><mi>k</mi><mo>+</mo><mn>1</mn></mfenced></mrow></msub></msup></mfenced><mrow><mi>i</mi><mo>⁢</mo><mfenced separators=""><mi>k</mi><mo>+</mo><mn>1</mn></mfenced></mrow></msup><mspace width="1em" /><mfenced separators=""><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced></math><img file="EP0723348A2_D0014.tif" /></maths>

0053If this equation does not hold, Pi marks Pj as "bad", removes j from Bi and creates an accusation that it was cheated by Pj, accij = (i, j). For each server marked "bad", Pi displays corresponding messages to the management on its display showing why it thinks something is wrong with Pi. Then, at step 416, the server broadcasts a signed set of all its accusations concatenated with the set of all new public keys <maths id="math0015" num=""><math display="block"><msub><mfenced open="{" close="}"><msub><mi>r</mi><mi>j</mi></msub></mfenced><mrow><mi>j</mi><mo>∈</mo><msub><mi>B</mi><mi>i</mi></msub></mrow></msub></math><img file="EP0723348A2_D0015.tif" /></maths> it received in the previous step. The signature is made with the old private key wi(t).

0054At step 418, each server Pi verifies signatures on the messages broadcasted in the previous step. If more than one message is broadcasted with the same signature, the corresponding server is marked "bad", set Bi is reduced and the proper messages for the management are displayed on Pi 's console. Servers display the set of pairs (j,l) on their consoles such that a new public key rl(t+1) was not acknowledged by Pj. This lets the management trace where the active link attacks are. However, the lack of acknowledgements for new public keys does not influence Bi. For each accusation accji by some server Pj, j ∈ Bi, server Pi broadcasts a signed response containing the share and the random vector used in communication with Pj : respi j = (i, j, ki j, ui j), so that to allow for a public trial to determine who was cheating. These responses should be concatenated and broadcasted with one signature.

0055At step 420, if more than one response was broadcasted with the signature of the same server, every server P marks it as "bad", reduces its set Bi and displays messages for the management. Each server P makes its own decision for every pair of (accj i,respi j) that were properly broadcasted by Pi in step (1). The values sent in respi j are treated with suspicion, so they are denoted with "primes": k'ij, u'ij. Every server P decides according to the following algorithm: <ol id="ol0006" compact="compact" ol-style=""><li>(a) If <maths id="math0016" num=""><math display="block"><msup><msub><mi>E</mi><mi>j</mi></msub><msup><mi>k</mi><mi mathvariant="italic">ij</mi></msup></msup><mfenced open="[" close="]"><msub><mi>u</mi><mi mathvariant="italic">ij</mi></msub></mfenced><mo>≠</mo><mfenced separators=""><msub><mi mathvariant="italic">uʹ</mi><mi mathvariant="italic">ij</mi></msub><mo>⁢</mo><msup><mfenced><msup><msub><mi>r</mi><mi>j</mi></msub><mfenced><mi>t</mi></mfenced></msup></mfenced><mrow><msub><mi>k</mi><mi mathvariant="italic">ij</mi></msub><mo>⁢</mo><mi>ʹ</mi></mrow></msup><mfenced separators=""><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo><msup><mi>g</mi><mrow><msub><mi>k</mi><mi mathvariant="italic">ij</mi></msub><mo>⁢</mo><mi>ʹ</mi></mrow></msup><mfenced separators=""><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced></mfenced><mo>,</mo></math><img file="EP0723348A2_D0016.tif" /></maths> or when Pi did not respond to Pj's accusation at all, then Pi is cheating and so it must be marked as "bad". Otherwise:</li><li>(b) If (ui j, ki j) are indeed the values that were used in msgi, then check whether u'ij = uij is the proper share of polynomial fi, by evaluating the same equation (2) as should be used by Pj in step (2). If the equation does not agree, then it is a proof that Pi sent a bad share to Pj and so it must be marked as "bad". If the equation is correct, then P marks Pj, as "bad".</li></ol>

0056For each server marked "bad", set Bi is reduced and corresponding messages on Pi's console are displayed. At step 422, each server Pi computes: <maths id="math0017" num=""><math display="block"><mtable><mtr><mtd><mspace width="4em" /></mtd><mtd><msubsup><mi>x</mi><mi>i</mi><mfenced separators=""><mi>t</mi><mo>+</mo><mn>1</mn></mfenced></msubsup><mo>↼</mo><msubsup><mi>x</mi><mi>i</mi><mfenced><mi>t</mi></mfenced></msubsup><mo>+</mo><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>k</mi><mo>∈</mo><msub><mi>B</mi><mi>i</mi></msub></mrow></munder></mstyle><msub><mi>f</mi><mi>k</mi></msub><mfenced><mi>i</mi></mfenced></mstyle><mspace width="1em" /><mrow><mo>(</mo></mrow></mtd></mtr><mtr><mtd><msubsup><mrow><msub><mo>∀</mo><mrow><mi>j</mi><mo>≠</mo><mi>i</mi></mrow></msub><mo>⁢</mo><msubsup><mi>y</mi><mi>j</mi><mfenced separators=""><mi>t</mi><mo>+</mo><mn>1</mn></mfenced></msubsup><mo>←</mo><msubsup><mi>y</mi><mi>j</mi><mfenced><mi>t</mi></mfenced></msubsup><mo>*</mo></mrow><mover><mi>k</mi><mo>‾</mo></mover><mo>-</mo></msubsup></mtd><mtd><mspace width="1em" /></mtd></mtr></mtable></math><img file="EP0723348A2_D0017.tif" /></maths> Also, each server deletes all the variables used in this protocol, except of new share xi(t+1), new key wi(t+1), set {yj(t+1)}j∈{1,n} and set {rj(t+1)}j∈{1,n} of new public keys.

0057The proper update polynomial δ(•) is equal to the sum <maths id="math0018" num=""><math display="block"><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>k</mi><mo>∈</mo><mi>B</mi></mrow></munder></mstyle><msub><mi>f</mi><mi>k</mi></msub><mfenced><mo>•</mo></mfenced><mo>⁢</mo><mfenced separators=""><mi>mod</mi><mspace width="1em" /><mi>q</mi></mfenced></mstyle><mo>,</mo></math><img file="EP0723348A2_D0018.tif" /></maths> where B = Bi (in step 420) for at least (k + 2) servers Pi, i ∈ {1, n}.

0058Whenever a server P is expecting to receive a signed broadcast of a message of a known format and it receives two such messages, both seemingly coming from the same server Pi, then P marks Pi as faulty. Of course, the attacker could always send the same message that Pi did. In this protocol, every server sends up to three messages. Therefore, whenever P gets a set Ci of messages seemingly signed by Pi, it should throw away those elements of Ci that were broadcasted by Pi in some previous step of the protocol, and then if all other elements of Ci are the same, take this element as Pi's message. Otherwise, mark Pi as "bad", because it is either cheating or it is duplicated by the adversary who compromised its authentication key. Another fine point is that if Pi sees some messages signed seemingly by itself, it also marks itself as "bad" and computes Bi accordingly. This way, even though it is duplicated, it will compute its new share xi(t+1) and all {yj(t+1)}j∈{1,n} correctly. Its new public authentication and encryption key ri(t+1) is not acknowledged through, and must still be taken care of.

Analysis of the Update Protocol

0059The adversary can interfere with the above protocol in three ways: <ul id="ul0006" list-style="bullet"><li>It can make the server it controls cheat in this protocol. A disabled server will look like it is cheating or like it is sending random messages (if it encrypts and signs messages with the wrong keys).</li><li>It can send messages signed with the keys of the server it compromised during the round before this update phase. For the other servers, this case is indistinguishable from the case when the server is still controlled by the adversary.</li><li>It can attack a link between a server and a communication channel.</li></ul>

0060Since at every update round there are (k + 2) servers who are honest, who were not compromised in the previous round and whose link to the communication channel is not under active attack, these servers' sets Bi will all be the same and will have at least (k + 2) elements. Therefore, the secret-sharing polynomial f will be updated with at least (k + 2) polynomials fi, none of which can be reconstructed by the adversary. In the worst case, the adversary can learn k shares of each of these polynomials, but since they are all of the degree (k + 1) and fi (0) = 0 for each of them, one needs (k + 1) shares to reconstruct them.

Recovery After Update

0061From the messages displayed on the servers' consoles, the management can decide which machines are controlled, compromised or disabled and which links were under active attack by the adversary. In particular, the consoles will display information on two (often intersecting) sets of servers: <ul id="ul0007" list-style="bullet"><li>Those who didn't receive some acknowledgements of their new public keys.</li><li>Those whose new public keys are not acknowledged by at least (k + 2) servers, whose secret shares xi(t+1) are badly computed and inconsistent with the new polynomial f(t+2). Also, their view of the current set {yj(t+1)}j∈{1,n} is not correct.</li></ul>

0062The first set gives the management information about the active link attacks. The managers then promptly remove the adversary from the deduced links. With regard to the second set, the managers first perform a key reinstallation procedure (step 316) and then trigger an automatic share recovery protocol (step 318). Let C be the set of servers in A whose public keys {rj} are well-distributed and acknowledged by other servers. Then |C| ≧ k + 2.

0063The reinstallation of Pi's key (step 316) is as follows: Through Pi's console, the managers install the set {rj}j∈ C and then ask Pi to pick its new random private key wi ∈ Zq. Pi picks such a number and displays the corresponding public key <maths id="math0019" num=""><math display="block"><msub><mi>r</mi><mi>i</mi></msub><mo>=</mo><msup><mi>g</mi><msub><mi>w</mi><mi>i</mi></msub></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced><mn>.</mn></math><img file="EP0723348A2_D0019.tif" /></maths>

0064The managers then install this number in all other servers. Set C is augmented by Pi. When this reinstallation is finished, the managers trigger the recovery protocol on servers C. Alternatively, the servers themselves are programmed so that whenever some public key is reinstalled in them they start an agreement protocol to trigger the recovery protocol automatically, when all the servers in the C are ready.

Share Recovery Protocol

0065Let Pu denote the server who's share xu = f(u) needs to be reinstalled. At first, step 610, the servers choose an initial set B⊂C \ {Pu} of (k + 2) servers. They are picked from C because they must be able to authenticate q themselves to Pu and vice-versa. This is easy since servers are ordered by indexes and they know the current state of C, i.e., servers who have working authentication and encryption keys. The protocol must have the following properties in the presence of the adversary: <ul id="ul0008" list-style="bullet"><li>Pu learns only xu, i.e., it can't learn any other share xi where i ∈ B.</li><li>No (k - 1) group F ⊂ A \ {Pu} of servers can learn xu or any xi, where i ∈ A \ F.</li><li>Server Pu learns the proper set {yi}i∈{1,n}.</li></ul>

0066The basic set of (k + 2) servers with valid shares of f, can recover not only x = f (0) (mod q) but any other value of f, in particular the share xu = f (uv) (mod q) that Pu needs. This can be done with the Lagrange interpolation formula. After set B of (k + 2) servers that are supposed to cooperate is established, each Pi, i ∈ B sends <maths id="math0020" num=""><math display="block"><msub><mi>a</mi><mi>i</mi></msub><mo>=</mo><msub><mi>x</mi><mi>i</mi></msub><mstyle displaystyle="true"><munder><mo>∏</mo><mrow><mi>j</mi><mo>∈</mo><mi>B</mi><mo>,</mo><mi>j</mi><mo>≠</mo><mi>i</mi></mrow></munder></mstyle><mfrac><mrow><mi>u</mi><mo>-</mo><mi>j</mi></mrow><mrow><mi>i</mi><mo>-</mo><mi>j</mi></mrow></mfrac><mfenced><mi mathvariant="italic">mod q</mi></mfenced></math><img file="EP0723348A2_D0020.tif" /></maths> to Pu. Then Pu adds them together to get <maths id="math0021" num=""><math display="block"><msub><mi>x</mi><mi>u</mi></msub><mo>=</mo><mi>f</mi><mfenced><mi>u</mi></mfenced><mo>=</mo><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mi>B</mi></mrow></munder></mstyle><msub><mi>a</mi><mi>i</mi></msub></mstyle><mn>.</mn></math><img file="EP0723348A2_D0021.tif" /></maths> However, if the present invention only did that, Pu would also learn all xi 's from ai 's. But the present invention can treat ais as trivial secret shares of xv. So the present invention requires servers in B to rerandomize these shares before sending them to Pu: Each server Pi in B picks (k + 2) random numbers {cij}j∈B in Zq. Then they exchange these values pairwise: Pi gives Ci j to Pj and gets Cj i. And then each sends a'i = a i + Σj∈Bcji - Σj∈Bcji (mod q) to Pu . Notice that Σi∈ Ba'i = xu (mod q), so this is another secret sharing of xu .Now the basic scheme must be made verifiable using the same tools used in the update phase protocol.

0067Given below is the full protocol for making the scheme verifiable. Notice that all broadcasts involve servers in C including the ones that are not currently in set B and the server Pu. For clarity, the below does not mention that for every authenticated broadcast, the recipients check the signature on the message and when there is a duplication attack (because the sender is cheating or its keys are compromised and duplicated), they mark this server as "bad" and display adequate messages on their consoles for the management. This is the same procedure as in the update protocol. The protocol for making the scheme verifiable is: <ul id="ul0009" list-style="none" compact="compact"><li>all Pi 's in B compute k + 2 random values {ci j}j∈ B in Zq each, and broadcast: <maths id="math0022" num="(3)"><math display="block"><mfenced separators=""><msub><mfenced open="{" close="}" separators=""><msup><mi>g</mi><msub><mi>c</mi><mi mathvariant="italic">ij</mi></msub></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced></mfenced><mrow><mi>j</mi><mo>∈</mo><mi>B</mi></mrow></msub><mo>⁢</mo><msub><mfenced open="{" close="}" separators=""><msup><msub><mi>E</mi><mi>j</mi></msub><msub><mi>k</mi><mi mathvariant="italic">ij</mi></msub></msup><mfenced open="[" close="]"><msub><mi>c</mi><mi mathvariant="italic">ij</mi></msub></mfenced></mfenced><mrow><mi>j</mi><mo>∈</mo><mi>B</mi></mrow></msub></mfenced></math><img file="EP0723348A2_D0022.tif" /></maths> and a signature of this message (step 612).</li></ul>

0068At step 614, all Pi 's in B decrypt values {cj i}j∈B from the above broadcasts and verify whether they were given right shares from every server Pj, by taking the exponent <maths id="math0023" num=""><math display="block"><msup><mi>g</mi><msub><mi>c</mi><mi mathvariant="italic">ji</mi></msub></msup></math><img file="EP0723348A2_D0023.tif" /></maths> broadcast by Pj in the same message. If this value does not agree, Pi broadcasts an accusation acci j = (i, j, Si[i, j]) of Pj to all servers (step 616). It also marks Pj as a "bad" server.

0069At step 618, just like in the update protocol, for each accusation accj i by some server Pj , server Pi verifies the signature Sj [j, i], and if this proves that the originator of the accusation knows x, then Pi responds by broadcasting ci j and the random vector used in communication with Pj : respi j = (i, j, ki j, ci j), so as to allow for a public trial to determine who was cheating (step 620).

0070At step 622, every server P (not only the ones in B), for all pairs accj i, respi j broadcasted in the two previous steps, verifies whether these are the true values used in the communication between Pi and Pj, and if they are, checks whether the exponent <maths id="math0024" num=""><math display="block"><msup><mi>g</mi><msub><mi>c</mi><mi mathvariant="italic">ji</mi></msub></msup><mfenced><munder><mi>mod p</mi><mo>̲</mo></munder></mfenced></math><img file="EP0723348A2_D0024.tif" /></maths> of the sent value agrees with the exponent broadcasted by Pi in the set <maths id="math0025" num=""><math display="block"><mrow><mo>(</mo><msub><mfenced open="{" close="}" separators=""><msup><mi>g</mi><msub><mi>c</mi><mi mathvariant="italic">ij</mi></msub></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced></mfenced><mrow><mi>j</mi><mo>∈</mo><mi>B</mi></mrow></msub><mn>.</mn></mrow></math><img file="EP0723348A2_D0025.tif" /></maths> This step is equivalent to the verification in step 420 of the update protocol. Either Pi or Pj will turn out to be cheaters and will be adequately marked as "bad" by P.

0071At step 624, every server considers its local set Fi of servers it marked as "bad" in the previous step. If | Fi | = m ≠ 0, they compute new B: B ← (B \ F) ∪ {max(B) + 1, ..., max(B) + m}. Due to broadcasts, all honest and active servers will have the same view of F and hence the same view of the new B. After they recompute the B, they start the protocol again from step 610.

0072At step 626, if nobody cheated in the previous step, every server Pi computes its subshare: <maths id="math0026" num="(4)"><math display="block"><msub><mi mathvariant="italic">aʹ</mi><mi>i</mi></msub><mo>=</mo><msub><mi>a</mi><mi>i</mi></msub><mo>+</mo><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>j</mi><mo>∈</mo><mi>B</mi></mrow></munder></mstyle><msub><mi>c</mi><mi mathvariant="italic">ij</mi></msub></mstyle><mo>-</mo><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>j</mi><mo>∈</mo><mi>B</mi></mrow></munder></mstyle><msub><mi>c</mi><mi mathvariant="italic">ji</mi></msub></mstyle><mfenced><mi mathvariant="italic">mod q</mi></mfenced></math><img file="EP0723348A2_D0026.tif" /></maths> At step 628, each server Pi in B broadcasts <maths id="math0027" num=""><math display="block"><msubsup><mi>E</mi><msub><mi>r</mi><mi>u</mi></msub><msub><mi>k</mi><mi>i</mi></msub></msubsup><mfenced open="[" close="]"><msubsup><mi>a</mi><mi>i</mi><mi>ʹ</mi></msubsup></mfenced></math><img file="EP0723348A2_D0027.tif" /></maths> to all servers where ki is a random number in Zq.

0073At step 630, Pu decrypts all {a'i}i∈ B from these broadcasts and computes xu = Σi∈ Ba'i (mod q). Then it checks whether the exponent <maths id="math0028" num=""><math display="block"><msup><mi>g</mi><msub><mi>x</mi><mi mathvariant="italic">u</mi></msub></msup><mfenced><munder><mi>mod p</mi><mo>̲</mo></munder></mfenced></math><img file="EP0723348A2_D0028.tif" /></maths> of this value is the same as the public key yu that was installed at Pu initially If it is, the reconstruction ends at step 632. If not, some server from B must have cheated. P finds the cheaters by evaluating for every i ∈ B: <maths id="math0029" num=""><math display="block"><msup><mi>g</mi><msub><mi>a</mi><mi>i</mi></msub></msup><mo>←</mo><mfenced><msub><mi>y</mi><mi>i</mi></msub></mfenced><mstyle displaystyle="false"><munder><mo>∏</mo><mrow><mi>j</mi><mo>∈</mo><mi>B</mi><mo>,</mo><mi>j</mi><mo>≠</mo><mi>i</mi></mrow></munder></mstyle><mfrac><mrow><mi>v</mi><mo>-</mo><mi>j</mi></mrow><mrow><mi>i</mi><mo>-</mo><mi>j</mi></mrow></mfrac><mfenced><mi mathvariant="italic">mod p</mi></mfenced></math><img file="EP0723348A2_D0029.tif" /></maths><maths id="math0030" num=""><math display="block"><msup><mi>g</mi><msub><mi>a</mi><mi>i</mi></msub></msup><mo>⁢</mo><mover><mo>=</mo><mo>?</mo></mover><mo>⁢</mo><msup><mi>g</mi><msub><mi>a</mi><mi>i</mi></msub></msup><mo>*</mo><mstyle displaystyle="true"><munder><mo>∏</mo><mrow><mi>j</mi><mo>∈</mo><mi>B</mi></mrow></munder></mstyle><msup><mi>g</mi><msub><mi>c</mi><mi mathvariant="italic">ij</mi></msub></msup><mo>*</mo><msup><mfenced separators=""><mstyle displaystyle="true"><munder><mo>∏</mo><mrow><mi>j</mi><mo>∈</mo><mi>B</mi></mrow></munder></mstyle><msup><mi>g</mi><msub><mi>c</mi><mi mathvariant="italic">ji</mi></msub></msup></mfenced><mfenced separators=""><mo>-</mo><mn>1</mn></mfenced></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced></math><img file="EP0723348A2_D0030.tif" /></maths> where the values <maths id="math0031" num=""><math display="block"><msub><mfenced open="{" close="}"><msup><mi>g</mi><msub><mi>c</mi><mi mathvariant="italic">ij</mi></msub></msup></mfenced><mrow><mi>i</mi><mo>,</mo><mi>j</mi><mo>∈</mo><mi>B</mi></mrow></msub></math><img file="EP0723348A2_D0031.tif" /></maths> are taken from broadcasts in step 612. If the second formula does not hold, it means that Pj did not send the proper a'i to Pu. To prove it to others, Pu broadcasts its accusation acci = (i, Stemp [i]) to all other servers (step 634). Also, it itself marks all the cheaters as a "bad" set F.

0074At step 636, like in step 618 of this protocol, every accused server Pi verifies the signature on the accusation acci and if it is valid, it broadcasts response respi = (i, ki, a'i).

0075At step 638, every server P checks all these accusations by first checking that these are the values used in the communication and then checking the same verification equations as Pu performed above. Again, they will all arrive at the same set F of servers they detected to be faulty. If it turns out that it is Pu who is cheating, then they will all send adequate messages to the system managers and the recovery procedure will be stopped (step 640). This event would mean that Pu is again controlled by the adversary. This is just like any other adversary detection: The system managers will read the warnings displayed by the servers and restart the whole recovery process. If however, Pu 's accusations are correct then, as usual, the servers display proper warnings for the system management and continue the recovery by recomputing the set B: B ← (B \ F) ∪ {max(B) + 1, ..., max (B) + m}, where |F| = m, and restarting the whole protocol from step 610.

Security of the Update Protocol in the Presence of Controlled Servers

0076Securing the above protocol in the presence of k cheating servers and no attacks on the links can be reduced to verifiable secret sharing. Namely, the solution is a mechanism with which the honest servers Pi will be able to detect if any particular server Pi was cheating in the protocol. In this case, they will unanimously mark its shares of updating polynomial fi as "bad". Pi cheats in the above protocol if and only if the values that it sends to other servers in step 612 are not proper values of any k degree polynomial f over Zq such that f(0) = 0 (mod q). This is a somewhat simplified case of verifiable secret sharing, which is called verified sharing of a value, because every server P distributes a known value zero among (n - 1) other servers (it also gives one share to itself). Just like in verifiable secret sharing, honest servers should unanimously agree whether the "secret" value zero was properly shared by P. Also, just like in verifiable secret sharing, it should be achieved in such a way that each server learns only its own secret share.

0077The modified steps 618-620 of the update protocol from above would be: <maths id="math0032" num=""><math display="block"><msup><msub><mi>x</mi><mi>i</mi></msub><mfenced separators=""><mi>t</mi><mo>+</mo><mn>1</mn></mfenced></msup><mo>←</mo><msup><msub><mi>x</mi><mi>i</mi></msub><mfenced><mi>t</mi></mfenced></msup><mo>+</mo><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>k</mi><mo>∈</mo><msub><mi>B</mi><mi>i</mi></msub></mrow></munder></mstyle><msub><mi>f</mi><mi>k</mi></msub><mfenced><mi>i</mi></mfenced><mo>⁢</mo><mfenced><mi mathvariant="italic">mod q</mi></mfenced></mstyle><mo>,</mo></math><img file="EP0723348A2_D0032.tif" /></maths> where Bi is the set of indexes of all servers whose update polynomials were not marked as "bad" by Pi. With verifiable secret sharing mechanism, if Pi and Pj are both honest during the update phase, then Bi = Bj, i.e., they will have the same judgment about the honesty of other servers.

0078Existing protocols for verifiable secret sharing all require a broadcast channel. Therefore, from this point, assume that each of the n secret-sharing servers has a link that connects it to a common broadcast channel like ethernet. Every message that gets onto this broadcast channel gets to all links connecting this channel to the servers.

0079If verifiable secret sharing in the presence of up to k cheating, disabled or frozen servers during the update is achieved, there will be at least n - k updating polynomials fi with which every honest server will update its shares.

0080This degree of re-randomization of shares is enough to ensure the second property of the proactive scheme, namely that knowing k shares before the update and k shares after does not let the adversary reconstruct the secret. The fine point is when k servers are controlled during the update: The adversary will then know k shares of each updating polynomial fi, and this will allow her to reconstruct all of them, because the free coefficient of them all is known to be zero. Hence, she can compute the total updating value δ(i) = (f1(i)+ f2(i)+ ... + fn(i)) (modq) of every server Pi . However, if the adversary compromises a set F of k servers during the update phase, she can not compromise any other servers in either the round before or after this update. Hence she knows all {xi(t)}i∈F and {δ(l)}i∈{1,n} which in particular allows her to compute {xi(t+1)}i∈F which she knows anyway. But she still cannot learn any additional share xi(t), j ∉ F or xi(t+1), j ∉ F, which would allow her to reconstruct the secret.

Security of the Update Protocol in the Presence of "Duplication" Attacks and Link Attacks

0081If the adversary compromises server A in round t and leaves it in the same round, then during the update phase between rounds t and (t + 1) this server will not be faulty, but the adversary will know all its secrets. Assume an adversary who has only compromise servers (no active disruption of the protocol). Let F be the set of servers compromised by the adversary during round t and during the update t/(t+1). In the worst case, |F|= (k -1). Let G be a set of "good" servers, who are absolutely secure against the adversary both in the round and during the update. Obviously, each fi, i ∈ G that they will send to servers F. Now, depending on the protocol, it may or may not learn the shares of fi, i ∈ G that A gets. If servers send the shares of their updating polynomials just encrypted under the key known to A, then the adversary can learn them.

Proactively Secure Public Key Certification Authority

0082Presented is a complete solution showing how to apply proactive secret sharing to implement a proactively secure Key Certification Authority center. Described is a system that performs an ElGamal signature operation of messages and maintains its signature key proactively. Such a system can be effectively used as a key certification authority, because the messages it signs could be in public keys and identification tags of other users.

Distributed Version of ElGamal Signature

0083At first, assume a distributed version of the ElGamal signature algorithm, in which a signature operation is performed by a group of participating servers, who form a signature center together. The signature is composed of the partial signatures of these servers. It can be checked with a single public verification key. This means that, conceptually, there is also a single signature key, only that it is shared among the servers forming the signature center. The algorithm allows a change in the distribution of this secret key among the servers that share it, i.e., it allows proactive update of shares.

Initialization

0084Let p be a large prime number and g a random number smaller than p. Both p and g are known by all the parties in the network. Each server Pi takes as its private key a random number xi, where i ∈ {0,n} and xi < p - 1. After the private keys of all the servers are initialized, it is required that in every consequent round, the sum x1(t)+x2(t)+...+xn(t)=x(mod q), where xi(t) stands for a private key of the server Pi at round t and x stand for a conceptual constant secret key of the signature center. Initially, each server computes the public counterpart of its private key: <maths id="math0033" num=""><math display="block"><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><msup><mi>g</mi><msub><mi>x</mi><mi>i</mi></msub></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced><mn>.</mn></math><img file="EP0723348A2_D0033.tif" /></maths>

0085Then they send out their parts of a public key to one another, so that the public verification counterpart of x can be computed: <maths id="math0034" num="(5)"><math display="block"><mi>y</mi><mo>←</mo><msub><mi>y</mi><mn>1</mn></msub><mo>⁢</mo><msub><mi>y</mi><mn>2</mn></msub><mo>…</mo><msub><mi>y</mi><mi>n</mi></msub><mo>=</mo><msup><mi>g</mi><msub><mi>x</mi><mn>1</mn></msub></msup><mo>⁢</mo><msup><mi>g</mi><msub><mi>x</mi><mn>1</mn></msub></msup><mo>…</mo><msup><mi>g</mi><msub><mi>x</mi><mi>n</mi></msub></msup><mo>=</mo><msup><mi>g</mi><mrow><msub><mi>x</mi><mn>1</mn></msub><mo>+</mo><msub><mi>x</mi><mn>2</mn></msub><mo>+</mo><mo>…</mo><mo>+</mo><msub><mi>x</mi><mi>n</mi></msub></mrow></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced></math><img file="EP0723348A2_D0034.tif" /></maths> The sequence (p, g, y, n) is a public key used for verification of the signatures produced by this signature center.

Issuing of a Signature

0086To sign message m, each server picks its own secret random number ki, relative prime to (p - 1). Then each server Pi computes the first part of its signature: <maths id="math0035" num=""><math display="block"><msub><mi>r</mi><mi>i</mi></msub><mo>=</mo><msup><mi>g</mi><msub><mi>k</mi><mi>i</mi></msub></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced><mn>.</mn></math><img file="EP0723348A2_D0035.tif" /></maths> Each server broadcasts its ri to other servers, so that each of them can compute a second part of its signature: <maths id="math0036" num="(6)"><math display="block"><msub><mi>s</mi><mi>i</mi></msub><mo>=</mo><msup><msub><mi>k</mi><mi>i</mi></msub><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><mfenced separators=""><mi>m</mi><mo>-</mo><msub><mi>x</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>r</mi><mn>1</mn></msub><mo>⁢</mo><msub><mi>r</mi><mn>2</mn></msub><mo>…</mo><msub><mi>r</mi><mi>n</mi></msub></mfenced><mo>⁢</mo><mfenced separators=""><mi mathvariant="italic">mod p</mi><mo>-</mo><mn>1</mn></mfenced></math><img file="EP0723348A2_D0036.tif" /></maths>

0087The value of ki-1(mod p-1) can be found by the Euclidean algorithm, just like in the original ElGamal signature scheme. The signed message is a following sequence: <maths id="math0037" num="(7)"><math display="block"><mi>S</mi><mfenced><mi>m</mi></mfenced><mo>=</mo><mfenced separators=""><mi>m</mi><mo>,</mo><msub><mi>s</mi><mn>1</mn></msub><mo>,</mo><msub><mi>s</mi><mn>2</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>s</mi><mi>n</mi></msub><mo>,</mo><msub><mi>r</mi><mn>1</mn></msub><mo>,</mo><msub><mi>r</mi><mn>2</mn></msub><mo>…</mo><mo>,</mo><msub><mi>r</mi><mi>n</mi></msub></mfenced></math><img file="EP0723348A2_D0037.tif" /></maths>

Verification of a Signature

0088The party that needs to verify the signature checks whether the following is true: <maths id="math0038" num="(8)"><math display="block"><msup><mi>g</mi><mi mathvariant="italic">nm</mi></msup><mo>=</mo><msup><mi>y</mi><mrow><msub><mi>r</mi><mn>1</mn></msub><mo>⁢</mo><msub><mi>r</mi><mn>2</mn></msub><mo>…</mo><msub><mi>r</mi><mi>n</mi></msub></mrow></msup><mo>⁢</mo><msup><msub><mi>r</mi><mn>1</mn></msub><msub><mi>s</mi><mn>1</mn></msub></msup><mo>⁢</mo><msup><msub><mi>r</mi><mn>2</mn></msub><msub><mi>s</mi><mn>2</mn></msub></msup><mo>…</mo><msup><msub><mi>r</mi><mi>n</mi></msub><msub><mi>s</mi><mi>n</mi></msub></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced></math><img file="EP0723348A2_D0038.tif" /></maths> We can show that this is true by the following transformations: <maths id="math0039" num=""><math display="block"><mtable columnalign="left"><mtr><mtd><msup><mi>y</mi><mrow><msub><mi>r</mi><mn>1</mn></msub><mo>…</mo><msub><mi>r</mi><mi>n</mi></msub></mrow></msup><mo>⁢</mo><msup><msub><mi>r</mi><mn>1</mn></msub><msub><mi>s</mi><mn>1</mn></msub></msup><mo>…</mo><msup><msub><mi>r</mi><mi>n</mi></msub><msub><mi>s</mi><mi>n</mi></msub></msup><mo>=</mo><msup><mfenced><msup><mi>g</mi><mrow><msub><mi>x</mi><mn>1</mn></msub><mo>+</mo><mo>…</mo><mo>+</mo><msub><mi>x</mi><mi>n</mi></msub></mrow></msup></mfenced><mrow><msub><mi>r</mi><mn>1</mn></msub><mo>…</mo><msub><mi>r</mi><mi>n</mi></msub></mrow></msup><mo>⁢</mo><msup><mfenced><msup><mi>g</mi><msub><mi>k</mi><mn>1</mn></msub></msup></mfenced><mrow><msup><msub><mi>k</mi><mn>1</mn></msub><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><mfenced separators=""><mi>m</mi><mo>-</mo><msub><mi>x</mi><mn>1</mn></msub><mo>⁢</mo><msub><mi>r</mi><mn>1</mn></msub><mo>…</mo><msub><mi>r</mi><mi>n</mi></msub></mfenced></mrow></msup><mo>…</mo><msup><mfenced><msup><mi>g</mi><msub><mi>k</mi><mi>n</mi></msub></msup></mfenced><mrow><msup><msub><mi>k</mi><mi>n</mi></msub><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><mfenced separators=""><mi>m</mi><mo>-</mo><msub><mi>x</mi><mi>n</mi></msub><mo>⁢</mo><msub><mi>r</mi><mn>1</mn></msub><mo>…</mo><msub><mi>r</mi><mi>n</mi></msub></mfenced></mrow></msup><mo>=</mo></mtd></mtr><mtr><mtd><mo>=</mo><msup><mi>g</mi><mrow><msub><mi>x</mi><mn>1</mn></msub><mo>⁢</mo><msub><mi>r</mi><mn>1</mn></msub><mo>…</mo><msub><mi>r</mi><mi>n</mi></msub><mo>+</mo><mo>…</mo><mo>+</mo><msub><mi>x</mi><mi>n</mi></msub><mo>⁢</mo><msub><mi>r</mi><mn>1</mn></msub><mo>…</mo><msub><mi>r</mi><mi>n</mi></msub></mrow></msup><mo>⁢</mo><msup><mi>g</mi><mrow><mi>m</mi><mo>-</mo><msub><mi>x</mi><mn>1</mn></msub><mo>⁢</mo><msub><mi>r</mi><mn>1</mn></msub><mo>⁢</mo><msub><mi>r</mi><mn>2</mn></msub><mo>…</mo><msub><mi>r</mi><mi>n</mi></msub></mrow></msup><mo>⁢</mo><msup><mi>g</mi><mrow><mi>m</mi><mo>-</mo><msub><mi>x</mi><mi>n</mi></msub><mo>⁢</mo><msub><mi>r</mi><mn>1</mn></msub><mo>…</mo><msub><mi>r</mi><mi>n</mi></msub></mrow></msup><mo>=</mo><msup><mi>g</mi><mrow><mi>n</mi><mo>*</mo><mi>m</mi></mrow></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced></mtd></mtr></mtable></math><img file="EP0723348A2_D0039.tif" /></maths>

Security Analysis

0089The security of the above basic distributed ElGamal algorithm, as well as the rest of the present protocol, relies on the assumption that computing logarithms in the final field of big prime order is computationally infeasible in probabilistic polynomial time. This is the fundamental security assumption of the ElGamal and DSA encryption and signature schemes. The above distributed version of ElGamal public key algorithm is just as secure as the original version. If the attacker can break the present invention's algorithm, she would be able to break the regular ElGamal as well. Assume that the attacker knows m, S(m) and x1, x2,...,Xn-1. What she still needs is xn. She can compute <maths id="math0040" num=""><math display="block"><msup><mi>g</mi><msub><mi>x</mi><mi>n</mi></msub></msup><mo>=</mo><mi>y</mi><mo>*</mo><msup><mi>g</mi><mrow><mo>-</mo><mfenced separators=""><msub><mi>x</mi><mn>1</mn></msub><mo>+</mo><msub><mi>x</mi><mn>2</mn></msub><mo>+</mo><mo>…</mo><mo>+</mo><msub><mi>x</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub></mfenced></mrow></msup><mo>,</mo></math><img file="EP0723348A2_D0040.tif" /></maths> where negative exponent is computed modulo (p - 1). We substitute x = xnsn, k = knr1r2...rn. Then the attacker knows: <maths id="math0041" num=""><math display="block"><msup><mi>g</mi><mi>x</mi></msup><mo>=</mo><msup><mfenced><msup><mi>g</mi><msub><mi>x</mi><mi>n</mi></msub></msup></mfenced><msub><mi>s</mi><mi>n</mi></msub></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced><mo>,</mo><msup><mi>g</mi><mi>k</mi></msup><mo>=</mo><msup><mfenced><msup><mi>g</mi><msub><mi>k</mi><mi>n</mi></msub></msup></mfenced><mrow><msub><mi>r</mi><mn>1</mn></msub><mo>⁢</mo><msub><mi>r</mi><mn>2</mn></msub><mo>…</mo><msub><mi>r</mi><mi>n</mi></msub></mrow></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced></math><img file="EP0723348A2_D0041.tif" /></maths> and x+1 = snkn + xnr1r2...,(2 = m (mod p-1). In this set of three equations, one of the first two can be derived from the rest. For example, gk = gx+k(gx) (mod p-1). So, left are the following two equations, where a, b are known and x, k are unknown: <maths id="math0042" num=""><math display="block"><msup><mi>g</mi><mi>x</mi></msup><mo>=</mo><mi>a</mi><mfenced><mi mathvariant="italic">mod p</mi></mfenced><mspace width="4em" /><mi>x</mi><mo>+</mo><mi>k</mi><mo>=</mo><mi>b</mi><mo>⁢</mo><mfenced separators=""><mi mathvariant="italic">mod p</mi><mo>-</mo><mn>1</mn></mfenced></math><img file="EP0723348A2_D0042.tif" /></maths>

0090The security of the original ElGamal algorithm is based on the fact that the second equation does not give out any information about x, if k is unknown, and hence, ElGamal is as secure as it is computationally infeasible to compute a logarithm x = logga (mod p) in probabilistic polynomial time.

Adapting the Distributed ElGamal to Proactive Threshold Secret Sharing Scheme

0091The present invention incorporates Shamir polynomial secret-sharing to the above distributed ElGamal. This incorporation creates a threshold proactive scheme, but the threshold is only during the round. As noted before, threshold during the update phase requires recovery mechanism. This scheme does not achieve robustness. Hence, this preliminary scheme is secure against an adversary who: <ul id="ul0010" list-style="bullet" compact="compact"><li>Can compromise up to k servers in each round.</li><li>Can freeze up to k servers during the round, but not during an update phase.</li></ul>

0092The present invention is related to the Desmedt and Frankel solution of threshold secret-sharing in the exponent, described in <nplcit id="ncit0008" npl-type="s"><text>Threshold Cryptosystems, Crypto 89, pp. 307-15</text></nplcit>, which is hereby incorporated by reference. Their idea was to use Shamir threshold secret-sharing by polynomial of degree k and then compute the exponent of the secret with a group of (k + 2) honest servers by computing components of Lagrange interpolation formula locally at each server. The similarity between their scheme and the present invention is that both use Lagrange reconstruction of a secret shared with a polynomial, but nobody can learn the reconstruction secret in the process. The secret is only used to either exponentiate a message (in the case of Desmedt and Frankel) or issue an ElGamal-derived signature (in the present invention). The present invention uses k degree polynomial function f to secret-share f (0) = x among n servers. It picks p and the element g ∈ Zp so that g is of prime order q, i.e., gq = 1 (mod p). Q Should be as big as possible, so that p = mq + 1 , m ∈ {2,3,4}. The public key becomes now a sequence (p, q, g, y, k).

0093The present invention assumes that during a safe initialization stage, each server gets its secret share of x, xi = f(i), where f is computed in Zq. To issue a signature, the servers agree on a group B of any (k + 2) active servers that will participate in signing. The other servers are idle. Knowing set B, each server Pi, i ∈ B computes: <maths id="math0043" num="(9)"><math display="block"><msub><mi>a</mi><mi>i</mi></msub><mo>=</mo><msup><msub><mi>x</mi><mi>i</mi></msub><mo>*</mo></msup><mstyle displaystyle="true"><munder><mo>∏</mo><mrow><mi>j</mi><mo>∈</mo><mi>B</mi><mo>,</mo><mi>j</mi><mo>≠</mo><mi>i</mi></mrow></munder></mstyle><mfrac><mrow><mn>0</mn><mo>-</mo><mi>j</mi></mrow><mrow><mi>i</mi><mo>-</mo><mi>j</mi></mrow></mfrac><mfenced><mi mathvariant="italic">mod q</mi></mfenced></math><img file="EP0723348A2_D0043.tif" /></maths> From the Lagrange interpolation formula, this ensures that <maths id="math0044" num="(10)"><math display="block"><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><mi>B</mi></mrow></munder></mstyle><msub><mi>a</mi><mi>i</mi></msub></mstyle><mo>=</mo><mi>x</mi><mfenced><mi mathvariant="italic">mod q</mi></mfenced></math><img file="EP0723348A2_D0044.tif" /></maths> because ∀i, xi = f(i), x = f(0) and f is a k degree polynomial in Zq. The existence of inverses of (i - j), i ≠ j is ensured by the fact that q is prime. Using ai 's as their partial secrets, servers in B issue their partial signatures (ri ,si), i ∈ B following the basic proactive protocol from above: <maths id="math0045" num=""><math display="block"><msub><mi>r</mi><mi>i</mi></msub><mo>=</mo><msup><mi>g</mi><msub><mi>k</mi><mi>i</mi></msub></msup><mfenced><mi mathvariant="italic">mod p</mi></mfenced></math><img file="EP0723348A2_D0045.tif" /></maths><maths id="math0046" num=""><math display="block"><mtable><mtr><mtd><msub><mi>s</mi><mi>i</mi></msub><mo>=</mo><msup><msub><mi>k</mi><mi>i</mi></msub><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>*</mo><mfenced separators=""><mi>m</mi><mo>-</mo><msub><mi>a</mi><mi>i</mi></msub><mstyle displaystyle="true"><munder><mo>∏</mo><mrow><mi>j</mi><mo>∈</mo><mi>B</mi></mrow></munder></mstyle><msub><mi>r</mi><mi>j</mi></msub></mfenced><mo>⁢</mo><mfenced><mi mathvariant="italic">mod q</mi></mfenced></mtd></mtr><mtr><mtd><mi>S</mi><mfenced><mi>m</mi></mfenced><mo>=</mo><mfenced separators=""><mi>m</mi><mo>⁢</mo><msub><mfenced open="{" close="}"><mfenced separators=""><msub><mi>r</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>s</mi><mi>i</mi></msub></mfenced></mfenced><mrow><mi>i</mi><mo>∈</mo><mi>B</mi></mrow></msub></mfenced></mtd></mtr></mtable></math><img file="EP0723348A2_D0046.tif" /></maths> The verification formula becomes: <maths id="math0047" num="(11)"><math display="block"><msup><mi>g</mi><mrow><mfenced separators=""><mi>k</mi><mo>+</mo><mn>2</mn></mfenced><mo>*</mo><mi>m</mi></mrow></msup><mo>=</mo><mi>y</mi><mstyle displaystyle="false"><munder><mo>∏</mo><mrow><mfenced separators=""><msub><mi>r</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>s</mi><mi>i</mi></msub></mfenced><mo>∈</mo><msub><mi>S</mi><mfenced><mi>m</mi></mfenced></msub><mo>⁢</mo><msub><mi>r</mi><mi>i</mi></msub></mrow></munder></mstyle><mstyle displaystyle="true"><munder><mo>∏</mo><mrow><mfenced separators=""><msub><mi>r</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>s</mi><mi>i</mi></msub></mfenced><mo>∈</mo><mi>s</mi><mfenced><mi>m</mi></mfenced></mrow></munder></mstyle><msubsup><mi>r</mi><mi>i</mi><msub><mi>s</mi><mi>i</mi></msub></msubsup><mfenced><mi mathvariant="italic">mod p</mi></mfenced></math><img file="EP0723348A2_D0047.tif" /></maths>

Verification and Robustness in Signing Protocol

0094The first property that must be added to the above preliminary threshold scheme is robustness during the round. This will make it secure against an adversary who can control up to k servers, but still only during the round, not during an update phase. The above threshold scheme is signers-dependent, because it is essential that before issuing the signature, honest servers agree on the (k + 2) element set B of servers that will cooperate to sign the message. To be able to pick set B of some currently active, honest servers, a mechanism with which honest servers can filter out cheaters is needed. Formally, each server, knowing B, m and S(m), should be able to verify for every server Pi, i ∈ B, whether its partial signature (ri, si) ∈ S(m) is correct, in the sense of being computed according to the protocol with the same m, g, p, q and the proper secret key ai computed according to equation (5).

0095To enable this mutual partial verification between the servers, the present invention treats secret shares xi(t) of each server as their private signature keys and gives all other servers the public verification counterpart to these keys: <maths id="math0048" num=""><math display="block"><msup><msub><mi>y</mi><mi>i</mi></msub><mfenced><mi>t</mi></mfenced></msup><mo>=</mo><msup><mi>g</mi><msup><msub><mi>x</mi><mi>i</mi></msub><mfenced><mi>t</mi></mfenced></msup></msup><mfenced><munder><mi>mod p</mi><mo>̲</mo></munder></mfenced><mn>.</mn></math><img file="EP0723348A2_D0048.tif" /></maths> Every honest processor P (not only those that are currently in B) verifies a partial signature (ri, si) ∈ S(m) of every server Pi in B in the following two steps: <ol id="ol0007" compact="compact" ol-style=""><li>1. Knowing current B and <maths id="math0049" num=""><math display="block"><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><msup><mi>g</mi><msub><mi>x</mi><mi>i</mi></msub></msup><mfenced><munder><mi>mod p</mi><mo>̲</mo></munder></mfenced><mo>,</mo></math><img file="EP0723348A2_D0049.tif" /></maths>P computes <maths id="math0050" num=""><math display="block"><msup><mi>g</mi><msub><mi>a</mi><mi>i</mi></msub></msup><mo>=</mo><msup><mfenced><msub><mi>y</mi><mi>i</mi></msub></mfenced><mstyle displaystyle="false"><munder><mo>∏</mo><mrow><mi>j</mi><mo>∈</mo><mi>B</mi><mo>,</mo><mi>j</mi><mo>≠</mo><mi>i</mi><mo>⁢</mo><mfrac><mrow><mn>0</mn><mo>-</mo><mi>j</mi></mrow><mrow><mi>i</mi><mo>-</mo><mi>j</mi></mrow></mfrac><mfenced><mi mathvariant="italic">mod q</mi></mfenced></mrow></munder></mstyle></msup><mfenced><mi mathvariant="italic">mod q</mi></mfenced><mn>.</mn></math><img file="EP0723348A2_D0050.tif" /></maths></li><li>2. Having computed <maths id="math0051" num=""><math display="block"><msup><mi>g</mi><msub><mi>a</mi><mi>i</mi></msub></msup></math><img file="EP0723348A2_D0051.tif" /></maths> as above, P takes S(m) and verifies Pi 's signature by the equation: <maths id="math0052" num=""><img file="EP0723348A2_D0052.tif" /></maths></li></ol>

0096In this way, all honest servers can determine set F ⊏B of faulty servers that cheated while issuing the signature S(m). * Since the servers are ordered by their indices i ∈ {1, n}, it is trivial for honest servers to update set B to filter out the detected cheaters and try a new set of active servers. For example, at the beginning of every round they start with B = 1, 2,..., k + 2 and every time they sign and detect a set of m > 0 cheaters F = {i1, i2,...im}, they take <maths id="math0053" num="(13)"><math display="block"><mi>B</mi><mo>←</mo><mfenced separators=""><mi>B</mi><mo>∖</mo><mi>F</mi></mfenced><mo>∪</mo><mfenced open="{" close="}" separators=""><mi>max</mi><mfenced><mi>B</mi></mfenced><mo>+</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>max</mi><mfenced><mi>B</mi></mfenced><mo>+</mo><mi>m</mi></mfenced></math><img file="EP0723348A2_D0053.tif" /></maths> Since the present invention assumes that at every round, up to k servers can be taken over by the adversary and thus can be cheating, the following update will be performed no more than k times (in the case when the cheaters come out "one by one"). This is equivalent to issuing up to k extra signatures every round. This is a negligible overhead.

0097The update protocol from above can be extended to ensure maintenance of public counterparts yi(t), of secret shares xi(t) for every round t. In step (2), when server Pi sends fi (j) to Pj, it also sends <maths id="math0054" num=""><math display="block"><msup><mi>g</mi><mrow><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>j</mi></mfenced></mrow></msup></math><img file="EP0723348A2_D0054.tif" /></maths> to all other servers. This will allow all the servers to compute the public key for all i: <maths id="math0055" num="(14)"><math display="block"><msup><msub><mi>y</mi><mi>i</mi></msub><mfenced separators=""><mi>t</mi><mo>+</mo><mn>1</mn></mfenced></msup><mo>←</mo><msup><msub><mi>y</mi><mi>i</mi></msub><mfenced><mi>t</mi></mfenced></msup><mo>*</mo><mfenced separators=""><msup><mi>g</mi><mrow><msub><mi>f</mi><mn>1</mn></msub><mfenced><mi>i</mi></mfenced></mrow></msup><mo>⁢</mo><msup><mi>g</mi><mrow><msub><mi>f</mi><mn>2</mn></msub><mfenced><mi>i</mi></mfenced></mrow></msup><mo>…</mo><msup><mi>g</mi><mrow><msub><mi>f</mi><mi>n</mi></msub><mfenced><mi>i</mi></mfenced></mrow></msup></mfenced><mo>⁢</mo><mfenced><mi mathvariant="italic">mod p</mi></mfenced></math><img file="EP0723348A2_D0055.tif" /></maths> Assuming "hardness" of computing logarithms in Zp, broadcasting <maths id="math0056" num=""><math display="block"><msup><mi>g</mi><mrow><msub><mi>f</mi><mi>i</mi></msub><mfenced><mi>j</mi></mfenced></mrow></msup></math><img file="EP0723348A2_D0056.tif" /></maths> does not help the adversary.

0098Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention as defined by the appended claims.

Contents5

Every citation, both ways

Citations
Document	Relation	Office	Cited during
US8085938B2	Cited by	United States of America	Applicant
EP3330880A4	Cited by	European Patent Office (EPO)	Search report
WO02088912A3	Cited by	World Intellectual Property Organization (WIPO)	International search
EP1676396A4	Cited by	European Patent Office (EPO)	Search report
US10867018B2	Cited by	United States of America	Applicant
DE19847944A1	Cited by	Germany	Search report
WO02088912A2	Cited by	World Intellectual Property Organization (WIPO)	International search
CN112183566A	Cited by	China	Search report
WO02088912A3	Cited by	World Intellectual Property Organization (WIPO)	International search
EP1676396A1	Cited by	European Patent Office (EPO)	Search report
US8718283B2	Cited by	United States of America	Applicant
US7330969B2	Cited by	United States of America	Applicant
CN110999206A	Cited by	China	Search report
US7263191B2	Cited by	United States of America	Applicant
WO2005076518A1	Cited by	World Intellectual Property Organization (WIPO)	International search
US7035405B1	Cited by	United States of America	Applicant
US7219226B2	Cited by	United States of America	Applicant

4 members in 3 offices; this record represents the family

This recordMember, by publication datePriority claim

Priority claims4

Priority claims
Document	Office	Kind	Date
37658095	United States of America	A	1995-01-23
19950376580	United States of America	–	1995-01-23
US19950376580	–	–	–
376580	–	–	–

Members4

Family members, oldest first
Document	Office	Kind
EP0723348A2This record	European Patent Office (EPO)	A2	1996-07-24
JPH08251157A	Japan	A	1996-09-27
US5625692A	United States of America	A	1997-04-29
JP3256427B2	Japan	B2	2002-02-12

4 legal events, as the office reported them to INPADOC

Over the term

Point at a mark for the event

Events

Legal events, newest first
	Event	Code
1997-01-22	Application withdrawnWithdrawn18W	18W
1996-12-06	Information on the status of an ep patent application or granted ep patentGrantedSTATUS: THE APPLICATION HAS BEEN WITHDRAWNSTAA	STAA
1996-07-24	Designated contracting statesAK	AK
1996-06-07	Public reference made under article 153(3) epc to a published international application that has entered the european phaseORIGINAL CODE: 0009012PUAI	PUAI