NEW DIRECTIONS IN CRYPTOGRAPHY 35 can be copied precisely,a true digital signature must be recog-a value y and knowledge of f.to calculate any x whatsoever nizable without being known. with the property that fx)=y.Indeed,if fis noninvertible in Consider the "login"problem in a multiuser computer sys- the usual sense,it may make the task of finding an inverse tem.When setting up his account,the user chooses a password image easier.In the extreme,if fx)=yo for all x in the domain, which is entered into the system's password directory.Each then the range off is (vo,and we can take any x as f(vo). time he logs in,the user is again asked to provide his password. It is therefore necessary that fnot be too degenerate.A small By keeping this password secret from all other users,forged degree of degeneracy is tolerable and,as discussed later,is logins are prevented.This,however,makes it vital to preserve probably present in the most promising class of one-way the security of the password directory since the information it functions. contains would allow perfect impersonation of any user.The Polynomials offer an elementary example of one-way func- problem is further compounded if system operators have legiti-tions.It is much harder to find a root xo of the polynomial mate reasons for accessing the directory.Allowing such legiti-equation p(x)=y than it is to evaluate the polynomial p(x)at mate accesses,but preventing all others,is next to impossible.x=xo.Purdy [11]has suggested the use of sparse polynomials This leads to the apparently impossible requirement for a of very high degree over finite fields,which appear to have new login procedure capable of judging the authenticity of very high ratios of solution to evaluation time.The theoretical passwords without actually knowing them.While appearing to basis for one-way functions is discussed at greater length in be a logical impossibility,this proposal is easily satisfied.When Section VI.And,as shown in Section V,one-way functions the user first enters his password PW.the computer automati- are easy to devise in practice. cally and transparently computes a function fPl)and stores The one-way function login protocol solves only some of this,not PW.in the password directory.At each successive the problems arising in a multiuser system.It protects against login,the computer calculates f),where X is the proffered compromise of the system's authentication data when it is not password,and compares f)with the stored value APW).If in use,but still requires the user to send the true password to and only if they are equal,the user is accepted as being authen-the system.Protection against eaves-dropping must be provided tic.Since the function fmust be calculated once per login,its by additional encryption,and protection against the threat of computation time must be small.A million instructions(costing dispute is absent altogether. approximately $0.10 at bicentennial prices)seems to be a rea- A public key cryptosystem can be used to produce a true sonable limit on this computation.If we could ensure,however.one-way authentication system as follows.If user 4 wishes to that calculation off required 1030 or more instructions,some- send a message M to user B.he "deciphers"it in his secret one who had subverted the system to obtain the password deciphering key and sends D(M).When user B receives it,he directory could not in practice obtain PW from APM),and can read it,and be assured of its authenticity by "enciphering" could thus not perform an unauthorized login.Note that APW)it with user 4's public enciphering key E4.B also saves D(M) is not accepted as a password by the login program since it as proof that the message came from A.Anyone can check this will automatically compute AAPW))which will not match the claim by operating on D(M)with the publicly known operation entry APW)in the password directory. E to recover M.Since only A could have generated a message We assume that the function fis public information,so that with this property,the solution to the one-way authentication it is not ignorance of fwhich makes calculation off difficult.problem would follow immediately from the development of Such functions are called one-way functions and were first public key cryptosystems. employed for use in login procedures by R.M.Needham [9,p. One-way message authentication has a partial solution sug- 91].They are also discussed in two recent papers [10],[11]gested to the authors by Leslie Lamport of Massachusetts Com- which suggest interesting approaches to the design of one- puter Associates.This technique employs a one-way function way functions. f mapping k-dimensional binary space into itself for k on the More precisely,a function f is a one-way fimnction if,for order of 100.If the transmitter wishes to send an N bit message any argument x in the domain of f.it is easy to compute the he generates 2N.randomly chosen.k-dimensional binary vec- corresponding value fx),yet,for almost all y in the range of tors x2Y2,.,xN,Yy which he keeps secret.The receiver f.it is computationally infeasible to solve the equationy=fx)is given the corresponding images under f.namely y,Yi2,Y2 for any suitable argument x. ·'yw,Yx.Later,when the message m=(m1,m2,···,mw)isto It is important to note that we are defining a function which be sent,the transmitter sends xi or Xi depending on whether is not invertible from a computational point of view.but whose m =0 or 1.He sends x2 or X2 depending on whether m2 noninvertibility is entirely different from that normally encoun-0 or 1.etc.The receiver operates with f on the first received tered in mathematics.A function f is normally called"nonin-block and sees whether it yields y or Y as its image and thus vertible"when the inverse of a point y is not unique,(i.e.,there learns whether it was x or Xi,and whether m=0 or 1.In a exist distinct pointsx and x2 such thatfx)=y=fx2)).We similar manner the receiver is able to determine m.m....m. emphasize that this is not the sort of inversion difficulty that But the receiver is incapable of forging a change in even one is required.Rather,it must be overwhelmingly difficult,given bit of m.NEW DIRECTIONS IN CRYPTOGRAPHY 35 can be copied precisely, a true digital signature must be recog- a value y and knowledge of f, to calculate any x whatsoever nizable without being known. with the property that f(x) 5 y. Indeed, if f is noninvertible in Consider the “login” problem in a multiuser computer sys- the usual sense, it may make the task of finding an inverse image easier. In the extreme, if f(x) [ y0 tem. When setting up his account, the user chooses a password for all x in the domain, which is entered into the system’s password directory. Each then the range of f is {y0}, and we can take any x as f 21 (y0). time he logs in, the user is again asked to provide his password. It is therefore necessary that f not be too degenerate. A small By keeping this password secret from all other users, forged degree of degeneracy is tolerable and, as discussed later, is logins are prevented. This, however, makes it vital to preserve probably present in the most promising class of one-way the security of the password directory since the information it functions. contains would allow perfect impersonation of any user. The Polynomials offer an elementary example of one-way func￾problem is further compounded if system operators have legiti- tions. It is much harder to find a root x0 of the polynomial mate reasons for accessing the directory. Allowing such legiti- equation p(x) 5 y than it is to evaluate the polynomial p(x) at mate accesses, but preventing all others, is next to impossible. x 5 x0. Purdy [11] has suggested the use of sparse polynomials This leads to the apparently impossible requirement for a of very high degree over finite fields, which appear to have new login procedure capable of judging the authenticity of very high ratios of solution to evaluation time. The theoretical passwords without actually knowing them. While appearing to basis for one-way functions is discussed at greater length in be a logical impossibility, this proposal is easily satisfied. When Section VI. And, as shown in Section V, one-way functions the user first enters his password PW, the computer automati- are easy to devise in practice. cally and transparently computes a function f(PW) and stores The one-way function login protocol solves only some of this, not PW, in the password directory. At each successive the problems arising in a multiuser system. It protects against login, the computer calculates f(X), where X is the proffered compromise of the system’s authentication data when it is not password, and compares f(X) with the stored value f(PW). If in use, but still requires the user to send the true password to and only if they are equal, the user is accepted as being authen- the system. Protection against eaves-dropping must be provided tic. Since the function f must be calculated once per login, its by additional encryption, and protection against the threat of computation time must be small. A million instructions (costing dispute is absent altogether. approximately $0.10 at bicentennial prices) seems to be a rea- A public key cryptosystem can be used to produce a true sonable limit on this computation. If we could ensure, however, one-way authentication system as follows. If user A wishes to that calculation of f send a message M to user B, he “deciphers” it in his secret 21 required 1030 or more instructions, some￾one who had subverted the system to obtain the password deciphering key and sends DA(M). When user B receives it, he directory could not in practice obtain PW from f(PW), and can read it, and be assured of its authenticity by “enciphering” could thus not perform an unauthorized login. Note that f(PW) it with user A’s public enciphering key EA. B also saves DA(M) is not accepted as a password by the login program since it as proof that the message came from A. Anyone can check this will automatically compute f(f(PW)) which will not match the claim by operating on DA(M) with the publicly known operation entry f(PW) in the password directory. EA to recover M. Since only A could have generated a message We assume that the function f is public information, so that with this property, the solution to the one-way authentication it is not ignorance of f which makes calculation of f problem would follow immediately from the development of 21 difficult. Such functions are called one-way functions and were first public key cryptosystems. employed for use in login procedures by R.M. Needham [9, p. One-way message authentication has a partial solution sug- 91]. They are also discussed in two recent papers [10], [11] gested to the authors by Leslie Lamport of Massachusetts Com￾which suggest interesting approaches to the design of one- puter Associates. This technique employs a one-way function way functions. f mapping k-dimensional binary space into itself for k on the More precisely, a function f is a one-way function if, for order of 100. If the transmitter wishes to send an N bit message any argument x in the domain of f, it is easy to compute the he generates 2N, randomly chosen, k-dimensional binary vec￾tors x1,X1,x2,X2 corresponding value f(x), yet, for almost all y in the range of , ???, xN,XN which he keeps secret. The receiver f, it is computationally infeasible to solve the equation y 5 f(x) is given the corresponding images under f, namely y1,Y1,y2,Y2 ???,yN,YN. Later, when the message m 5 (m1,m2 for any suitable argument x. , ???,mN) is to It is important to note that we are defining a function which be sent, the transmitter sends x1 or X1 depending on whether is not invertible from a computational point of view, but whose m1 5 0 or 1. He sends x2 or X2 depending on whether m2 5 noninvertibility is entirely different from that normally encoun- 0 or 1, etc. The receiver operates with f on the first received tered in mathematics. A function f is normally called “nonin- block and sees whether it yields y1 or Y1 as its image and thus vertible” when the inverse of a point y is not unique, (i.e., there learns whether it was x1 or X1, and whether m1 5 0 or 1. In a similar manner the receiver is able to determine m2,m3 exist distinct points x ,...,mN. 1 and x2 such that f(x1) 5 y 5 f(x2)). We emphasize that this is not the sort of inversion difficulty that But the receiver is incapable of forging a change in even one is required. Rather, it must be overwhelmingly difficult, given bit of m