38 DIFFIE AND HELLMAN view correct.Experience has shown,however,that few systems the NP includes the class p and one of the great open sections can resist the concerted attack of skillful cryptanalysts,and in complexity theory is whether the class NP is directly larger. many supposedly secure systems have subsequently been Among the problems known to be solvable in NP time,not broken. known to be solvable in P time,are versions of the eling In consequence of this,judging the worth of new systems salesman problem,the satisfiability problem for positional cal- has always been a central concern of cryptographers.During culus,the knapsack problem,the graph ring problem,and many the sixteenth and seventeenth centuries,mathematical argu- scheduling and minimization problems [13,pp.363-404],[14]. ments were often invoked to argue the strength of cryptographic We see that it is not lack of interest or effort which has prevented methods,usually relying on counting methods which showed people from finding solutions in P time for these problems.It the astronomical number possible keys.Though the problem is thus strongly believed that at least one of these problems is far too difficult to laid to rest by such simple methods,even must not be in the class p and that therefore the class NP is the noted alraist Cardano fell into this trap [2,p.145].As strictly larger. systems those strength had been so argued were repeatedly Karp has identified a subclass of the NP problems,called broken,the notion of giving mathematical proofs for the secu- NP complete,with the property that if any one of them is in rity of systems fell into disrepute and was replaced by certica- B then all NP problems are in P Karp lists 21 problems which tion via crypanalytic assault. are NP complete,including all of the problems mentioned During this century,however,the pendulum has begun swing above [14]. back in the other direction.In a paper intimately connected While the NP complete problems show promise for crypto- with the birth of information theory,Shannon showed that the graphic use,current understanding of their difficulty includes one time pad system,which had been use since the late twenties only worst case analysis.For cryptographic purposes,typical offered "perfect secrecy(a summ of unconditional security). computational costs must be considered.If,however,we replace The probably secure terms investigated by Shannon rely on the worst case computation time with average or typical computa- use of either they whose length grows linearly with the length tion time as our complexity measure,the current proofs of the of the usage or on perfect source coding and are therefore equivalences among the NP complete problems are no longer too provideldy for most purposes.We note that neither public valid.This suggests several interesting topics for research.The cryptosystems nor one-way authentication systems can uncon- ensemble and typicality concepts familiar to information theo- ditionally secure because the public information always deter- rists have an obvious role to play. mines the secret information uniquely among members of a finite set.With unlimited computation,problem could therefore We can now identify the position of the general cryptanalytic problem among all computational problems. be solved by a straightforward touch. The past decade has seen the rise of two closely related The cryptanalytic difficulty of a system whose encryption and decryption operations can be done in P time cannot be deciplines devoted to the study of the costs of computation computational complexity theory and the analysis of loga- greater than NP rithms.The former has classified known problems in computing To see this,observe that any cryptanalytic problem can be into broad classes by difficulty,while the latter concentrated on solved by finding a key,inverse image,etc.,chosen from a finding better algorithms and lying the resources they consume. finite set.Choose the key nondeterministically and verify in P After a brief discussion into complexity theory,we will examine time that it is the correct one.If there are M possible keys to its application to cryptography,particularly the analysis of one- choose from,an M-fold parallelism must be employed.For way functions. example in a known plaintext attack,the plaintext is encrypted The function is said to belong to the complexity class P(for simultaneously under each of the keys and compared with the polynomial)if it can be computed by a deterministic making cryptogram.Since,by assumption,encryption takes only P Machine in a time which is bounded above by some polynomial time,the cryptanalysis takes only NP time. function of the length of its input.One might think of this as We also observe that the general cryptanalytic problem is the class of easily computed functions,but more accurate to NP complete.This follows from the breadth of our definition say that a function not in this class must be hard to compute of cryptographic problems.A one-way function with an NP for at least some inputs.There problems which are known not complete inverse will be discussed next. to be in the class P [13.405-4251. Cryptography can draw directly from the theory of NP com- There are many problems which arise in engineering which plexity by examining the way in which NP complete problems cannot be solved in polynomial time by any known uniques, can be adapted to cryptographic use.In particular,there is an unless they are run on a computer with an submited degree of NP complete problem known as the knapsack problem which parallelism.These problems may or not belong to the class p lends itself readily to the construction of a one-way function. but belong to the class NP(nondeterministic,polynomial)of LetY=x)=a·.·x where a is a known vector of n problems solvable polynomial time on a "nondeterministic"intergers(a,z,,a)andx is a binary n-vector.Calculation computer(i.e.,with an unlimited degree ofparallelism).Clearly of y is simple,involving a sum of at most n integers.The38 DIFFIE AND HELLMAN view correct. Experience has shown, however, that few systems the NP includes the class P, and one of the great open sections can resist the concerted attack of skillful cryptanalysts, and in complexity theory is whether the class NP is directly larger. many supposedly secure systems have subsequently been Among the problems known to be solvable in NP time, not broken. known to be solvable in P time, are versions of the eling In consequence of this, judging the worth of new systems salesman problem, the satisfiability problem for positional cal￾has always been a central concern of cryptographers. During culus, the knapsack problem, the graph ring problem, and many the sixteenth and seventeenth centuries, mathematical argu- scheduling and minimization problems [13, pp. 363–404], [14]. ments were often invoked to argue the strength of cryptographic We see that it is not lack of interest or effort which has prevented methods, usually relying on counting methods which showed people from finding solutions in P time for these problems. It the astronomical number possible keys. Though the problem is thus strongly believed that at least one of these problems is far too difficult to laid to rest by such simple methods, even must not be in the class P, and that therefore the class NP is the noted alraist Cardano fell into this trap [2, p. 145]. As strictly larger. systems those strength had been so argued were repeatedly Karp has identified a subclass of the NP problems, called broken, the notion of giving mathematical proofs for the secu- NP complete, with the property that if any one of them is in rity of systems fell into disrepute and was replaced by certica- P, then all NP problems are in P. Karp lists 21 problems which tion via crypanalytic assault. are NP complete, including all of the problems mentioned During this century, however, the pendulum has begun swing above [14]. back in the other direction. In a paper intimately connected While the NP complete problems show promise for crypto- with the birth of information theory, Shannon showed that the graphic use, current understanding of their difficulty includes one time pad system, which had been use since the late twenties only worst case analysis. For cryptographic purposes, typical offered “perfect secrecy” (a summ of unconditional security). computational costs must be considered. If, however, we replace The probably secure terms investigated by Shannon rely on the worst case computation time with average or typical computa- use of either they whose length grows linearly with the length tion time as our complexity measure, the current proofs of the of the usage or on perfect source coding and are therefore equivalences among the NP complete problems are no longer too provideldy for most purposes. We note that neither public valid. This suggests several interesting topics for research. The cryptosystems nor one-way authentication systems can uncon- ensemble and typicality concepts familiar to information theo- ditionally secure because the public information always deter- rists have an obvious role to play. mines the secret information uniquely among members of a We can now identify the position of the general cryptanalytic finite set. With unlimited computation, problem could therefore problem among all computational problems. be solved by a straightforward touch. The cryptanalytic difficulty of a system whose encryption The past decade has seen the rise of two closely related and decryption operations can be done in P time cannot be deciplines devoted to the study of the costs of computation greater than NP. computational complexity theory and the analysis of loga- To see this, observe that any cryptanalytic problem can be rithms. The former has classified known problems in computing solved by finding a key, inverse image, etc., chosen from a into broad classes by difficulty, while the latter concentrated on finite set. Choose the key nondeterministically and verify in P finding better algorithms and lying the resources they consume. time that it is the correct one. If there are M possible keys to After a brief discussion into complexity theory, we will examine choose from, an M-fold parallelism must be employed. For its application to cryptography, particularly the analysis of one- example in a known plaintext attack, the plaintext is encrypted way functions. simultaneously under each of the keys and compared with the The function is said to belong to the complexity class P (for cryptogram. Since, by assumption, encryption takes only P polynomial) if it can be computed by a deterministic making Machine in a time which is bounded above by some polynomial time, the cryptanalysis takes only NP time. We also observe that the general cryptanalytic problem is function of the length of its input. One might think of this as NP complete. This follows from the breadth of our definition the class of easily computed functions, but more accurate to say that a function not in this class must be hard to compute of cryptographic problems. A one-way function with an NP complete inverse will be discussed next. for at least some inputs. There problems which are known not Cryptography can draw directly from the theory of NP com- to be in the class P [13,405–425]. There are many problems which arise in engineering which plexity by examining the way in which NP complete problems cannot be solved in polynomial time by any known uniques, can be adapted to cryptographic use. In particular, there is an unless they are run on a computer with an submited degree of NP complete problem known as the knapsack problem which parallelism. These problems may or not belong to the class P, lends itself readily to the construction of a one-way function. but belong to the class NP (nondeterministic, polynomial) of Let Y 5 f(x) 5 a ??? x where a is a known vector of n intergers (a1,a2, ???, an problems solvable polynomial time on a “nondeterministic” ) and x is a binary n-vector. Calculation computer (i.e., with an unlimited degree of parallelism). Clearly of y is simple, involving a sum of at most n integers. The