1 tion) and which nonmechanical solutions (which in Our this manipulate also allowed. data) goa ! is to are divide D into n pieces D, ... D n in such a way that: more (1) of any k or knowledge D i pieces makes D Programming R. Rivest computable; easily Techniques Editor of 1 k- any leaves knowledge (2) or pieces Di fewer D the sense that all its completely undetermined (in equally are possible values likely). How to Share a Secret threshold scheme. Such a scheme is called a (k, n) Shamir Adi in threshold schemes the Efficient can helpful be very Technology Massachusetts Institute of order In keys. cryptographic of management protect to in we the protect to order encryp- but it, encrypt can data need we key tion a (further encryptions different method paper show how to divide we D into n this In data it). solve than rather problem the change most The reconstructable pieces in such a way that D is easily a secure key management scheme keeps the key in single, k pieces, but even complete knowledge of from any a well-guarded location (a computer, a human brain, or about D. information no absolutely reveals pieces 1 - k unreliable safe). This scheme is highly since a single construction This technique enables the of robust key misfortune or death, sudden breakdown, computer (a schemes systems cryptographic for that management ob- sabotage) can make the information inaccessible. An even reliably and securely can function when misfor- key at the dif- of copies multiple store to is solution vious half destroy tunes ex- security and pieces the breaches ferent locations, but this increases the danger of security the one but all pose of pieces. remaining er- human or betrayal, penetration~ (computer breaches key Key Words and Phrases: cryptography, manage- rors). scheme with n threshold = 2k- 1 n) (k, a using By interpolation ment, get a very robust we management scheme: We can key 5.6 5:39, Categories: CR when of the original key even recover [n/2J = k- 1 n the are destroyed, but our opponents cannot pieces reconstruct the key even when security breaches expose 1 pieces. k remaining [n/21 of k- = the between In other applications the tradeoff is not between but reliability, and conve- secrecy and safety nience of use. Consider, for example, a company that ex- checks digitally signs all its each (see RSA [5]). If of ecutive given a copy is the company's secret signature is key, the system If convenient but easy to misuse. the necessary cooperation of all the company's executives is Introduction 1. in- order to sign each in the system is safe but check, following Liu [4], In problem: the considers solution three least at requires standard The convenient. on working are scientists lock to wish They Eleven project. secret a is a per check, and it signatures easy to implement with so the up documents in a cabinet that the cabinet can be opened if Each small given is executive a scheme. threshold n) (3, only and of if six or more the scientists are present. What is the card magnetic the and company's piece, Di one with number the is What needed? locks of number smallest of smallest generating signature in them of three any accepts device keys the to carry? must scientist each locks copy temporary a destroy) later (and generate to order of minimal It is not hard to show that the solution uses 462 actual the signature key D. The device does not contain per keys 252 and locks are numbers scientist. These any secret information and need thus protected be it not clearly impractical, and they become exponentially have inspection. against must executive unfaithful An at worse scientists increases. number the when of least company's to order two in the forge accomplices to one In in the this generalize we problem paper scheme. this in signature (e.g., safe combina- data which the secret is some the D in Threshold schemes are ideally suited to applications fee without granted to Permission is material this of part or all copy group a which suspicious with individuals mutually of made the direct for distributed or commer- not are copies that provided would conflicting must cooperate. interests Ideally we advantage, cial the of title the publica- the ACM copyright notice and tion and by is copying that permis- given is appear, date its and notice like cooperation to be the on mutual consent, but based for the sion otherwise, copy To Machinery. Association Computing of power the can member each to gives mechanism this veto fee and/or specific or to permission. republish, requires a By group. choos- the of activities the paralyze properly Laboratory Author's present address: Computer for A. Shamir, Institute Massachusetts Science, MA Cambridge, Technology, of n can any give sufficiently parameters and k the ing we 02139. the while action some take to authority majority large the was This supported by under Office of Naval Research research block to power giving any sufficiently large minority the contract N00014-76-C-0366. no. @1979 $00.75. ACM 0001-0782/79/1100-0612 it. Communications November 1979 612 of Volume 22 the ACM Number 11

2 2. n) Threshold Scheme A Simple (k, affecting the other D i pieces. the company) without only executive leaving a when deleted is piece (A is based interpolation: on polynomial' Our scheme to makes it completely inaccessible, himself.) even ... the (x,, k 2-dimensional points y,) given in plane change changing It is easy to (3) the D i pieces without D--all one the original data Yk). we need is a new polynomial (xk, with distinct xi's , there is one and only degree for =yi q(x) all that such 1 - k polynomial q(x) of of change frequent A term. free the with q(x) same data of generality, we can assume that the i. Without loss this type can greatly enhance security since the pieces it divide To number. a be can (or is D made) pieces into exposed security breaches cannot be accumulated by polynomial degree k-1 random a pick we D~, all the are them of values of unless of same edition which in q(x)=ao+alx+ ao=D , and ... ak_ixk-~ polynomial. the q(x) evaluate: (4) we pieces, Di as values polynomial of tuples using By of can get a hierarchical scheme in which the number i ... D = D~ = q(i) ... D n = q(n). q(1) im- on needed to determine pieces D depends their of k any Given of subset these D~ values (together with company's example, if we For the portance. give find coefficients can we of identifying their the indices), each q(x), of values three president vice-president by q(x) D=q(O). evaluate then and interpolation, values two of q(x), and each executive one value of 1 the values, these of on k- just of Knowledge other then q(x), to checks enables scheme threshold n) (3, a suffice D. calculate to order in not does hand, signed by or executives, be three any by either any use To make this claim more precise, we modular of one executives two by or vice-president, a is whom of integers set The arithmetic. real of instead arithmetic the alone. president a p which in field a forms number modulo prime inter- A different (and somewhat less efficient) threshold Given we an integer valued data D, polation is possible. by scheme was recently [2]. Blakley G.R. developed bigger is which p prime a pick The n. and D both than chosen coefficients ak_~ in q(x) are randomly ... a~ 1979 September revised 1979; April Received integers in p), from a uniform [0, over the distribution modulo p. and the values D~ ... Dn are computed are assume Let us now that k-1 of these n pieces References in to an opponent. revealed each candidate value D' For 1. J., Hopcroft, A., Aho, and Ullman, J. The Design and Analysis Mass., Reading, Addison-Wesley, AIgorithms. Computer of 1974. polynomial can one only and one construct he p) [0, cryptographic keys. Proc. AFIPS 2. Blakley, G.R. Safeguarding '(0) such q '(x) of degree k- 1 that q =D' and =D~ '(0 q 313-317. 1979 NCC, Vol. 48, Arlington, Va., June 1979, pp. the p k- 1 given arguments. By for construction, these The Art D. of Computer Programming, Vol. 2: Knuth, 3. Reading, SeminumericalAlgorithms. Addison-Wesley, Mass., 1969. likely, equally polynomials possible are there is thus and 4. Liu, C.L. Introduction to Combinatorial Mathematics. McGraw- the nothing abolutely the about deduce can opponent Hill, New 1968. York, real value of D. method Adleman, 5. A R., for obtaining Rivest, Shamir, A., and L. public-key cryptosystems. Comm. A CM 21, digital 2 signatures and polynomial Efficient O(n log 2 n) algorithms evalu- for (Feb. 120-126. 1978), but and interpolation are discussed in [1] and [3], ation even algorithms fast quadratic straightforward the are enough the If schemes. management key practical for to number long, it is advisable is break it into shorter D blocks of bits (which are handled separately) order to in multiprecision blocks operations. The avoid arithmetic be short, since the smallest usable cannot arbitrarily of p is n value 1 (there must be at least n + 1 distinct + arguments in [0, p) to evaluate q(x) at). However, this is not severe limitation since sixteen bit modulus (which a unit) be handled by a cheap sixteen bit arithmetic can D~ suffices for applications with up to 64,000 pieces. n) Some of the useful properties of this threshold (k, and (when compared to the mechanical locks scheme solutions) keys are: (1) size The of each piece does not exceed the size of the original data. (2) When k is dynamically fixed, D~ pieces can be kept or leave join executives when (e.g., deleted or added any LThe be replaced by can other collection of func- polynomials tions which are easy to evaluate and to interpolate. 613 November 1979 Communications of Volume 22 the ACM Number 11