NEW DIRECTIONS IN CRYPTOGRAPHY 33 A public key cryptosystem is a pair of families (EkKEK)involves a matrix in version which is a harder problem.And and (Dx'kek of algorithms representing invertible it is at least conceptually simpler to obtain an arbitrary pair of transformations. inverse matrices than it is to invert a given matrix.Start with the identity matrix and do elementary row and column opera- Es:{M→{G (2)tions to obtain an arbitrary invertible matrix E.Then starting with do the inverses of these same elementary operations in reverse order to obtain D=E-1.The sequence of elementary Dk:{M0→{M0 (3) operations could be easily determined from a random bit string. Unfortunately,matrix inversion takes only about n opera- on a finite message space {M,such that tions.The ratio of"cryptanalytic"time(i.e.,computing D from E)to enciphering or deciphering time is thus at most n.and 1)for every K (K),Ek is the inverse of DK, 2)for every K {K)and M (M,the algorithms Ex and enormous block sizes would be required to obtain ratios of 106 Dk are easy to compute, or greater.Also,it does not appear that knowledge of the 3)for almost every K (K),each easily computed algo- elementary operations used to obtain E from I greatly reduces the time for computing D.And,since there is no round-off rithm equivalent to D&is computationally infeasible to derive from Ek, error in binary arithmetic,numerical stability is unimportant in 4)for every K (K),it is feasible to compute inverse pairs the matrix inversion.In spite of its lack of practical utility,this Ex and Dk from K. matrix example is still useful for clarifying the relationships necessary in a public key cryptosystem. Because of the third property,a user's enciphering key Ek can A more practical approach to finding a pair of easily com- be made public without compromising the security of his secret puted inverse algorithms E and D:such that D is hard to infer deciphering key D&.The cryptographic system is therefore split from E,makes use of the difficulty of analyzing programs in into two parts,a family of enciphering transformations and a low level languages.Anyone who has tried to determine what family of deciphering transformations in such a way that,given operation is accomplished by someone else's machine language a member ofone family,it is infeasible to find the corresponding program knows that E itself(i.e.,what E does)can be hard to member of the other. infer from an algorithm for E.If the program were to be made The fourth property guarantees that there is a feasible way purposefully confusing through addition of unneeded variables of computing corresponding pairs of inverse transformations and statements,then determining an inverse algorithm could be when no constraint is placed on what either the enciphering or made very difficult.Ofcourse,Emust be complicated enough to deciphering transformation is to be.In practice,the cryptoequip-prevent its identification from input-output pairs. ment must contain a true random number generator (e.g.,a Essentially what is required is a one-way compiler:one which noisy diode)for generating K,together with an algorithm for takes an easily understood program written in a high level generating the Ex-D&pair from its outputs. language and translates it into an incomprehensible program Given a system of this kind,the problem of key distribution in some machine language.The compiler is one-way because is vastly simplified.Each user generates a pair of inverse trans-it must be feasible to do the compilation,but infeasible to formations,E and D,at his terminal.The deciphering transfor- reverse the process.Since efficiency in size of program and mation D must be kept secret,but need never be communicated run time are not crucial in this application,such as compilers on any channel.The enciphering key E can be made public by may be possible if the structure of the machine language can placing it in a public directory along with the user's name and be optimized to assist in the confusion. address.Anyone can then encrypt messages and send them to Merkle [1]has independently studied the problem of distrib- the user,but no one else can decipher messages intended for uting keys over an insecure channel.His approach is different him.Public key cryptosystems can thus be regarded as multiple from that of the public key cryptosystems suggested above, access ciphers. and will be termed a public key distribution system.The goal It is crucial that the public file of enciphering keys be pro- is for two users,4 and B,to securely exchange a key over an tected from unauthorized modification.This task is made easier insecure channel.This key is then used by both users in a by the public nature of the file.Read protection is unnecessary normal cryptosystem for both enciphering and deciphering. and,since the file is modified infrequently,elaborate write Merkle has a solution whose cryptanalytic cost grows as n2 protection mechanisms can be economically employed. where n is the cost to the legitimate users.Unfortunately the A suggestive,although unfortunately useless,example of a cost to the legitimate users of the system is as much in transmis- public key cryptosystem is to encipher the plaintext,represented sion time as in computation,because Merkle's protocol requires as a binary n-vector m.by multiplying it by an invertible binary n potential keys to be transmitted before one key can be decided n X n matrix E.The cryptogram thus equals Em.Letting D= on.Merkle notes that this high transmission overhead prevents E-we have m=Dc.Thus,both enciphering and deciphering the system from being very useful in practice.If a one megabit require about n operations.Calculation of D from E,however,limit is placed on the setup protocol's overhead,his techniqueNEW DIRECTIONS IN CRYPTOGRAPHY 33 A public key cryptosystem is a pair of families {EK}KP{K} involves a matrix in version which is a harder problem. And and {DK}KP it is at least conceptually simpler to obtain an arbitrary pair of {K} of algorithms representing invertible transformations, inverse matrices than it is to invert a given matrix. Start with the identity matrix I and do elementary row and column opera￾EK:{M} → {M} (2) tions to obtain an arbitrary invertible matrix E. Then starting with I do the inverses of these same elementary operations in reverse order to obtain D 5 E21. The sequence of elementary DK:{M} → {M} (3) operations could be easily determined from a random bit string. Unfortunately, matrix inversion takes only about n3 opera￾on a finite message space {M}, such that tions. The ratio of “cryptanalytic” time (i.e., computing D from E) to enciphering or deciphering time is thus at most n, and 1) for every K P {K}, EK is the inverse of DK, enormous block sizes would be required to obtain ratios of 106 2) for every K P {K} and M P {M}, the algorithms EK and or greater. Also, it does not appear that knowledge of the DK are easy to compute, elementary operations used to obtain E from I greatly reduces 3) for almost every K P {K}, each easily computed algo- the time for computing D. And, since there is no round-off rithm equivalent to DK is computationally infeasible to error in binary arithmetic, numerical stability is unimportant in derive from EK, the matrix inversion. In spite of its lack of practical utility, this 4) for every K P {K}, it is feasible to compute inverse pairs matrix example is still useful for clarifying the relationships EK and DK from K. necessary in a public key cryptosystem. Because of the third property, a user’s enciphering key EK can A more practical approach to finding a pair of easily com￾be made public without compromising the security of his secret puted inverse algorithms E and D; such that D is hard to infer deciphering key DK. The cryptographic system is therefore split from E, makes use of the difficulty of analyzing programs in into two parts, a family of enciphering transformations and a low level languages. Anyone who has tried to determine what family of deciphering transformations in such a way that, given operation is accomplished by someone else’s machine language a member of one family, it is infeasible to find the corresponding program knows that E itself (i.e., what E does) can be hard to member of the other. infer from an algorithm for E. If the program were to be made The fourth property guarantees that there is a feasible way purposefully confusing through addition of unneeded variables of computing corresponding pairs of inverse transformations and statements, then determining an inverse algorithm could be when no constraint is placed on what either the enciphering or made very difficult. Of course, E must be complicated enough to deciphering transformation is to be. In practice, the cryptoequip- prevent its identification from input—output pairs. ment must contain a true random number generator (e.g., a Essentially what is required is a one-way compiler: one which noisy diode) for generating K, together with an algorithm for takes an easily understood program written in a high level generating the EK 2 DK pair from its outputs. language and translates it into an incomprehensible program Given a system of this kind, the problem of key distribution in some machine language. The compiler is one-way because is vastly simplified. Each user generates a pair of inverse trans- it must be feasible to do the compilation, but infeasible to formations, E and D, at his terminal. The deciphering transfor- reverse the process. Since efficiency in size of program and mation D must be kept secret, but need never be communicated run time are not crucial in this application, such as compilers on any channel. The enciphering key E can be made public by may be possible if the structure of the machine language can placing it in a public directory along with the user’s name and be optimized to assist in the confusion. address. Anyone can then encrypt messages and send them to Merkle [1] has independently studied the problem of distrib￾the user, but no one else can decipher messages intended for uting keys over an insecure channel. His approach is different him. Public key cryptosystems can thus be regarded as multiple from that of the public key cryptosystems suggested above, access ciphers. and will be termed a public key distribution system. The goal It is crucial that the public file of enciphering keys be pro- is for two users, A and B, to securely exchange a key over an tected from unauthorized modification. This task is made easier insecure channel. This key is then used by both users in a by the public nature of the file. Read protection is unnecessary normal cryptosystem for both enciphering and deciphering. and, since the file is modified infrequently, elaborate write Merkle has a solution whose cryptanalytic cost grows as n2 protection mechanisms can be economically employed. where n is the cost to the legitimate users. Unfortunately the A suggestive, although unfortunately useless, example of a cost to the legitimate users of the system is as much in transmis￾public key cryptosystem is to encipher the plaintext, represented sion time as in computation, because Merkle’s protocol requires as a binary n-vector m, by multiplying it by an invertible binary n potential keys to be transmitted before one key can be decided n 3 n matrix E. The cryptogram thus equals Em. Letting D 5 on. Merkle notes that this high transmission overhead prevents E21 we have m 5 Dc. Thus, both enciphering and deciphering the system from being very useful in practice. If a one megabit require about n limit is placed on the setup protocol’s overhead, his technique 2 operations. Calculation of D from E, however