% -*-LaTeX-*- % Converted automatically from troff to LaTeX by tr2tex on Mon Aug 6 12:50:37 1990 % tr2tex was written by Kamal Al-Yahya at Stanford University % (Kamal%Hanauma@SU-SCORE.ARPA) \documentstyle[troffms,11pt]{article} %\documentstyle[11pt]{article} \textheight 8in \begin{document} % % input file: crypt.troff % \ %.nr PS 12 %.ps 12 %.nr VS 14 \par\vspace{14.0pt} %.nr HM .6i %.hm .6i %.nr LL 6.5i %.ll 6.5i \centerline{\bf Cryptanalysis: A Survey of Recent Results} %.sp4 %center; c c c c. \begin{center} \begin{tabular}{cc} Ernest F. Brickell & Andrew M. Odlyzko \\ Sandia National Laboratories & AT\&T Bell Laboratories \\ Albuquerque, NM 87185 & Murray Hill, NJ 07974 \end{tabular} \end{center} \baselineskip=2.0\normalbaselineskip \begin{abstract} In spite of the progress in computational complexity, it is still true that cryptosystems are tested by subjecting them to cryptanalytic attacks by experts. Most of the cryptosystems that have been publicly proposed in the last decade have been broken. This paper outlines a selection of the attacks that have been used and explains some of the basic tools available to the cryptanalyst. Attacks on knapsack cryptosystems, congruential generators, and a variety of two key secrecy and signature schemes are discussed. There is also a brief discussion of the status of the security of cryptosystems for which there are no known feasible attacks, such as the RSA, discrete exponentiation, and DES cryptosystems. \end{abstract} \newpage \pagestyle{plain} % \bf 1. Introduction % \rm \par The last decade has seen explosive growth in unclassified research in all aspects of cryptology, and cryptanalysis has been one of the most active areas. Many cryptosystems which had been thought to be secure have been broken, and a large collection of mathematical tools useful in cryptanalysis have been developed. The purpose of this survey is to present some of the recent attacks in a way that explains and systemizes the cryptanalytic techniques that are used, with the hope that they will be useful in assessing the security of other cryptosystems. \par Most of the discussion in this paper is devoted to public key systems. This reflects the general developments in cryptography over the last decade. At the beginning of the 1970's only classical (single key) cryptography was known, but very little unclassified research was being done on it. The reasons for this lack of interest were manifold. There did not seem to be much need for commercial encryption. The vast body of classified work in cryptography discouraged researchers who naturally like to discover new results. Finally, perhaps the most important factor was that in spite of the development of the beautiful Shannon theory of secrecy systems, and the use of some tools from abstract algebra, generally speaking cryptography appeared to consist of a large bag of tricks, without a coherent mathematical framework. \par The situation changed drastically in the 1970's. First of all, with growth in communications and proliferation of computers, the need for cryptographic protection became widely recognized. Second, the invention of public key cryptography by Diffie and Hellman appeared to provide an answer to the commercial need for security that avoided some of the disadvantages of classical cryptography, such as the difficulty of key management. Furthermore, this development galvanized the research community because it appeared to open up a brand new field, and it presented the exciting promise of using new tools from the rapidly developing field of computational complexity to develop systems with simple mathematical descriptions. The security of these systems would depend on the intractability of well known problems, and hopefully would eventually lead to proofs of unbreakability of such systems. \par Ironically, the promise of provable security through reduction to well known mathematical problems has not only not been fulfilled, but instead, the fact that attacks on the new cryptosystems could be formulated as mathematically attractive problems, and that various tools from computational complexity, number theory and algebra could be brought to bear on them, has resulted in the breaking of many systems. The old one-time pad remains the only system that is known to be unconditionally secure. \par The ideal proof of security for a public key cryptosystem would be to show that any attack that has a nonnegligible probability of breaking the system requires an infeasible amount of computation. While no public key system has been shown to satisfy this strong definition of security, the situation is not completely bleak. Many systems have been developed whose security has been proved to be equivalent to the intractability of a few important problems, such as factoring integers, that are almost universally regarded as very hard. (Many of the systems that have been broken were derived from these presumably secure ones by weakening them in order to obtain greater speed.) Furthermore, the extensive work of the last decade, both in cryptography itself and in general computational complexity, has given cryptologists a much better understanding of what makes a system insecure. The aim of this survey is to distill some of the lessons of this research. \par Before outlining the contents of this paper, we have to explain what we mean by saying that a cryptographic system is insecure. One can define a fairly precise notion in terms of a polynomial fraction of instances of the system being decipherable in polynomial time. Such an approach is unsatisfactory for two reasons, though. One is that in practice one has to build systems of fairly limited size, and so one cannot assume that asymptotic properties apply. A more serious one is that for many cryptanalytic attacks, no rigorous proofs of effectiveness exist. Instead one relies on heuristics and experimental evidence; for example, one shows that a reduced-size version of a proposed cryptosystem can be broken relatively fast on a small general purpose computer, and then one argues that since the effort involved in the attack does not increase too fast with the size of the problem, even the full size cryptosystem is insecure from a determined attacker. This approach is occasionally used also in other areas of computational complexity (factoring polynomials or integers, for example), where the best practical algorithms rely on unproved assumptions. Use of such approaches in cryptography is very easy to justify. Since cryptosystems often protect very sensitive information and once adapted, are difficult to change, it is important that they be above suspicion. We will see later, for example, that attacks on some of the knapsack cryptosystems depend on being able to find very short non-zero vectors in lattices. In general, it is not known just how difficult a task it is to find such vectors, and the known polynomial time algorithms are not guaranteed to find such vectors. On the other hand, these algorithms usually work much better than they are guaranteed to, and moreover, there has been a lot of progress recently on obtaining improved algorithms. Therefore it seems prudent in assessing the security of the knapsack cryptosystems to assume that one can find even the shortest non-zero vector in a lattice relatively fast. \par The remainder of this paper is organized as follows. Sections 2 and 3 discuss the cryptanalysis of knapsack cryptosystems. Section 4 contains the cryptanalysis of the Ong, Schnorr, and Shamir signature schemes, and Section 5 that of the Okamoto-Shiraishi scheme. Section 6 briefly mentions several two-key cryptosystems that have been broken. Sections 7, 8, 9 describe what is known about the security of RSA, discrete exponentiation, and the McEliece cryptosystem. The next two sections deal with the cryptanalysis of some single key systems, with Section 10 covering the remarkable success in breaking congruential generators, and Section 11 discussing the remarkable lack of success in breaking DES. Section 12 briefly discusses the successful cryptanalysis of FEAL. Finally Section 13 contains some miscellaneous comments. % \bf 2. Knapsack Cryptosystems % \rm \par Knapsack cryptosystems are based on the knapsack (or more precisely the subset sum) problem; i.e., given a set of integers (or weights) $a_1 , \ \ \it\hbox{...},\ a_n$ and a specified sum $s$, find a subset of $ \{ a_1 ,\ \ \it\hbox{...},\ a_n \}$ that sums to exactly $s$, or equivalently find a 0-1 vector $(x_1 , \ \ \it\hbox{...},\ x_n )$ such that $\sum_{{i=1}}^n \ x_i \,a_i \ =\ s$. We will sometimes refer to the set of weights as a knapsack. Merkle and Hellman \cite{88} discovered a way to use the knapsack problem as the basis for a two-key cryptosystem. Although the knapsack problem is NP-hard %e \cite{49}, there are knapsacks for which the problem is easy. An example of an easy knapsack which was used in \cite{88} is a superincreasing sequence, that is a sequence of positive integers $b_1 ,\ \ \it\hbox{...},\ b_n$ such that $b_j \ > \ \sum_{{i} < j} \, b_i ,\ {\rm for} \ 1\ < j\ \le\ n$. \par The basic technique for using the knapsack problem as a two key cryptosystem is straightforward. %.ta 4 Public key: Positive integers $a_1 ,\ \ \it\hbox{...},\ a_n$. Private key: A method for transforming $a_1 , \ \ \it\hbox{...,}\ a_n$ into an easy knapsack. Message Space: $n$-dimensional 0-1 vectors $(x_1 ,\ \ \it\hbox{...,}\ x_n )$. Encryption: $s \ =\ \sum_{{i=1}}^n \ x_i a_i$. Decryption: Solve the knapsack problem with weights $a_1 ,\ \ \it\hbox{...,} \ a_n$ and sum $s$. \par Merkle and Hellman used a superincreasing sequence as an easy knapsack and disguised it with one or more modular multiplications. Specifically, an easy knapsack $b_1 ,\ \ \it\hbox{...,}\ b_n$ can be disguised with a modular multiplication by selecting $ M \ > \ \sum_{{i=1}}^n \ b_i$ and $W$ with $(W,\ M) \ =\ 1$, and computing $$ a_i \ \equiv\ b_i \,W \ ( {\rm mod} \ M )\ . \eqno (2.1)$$ Any solution $( x_1 ,\ \ \it\hbox{...},\ x_n )$ to the knapsack problem $\sum_{{i=1}}^n \ x_i a_i \ =\ s$ is also a solution to the knapsack problem $\sum_{{i=1}}^n \ x_i b_i \ =\ s^{\prime}$ where $s^{\prime} \ \equiv\ s W^{-1} \ ( {\rm mod} \, M) \ {\rm and} \ \ 0 \ \le \ s^{\prime} \ < \ M$. Merkle and Hellman \cite{88} further observed that the disguising operation could be {\it iterated } many times. For instance given the above knapsack $a_1 , \ \ \it\hbox{...,}\ a_n$, a new knapsack $c_1 ,\ \ \it\hbox{...,}\ c_n$ could be formed by choosing a new modulus $M_2 \ > \ \sum_{{i=1}}^n \ a_i$ and multiplier $W_2$ with $(W_2 ,\ M_2 ) \ =\ 1$ and defining $c_i \ \equiv a_i \,W_2 \ {\rm mod} \ M_2$. The knapsack $c_1 ,\ \ \it\hbox{...,}\ c_n$ is called a {\it double-iterated knapsack.} \par The designer of the system can further complicate matters by permuting the weights before publishing them. For clarity of exposition, we will assume that the weights are not permuted, but we will discuss the permutation when it is relevant. \par One reason to be suspicious about the security of knapsack cryptosystems is that they are basically linear. Specifically $\sum_{{i=1}}^n \ x_i \,a_i \ +\ \sum_{{i=1}}^n \ y_i \,a_i \ =\ \sum_{{i=1}}^n \,( x_i \ +\ y_i ) \,a_i$. In fact, if (as we may assume) not all the $a_i$ are even, then by looking at the least significant bit of the ciphertext $s$ we obtain a bit of information about the plaintext, although this usually does not yield even a single bit of the plaintext. Although there is no attack on the cryptosystem based just on this linearity, it should raise questions about its security because linearity in cryptosystems is known to be dangerous. Another cause for suspicion is due to a result of Brassard \cite{15}. Essentially it says that if the problem of breaking a cryptosystem is % \bf NP% \rm -hard, then % \bf NP% \rm =% \bf CoNP% \rm . When the Merkle-Hellman knapsack cryptosystem was proposed, the only attack known was to use an algorithm which would solve any knapsack problem. If one believes that % \bf NP% $\neq$ \bf CoNP% \rm , then it seems likely that there is an attack on the Merkle-Hellman knapsack cryptosystem that runs faster than algorithms that solve the general knapsack problem. This suspicion does not apply to RSA, since factoring integers is not believed to be % \bf NP% \rm -hard. \par These suspicions were extended by various authors. Herlestam \cite{60} observed by using simulations that often a single bit of the message could be easily recovered. Shamir \cite{126} showed that Merkle-Hellman knapsacks in which the modulus $M$ has close to $n$ bits can be broken easily, and \cite{125} that compact knapsacks (i.e. general knapsacks with few weights $c_i$ and with coefficients $x_i$ that are allowed to vary over a wider range than just the set $ \{ 0,1 \} $) ought to be avoided. Amirazizi, Karnin, and Reyneri \cite{6} also showed that compact knapsacks are insecure, but with an even more powerful argument than that of \cite{125}, since they were able to use the theorem of H. W. Lenstra \cite{83} that integer programming in a fixed number of variables is solvable in polynomial time. (This key result \cite{83} was proved at the end of 1980 and became widely known right away, although it was not published until much later.) Shamir and Zippel \cite{127} showed using continued fractions that if the modulus $M$ was known, a cryptanalyst could break the single iterated system. Ingemarsson \cite{62} developed a method of successive reduction modulo suitably chosen integers which seemed to apply to a wide class of knapsacks. However, none of these attacks could convincingly be shown to apply to the Merkle-Hellman system. \par Eier and Lagger \cite{42} and independently Desmedt, Vandewalle, and Govaerts \cite{37} made a key observation that led eventually to the complete demise of these knapsack systems. >From (2.1), there exist integers $k_1 ,\ \ \it\hbox{...,}\ k_n$ such that $$ a_i \, U \ -\ k_i \,M \ =\ b_i \eqno (2.2)$$ where $U \ \equiv\ W^{-1} \, {\rm mod} \ M$. Therefore $$ {{U \over M }} \ -\ {{k_i \over a_i }} \ = \ {{b_i \over a_i M}} \ \ , \eqno (2.3)$$ and so all of the $k_i / a_i$ are close to $U/M$. Furthermore, as was apparently realized by the authors of \cite{42} and \cite{37}, the actual values of $U$ and $M$ are not important, since if one finds any pair of integers $u$ and $m$ with ${{u \over m }} \ -\ {{U \over M }}$ small, one can use $u$ and $m$ to decrypt the knapsack. For an arbitrary collection of integers $a_i$ it is highly unlikely that there would exist $k_i$ such that all of the $k_i / a_i$ would be close together. This seemed to provide a way to attack the Merkle-Hellman system. \par Shamir \cite{122} completed the cryptanalysis of the single iterated Merkle-Hellman system by making two more observations. Since the $a_i$'s are superincreasing, $a_i \ < \ M \,2^{{i-n}}$. Hence, for small $i$, the $k_i / a_i$ are extremely close together; from (2.2) we see that $$ |b_i k_1 \ -\ b_1 k_i | \ \le \ M 2^{{i-n}}\ . \eqno (2.4)$$ Only a few (3 to 4) of these inequalities uniquely determine the $k_i$'s, and once the $k_i$'s are found, it is easy to break the system. The system (2.4) is an instance of integer programming with a small number of variables. Therefore the Lenstra \cite{83} integer linear programming algorithm can find the $k_i$'s fast. For this attack, it is necessary for the cryptanalyst to know which of the public weights correspond to the smallest elements in the superincreasing sequence. If the knapsack was permuted before it was published, he would not know this. Since he only needs to know the 3 or 4 smallest elements, however, he can find them in polynomial time $(O (n^3 )$ or $O ( n^4 ))$ by trying all possibilities. \par The Shamir attack sketched above was universally accepted as valid when it was announced, although nobody up to that time had implemented the Lenstra integer programming algorithm. (In fact, as will be explained later, for the standard version of the Merkle-Hellman system, in which $M$ has about $2n$ bits, one can use continued fractions to find the $k_i$.) Furthermore, the Shamir attack did not seem to generalize to other knapsack systems. These problems were soon overcome, though, because Adleman \cite{3} found that the Lovasz lattice basis reduction algorithm \cite{81} could be used instead of the Lenstra integer programming algorithm, and this enabled him to break the Graham-Shamir knapsack cryptosystem (see \cite{127} for a definition). The introduction of this new tool, the Lovasz algorithm, was the main key to most of the major breakthroughs that were achieved in analyzing knapsacks. The Lovasz algorithm and more efficient ones that were derived later by Radziszowski and Kreher \cite{113} and by Schnorr \cite{117}, \cite{118} are now among the basic tools of constructive diophantine approximation, and will be discussed after we introduce some defintions. % \bf 2.1 Diophantine Approximation % \rm \par Simultaneous diophantine approximation is the study of approximating a vector of reals $( \theta_1 ,\ \ \it\hbox{...,}\ \theta_n )$ by a vector of rationals $\left( {{p_1 \over p }} , \ \ \it\hbox{...,}\ {{p_n \over p }} \right)$ all having the same denominator. An approximation $\left( {{p_1 \over p }} , \ \ \it\hbox{...,}\ {{p_n \over p }} \right)$ to a vector of rationals $\left( { {q_1 \over q }} , \ \ \it\hbox{...,}\ {{q_n \over q }} \right)$ is said to be an unusually good simultaneous diophantine approximation (UGSDA), if $| p \, {{q_i \over q }} \ -\ p_i | \ \le \ q^{ - \delta }$ for some $ \delta \ > \ {{1 \over n }}$. Lagarias \cite{75} has justified this definition by showing that unusually good simultaneous diophantine approximations are indeed unusual. \par For breaking knapsack type cryptosystems, we are interested in the algorithmic question of finding unusually good simultaneous diophantine approximations that are known to exist. For $n \ =\ 1$, continued fractions can be used to find UGSDA. The set of convergents to the continued fraction expansion of ${{q_1 \over q }}$ contains every rational ${{r_1 \over r }}$ such that $r \ < \ q$ and $| r \, {{q_1 \over q }} \ -\ r_1 | \ \le \ {{1 \over r }}$. Thus if ${{p_1 \over p }}$ is an UGSDA to ${{q_1 \over q }}$ then ${{p_1 \over p }}$ will be a convergent. \par More surprisingly, continued fractions can also be used to find UGSDA for $n \ =\ 2$. To see this let $ \left( {{q_1 \over q }} ,\ {{q_2 \over q }} \right) $ be a pair of rationals that have an UGSDA $ \left( {{p_1 \over p }} ,\ {{p_2 \over p }} \right) $. Let $c_i \ =\ q_i p \ -\ q p_i$. Then $ |c_i | \ < \ q^{{} {1\over 2}} $. Taking these equations mod $q$, we obtain $ c_i \ \equiv \ q_i p \ {\rm mod} \ q $. Let us assume for now that $GCD ( q_2 ,\ q ) \ =\ 1$. Then ${{c_1 \over c_2 }} \ \equiv \ {{q_1 \over q_2 }}$ mod $q$. Let $x \ \equiv \ {{q_1 \over q_2 }}$ mod $q$. Then $c_2 x \ \equiv \ c_1 \ {\rm mod} \ q$, and there exists a $y$ such that $c_2 \ {{x \over q }} \ -\ y \ =\ {{c_1 \over q }}$ and $| {c_1 \over q} |\ < \ |c_2 |^{-1}$. Therefore we can find ${{y \over c_2 }}$ as a convergent in the continued fraction expansion of ${x \over q }$. Using $c_2$, we can find $p \ \equiv\ q_2^{-1} \ c_2 \ {\rm mod} \ q$ and then $p_1$ and $p_2$ are easily determined. If $GCD ( q_2 ,\ q ) \ =\ d \ \neq\ 1$, then one can replace $q$ and $q_2$ by ${q \over d }$ and ${q_2 \over d }$ and proceed as above. This provides an attack on the single iterated Merkle-Hellman cryptosystem for certain parameters. In particular, if $M \ < \ 2^{{2n} \,-\,8}$ and if $b_1 \ > \ M/2$, then using (2.4) we see that $ \left( {{k_2 \over k_1 }} ,\ {{k_3 \over k_1 }} \right) $ is an UGSDA to $ \left( {{b_2 \over b_1 }}, \ {{b_3 \over b_1 }} \right) $ . %e added sentence The knapsack cryptosystem of Henry \cite{59} can also be broken by using continued fractions. \par Finding UGSDA is related to finding short vectors in a lattice. Given a set of $n$ independent vectors in $R^n$, ${\bf b}_1 ,\ \ \it\hbox{...,} \ {\bf b}_n$, a lattice $L$ is the set of points $$ L \ =\ \{ \ \sum_{{i=1}}^n \ z_i {\bf b}_i \ : \ z_i \ \in \ Z \kern-0.40em Z \ \} \ . $$ The vectors ${\bf b}_1 ,\ \ \it\hbox{...,} \ {\bf b}_n$ are said to be a basis for $L$. Consider the lattice $L$ generated by the row vectors ${\bf b}_0 ,\ \ \it\hbox{...,}\ {\bf b}_n$ of the matrix {\nobreak $$ \left(\ \matrix { \lambda \cr 0 \cr \cr \cr 0 \cr 0} \ \ \matrix {p_1 \cr -p \cr \cr \cr 0 \cr 0} \ \ \matrix {p_2 \cr 0 \cr \cr \cr 0 \cr 0} \ \ \ \ \ \ \ \matrix {p_{{n\,-\,1}} \cr 0 \cr \cr \cr -p \cr 0} \ \ \matrix {p_n \cr 0 \cr \cr \cr 0 \cr -p}\ \right) $$ } where $ \lambda$ is a real number between 0 and 1. There is an obvious relationship between short vectors in this lattice and UGSDA to $\left( {{p_1 \over p }} , \ \ \it\hbox{...},\ {{p_n \over p }} \right)$ since a vector ${\bf v} \ =\ \sum_{{i=0}}^{{n}} \ q_i \, {\bf b}_i$ in $L$ has length ${| \kern-0.20em |} \, {\bf v} \,{| \kern-0.20em |} \ =\ \sqrt { \sum_{{i=1}}^{{n}} \ (q_0 \,p_i \ -\ q_i \,p )^2 \ +\ \lambda^2 \, q_0^2}$. ( $ \lambda$ should be chosen small enough so that $ \lambda q_0$ is not the largest term in this sum.) \par Although the problem of finding the shortest vector in a lattice is not known to be NP-hard, there is no known polynomial time algorithm for solving it. There are, however, polynomial time algorithms for finding relatively short vectors in a lattice. The first such algorithm was due to Lovasz \cite{81} . For a lattice with a basis in which all coefficients in the basis are integers with absolute value $<$ $B$, the algorithm is guaranteed to terminate in $O (n^6 ( {\rm \log} \,B )^3 )$ bit operations and produce a vector ${\bf v}$ such that ${| \kern-0.20em |} {\bf v} {| \kern-0.20em |}^2 \ \le \ 2^n \ {| \kern-0.20em |} {\bf u} {| \kern-0.20em |}^2$ where ${\bf u}$ is the shortest nonzero vector in the lattice. In practice, modifications of the Lovasz algorithm run much faster than this, usually about $O (n ( {\rm \log} \,B )^3 )$ steps, and produce vectors that are much closer to the length of the shortest vector in the lattice. In particular, on all of a small set of test cases which came from knapsack cryptosystems, an implementation of the Lovasz algorithm by Brickell \cite{18} found vectors that could be used to break the cryptosystem even though the vectors needed were only about $1/n$ times the length of the original basis vectors in the lattice. There are also other lattice basis reduction algorithms due to Schnorr \cite{118} that produce vectors that are guaranteed to be closer in length to the shortest vector in the lattice, but these algorithms are slower. % \bf 2.2. Multiple Iterated Knapsacks % \rm \par An $I$-iterated knapsack cryptosystem is one in which $I$ modular multiplications are used to disguise an easy knapsack. For an $I$-iterated knapsack, there are $I$ independent UGSDA. These UGSDA were studied by Brickell, Lagarias, and Odlyzko \cite{22} and more extensively by Lagarias \cite{75}, %e \cite{76} and were later used to break the multiple iterated knapsack by Brickell \cite{18}. \par These UGSDA can be used to break all of the knapsack cryptosystems %e added 38,96,119,120 \cite{8}, \cite{17}, \cite{38}, \cite{41}, \cite{96}, \cite{103}, \cite{119}, \cite{120}, \cite{121}, \cite{133} that have been proposed that rely on modular multiplications as a disguising technique. See the surveys by Brickell \cite{20} and Desmedt \cite{35} for more details. % \bf 2.3. Low Density Attacks % \rm \par The density of a knapsack $a_1 ,\ \ \it\hbox{...},\ a_n$ in which $A \ = \ {\rm max} \ \ \{ a_1 ,\ \ \it\hbox{...},\ a_n \} $ is defined to be ${{n \over {\rm \log}_2 (A)}}$. There are algorithms due to Brickell \cite{16} and to Lagarias and Odlyzko \cite{77} for solving knapsacks of low density. The Lagarias-Odlyzko \cite{77} algorithm consists of looking for short vectors in the lattice $L$ generated by the row vectors in the matrix $$ \left( \matrix { \matrix {1 \cr 0 \cr . \cr . \cr . \cr 0 \cr 0} \matrix {0 \cr 1 \cr \cr \cr \cr 0 \cr 0} \matrix {... \cr ... \cr \cr \cr \cr ... \cr ...} \matrix {0 \cr 0 \cr \cr \cr \cr 1 \cr 0} \matrix { a_1 \cr a_2 \cr \cr \cr \cr a_n \cr s} } \right) $$ where $s$ is the sum for the knapsack problem. In \cite{77}, the algorithm is analyzed with the Lovasz basis reduction algorithm \cite{81} being used to find the short vectors in $L$. The polynomial time algorithm will solve almost all knapsack problems of density $<$ ${2 \over n }$. (Frieze \cite{45} has obtained a simpler proof of this result.) In practice, the algorithm is successful on knapsacks of much higher density, but the densities for which the algorithm succeeds does appear to go to 0 as $n$ increases. Using more efficient lattice basis reduction algorithms \cite{113}, \cite{117}, \cite{118} would increase the critical density below which this attack succeeds. % \bf 3. Generalized Knapsack Cryptosystems % \rm \par In this section, we will examine several cryptosystems that have been proposed that use similar ideas to those used in the knapsack cryptosystems. % \bf 3.1. Lu-Lee Systems % \rm The Lu-Lee Cryptosystem \cite{84}: \begin{description} \item [$\bullet$ \ \ Public Key:] $c_1 , c_2 , r,\ M_1 ,\ M_2$ all positive integers. \item [$\bullet$ \ \ Messages:] integers $m_1 , \ m_2$ such that $0 \ < \ m_1 \ < \ M_1 ,$ $0 \ < \ m_2 \ < \ M_2$. \item [$\bullet$ \ \ Encryption:] $E( m_1 ,\ m_2 ) \ =\ c_1 m_1 \ + \ c_2 m_2 \ {\rm mod} \ r$. (3.1.1) \item [$\bullet$ \ \ Decryption:] The parameters were chosen so that the encryption function is one-to-one on the message space. The knowledge of the private key allows easy decryption. \end{description} \par This cryptosystem was broken by Adleman and Rivest \cite{4}, Goethals and Couvreur \cite{51} and Kochanski \cite{70}. Adiga and Shankar \cite{2} suggested a modification of this scheme. The Modified Lu-Lee cryptosystem \cite{2}: \begin{description} \item [$\bullet$ \ \ Public Key:] $c_1 ,\ c_2 , r,\ M$ all positive integers. \item [$\bullet$ \ \ Messages:] Positive integers $m \ < \ M$. \item [$\bullet$ \ \ Encryption:] Pick $m_1 \ < \ M_1 ,\ m_2 \ < \ M_2$, and compute %.ta 10 $E(m) \ =\ m \ +\ c_1 m_1 \ +\ c_2 m_2 \ {\rm mod} \ r$. (3.1.2) %.ta 4 \item [$\bullet$ \ \ Decryption:] Same remarks as above apply. \end{description} \par For both of these systems, cryptanalysis by solving (3.1.1) or (3.1.2) by integer linear programming is immediate. Kannan's integer linear programming algorithm \cite{67} runs in $O(n^{9n} \, {\rm \log} r )$ in worst case on problems with $n$ variables and integer coefficients bounded by $r$. Since $n \ \le \ 4$ for (3.1.1) and (3.1.2), Kannan's algorithm is a viable threat to these systems. % \bf 3.2 Niederreiter cryptosystem % \rm \par Niederreiter \cite{95} proposed a knapsack type cryptosystem using algebraic coding theory. \begin{description} \item [$\bullet$ \ \ Private Key:] $H$, an $(n\,-\,k)$ by $n$ parity check matrix of a $t$-error correcting %.ta 10 linear $(n, \ k)$ code, $C$, over $GF(q)$ with an efficient decoding algorithm. $P$, an $ n \ \times \ n$ permutation matrix. $M$, a nonsingular $(n\,-\,k) \,\times\, (n \,-\, k)$ matrix . %.ta 4 \item [$\bullet$ \ \ Public Key:] $K \ =\ MHP \ {\rm and} \ t$. \item [$\bullet$ \ \ Messages:] $n$ dimensional vectors ${\bf y}$ over $GF(q)$ with weight $\le \ t$. \item [$\bullet$ \ \ Encryption:] ${\bf z} \ =\ K {{\bf y}}^T$. \item [$\bullet$ \ \ Decryption:] Since ${\bf z} \ =\ K {{\bf y}}^T \ =\ MHP {{\bf y}}^T$, $M^{-1} {\bf z} \ =\ HP {{\bf y}}^T \ =\ H( {\bf y} P^T )^T$. Use the decoding algorithm for $C$ to find ${\bf y} P^T$ and thus ${\bf y}$. \end{description} \par This cryptosystem is said to be of knapsack type because the encryption can be viewed as picking $t$ columns from the matrix $K$ and forming a weighted sum of these $t$ column vectors. \par We will mention three cryptanalytic attacks on this system. In the first attack, for a ciphertext, ${\bf z}$, we pick a submatrix $J$ of $K$ consisting of $(n \,-\, k)$ columns of $K$. We then compute ${{\bf y}}^{\prime} \ =\ J^{-1} \, {\bf z}$. If all of the $t$ columns that were added to form ${\bf z}$ are in $J$, then ${{\bf y}}^{\prime}$ will be the encrypted message, i.e. ${{\bf y}}^{\prime}$ will satisfy $K {{\bf y}}^{\prime} \ =\ {\bf z}$ and have at most $t$ non zero entries. The probability of this occurrence is $ \rho \ =\ \left( \matrix {n-k \cr t} \right) \ / \left( \matrix {n \cr t} \right)$. Thus the expected number of times we must repeat this procedure before we are successful is ${1 \over \rho}$ . There are two examples mentioned in \cite{95}. For the first $n \ =\ 104$, $k \ =\ 24$, $t \ =\ 15$, and so ${1 \over \rho} \ =\ 72$. For the second example, $n\ =\ 30$, $k \ =\ 12,$ $t \ =\ 9$, and ${1 \over \rho} \ =\ 295$. \par Another attack on this cryptosystem is based on a deterministic linear algebra procedure. It is easy to find some vector ${\bf w}$ such that $K {{\bf w}} \ =\ {\bf z}$. Once ${\bf w}$ is found, we must have ${\bf w} \ =\ {\bf y} \ +\ {\bf c}$, for some codeword ${\bf c}$ in $C$. We can write $C$ as the direct sum of two subspaces $C_1$ and $C_2$, with $C_1$ of dimension $[k/2]$, and list all the codewords of $C_1$ and $C_2$ (approximately $q^{{k/2}}$ in each case). Then, for each ${\bf c}_1$ in $C_1$, we only need to check whether $ {\bf w} \ -\ {\bf y} \ -\ {\bf c}_1$ is in $C_2$. In both of the examples presented in \cite{95}, this procedure would be very fast. \par There is another attack based on the low density algorithm of \cite{77} that can be used if $GF( q )$ is a prime field, i.e., $q$ is a prime. Let ${{\bf v}}_1^T ,\ \ \it\hbox{...},\ {{\bf v}}_n^T$ be the $n$ column vectors of $K$. Let $v_i \ =\ (v_{{i1}} , \ v_{{i2}} ,\ \ \it\hbox{...},\ v_{{i,} n\,-\,k} )$. Let $r$ be an integer. Let $L$ be the lattice generated by the row vectors in the matrix $$ Q \ =\ \left( \matrix { \matrix {1 \cr 0 \cr . \cr 0 \cr 0 \cr 0 \cr 0 \cr . \cr 0} \matrix {0 \cr 1 \cr \cr 0 \cr 0 \cr 0 \cr 0 \cr \cr 0} \matrix {... \cr ... \cr \cr ... \cr ... \cr ... \cr ... \cr \cr ...} \matrix {0 \cr 0 \cr \cr 1 \cr 0 \cr 0 \cr 0 \cr \cr 0} \matrix {0 \cr 0 \cr \cr 0 \cr 1 \cr 0 \cr 0 \cr \cr 0} \matrix {rv_{11} \cr rv_{21} \cr \cr rv_{n1} \cr rz_1 \cr rq \cr 0 \cr \cr 0} \matrix {rv_{12} \cr rv_{22} \cr \cr rv_{n2} \cr rz_2 \cr 0 \cr rq \cr \cr 0} \matrix {... \cr ... \cr \cr ... \cr ... \cr ... \cr ... \cr \cr ...} \matrix {rv_{{1,} n\,-\,k} \cr rv_{{2,} n\,-\,k} \cr \cr rv_{{n,} n\,-k} \cr rz_{n-k} \cr 0 \cr 0 \cr \cr rq} } \right) $$ \par The vector ${{\bf y}}^* \ =\ ( y_1 ,\ \ \it\hbox{...}, \ y_n , \ 0 , \ 0 ,\ \ \it\hbox{...}, \ 0 )$ is a vector in the lattice and has at most $t$ non zero entries. If $ r \ge t $, then ${\bf y}^*$ will be the shortest vector in the lattice. (Since K generates a $t$-error correcting linear code, there cannot be two vectors, ${\bf y}_1^*$ and ${\bf y}_2^*$, such that $ K {\bf y}_1^* \ =\ K {\bf y}_2^*$ and such that the Hamming weight of each of ${\bf y}_1^*$ and ${\bf y}_2^*$ is $ \le \ t$.) Although the lattice basis reduction algorithm is not guaranteed to find ${\bf y}^*$, this attack does cast suspicion on the security of the cryptosystem. % \bf 3.3. Goodman-McAuley knapsack % \rm \par The Goodman-McAuley \cite{52} knapsack cryptosystem uses modular multiplication to disguise an easy knapsack that is substantially different from those discussed earlier. \par The Goodman-McAuley knapsack cryptosystem: \begin{description} \item [$\bullet$ \ \ Public Key:] integers $b_1 ,..., b_n ,\ q$ and $p$. \item [$\bullet$ \ \ Private Key:] integers $h,\ r$ satisfying $h\ \ge\ r\ +\ q$; primes $p_1 ,..., p_n$ such that $p_i \ \ge\ 2^h$ for $1\ \le\ i\ \le\ n$; $p\ =\ \prod_{{i=1}}^{{n}} \,p_i$; non-negative integers $a_{{ij}}$ for $1\ \le\ i,j\ \le\ n$, such that $\sum_{{j=1}}^{{n}} \,a_{{ij}} \ < \ 2^r$ for $1\ \le\ i\ \le\ n$, and the matrix $A\ =\ (a_{{ij}} )$ is nonsingular; non-negative integers $a_i$ such that $a_i \ \equiv \ a_{{ij}} \ {\rm mod} \,p_j$ for $1\ \le\ i\ \le\ n,\ 1\ \le\ j\ \le\ n$; $W$ relatively prime to $p$ such that $b_i \ \equiv \ W \,a_i \ {\rm mod} \,p$, for $1\ \le\ i\ \le\ n$. \item [$\bullet$ \ \ Messages:] ${\bf m} \ =\ (m_1 ,..., m_n )$ such that $0\ \le\ m_i \ \le\ 2^q $. \item [$\bullet$ \ \ Encryption:] $c\ =\ \sum_{{i=1}}^{{n}} \,m_i \,b_i \ {\rm mod} \,p$. \item [$\bullet$ \ \ Decryption:] Let ${\bf d} \ =\ (d_1 ,..., d_n )$ where $d_i \ \equiv \ cW^{-1} \ {\rm mod} \,p_i$. Then ${\bf m} \ =\ {\bf d} \,A^{-1}$. \end{description} \par If $ n $ is small, this cryptosystem can be broken by the Lenstra \cite{83} or Kannan \cite{67} linear programming algorithms. There is also a greatest common divisor attack that works for small $r$, and enables the cryptanalyst to recover all the secret information. Since $p_j |a_i \ -\ a_{ij} $, we have $p_j |\,b_i \ -\ a_{ij} \,W$, and so $p_j |a_{ij} \,b_k \ -\ a_{kj} \,b_i$. Since $a_{ij} ,\ a_{ij}\ < \ W2^r$, the cryptanalyst can find $(y,z)$ such that $p_j |GCD(p,\,yb_k \,-\,zb_i )$ by checking all pairs $y,z$ with $0\ \le\ y,z\ \le\ 2^r$. If for each pair $j,l$ there exist $0\ \le\ y,z\ \le\ 2^r$ such that $p_j | yb_k \ -\ zb_i$ and $p_{l} \,{ {|} } \,yb_k \ -\ zb_i$, then the cryptanalyst will find all of the $p_j$'s by taking GCD's. If this is not the case, he can pick a different $k$ and continue. (Note that if $p_j p_{l} |y_1 b_k \,-\,z_1 b_i$ and $p_j p_{l} |y_2 b_k \,-\,z_2 b_i$, then $y_1 z_2 \ \equiv \ y_2 z_{1,}\ {\rm mod} \,p_j p_{l}$. Since $0\ < \ y_{1,}\ z_2 \ < \ p_j p_{l}$, this implies $y_1 z_2 \ =\ y_1 z_1$. Hence if the GCD attack fails to separate $p_j$ and $p_{l}$, then it must be the case that ${a_{ij} \over a_{kj}} \ =\ {a_{il} \over a_{kl}}$. But this cannot be true for all $k$ since $A$ is nonsingular.) \par Even if $n$ and $r$ are chosen large enough so that the above attacks will not work, the cryptosystem can still be broken using lattice basis reduction. Consider the lattice spanned by the rows ${\bf v}_0 ,..., {\bf v}_n$ of the matrix $$ \left( \matrix { \matrix {b_1 \cr p \cr 0 \cr . \cr . \cr . \cr 0} \matrix {b_2 \cr 0 \cr p \cr \cr \cr \cr 0} \matrix {... \cr ... \cr ... \cr \cr \cr \cr ...} \matrix {b_n \cr 0 \cr 0 \cr \cr \cr \cr p} \matrix {\epsilon \cr 0 \cr 0 \cr \cr \cr \cr 0} } \right) $$ Let $k_{ij}$ be the integers satisfying $b_i \,W^{-1} \ -\ k_{ij} \,p_j \ =\ a_{ij}$. Then $b_i \,W^{-1} \, {p \over p_j} \ -\ k_{ij} \,p\ =\ a_{ij} \,{p \over p_j}$. Thus, there are $n$ vectors in the lattice of the form $W^{-1} \, {p \over p_j} \, {\bf v}_0 \ -\ \sum_{{j=1}}^{{n}} \, k_{ij} \,{\bf v}_j \ =\ (x_1 ,..., x_n )$ where $\sum_{{i=1}}^{{n}} \,x_i \ < \ 2^{-q} \,p$. Even if the Lovasz lattice basis reduction algorithm does not produce these vectors, but instead finds vectors ${\bf u}_i \ =\ (x_{i1} ,..., x_{in} )$ that satisfy $\sum_{{j=1}}^{{n}} \,|x_{ij} | \ < \ 2^{-q} \,p$, the cryptanalyst can still use these vectors to break the system. % \bf 3.4. Pieprzyk knapsack % \rm \par Pieprzyk \cite{104} designed a knapsack type public key cryptosystem based on polynomials over $GF(2)$. In the following description, all polynomials are over $GF(2)$. \par The Pieprzyk knapsack \begin{description} \item [$\bullet$ \ \ Public key:] polynomials $k_1 (x) ,..., k_n (x)$ and integer $d$. \item [$\bullet$ \ \ Private key:] polynomials $\Psi (x),\ \phi_1 (x) ,..., \phi_n (x)$, $p_1 (x) ,.., p_n (x),\ a(x)$ such that for $1\ \le\ i\ \le\ n$, deg $\,\phi_i (x)\ =\ d\ +\ 1,\ \phi_i (x)$ is irreducible, $p_i (x)\ \equiv 1\ {\rm mod} \,\phi_i (x),\ p_j (x)\ \equiv 0\ {\rm mod} \,\phi_i (x)$ if $i\ \neq j,\ {\rm deg}\,\Psi (x)\ \ge\ \sum_{{i=1}}^{{n}} \ {\rm deg} \,\phi_i (x)\ +\ d$ and $\Psi (x)$ is irreducible, and $k_i (x)\ \equiv \ p_i (x) \,a(x) \ {\rm mod} \,\Psi (x)$. \item [$\bullet$ \ \ Messages:] $M\ =\ (m_1 (x) ,..., m_n (x))$ where ${\rm deg}\ m_i (x)\ \le\ d$. \item [$\bullet$ \ \ Encryption:] $c(x)\ =\ \sum_{{i=1}}^{{n}} \ m_i (x) \,k_i (x)$ \item [$\bullet$ \ \ Decryption:] Let $c^{\prime} (x) \ = c (x) \,a^{-1} (x) \ {\rm mod} \ \Psi (x)$. $c^{\prime} (x)\ \equiv \ \sum_{{i=1}}^{{n}} \,m_i (x) \,p_i (x)\ {\rm mod} \ \Psi (x)$. Since ${\rm deg}\, \left( \sum_{{i=1}}^{{n}} \,m_i (x) \,p_i (x) \right)\ \ {\rm deg} \,\Psi (x)$, $c^{\prime} (x)\ =\ \sum_{{i=1}}^{{n}} \,m_i (x) \,p_i (x)$. So $m_j (x)\ =\ c^{\prime} (x) \ {\rm mod} \ \phi_j (x)$. \end{description} \par The Pieprzyk knapsack is similar to the Goodman-McAuley knapsack except that integers have been replaced by polynomials. It can be broken by a similar GCD attack as well. However, in this case a much simpler solution is available. As is the case with the Luccio-Mazzone system described in Section 6.5, this cryptosystem can be broken by simple linear algebra. Note that the encryption does not involve any modular reductions. In fact, encryption is a linear transformation of the plaintext, and the matrix giving this transformation can be constructed easily from the coefficients of the polynomials $k_i (x)$. Since decryption is guaranteed to work, this matrix must have full rank. % \bf 3.5. Chor-Rivest knapsack % \rm \par The Chor-Rivest \cite{138} knapsack cryptosystem is the only knapsack cryptosystem that has been published that does not use some form of modular multiplication to disguise an easy knapsack. There is no feasible method known for breaking this system. \par The Chor-Rivest Cryptosystem \begin{description} \item [$\bullet$ \ \ Public key:] Integers $c_0 ,c_1 ,..., c_{p-1} ,p,h,$ where $p$ is a prime power, $h\ \le\ p$, and finding discrete logarithms in $GF(p^h )$ is feasible. \item [$\bullet$ \ \ Private key:] $f(x)$ is a monic irreducible polynomial over $GF(p)$ of degree $h$, $GF(p^h )$ will be implemented as $GF(p)\,[x]/f(x)$, $t$ is a root of $f(x)$, $g$ is a generator of the multiplicative group of $GF(p^h )$; for $\alpha \in GF(p)$, $a_{\alpha}$ is an integer such that $g^{{a}_{\alpha}} \ =\ t\ +\ \alpha$, $\pi$ is a one to one map from $\{ 0,1 ,..., p-1 \} $ into $GF(p)$, $b_i \ =\ a_{{\pi(i)}}$, $d$ is an integer, $0\ \le\ d\ \le\ p^h \ -\ 2$, and $c_i \ =\ b_i \ +\ d$. \item [$\bullet$ \ \ Messages :] Vectors $M\ =\ (m_0 ,.., m_{p-1} )$ of nonnegative integers such that $\sum_{{i=0}}^{{p-1}} \,m_i \ =\ h$. \item [$\bullet$ \ \ Encryption :] $E(M)\ \equiv \ \sum_{{i=0}}^{{p-1}} \,m_i c_i \ {\rm mod} \ p^h \ -\ 1$. \item [$\bullet$ \ \ Decryption :] Compute $r\ \equiv \ E(M)\ -\ hd\ \equiv \ \sum_{{i=0}}^{{p-1}} \,m_i b_i \ {\rm mod} \ p^h \ -\ 1$. Then $g^r \ =\ \prod_{{i=0}}^{{p-1}} \,g^{{m}_i b_i}$. Since we are implementing $GF(p^h )$ as $GF(p)\,[x]/f(x),\ g^r$ is represented as a polynomial in $x$ of degree $< h$. Now $\theta(t)\ =\ \prod_{{j=0}}^{{p-1}} \,(t\,+\,\pi(j ))^{{m}_j}$ is represented by a polynomial of degree $h$, and $\theta(x)\ =\ g^r$ in $GF(p)[x]/f(x)$. So $\theta(x)\ =\ u(x) \ +\ f(x)$ in $GF(p)\,[x]$, where $u(x)$ represents $g^r$. Thus by factoring $u(x) \ +\ f(x)$, the values of $m_0 ,..., m_{{p-1}}$ can be obtained. \end{description} \par Chor and Rivest show that if some of the secret information is revealed, then the system is insecure. In particular, the cryptosystem is insecure if $g$ and $d$ are known in some model of $GF(p^h )$, or if $t$ is known, or if $\pi$ and $d$ are known. They also mention an attack with nothing known that runs in $O(p^{{2} \sqrt {h}} \,h^2 \, {\rm \log} \,p)$. However this attack is infeasible for the parameters they suggest (e.g. $p\ =\ 197$ and $h\ =\ 24$). \par If $d$ is known, then it is possible to reduce the cryptanalysis problem to the problem of finding the root of a very high degree polynomial. Since $d$ is known, the $b_i$'s are also known. It can be shown that one can assume that the cryptanalyst knows $\pi^{-1} (0)$ and $\pi^{-1} (1)$. Without loss of generality, suppose $\pi(0)\ =\ 0$ and $\pi(1)\ =\ 1$. Then $g^{{b}_0} \ =\ t$. Let $e_0 \ =\ b_0^{-1} \ {\rm mod} \ p^h -1$. Then $t^{{e}_o} \ =\ g$, and $t^{{e}_0 b_1} \ =\ g^{{b}_1} \ =\ t\ +\ 1$. A somewhat similar argument can be used if $d$ is not known. In both cases, though, one has to find the root of a very high degree trinomial. Rabin \cite{112} and Ben-Or \cite{11}, for example, have shown that a root of a polynomial of degree $w$ over $GF(p)$ can be found in $O(w\, {\rm \log} \,w\, {\rm \log\,\log} \,w\, {\rm \log}\,p)$ operations, but these algorithms are infeasible here since $w$ is of the order of $p^h$. No faster method for finding a root of a trinomial is known. % {\bf 4. The Ong-Schnorr-Shamir signature schemes} \par Ong, Schnorr, and Shamir \cite{101} proposed a signature scheme based on polynomial equations modulo $n$. Their motivation was to develop a scheme that requires little computation for generation and verification of signatures, an area where the RSA scheme is deficient. % \begin{description} \item [$\bullet$ \ \ Public Key:] polynomial $P ( x_1 ,..., x_d )$ and modulus $n$. \item [$\bullet$ \ \ Private Key:] a method of solving $P ( x_1 , \ \ \it\hbox{...},\ x_d ) \ \equiv \ m$ mod $n$ for $x_1 ,\ \ \it\hbox{...},\ x_d$ %.ta 10 using only a small number of multiplications, additions, and divisions mod $n$. \item [$\bullet$ \ \ Messages:] $m \ \in \ {Z \kern-0.40em Z}_n$. \item [$\bullet$ \ \ Signature:] $x_1 ,\ \ \it\hbox{...},\ x_d$ such that $P( x_1 ,\ \ \it\hbox{...},\ x_d ) \ \equiv \ m $ mod $n$. \item [$\bullet$ \ \ Verification:] Check that $P( x_1 ,\ \ \it\hbox{...},\ x_d ) \ \equiv\ m$ mod $n$. \end{description} \par This scheme generated a great deal of interest when it was first announced \cite{100} using a polynomial $P$ of degree 2. In fact the authors offered \$100 reward for its cryptanalysis. This reward was won by Pollard \cite{107}, but this did not deter the authors, who within a few months described a cubic version. This was also broken by Pollard \cite{107}, which caused the authors to publish a quartic version \cite{102}. This version was broken by Estes, Adleman, Kompella, McCurley, and Miller \cite{44} and independently by Schnorr\cite{107}, and there have been no more schemes of this type proposed. We will give a brief exposition of the Pollard attack on the quadratic version. % \bf 4.1 Cryptanalysis of the Quadratic OSS % \rm \par The quadratic version proposed in \cite{100} uses the polynomial $P( x_1 ,\ x_2 ) \ =\ x_1^2 \ +\ kx_2^2$ where the private key is an integer $u$ such that $k \ =\ u^2$. To forge a signature to $m$, it is necessary to find $x,\,y$ such that $x^2 \ +\ k y^2 \ =\ m$. \par Note that the signature scheme is multiplicative; i.e., if $x_1^2 \ +\ k y_1^2 \ =\ m_1$ and $x_2^2 \ +\ ky_2^2 \ =\ m_2$, then $x \ =\ x_1 x_2 \ -\ k y_1 y_2$ and $y \ =\ x_1 y_2 \ +\ x_2 y_1$ is a solution to $x^2 \ +\ ky^2 \ =\ m_1 m_2$. % \bf The Pollard algorithm % \rm \begin{itemize} \item[(1)] Do (2) and (3) until $m$ and $k$ are small enough so that $x^2 \ +\ ky^2 \ =\ m$ can be solved with $x ,y \ \in \ \{ 0, \, 1 \} $, or until $m$ is a square. \item[(2)] Replace $m$ by a number $< 2 \sqrt k$. \item[(3)] Interchange $m$ and $k$ by using $x \ \leftarrow \ {{x \over y }}$ and $y \ \leftarrow \ {{1 \over y }}$. \item[(4)] Solve with $x, y \ \in \ \{ 0, \,1 \}$ and use the transformations of (2) and (3) to work back to the original equation. \end{itemize}\par\noindent \par To explain step (2), first find $m_0$ such that $m_0 \ =\ m$ mod $n$, $m_0 \ \equiv \ 3$ mod 4, $m_0$ is prime, and $-k$ is a quadratic residue mod $m_0$. The integer $m_0$ is found by examining the integers in the sequence $m$, $ m \ +\ n$, $m \ +\ 2n$, until an integer is found satisfying all the conditions. Assuming appropriate randomness conditions on this set of integers, a success is expected with $O( \log \,n)$ trials. Solve $x_0^2 \ \equiv\ -k$ mod $m_0$ and thus $x_0^2 \ +\ k \ = \ m_0 m_1$. \par Next we want to find $m_2 \ < \ 2 \sqrt k$ and $x_1 ,\ y_1$ such that $x_1^2 \ +\ y_1^2 \,k \ =\ m_1 m_2$. Let $Q\ =\ m_1^{{} {1\over 2}} \, k^{{-1/4}}$. Use continued fractions to find $a, \ b$ with $|a| \ < \ Q$ such that $\left| {{x_0 \over m_1 }} \ +\ {{b \over a }} \right| \ \le\ {{1 \over aQ }}$. Setting $x_1 \ =\ x_0 a \ +\ m_1 b$ and $y_1 \ =\ a$ satisfies the requirements. \par Using the multiplicative property, the problem of solving $x^2 \ +\ k y^2 \ \equiv \ m$ mod $n$ reduces to solving $x^2 \ +\ ky^2 \ \equiv \ m_2$ mod $n$ and this satisfies step (2). \par $O( {\rm \log} \, {\rm \log} \,k)$ iterations of steps (2) and (3) will result in a small enough $k$ and $m$ so that a solution is easily found. % \bf 4.3 Other OSS Schemes % \rm \par After Pollard broke the quadratic and cubic OSS schemes, Ong, Schnorr, and Shamir developed a scheme using fourth degree polynomials which was essentially a quadratic scheme over a quadratic number field. This scheme was broken \cite{44} by reducing its cryptanalysis to the cryptanalysis of the quadratic scheme over the integers. \par The success that the cryptanalysts have had with the OSS schemes does not imply that there are no secure signature schemes of this type. However it is enough evidence to create strong suspicions about the security of any such schemes. Also, as their complexity increases, their speed improvement over RSA/Rabin decreases. For these reasons, there has been no further search for new OSS type signature schemes. % \bf 5. The Okamoto-Shiraishi Signature Scheme % \rm \par The Okamoto-Shiraishi signature scheme \cite{99} is based on the difficulty of finding approximate $k$th roots mod $n$. This signature scheme is interesting because (as is case with the OSS schemes) it is possible to generate these signatures much faster than RSA signatures. %e added sentence It has also been used as an example of a subliminal channel \cite{129}. \begin{description} \item [$\bullet$ \ \ Private Key:] Factorization of $n \ =\ p^2 q$. \item [$\bullet$ \ \ Public Key:] $n$, a small integer $k$, and a one-way function $h$. \item [$\bullet$ \ \ Messages:] $m$ in the domain of $h$. \item [$\bullet$ \ \ Signature:] $s$ such that $s^k \ - \ h(m) \ \equiv \ \delta$ mod $n$ where $| \delta | \ \le \ n^{{2/3}}$. \end{description} \par This scheme was originally proposed for $k \,=\, 2$. This version was quickly broken by Brickell and DeLaurentis \cite{21}. The techniques of this attack also extend to $k \,=\,3$. Shamir \cite{124} found a different method to break the $k \,=\,2$ case. We will present his method and also the \cite{21} method for $k \,=\, 3$. \par For $k\,=\,2$, the forger is given $M \ =\ h(m)$ and wants to find $s$ such that $s^2 \ -\ M \ \equiv \ \delta$ mod $n$ for some $ \delta$ satisfying $| \delta | \ \le \ n^{{2/3}} $. The forger picks $r$ and computes $x$ such that $1 \ \le \ x \ < \ n^{1/3}$ and $2rx \ -\ M \ +\ r^2 \ \equiv \ \gamma $ mod $n$ for $\gamma \ < \ O( n^{2/3} )$. Such an $x$ does not exist for all choices of $r$ (for example $r \ =\ {{n \ +\ 1 \over 2 }} )$. However if the $n^{2/3}$ different valid signatures to $M$ mod $n$ are randomly distributed over the interval [0,$n$], then we expect that an $x$ will exist for most choices of $r$. If an $x$ exists, it can be found through a variation of the extended Euclidean algorithm ( \cite{99} middle bits methods). Given $x,\ s \ =\ r \ +\ x$ is then a valid signature. \par For the cubic scheme, again let $M \ =\ h(m)$. Pick $r \ =\ \left\{ {n \over 3 }\right\}$ (i.e., $r \ =\ {{n \over 3 }} \ +\ \theta$ for $ | \theta | \ \le \ 1/2.$) Compute $z \ =\ M \ -\ r^3$ mod $n$, and let $x \ =\ $nearest integer to $ z^{1/3}$ that is divisible by 3 (i.e. $x \ =\ z^{1/3} \ +\ \epsilon $ for $| \epsilon | \ \le \ 3/2)$. Then $s \ =\ r \ +\ x$ is a valid signature to $m$, since \begin{eqnarray*} s^3 \ & \equiv \ & r^3 \ +\ 3 r^2 x \ +\ 3rx^2 \ +\ x^3 \ {\rm mod} \ n \\ & \equiv \ & r^3 \ +\ 3 \left( {{n \over 3 }} +\theta \right)^2 \ x \ +\ 3 \ \left( {{n \over 3 }} + \theta \right) \ x^2 \ +\ z \ +\ 3 z^{2/3} \ \epsilon \ +\ 3 z^{1/3} \ \epsilon^2 \ +\ \epsilon^3 \ {\rm mod} \ n \\ & \equiv \ & M \ +\ 3\, \theta^2 \,x \ +\ 3\, \theta x^2 \ +\ 3 z^{2/3} \ \epsilon \ +\ 3 z^{1/3} \ \epsilon^2 \ +\ \epsilon^3 \ {\rm mod} \ n \\ & \equiv \ & M \ +\ \delta \ {\rm mod} \ n\ \ \ \ {\rm for} | \delta | \ \le \ O( n^{2/3} ). \end{eqnarray*} \par\vspace{0.2\baselineskip} Although this specific attack is easily guarded against by disallowing signatures that are close to ${n \over 3 }$, the basic attack can be generalized. For example, let $r \ =\ \left[ {un \over v }\right]$ for an arbitrary rational ${u \over v }$. Pick $x$ as above except divisible by $v^2$. If $ \epsilon$ is small enough, then $r \ +\ x$ will be a valid signature, otherwise pick a different $u, \ v$ and try again. \par Okamoto \cite{98} also proposed an encryption scheme based on similar ideas. Again $n$ is an integer of the form $n \ =\ p^2 q$. The public key also contains an integer $u \ =\ a \ +\ bpq$ where $0 \ < \ a \ < \ {1\over 2} \sqrt pq$. This system can be broken by using $u^2$ mod $n$ to solve for $a$. We have $$ u^2 \ \equiv \ a^2 \ +\ 2abpq \ \equiv \ 2au \ -\ a^2 \ {\rm mod} \ n. $$ Solve $0 \ < \ a \ < \ n^{1/3}$ and $| \ u^2 \ -\ 2au \ {\rm mod} \ n | \ < \ n^{2/3}$ by the methods mentioned earlier. After Shamir discovered how to break this scheme (his attack is discussed in \cite{O2}), Okamoto \cite{O2} modified the cryptosystem. In the new system, $u$ is chosen in a different manner. A message $(m_1, m_2)$ for $0 < m_i < n^{1/9} , i = 1,2$ is encrypted as $c \equiv (m_1 u + m_2 )^l \bmod n$. Vallee, Girault, and Toffin \cite{132,VGT2} cryptanalyzed this modified scheme for any $l$ by using lattice basis reduction. % \bf 6. Additional broken two-key systems % \rm \par In this section, we will discuss several two-key cryptosystems that were broken soon after their publication. Several of them relied on composition of polynomials over finite fields. In addition to the specific attacks on such schemes that are mentioned below, there are now some fairly general techniques for decomposing polynomials developed by von zur Gathen, Kozen, and Landau \cite{50} that cast suspicion on all similar schemes. % \bf 6.1 Matsumoto-Imai cryptosystem % \rm \par The Matsumoto-Imai cryptosystem \cite{86} uses polynomials over $GF(2^m )$. The private key consists of secret information about the public encryption polynomial. \begin{description} \item [$\bullet$ \ \ Private key:] $E(X) \ =\ a ( b+X^{\alpha} )^{\beta} $. \item [$\bullet$ \ \ Public key:] $E(X) \ =\ \sum_{i=0}^{{2}^m - 2} e_i X^i$. \item [$\bullet$ \ \ Messages:] $M$ in $GF(2^{m})$. \item [$\bullet$ \ \ Encryption:] $C \ =\ E(M)$. \item [$\bullet$ \ \ Decryption:] Use the private key to solve for $M$. \end{description} \par Matsumoto and Imai suggested that the Hamming weight of $\beta$ should be small so the public key is not too long. Delsarte et al. \cite{36} showed that the public polynomial $E(X)$ would have a special form and this form would actually reveal the private key (or at least something that was functionally equivalent to the private key). % \bf 6.2 Cade Cryptosystem % \rm \par The Cade \cite{24} cryptosystem also uses polynomials over $GF(2^m )$, for $m \ =\ 3r$. Let $M(x) = x^{q+1}$, where $ q = 2^m$. \begin{description} \item [$\bullet$ \ \ Private key:] $T(x) = a_0 x + a_1 x^q + a_2 x^{{q}^2 }$ %.ta 10 $S(x) = b_0 x + b_1 x^q + b_2 x^{{q}^2 }$ where $S$ and $T$ are chosen to be invertible. $P(x) \equiv S M T (x) \ {\rm mod} \ (x^{{q}^3 } - x )$. %.ta 4 \item [$\bullet$ \ \ Public key:] $P(x) = p_{00} x^2 + p_{10} x^{q+1} + p_{11} x^{2q} + p_{20} x^{{q}^2 + 1 } + p_{21} x^{ q^2 + q } + p_{22} x^{{2} q^2 } $. %.ta 4 \item [$\bullet$ \ \ Messages:] $M$ in $ GF(2^{m)}$. %.ta 4 \item [$\bullet$ \ \ Encryption:] $C \ =\ P(M)$. \item [$\bullet$ \ \ Decryption:] Use the private key to solve for $M$. \end{description} \par James, Lidl, and Niederreiter \cite{63} have shown that the private variables $a_0 , ... , b_2 $ can be found from the public key. Cade \cite{25} has since used similar ideas to develop a much more complicated cryptosystem. % \bf 6.3 Yagisawa % \rm \par Yagisawa \cite{136} described a cryptosystem which combined exponentiation mod $p$ with arithmetic mod $p \ -\ 1$. Brickell \cite{19} showed that it could be broken without finding the private key. \par To construct a public key in Yagisawa's cryptosystem, a designer picks a prime p and integers $k_1$, $k_2$, A, and B such that 2 $\le$ A, B $\le$ p-2, 0 $\le$ $k_1$ $\le$ p-2, 0 $\le$ $k_2$ $\le$ p-2, and GCD($k_1$-$k_2$, p-1) =1. He then picks integers $ \beta_1$ and $ \beta_2$ such that $ \beta_1 + \beta_2 k_1 {\equiv} 1\ {\rm mod}\ p-1$ and computes $C {\equiv} B^{{} \beta_1 + \beta_2 k_2}\ {\rm mod}\ p$ and $D{\equiv} B^{{} \beta_1 + \beta_2}\ {\rm mod}\ p$. \par The public key will consist of $(A,B,C,D,\ k_1 \ ,k_2$,p). To encrypt a message ($X_1$, $X_2$, $X_3$) where 0 $\le$ $X_i$ $\le$ p-2, one computes ($Y_1$, $Y_2$, $Y_3$) where $Y_1 {\equiv} X_1 + X_2 + X_3\ \ \ {\rm mod}\ p-1$, $Y_2 {\equiv} {k_1 X_1} + {k_2 X_2} + X_3\ \ \ {\rm mod}\ p-1$, $F {\equiv} B^{{X}_1} C^{{X}_2} D^{{X}_3}\ \ \ {\rm mod}\ p $, and $Y_3 {\equiv} A^F X_3 \ {\rm mod}\ p\ $. \par The designer, given ($Y_1$, $Y_2$, $Y_3$), can compute $F\ \equiv \ \beta_1 \,Y_1 \ +\ \beta_2 \,Y_2 \ {\rm mod} \ p$ and hence can compute $X_3$, and then $X_1$ and $X_2$. \par Even though the cryptanalyst does not know $ \beta_1$ and $ \beta_2$, he can decrypt in much the same manner because he can actually find $B^{{} \beta_1}$ and $B^{{} \beta_2}$. To do this he first computes $r{\equiv}({k_1 - k_2})^{-1}\ \ {\rm mod}\ p-1.$ Since $p$ is prime, for all $X$, $X^{{r({k}_1 - k_2})} {\equiv} X\ {\rm mod}\ p.$ $(C^{{k}_1} {B^{-k_2}})^r {\equiv}{B^{{} \beta_1 ({k_1 - k_2}) r} } {\equiv} B^{{} \beta_1}\ \ {\rm mod}\ p$ and $( C^{-1} B )^r$ $\equiv \ B^{ \beta_2 ( k_1 \,-\, k_2 ) r } \ {\equiv} B^{{} \beta_2}\ \ {\rm mod}\ p.$ Hence the cryptanalyst can also compute F. % \bf 6.4 TMKIF Cryptosystem % \rm \par Tsujii, Matsumoto, Kurosama, Itoh, and Fujioka \cite{139} have devised a public key cryptosystem in which encryption is the evaluation of some rational functions. They remark that if a certain polynomial in a small (e.g. 4) number of variables could be factored, then their system is insecure. Unfortunately, multi-variate polynomials can be factored in polynomial time, as was shown by Lenstra \cite{82} and others. % \bf 6.5 Luccio-Mazzone % \rm \par In our early discussions of knapsack cryptosystems we noted that in general, their linearity was a reason to be suspicious of then. A surprisingly large number of cryptosystems that have been proposed either formally or informally have succumbed to attacks based on this weakness, for example the Pieprzyk cryptosystem (Section 3.4). As another example, Luccio and Mazzom \cite{85} have proposed a system (which is not really a two key system, though) for sending information simultaneously to several receivers. Each receiver $i$, $1\ \le\ i\ \le\ n$, has a secret key $(k_i ,c_{i})$ known only to himself and the sender, and a large prime $p$ is public. To send message $m_i$ to receiver $i$, for $1\ \le\ i\ \le\ n$, the sender finds an $(n-1)$-degree polynomial $f(z)$ in $GF(p)\,\cite{2}$ such that $f(k_i )\ =\ c_i \,m_i\ {\rm mod} \ p$, and broadcasts the coefficents of $f(z)$. Receiver $i$ then obtains \par\vspace{0.2\baselineskip} $$ m_i \ \equiv \ c_i^{-1} \,(f(k_i ))\ \ \ {\rm mod} \ p. $$ \par\vspace{0.2\baselineskip} As was noted by Hellman \cite{57}, this system is very insecure, as the coefficents of the polynomial $f(z)$ are a linear transformation of the messages $(m_1 ,..., m_n )$, and so a knowledge of $n$ or slightly more ciphertext-plaintext pairs suffices to break the system. % \bf 7. The RSA Cryptosystem % \rm \par The cryptosystem found by Rivest, Shamir, and Adleman \cite{116} is the best known two-key cryptosystem. A message is encrypted as $f(m) = m^e \ {\rm mod} \ n $ where $n$ is a composite integer that is usually chosen as the product of only two primes, $p$ and $q$, and $e$ is relatively prime to $(p-1)(q-1)$. Both $n$ and $e$ are public, while $p$ and $q$ have to be kept secret. If the cryptanalyst can factor $n$, he can decrypt messages just as easily as the intended user. With the exception of some special situations discussed below, it is not known how to break the RSA system without factoring $n$. However, this has not been proved, although there are some interesting results of Alexi, Chor, Goldreich, and Schnorr \cite{5} that say that recovering even a single bit of information from an RSA ciphertext is as hard as deciphering the full message. \par Since there are several very good surveys of integer factoring algorithms (e.g., Lenstra and Lenstra \cite{80} and Pomerance \cite{108}), we will not go into details, but will only sketch briefly how effective those algorithms are and what precautions need to be taken in choosing the parameters of an RSA cryptosystem. We will also briefly mention some recent developments that could have dramatic impact on this area. \par It has long been recognized that the primes $p$ and $q$ which give the public modulus $n\ =\ pq$ have to be carefully chosen, so that, for example, $p\ -\ 1,\ p \ +\ 1,\ q\ -\ 1,$ and $q\ +\ 1$ all have relatively large prime factors. However, it is easy to find primes that satisfy these conditions, as was shown by Williams and Schmid \cite{135} and Gordon \cite{53}. It has also been shown that using very small public encryption exponents is insecure. It has recently been shown that precaution must also be taken in choosing the secret exponent, $d$. Wiener \cite{W1} has proven that if $e < n$, and $d < n^{1/4}$, then $d$ can be easily determined, and thus $n$ can be factored. \par Integer factorization has advanced significantly in the last decade. When RSA was invented, the largest ``hard'' integer (i.e., an integer that did not have many prime factors that were either small or of special form that allows them to be split off easily) that had been factored up to then was under 40 (decimal) digits in length. Right now, hard integers of over 110 digits are being factored. This progress is due to advances in both amounts of computing power that are available and theory. As far as hardware is concerned, the most striking development has been the successful implementation of factoring algorithms on networks of workstations. This work was pioneered by Caron and Silverman \cite{26}, and extended by A. Lenstra and M. Manasse \cite{LM}. In their recent factorization of a 111 digit integer, Lenstra and Manasse used roughly the computing power of a 300 mips (million instructions per second) machine running for a year. What was remarkable about this was that this computation was accomplished in several weeks, employed machines from around the whole world, and used only spare time on them. This is in contrast to the situation a few years ago, when it seemed that one needed to have access either to supercomputers or to special purpose machines like that proposed in \cite{109} to factor large integers. Since every factor of 10 increase in computing power allows one to factor integers slightly over 10 decimal digits longer, and the Lenstra-Manasse implementation is relatively portable and extendible to networks with many more machines, one can expect that in the very near future, networks of workstations around some universities or industrial laboratories could be used in their idle time to factor 130 digit integers in a few weeks or months of elapsed time. In particular, it seems very likely that the RSA challenge cipher will be broken in the next year or so, since it involves factoring an integer of 129 digits. Since workstations are becoming more powerful very rapidly (much more rapidly than supercomputers, say) and computer networks are proliferating very fast, and are going to be much more easily accessible than special purpose machines like that of \cite{109}, one should not regard even 140 digit moduli as safe from present day algorithms. \par While one can make fairly good projections about the development of technology and how that will affect the security of the RSA cryptosystem, it is much harder to be certain about theoretical developments. Most of the advances in factoring in the last decade have been due to new ideas, not faster machines. Then, for a while, theoretical advances slowed down. Most of the fast factoring algorithms that have been considered until recently have been shown (under various assumptions) to run in time \par\vspace{0.2\baselineskip} $$ {\rm \exp} \, \left( (1+o(1))\ (( {\rm \log} \,n)\ ( {\rm \log\,\log} \,n))^{1/2} \right) $$ as $n\ \to\ \infty$ for the ``hard'' integers $n$ that are of interest in cryptography. This was explained on technical grounds as being due to all these algorithms relying in one way or another on the density of so-called ``smooth'' integers (integers with only small prime factors). Recently, however, a new method was suggested by J. Pollard, developed further by H. Lenstra, and implemented by A. Lenstra and M. Manasse \cite{LLMP}. It is referred to as the number field sieve. It is very practical when it is applied to factoring so-called Cunningham integers, that is integers $n$ of the form $$ n \,=\, a^k \,\pm 1 \,, $$ where $a$ is small and $k$ is large. If we let $$ M(n,\,r) \ =\ \exp (( r+ o(1)) ( \log \,n )^{1/3} ( \log \,\log \,n)^{2/3} ) \,, $$ then the number field sieve factors Cunningham integers $n$ in time $$ M( n,\,1.526...) \,. $$ This algorithm is fast not only asymptotically, but also in practice, although it is quite complicated to implement, and A. Lenstra and Manasse have used it to factor Cunningham integers of about 150 decimal digits. \par The number field sieve can also be extended to factor general integers. The best currently known method of doing this yields a running time estimate of $$ M(n,2.080...).$$ Although asymptotically this is still far better than other algorithms, the point at which this method would be faster than algorithms such as the quadratic sieve appears to be in the vicinity of 200 decimal digits. On the other hand, the number field sieve is a very recent invention, and so it is likely that substantial improvements might occur which would make it practical. \par One of the fascinating questions about RSA is whether it is as secure as factoring. There are several modifications and restrictions of RSA for which this has been proven (Rabin \cite{111}, Williams \cite{134}), but it has never been shown for RSA itself. There are however, no known attacks on RSA that are faster than factoring the modulus. \par Some of the protocols for using RSA have been broken. They are described in ``Protocol Failures in Cryptosystems,'' by J. H. Moore \cite{90} in this book. % \bf 7.1 Variations on RSA % \rm \par While the basic RSA cryptosystem has resisted all attacks, that is not true for all variants of it. Kravitz and Reed \cite{73} have proposed using irreducible binary polynomials in place of the primes $p$ and $q$. That is, $p(z)$ and $q(z)$ are two secret irreducible polynomials over $GF(2)$ of degrees $r$ and $s$, respectively, the public modulus is the polynomial $n(z)\ =\ p(z)\ q(z)$, and the public encryption exponent $e$ is chosen to be relatively prime to $(2^r -1)\ (2^s -1)$. This system can be broken by factoring $n(z)$, which is usually quite easy to do. However, a further weakness exists in this system, and was already noted in \cite{73}, and more extensively by Delsarte and Piret \cite{33} and by Gait \cite{48}, namely that the decryption exponent is the multiplicative inverse of $e$ modulo one of $(2^u -1)\ (2^{t-u} -1)$, $1\ \le\ u\ \le\ t/2$, where $t\ =\ r+s$ is the degree of $n(z)$. Thus the number of possible decryption exponents grows only linearly with the number of bits in the public key. % \bf 8. Discrete Exponentiation % \rm \par In the seminal paper of Diffie and Hellman \cite{39} which started two key cryptography, they suggested using exponentiation modulo a prime as a public key exchange algorithm. Let $p$ be a prime and $ \alpha$ a primitive element mod $p$. Alice chooses a random integer $a$ and Bob a random integer $b$. Alice sends $ \alpha^a$ mod $p$ to Bob. Bob sends $ \alpha^b$ mod $p$ to Alice. Then both can compute $ \alpha^{ab}$ mod $p$. There have been numerous extensions of this basic scheme. The scheme clearly extends to finite fields %e \cite{106}. Shmuely \cite{128} and McCurley \cite{140} have studied this idea mod $n$ when $n$ is composite. Miller \cite{89} and Koblitz \cite{69} have extended this idea to elliptic curves. El Gamal \cite{43} developed techniques for using discrete exponentiation directly for encryption and signatures. \par The security of the discrete exponentiation cryptosystems is based on the difficulty of the discrete logarithm problem, i.e. given $ \alpha ,\ \beta$, find $x$ such that $ \alpha^x \ =\ \beta$. There have been significant advances in algorithms for finding discrete logarithms in finite fields, particularly in $GF( 2^n )$, where a striking advance was made by Coppersmith \cite{141}. These results are surveyed in \cite{97} and \cite{McC}. With current algorithms, the complexity of finding discrete logarithms in a prime field $GF(p)$ for a general prime $p$ is essentially the same as the complexity of factoring an integer $n$ of about the same size where $n$ is the product of two approximately equal primes \cite{29}, \cite{LO}. In particular, the number field sieve can also be extended to compute discrete logs in prime fields, but so far it is only practical when the prime is a factor of a Cunningham integer \cite{Gord}. However finding discrete logarithms in $GF (2^k )$ is considerably easier. \par When utilizing finite fields $GF(q)$, whether $q$ is prime or $q \ =\ 2^k$, it is necessary to ensure that $q-1$ has a large prime factor, as otherwise it is easy to find discrete logarithms in $GF(q)$. This restriction is similar to the need to choose the secret primes in the RSA system carefully, cf. \cite{53}, \cite{135}. \par To date, there are no subexponential algorithms for finding discrete logarithms in elliptic curves. % \bf 9. The McEliece Cryptosystem % \rm \par In 1978 McEliece \cite{87} introduced a two key cryptosystem based on error correcting codes. An implementation of this scheme would be two to three orders of magnitude faster than RSA. It has two major drawbacks. The key is quite large and it increases the bandwidth. For the parameters suggested by McEliece \cite{87}, the key would have $2^{19}$ bits, and a ciphertext would be twice as long as a message. \par Let $d_H$ denote the Hamming distance. The following is a description of the McEliece cryptosystem for parameters $n,\ k,\ t$. \begin{description} \item [$\bullet$ \ \ Private Key:] $G^{\prime}$ - a $k \,\times \, n$ generator matrix for a Goppa code that can correct $t$ %.ta 10 errors; $P$ - an $n \, \times \,n$ permutation matrix; $S$ - a $k \, \times \, k$ nonsingular matrix. \item [$\bullet$ \ \ Public Key:] $G \ =\ S G^{\prime} P$, a $k \, \times \,n$ matrix. \item [$\bullet$ \ \ Messages:] $k$-dimensional vectors over $GF(2)$. \item [$\bullet$ \ \ Encryption:] ${\bf c} \ =\ {\bf m} G \ +\ {\bf z} $ for ${\bf z} $ a randomly chosen $n$-dimensional vector over GF(2) with Hamming weight at most $t$. \item [$\bullet$ \ \ Decryption:] Let ${ {\bf c}}^{\prime} \ =\ {\bf c} P^{-1}$. Using a decoding algorithm for the Goppa code, %.ta 10 find ${{\bf m}}^{\prime}$ such that $d_H \,( {{\bf m}}^{\prime} G, \ {{\bf c}}^{\prime} ) \ \le \ t$. Then ${\bf m} \ =\ {{\bf m}}^{\prime} \,S^{-1}$. \end{description} \par McEliece suggested that for $n \ =\ 1024$, $t$ should be 50. For $n \ =\ 2^r$, the maximum $k = 2^r - r t $. \par The security of this scheme is based on the NP-completeness of the general decoding problem for linear codes \cite{12}. The only attacks on the system so far have come from improvements in algorithms that would decode any error correcting code. \par An obvious attack on this system is to pick $k$ columns of the matrix $G$. Let $G_k$, ${\bf c}_k$, ${\bf z}_k$ be restrictions onto these $k$ columns. If ${\bf z}_k = {\bf 0}$, then ${\bf m} G_k \ =\ {\bf c}_k$, and ${\bf m}$ can be found by linear algebra. A given choice of $k$ columns can be checked in $k^3$ operations (assuming that fast matrix multiplication is not used) to see if it gives an appropriate ${\bf m}$. For $n = 1024$ and $t = 50$, the expected number of operations before a success is about $2^{80.7}$. However, Adams and Meijer \cite{1} showed that for $n \ =\ 1024$, $t \ =\ 37$ is the optimum value based on this attack, and for this value of $t$, the expected number of operations is about $2^{84.1}$. \par Lee and Brickell \cite{79} modified this attack. They found that after picking $k$ columns, it was more efficient to check if ${\bf z}_k$ had at most two 1's. Against this attack, for $n \ =\ 1024$ $t \ =\ 38$ is optimal. For $t \ =\ 37$ or 38, the expected number of operations is about $2^{73.4}$. \par To the best of our knowledge, there have been no successful attempts to cryptanalyze this system which examined possible leakage of the structure of Goppa codes into the public key. \par Rao and Nam \cite{114} have proposed using a variant of the McEliece scheme as a single key cryptosystem. The key consists of a matrix $G^{\prime}$ generated in exactly the same manner as in the McEliece scheme, and a set $F$ of possible error vectors. A message ${\bf m}$ is encrypted by picking a ${\bf z} \ \in \ F$ at random and forming ${\bf c} \ =\ {\bf m} \,G^{\prime} \ +\ {\bf z}$. Rao and Nam give two methods of selecting the set $F$. Hin \cite{61} showed how to break the Rao-Nam system for one of these methods and Struik and Tilburg \cite{131} for the other. Both of these attacks used a chosen plaintext attack in which the cryptanalyst needs $|F|$ different encryptions of a fixed message ${\bf m}$. \par The Rao-Nam system could be modified slightly by using a pseudo-random function $f$, and letting ${\bf z} \ =\ f( {\bf m} )$ so that there is only 1 encryption for each message ${\bf m}$. It is not known if the above attacks could be modified so that they would also break this system. % \bf 10. Congruential Generators % \rm \par A % \bf congruential generator % \rm is a method of generating a sequence $s_0 , s_1 , \ \it\hbox{...}$ where $s_i $ is computed by the recurrence $$ s_i \ \equiv \ \sum_{j=1}^k \alpha_j \phi_j ( s_0 , \ \it\hbox{...} , s_{i-1} ) \ {\rm mod} \ m . $$ Research in the last few years has uncovered serious weaknesses in using congruential generators as secure pseudo random number generators. Methods have been found for cryptanalyzing congruential generators in which the cryptanalyst knows the functions $ \phi_j$ but not the coefficients $ \alpha_j$ and the modulus $m$. We will examine these results in the section 10.1. \par The simplest congruential generator, the % \bf linear congruential generator% \rm , has the form $$ s_i \ \equiv \ a s_{i-1} \ +\ b \ {\rm mod} \ m. $$ \par A % \bf truncated congruential generator % \rm generates a sequence $x_0 , x_1 ,\ \it\hbox{...}$ where $ x_i $ is the leading $k$ bits of $s_i$ for some sequence $s_i$ produced by a congruential generator. Alternately, we could determine the $x_i$ by some window of $k$ of the bits of the $s_i$. Truncated linear congruential generators have recently been shown to be insecure even if the parameters $a, b$ and $m$ are secret. We will examine these results in sections 10.2 and 10.3. \par There have been no attacks proposed for truncated nonlinear congruential generators. % \bf 10.1 Congruential generators (nontruncated) % \rm \par We will evaluate the security of congruential generators relative to a variation of a known plaintext attack. We will assume that the cryptanalyst knows the functions $ \phi_j$, but does not know the coefficients $ \alpha_j$ or the modulus $m$. The cryptanalyst is given $s_1 , \ \it\hbox{...} , s_{i-1}$. He tries to guess $s_i$. After he guesses, he is told the correct value. We will say that such an attack breaks the cryptosystem if there is a bound that is polynomial in log $m$ and $k$ on the running time of the attack and on the number of errors that are made by the cryptanalyst. \par The cryptanalysis of congruential generators was started by Boyar\cite{105} when she found how to break linear congruential generators. (Knuth \cite{68} had an earlier result, but his algorithm was exponential in log $m$.) Boyar also showed how to break quadratic and cubic congruential generators. Lagarias and Reeds \cite{78} then extended Boyar's result by showing that the same algorithm would break any congruential generator, where $k=1$ and $ \phi$ is a polynomial depending only on $s_{i-1} $. Recently, Krawczyk \cite{74} has proven how to break any congruential generator, in which the functions $ \phi_j$ are computable over the integers in time polynomial in log $m$. \par Krawczyk's algorithm is only a slight modification of Boyar's and we will present it here because of its simplicity. The basic idea that Krawczyk introduces is that he does not try to find the $ \alpha_j$'s. \par Let $$ B_i \ =\ \left( \matrix { \matrix { \phi_1 ( s_0 , \ \it\hbox{...} , s_{i-1} ) \cr \phi_2 ( s_0 , \ \it\hbox{...} , s_{i-1} ) \cr . \cr . \cr . \cr \phi_k ( s_0 , \ \it\hbox{...} , s_{i-1} )} } \right) . $$ \par The first idea used by both Boyar and Krawczyk is that for all but possibly $k$ values of $i$, there exist integers $ \gamma_j , \ j = 1 ,... , i$ such that $ \gamma_i \neq 0$ and $ \gamma_i B_i \ =\ \sum_{j=0}^{i-1} \gamma_j B_j$. Then $ \gamma_i s_i \ \equiv\ \sum_{j=0}^{i-1} \gamma_j s_j \ \bmod \ m$. Thus, either $s_i$ can be predicted (in the case that $ \gamma_i s_i \ \equiv\ \sum_{j=0}^{i-1} \gamma_j s_j$) or a multiple of $m$ can be computed after the correct value of $s_i$ is given. The size of such a multiple of $m$ will be polynomial in log $m$ and $k$. \par Once we know a multiple of $m$, we do the following for each $i$. Let $\hat m$ be the current multiple of $m$ that is known. \begin{itemize} \item[(1)] Given $s_{{i-1}}$, try to express $B_i$ as $B_i \ \equiv\ \sum_{j=0}^{i-1} \gamma_j B_j \ {\rm mod} \ \hat m$. \item[(2)] If (1) is successful, compute $p$ as $p \ \equiv\ \sum_{j=0}^{i-1} \gamma_j s_j \ {\rm mod} \ \hat m$ and if $p \ \neq\ s_i$, then replace $\hat m$ by gcd$(\hat{m} , p - s_i$ ). \end{itemize} \par Krawczyk has shown that if $p \ \neq\ s_i$, then $\hat m \ \neq \ {\rm gcd} (\hat {m} , p - s_i$ ). He also showed that for a fixed $\hat m$, step (1) fails at most $k \ {\rm \log} \ \hat m + 1$ times. From these results, it follows that this algorithm breaks these congruential generators in polynomial time. % \bf 10.2 Linear truncated congruential generators with known parameters % \rm \par In this section, we will consider the security of truncated linear congruential generators in which the cryptanalyst knows the parameters $a, b$ and $m$. These generators were shown to be insecure by Frieze, Hastad, Kannan, Lagarias, and Shamir (\cite{47},\cite{56}, \cite{46}). All of the known attacks are attacks on linear congruential generators in which some constant fraction of the bits of each $s_i$ are used as the pseudo random sequence. The attacks are all based on lattice basis reduction. Each of the attacks that we will describe has been proven to break certain truncated linear congruential generators. However, it has not been determined whether these attacks would also be effective against most truncated linear congruential generators. \par Let $s_i$ be a sequence generated by $$ s_i \ \equiv \ a s_{i-1} \ +\ b \ {\rm mod} \ m. \eqno (10.1)$$ Let $n \ =\ {\rm \log}_2 m $. For $0 < \beta < 1$ such that $ \beta n$ is an integer, we can write $$ s_i \ = \ x_i 2^{ \beta n } \ + \ y_i \eqno (10.2)$$ so that $y_i$ is the lower $ \beta n$ bits of $s_i$ and $x_i$ is the high order $(1 - \beta ) n$ bits of $s_i$. \par To evaluate the security of these sequences, we will assume that the cryptanalyst knows $x_1 , \ \it\hbox{...} , x_{i-1} $, and he wants to predict $x_i$. For the remainder of this section, we will assume that $b = 0$, for if $b \neq 0$, we could examine the sequence $\hat x_i \ =\ x_i - x_{i-1} $. This sequence is essentially the truncation of the sequence $\hat s_i \ =\ s_i - s_{i-1}$ which is generated by $\hat s_i \ \equiv\ a \hat s_{i-1} \ {\rm mod} \ m$. If we could predict the sequence $\hat x_i$, then we could also predict the sequence $x_i$. \par Let $L$ be the lattice spanned by the vector $(m ,\ 0,\ \ \hbox{...} ,\ 0)$ and by the $k-1$ vectors $$ ( a^{i-1} ,\ 0 ,\ \ \hbox{...} ,\ 0,\ -1,\ 0,\ \ \hbox{...},\ 0 ), \ {\rm for} \ i\ =\ 2, \ \ \hbox{...},\ k $$ where the -1 is in the $i$'th coordinate. All vectors ${\bf w} \ =\ (w_{1,}\ \ \it\hbox{...}, w_{k)}$ in $L$ satisfy $$ \sum_{i=1}^k w_i s_i \ \equiv \ 0 \ {\rm mod} \ m. \eqno (10.3)$$ \par The attack consists of two steps. First, find a reduced basis for $L$, of vectors ${\bf w}^j$, $j=1 ,\ \ \it\hbox{...},\ k$. We have $$ \sum_{i=1}^k \,w_i^j \,s_i \ =\ \sum_{i=1}^k w_i^j \,x_i 2^{ \beta n } \ +\ \sum_{i=1}^k w_i^j \,y_i . \eqno (10.4)$$ \par If $$ |\ \sum_{i=1}^k w^j_i y_i | \ < \ {m \over 2 }\eqno (10.5)$$ for $j=1,\ \ \it\hbox{...},\ k$, then since we know that each equation in (10.4) is 0 mod $m$, and we know the $x_i$, we get $k$ independent equations over the integers for the $s_i$, $i=1,\ \ \it\hbox{...}, \ k$. \par If the vectors in the reduced basis satisfy (10.5), then this attack will be successful. % \bf Theorem 10.1 \cite{46}:% \rm \ \ Let $m$ be squarefree, $ \epsilon \ > \ 0$, and $k$ be a given integer. There exists constants $c_k$ and $ C ( \epsilon , k )$ such that if $m \ >\ C( \epsilon , k )$ and if $(1 - \beta ) n\ > \ n ( {1 \over k }+ \epsilon ) + c_k $, then the reduced basis found by the Lovasz algorithm will satisfy (10.5) for at least 1 - $O(m^{{-} {\epsilon \over 2 }} )$ of the possible coefficients $a$. \par The constant $c_k \ =\ O(k^2 )$ and $C ( \epsilon , k ) \ =\ e^{{2k}^{{c}_0 \epsilon^{-1}}} $ for some constant $c_0$. Frieze, et al. also have a similar result for $m$ which are almost squarefree and they have proved Theorem 10.1 for $k = 3$ and any $m$. It is an interesting question to determine if this attack will work for $k>3$ and $m$ an integer that is not almost squarefree, for example $m = 2^n$. To prove that the attack will work in this case appears to need different proof techniques than those used in \cite{46}. The attack that has been described will also be effective against truncated linear congruential generators in which some block of bits other than the most significant bits are used for the pseudo random sequence. However, in this case, the algorithm is not quite as efficient, and asymptotically twice as many bits are needed to break the system. \par It would also be interesting to determine whether this attack would be successful when the modulus $m$ is not so large compared with $k$. This could probably be established by experimental evidence, but to our knowledge, there has been no computational experience with this algorithm. % \bf 10.3 Truncated linear congruential generators with unknown parameters % \rm \par In this section, we assume that the cryptanalyst does not know the parameters $a$, $b$, and $m$. Boyar \cite{Bo} showed that if only a few bits ($O$(log log $m$)) were truncated, then her attack would still work. Stern \cite{130} has recently discovered an extension of the FHKLS method that will break the truncated LCG's when a constant fraction of the bits have been truncated. \par Let us first consider his algorithm when $m$ is known. Let ${\bf v}_i$ be the vector $(x_{i+1} - x_i , x_{i+2} - x_{i+1} , x_{i+3} - x_{i+2} )$. In Part 1 of the algorithm, use the algorithm of Hastad, Just, Lagarias, and Schnorr \cite{55} to find a short integer relation $$ \sum_{i=1}^k \lambda_i v_i \ = \ 0. $$ Let $ {\bf w}_i$ be the vector $(s_{i+1} - s_i , s_{i+2} - s_{i+1} , s_{i+3} - s_{i+2} )$. Then, let $$ {\bf u} \ = \ \sum_{i=1}^k \lambda_i {\bf w}_i . $$ Stern has shown that if $k$ is at least $\sqrt {6 (1- \beta ) \ \log \ m }$, then for most $a$, ${\bf u}$ will be the zero vector. If ${\bf u}$ is the zero vector, then Part 1 is successful. \par If Part 1 is successful, then the cryptosystem is insecure under a type of known plaintext attack. Assume that the cryptanalyst knows the values of $x_0 ,\ \ \it\hbox{...},\ x_{i-1}$, and that he is also given the $h$ least significant bits of $x_i$. From this information, he is asked to predict the next bit of $x_i$. Stern has shown that if part 1 was successful, then out of the $(1 - \beta ) n$ bits of $x_i$, the expected number of mistakes is only $\sqrt { 6 (1- \beta ) \ {\rm \log} \ {m \over 2 }}$. \par Now we will consider the case when the cryptanalyst does not know $a$ or $m$. Stern has shown that if Part 1 is successful, then the polynomial $P(z) \ =\ \sum_{i=0}^{k-1} \lambda_i z^i $ satisfies $P(a) \ \equiv\ 0 \ {\rm mod} \ m$. Stern suggests that by repeatedly using part 1, we could obtain many such polynomials and use them to determine $m$ and $a$. Stern could prove that this method would work based on an assumption that involves the randomness of the polynomials $P$. Lacking a proof of this assumption, it would be interesting to also test this algorithm. % \bf 11. DES % \rm \par The most remarkable news about the cryptanalysis of DES %e \cite{93} is that there are no substantial attacks to mention. See Konheim's book \cite{72} for a complete description of the algorithm. Although DES has been the US standard for almost ten years, and been the focus of many attempts at cryptanalysis %e \cite{14}, \cite{40}, it remains unbroken. The fastest attacks known at this time require $ |K | / 2 $ encryptions where $|K| \ =\ 2^{56}$ is the total number of possible keys. % \bf 11.1 Cryptanalytic attacks on weakened DES % \rm \par There has been some success in breaking weakened DES-like cryptosystems. Grossman and Tuckerman \cite{54} showed DES could be made weak by modifying the method in which the S-boxes were used. Another way to weaken DES is to shorten the number of rounds from the 16 that were proposed. Andelman and Reeds \cite{7} developed a general technique for cryptanalyzing substitution-permutation cryptosystems which worked extremely well on networks with only 3 or 4 rounds. Chaum and Evertse \cite{27} found a known plaintext attack on a 6 round DES that is faster than exhaustive key search. Davies \cite{Da} expoited some non random structures that he found in the S-boxes of DES that enabled him to break an 8 round DES using $2^{40}$ known plaintext messages. Biham and Shamir \cite{BS} have recently announced a chosen plaintext attack that can break an 8 round DES with $2^{18}$ plaintext-ciphertext pairs in which the plaintexts satisfy certain properties. Their method extends to a 15 round DES, which can be broken with $2^{52}$ plaintext-ciphertext pairs. Howver, for the full 16 round DES, their method requires more plaintext-ciphertext pairs than the $2^{55}$ encryptions needed for an exhaustive key search. \par Although there has been no success against the full DES algorithm, there has been cryptanalytic success in breaking one of the proposed modes of operation of DES %e \cite{94}. In output feedback mode (OFB), DES is used to generate a pseudo random sequence, which is then used as a one-time pad to encrypt the message. It makes use of a function, $f_{k,m}$, where $k$ is any valid DES key and $1\ \le\ m\ \le\ 64$. $f_{k,m} ( x ) \ =\ x$ shifted left $m$ bits and concatenated with the leftmost $m$ bits of $E_k ( x )$. ($E_k ( x) $ is the DES encryption of $x$ using key $k$.) To generate a sequence $s_1 , \ \it\hbox{...}$ using OFB, a key, $k$, and an initial 64 bit vector $x_0$ are chosen. Then for $i\, \ge\, 1$, $s_i = E_k ( x_{i-1} )$ and $x_i = f_{k,m} ( x_{i-1} )$. Davies and Parkin \cite{30} observed that for a fixed key $k$ and $m = 64$, the function, $f$, is a permutation. The expected cycle size of a random permutation on $N$ elements is $N/2$. However, if $m \,\le\, 63$, then $f$ is not a permutation. The expected cycle size for a random function on $N$ elements is only about $N^{1/2}$. Therefore only $m=64$ should be considered secure for OFB. % \bf 11.2 Cycles in DES % \rm \par Kaliski, Rivest, and Sherman \cite{66} examined DES to see if any of several properties held. As an example, they wanted to determine whether the $2^{56}$ permutations $E_k $ for $ k \in K$ formed a subgroup. That is for any two keys $k_1$ and $k_2 $, is there another key $k_3 $ such that $E_{ k_1 } ( E_{ k_2 } ( x )) \ =\ E_{ k_3 } ( x)$ for all messages $x$. It was quite important to determine if DES had these properties, because if any one of them held, there would be an attack on DES that would require only $\sqrt {|K|} $ operations. By examining the results of some cleverly designed experiments on DES, they concluded that it was extremely unlikely that DES had any of these properties. \par Additional cycling experiments have been performed by Moore and Simmons \cite{91},\cite{92}. Soon after DES was released, four keys were labeled as weak keys. (These keys had the first 28 bits identical and also the last 28 bits identical.) In addition, several other keys were labeled as semi-weak keys %e \cite{64}. Coppersmith \cite{144} and Moore and Simmons found some remarkable properties of these keys. In particular, they were able to find fixed points or antifixed points, that is messages such that the encryption of the message is either the message itself or the complement of the message. Unfortunately, it is not apparent how to apply these results to give any information about other keys. Quisquater and Delescaille \cite{QD} constructed an algorithm for finding collisions in DES. A collision is a message, $m$, and a pair of keys, $k_1, k_2$, such that both keys encrypt the message to the same ciphertext. Using their algorithm, they discovered many collisions in DES. It is not known how the existence of collisions can be used to aid in the cryptanalysis of DES.k % \bf 11.3 Structural properties of DES % \rm \par The S-boxes introduce nonlinearity into the DES. There are eight S-boxes in the DES, each of which is a set of four permutations on sixteen elements. In the first public analysis of DES by Hellman et al. \cite{58}, there were several properties noted that were satisfied by all of the S-boxes. It was obvious that the S-boxes were not chosen at random, but there is no known cryptographic weakness resulting from these properties. Shamir \cite{123} discovered an additional property of the S-boxes that at first looked very suspicious. However, Brickell, Moore, and Purtill \cite{23} showed that this additional property was the result of the design properties noted by Hellman et al. \cite{58} and Brickell et al. \cite{23}. % \bf 11.4 Birthday Attacks % \rm \par There have been some cryptanalytic attacks based on the so called ``birthday paradox.'' If $ \alpha \sqrt n$ items are drawn with replacement from a set of size $n$, the probability that 2 of them will be a match is about $1 \ -\ e^{{-} \alpha^2 / 2 }$. This means that in a random group of 24 people, the probability that two will have the same birthday is about 1/2. This is an old and well understood concept and it has been the essential point of some recent cryptanalytic attacks. \par Rabin \cite{110} described a scheme for authenticating data using any block cipher as a hash function and RSA for a signature of the hashed value. Yuval \cite{137} showed that this system could be broken with a birthday attack. Let $n$ be the size of the image space of the hash function. (For DES, $n = 2^{64}$.) Suppose that Alice has two messages, $x$, a message that Bob wants to sign, and $y$, a message that Alice wants signed but Bob is not willing to sign. Alice prepares about $\sqrt n$ different slight variations of $x$ and of $y$ and computes the hash functions of each of them. With high probability, she will find variations $\hat x$ and $\hat y$ that hash to the same point. She gives $\hat x$ to Bob to be signed, but she can now use the signature of $\hat x$ as a signature for $\hat y$. \par Another version of the birthday attack can be used to break this system even if Alice only has access to one valid signature and cannot obtain any additional ones. In the Rabin scheme, a text, $M_{1,}\ \ \it\hbox{...},\ M_r$, is signed by picking an $H_0$ at random. Then, $H_i \ =\ E_{ M_i } (H_{i-1} )$ for $i = 1 ,\ \ \it\hbox{...},\ r$. Finally, the pair $(H_0 ,\ H_r )$ is signed using RSA. \par Suppose that Alice is given the signature for a pair $(H_0 ,\ G )$. She then picks $M_1 ,\ \ \it\hbox{...},\ M_{r-2}$ to be anything she likes, and computes $H_i \ =\ E_{ M_i } (H_{i-1} ) $ for $i = 1 ,\ \ \it\hbox{...},\ r\,-\,2$. Alice picks $\sqrt n$ $X$'s and computes $E_X ( H_{r-2} )$ for each $X$. She picks $\sqrt n$ $Y$'s and computes $D_Y ( G )$ for each $Y$. With high probability, she will find a pair $(X,Y)$ such that $E_X ( H_{r-2} ) \ =\ D_Y ( G )$. Then the signature for $(H_0 , G )$ will be a valid signature for $M_1 ,\ \ \it\hbox{...},\ M_{r-2} , X , Y $. \par Davies and Price \cite{31} proposed an iterated form of the Rabin scheme in order to avoid this latter birthday attack. They proposed going through all of the messages twice. Coppersmith \cite{28} showed that this scheme is still susceptible to a birthday attack. See Jueneman \cite{65} for a survey of these results. \par % \bf 12. FEAL \rm FEAL (Fast Data Encipherment Algorithm) was proposed by Shimizu and Miyaguchi \cite{SM} at Eurocrypt 87 as an alternative to DES for use in software. FEAL is a 4 round substitution-permutation cryptosystem with a 64 bit key. Den Boer \cite{DB} soon found an attack on FEAL which requires only 10,000 chosen plaintexts. This has since been improved by Murphy \cite{Mu} to an attack which needs only 20 chosen plaintexts. FEAL has since been modified to become FEAL-N \cite{MSS}, where N is the number of rounds. The methods that Biham and Shamir \cite{BS} developed can be used to break FEAL-8 with less than 2000 chosen plaintexts, and to break FEAL-N for N $\leq 31$ with fewer chosen plaintexts than the number of encryptions needed in an exhaustive key search. \bf 13. Additional Comments % \rm \par In this section we will mention a few additional results, but without any details. \par The need to protect computer files has created a need for very efficient secure cryptosystems. However, many of the cryptosystems designed and sold to fill this need have been shown to be insecure. Reeds and Weinberger \cite{115} have shown how to break the ${\rm UNIX}^{\rm TM}$ crypt command using a ciphertext only attack. Kochanski \cite{71} studied five security products designed for the IBM Personal Computer. He found them to be extremely insecure. He broke all of them using only a PC and without any knowledge about the encryption algorithms that was not provided by the manufacturer with the purchase of the product. Four of them, he broke with a ciphertext only attack. A purchaser of these products should be very skeptical about their claims of security. \par Rivest, Adleman, and Dertouzos \cite{143} introduced several privacy homomorphisms. Essentially, a privacy homomorphism is an encryption function in which desired operations on plaintext messages can be achieved by performing corresponding operations on ciphertext messages. For example, $E(m)\ \equiv \ m^e \, {\rm mod} \,n$, the RSA encryption function, is a privacy homomorphism since $E(m_1 ) \ast E(m_2 )\ \equiv \ E(m_1 m_2 )\, {\rm mod} \,n$. There are four other privacy homomorphisms mentioned in \cite{143}. Brickell and Yacobi \cite{142} showed that two of these can be broken with ciphertext only attacks and the other two can be broken with known plaintext attacks. \par Although many of the encryption machines used during World War II were broken during the war, new techniques for breaking them are still being discovered. The techniques of Andelman and Reeds \cite{7} for cryptanalyzing rotor machines and the comprehensive book covering cryptanalysis of WWII era encryption machines by Deavours and Kruh \cite{32} are excellent examples. \par Schnorr \cite{Sc} proposed a algorithm for contructing a string, $G_n(x)$ of length $2n 2^{2n}$ bits from a random seed, $x$, of length $n 2^n$ bits. He claimed that no statistical test that depended on fewer than $2^{o(n)}$ bits could distinguish $G_n(x)$ from a random bit string. However, Rueppel \cite{Ru} has demonstrated a statistical test that depends on only $4n$ bits that does distinguish (with very high proability) $G_n(x)$ from a random string. Furthermore, Rueppel has shown that the seed, $x$, can be computed in time $O(n 2^n)$ using only $n 2^n + O(1)$ bits of $G_n(x)$. Thus, Schnorr's random number generator expands the randomness of the seed by at most a constant number of bits. \par Matias and Shamir \cite{MS} developed a novel idea for encrypting video signals. A randomly generated curve which passes through all pixels of a video signal is used to tranmit the video picture. The light values at the pixels are then sent in the clear. Johan Hastad \cite{H1} showed that this method was insecure if the same curve is used to transmit many pictures. Bertilsson, Brickell, and Ingemarsson \cite{BBI} showed that it was insecure if many different curves were used to transmit similar pictures. Together, these results indicate that this scheme is unlikely to be secure without some major modifications. \par A radically different concept for a cryptosystem has been proposed by Bennett, Brassard, Breidbart, and Wiesner \cite{10}. They call it quantum cryptography and its security is based on the uncertainty principle of quantum physics. (A very complete list of references on this subject can be found in the paper of Bennett and Brassard \cite{9}.) If such systems become feasible, the cryptanalytic tools discussed here will be of no use. % \bf Acknowledgement % \rm The authors would like to thank Joan Boyar, D. Coppersmith, J. Hastad, H. W. Lenstra, Jr., and C. Schnorr for useful comments. \newpage \begin{thebibliography}{222} \bibitem{1} C. M. Adams and H. Meijer, ``Security-related comments regarding McEliece's Public-key Cryptosystem,'' % \it Advances in Cryptology-CRYPTO'87, \rm Lecture Notes in Computer Science, vol. 293, Springer-Verlag, New York, 1988, pp. 224-230. \bibitem{2} B. S. Adiga and P. Shankar, ``Modified Lu-Lee Cryptosystem,'' % \it Electronics Letters% \rm , August 29, 1985, Vol 21, No.18, pp. 794-795. \bibitem{3} L. M. Adleman, ``On Breaking Generalized Knapsack Public Key Cryptosystems,'' % \it Proc. Fifteenth ACM Symposium on Theory of Computing, % \rm 1983, pp. 402-412. \bibitem{4} L. M. Adleman, R. L. Rivest, ``How to break the Lu-Lee (COMSAT) public-key cryptosystem,'' MIT Laboratory for Computer Science, July 1979. \bibitem{5} W. Alexi, B. Chor, O. Goldreich, and C. P. Schnorr, ``RSA and Rabin functions: certain parts are as hard as the whole,'' % \it SIAM J. Comp.% \rm , vol. 17, 1988, 194-209. \bibitem{6} H. R. Amirazizi, E. D. Karnin and J. M. Reyneri, ``Compact Knapsacks are Polynomially Solvable,'' (extended abstract), Crypto 81 Abstracts, Santa Barbara, 1981. Reprinted in % \it ACM SIGACT NEWS% \rm , vol. 15, 1983, pp. 20-22. \bibitem{7} D. Andelman and J. Reeds, ``On the Cryptanalysis of Rotor Machines and Substitution-Permutation Networks,'' % \it IEEE Trans. Inform. Theory% \rm , vol. IT-28, No. 4, July 1982, pp. 578-584. \bibitem{8} B. Arazi, ``A Trapdoor Multiple Mapping,'' % \it IEEE Trans. Inform. Theory% \rm , vol. 26, no. 1, Jan. 1980, pp. 100-102. \bibitem{9} C. H. Bennett and G. Brassard, ``Quantum Public Key Distribution Reinvented,'' % \it SIGACT News% \rm , Vol. 18, no. 4, Summer 1987, pp. 51-53. \bibitem{10} C. H. Bennett, G. Brassard, S. Breidhart, and S. Wiesner, ``Quantum Cryptography, or Unforgeable Subway Tokens,'' % \it Advances in Cryptography: Proc. CRYPTO 82% \rm , Plenum Press, New York, 1983, pp. 267-275. \bibitem{11} M. Ben-Or, ``Probabilistic Algorithms in Finite Fields,'' % \it Proc. 22nd IEEE Found. Computer Sci. Symp.% \rm , 1981, pp. 394-398. \bibitem{12} E. R. Berlekamp, R. J. McEliece, and H. C. A. van Tilborg, ``On the Inherent Intractability of Certain Coding Problems,'' % \it IEEE Trans. Inform. Theory, % \rm vol. IT-24, 1978, pp. 384-386. \bibitem{BBI} Michael Bertilsson, Ernest F. Brickell, Ingemar Ingemarsson, ``Cryptanalysis of Video Encryption based on space-filling curves,'' to appear in the Proceedings of Eurocrypt89. \bibitem{BS} E. Biham and A. Shamir, ``Differential Cryptanalysis of DES-like Cryptosystems (extended abstract),'' to appear in \it Advances in Cryptology-CRYPTO'90. \bibitem{13} J. Boyar, ``Inferring Sequences Produced by Pseudo-Random Number Generators,'' % \it J. ACM, % \rm vol. 36, 1989, pp. 129-141. \bibitem{Bo} J. Boyar, ``Inferring Sequences Produced by a Linear Congruential Generator Missing Low-Order Bits,'' \it Journal of Cryptology, \rm vol. 1, no. 3, 1989, pp.177-184. \bibitem{14} D. K. Branstead, J. Gait, and S. Katzke, ``Report of the Workshop on Cryptography in Support of Computer Security,'' National Bureau of Standards, September 21-22, 1976, NBSIR 77-1291, September 1977. \bibitem{15} G. Brassard, ``A Note on the Complexity of Cryptography,'' % \it IEEE Transactions on Information Theory% \rm , vol. IT-25, 1979, pp. 232-233. \bibitem{16} E. F. Brickell, ``Solving low density knapsacks,'' % \it Advances in Cryptology-Proc. Crypto 83% \rm , Plenum Press, New York, 1984, pp. 25-37. \bibitem{17} E. F. Brickell, ``A New Knapsack Based Cryptosystem,'' presented at Crypto 83, Santa Barbara, California, U.S.A., August 21-24, 1983. \bibitem{18} E. F. Brickell, ``Breaking Iterated Knapsacks,'' % \it Advances in Cryptology: Proc. CRYPTO'84, \rm Lecture Notes in Computer Science, vol. 196, Springer-Verlag, New York, 1985, pp. 342-358. \bibitem{19} E. F. Brickell, ``Cryptanalysis of the Yagisawa Public Key Cryptosystem,'' Abstracts of Papers, Eurocrypt 86, May 20-22, 1986. \bibitem{20} E. F. Brickell, ``The Cryptanalysis of Knapsack Cryptosystems,'' in % \it Applications of Discrete Mathematics, % \rm R. D. Ringeisen and F. S. Roberts, eds., SIAM, Philadelphia, 1988, pp. 3-23. \bibitem{21} E. F. Brickell and J. M. DeLaurentis, ``An Attack on a Signature Scheme Proposed by Okamoto and Shiraishi,'' % \it Advances in Cryptology-CRYPTO'85, \rm Lecture Notes in Computer Science, vol. 218, Springer-Verlag, New York, 1986, pp.28-32. \bibitem{22} E. F. Brickell, J. C. Lagarias, and A. M. Odlyzko, ``Evaluation of the Adleman Attack on Multiple Iterated Knapsack Cryptosystems,'' % \it Advances in Cryptology, Proc. Crypto 83% \rm , Plenum Press, New York, 1984, pp. 39-42. \bibitem{23} E. F. Brickell, J. H. Moore, and M. R. Purtill, ``Structure in the S-boxes of the DES (extended abstract),'' % \it Advances in Cryptology-CRYPTO'86, \rm Lecture Notes in Computer Science, vol. 263, Springer-Verlag, New York, 1987, pp. 3-8. \bibitem{142} E.F. Brickell and Y. Yacobi, ``On Privacy Homomorphisms,'' \it Advances in Cryptology-EUROCRYPT'87, \rm Lecture Notes in Computer Science, vol. 304, Springer-Verlag, New York, 1988, pp. 117-126. \bibitem{24} J. J. Cade, ``A Public Key Cipher Which Allows Signatures,'' Paper presented at 2nd SIAM Conference on Applied Linear Algebra, Raleigh 1985. \bibitem{25} J. J. Cade, ``A Modification of a Broken Public-key Cipher,'' % \it Advances in Cryptology-CRYPTO'86, \rm Lecture Notes in Computer Science, vol. 263, Springer-Verlag, New York, 1987, pp. 64-83. \bibitem{26} T. R. Caron and R. D. Silverman, ``Parallel Implementation of the Quadratic Scheme,'' % \it J. Supercomputing% \rm , vol. 1, no. 3, 1987, pp. 273-290. \bibitem{27} D. Chaum and J. Evertse, ``Cryptanalysis of DES with a Reduced Number of Rounds,'' % \it Advances in Cryptology-CRYPTO'85, \rm Lecture Notes in Computer Science, vol. 218, Springer-Verlag, New York, 1986, pp. 192-211. \bibitem{138} B. Chor and R. Rivest, ``A Knapsack Type Public Key Cryptosystem Based on Arithmetic in Finite Fields,'' % \it IEEE Trans. Information Theory, % \rm vol. 34, 1988, pp. 901-909.. \bibitem{28} D. Coppersmith, ``Another Birthday Attack,'' % \it Advances in Cryptology-CRYPTO'85, \rm Lecture Notes in Computer Science, vol. 218, Springer-Verlag, New York, 1986, pp. 14-17. \bibitem{141} D. Coppersmith, ``Fast Evaluation of Logarithms in Fields of Characteristic Two,'' % \it IEEE Trans. Information Theory \rm , vol. IT-30, 1984, pp. 587-594. \bibitem{144} D. Coppersmith, ``The real reason for Rivest's phenomenon,'' in % \it Advances in Cryptology-CRYPTO'85, \rm Lecture Notes in Computer Science, vol. 218, Springer-Verlag, New York, 1986, pp. 535-536. \bibitem{29} D. Coppersmith, A. M. Odlyzko, and R. Schroeppel, ``Discrete Logarithms in $GF(p)$,'' % \it Algorithmica% \rm , vol. 1, no. 1, 1986, pp. 1-16. \bibitem{Da} D. W. Davies, ``Investigation of a potential weakness in the DES algorithm,'' unpublished manuscript circulated in July, 1988. \bibitem{30} D. W. Davies and G. I. P. Parkin, ``The average cycle size of the key stream in output feedback encipherment,'' % \it Advances in Cryptology, Proc. of CRYPTO 82, % \rm Plenum Press, 1983, pp. 97-98. \bibitem{31} D. W. Davies and W. L. Price, ``The Application of Digital Signatures based on Public Key Cryptosystems,'' NPL Report DNACS 39/80, National Physical Laboratory, Teddington, Middlesex, England, Dec. 1980. \bibitem{32} C. A. Deavours and L. Kruh, \it Machine Cryptography and Modern Cryptanalysis, \rm Artech House, Dedham, MA,1985. \bibitem{33} P. Delsarte and P. Piret, ``Comment on 'Extension of RSA Cryptostructure: A Galois Approach','' % \it Electronics Letters% \rm , vol. 18, 1982, pp. 582-583. \bibitem{DB} B. Den Boer, ``Cryptanalysis of F.E.A.L.,'' \it Advances in Cryptology-EUROCRYPT'88, \rm Lecture Notes in Computer Science, vol. 330, Springer-Verlag, New York, 1988, pp. 293-299. \bibitem{34} D.E.R. Denning, \it Cryptography and Data Security, \rm Addison-Wesley, Menlo Park, California, 1983. \bibitem{35} Y. Desmedt, ``What happened with Knapsack Cryptographic Schemes?,'' \it Performance Limits in Communication, Theory and Practice, % \rm J. K. Skwirzynski, ed., Kluwer, 1988, pp. 113-134. \bibitem{36} P. Delsarte, Y. Desmedt, A. Odlyzko, and P. Piret, ``Fast Cryptanalysis of the Matsumoto-Imai Public Key Scheme,'' % \it Advances in Cryptology, Proc. EUROCRYPT'84, \rm Lecture Notes in Computer Science, vol. 209, Springer-Verlag, New York, 1985, pp. 142-149. \bibitem{37} Y. G. Desmedt, J. P. Vandewalle and R. J. M. Govaerts, ``A Critical Analysis of the Security of Knapsack Public Key Algorithms,'' % \it IEEE Trans. Inform. Theory% \rm , vol. IT-30, no. 4, July 1984, pp. 601-611, also in \it Abstract of papers, IEEE Intern. Symp. Inform. Theory% \rm , (Les Arcs, France), June 1982, pp. 115-116. \bibitem{38} Y. Desmedt, J. Vandewalle, and R. Govaerts, ``A General Public Key Cryptographic Knapsack Algorithm Based on Linear Algebra,'' % \it Abstract of papers, IEEE Intern. Symp. Inform. Theory% \rm , St. Jovite, Quebec, Canada, September 26-30, 1983, pp. 129-130. \bibitem{39} W. Diffie and M. E. Hellman, ``New Directions in Cryptography,'' IEEE Trans. Inform. Theory, IT 22, 1976, pp. 644-654. \bibitem{40} W. Diffie and M. E. Hellman, ``Exhaustive Cryptanalysis of the NBS Data Encryption Standard,'' % \it Computer, % \rm vol. 10, 1977, pp. 74-84. \bibitem{41} A. DiPorto, ``A Public Key Cryptosystem Based on a Generalization of the Knapsack Problem,'' presented at Eurocrypt 85, Linz, Austria, April 9-11, 1985. \bibitem{42} R. Eier and H. Lagger, ``Trapdoors in Knapsack Cryptosystems,'' \it Cryptography, Proc. Burg Feuerstein 1982, \rm Lecture Notes in Computer Science, vol. 149, Springer-Verlag, New York, 1983, pp. 316-322. \bibitem{43} T. ElGamal, ``A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,'' % \it IEEE Trans. Infor. Theory, % \rm vol IT-31, no.4, July 1985, pp 469-472. \bibitem{44} D. Estes, L. M. Adleman, K. Kompella, K. S. McCurley, and G. L. Miller, "Breaking the Ong-Schnorr-Shamir Signature Scheme for Quadratic Number Fields,'' % \it Advances in Cryptology-CRYPTO'85, \rm Lecture Notes in Computer Science, vol. 218, Springer-Verlag, New York, 1986, pp. 3-13. \bibitem{45} A. M. Frieze, ``On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem,'' % \it SIAM J. Comp.% \rm , vol. 15, no. 2, May 1986, pp. 536-539. \bibitem{46} A. M. Frieze, J. Hastad, R. Kannan, J. C. Lagarias, and A. Shamir, "Reconstructing Truncated Integer Variables Satisfying Linear Congruences,'' % \it SIAM J. Comput.% \rm , vol. 17, 1988, pp. 262-280. \bibitem{47} A. M. Frieze, R. Kannan, and J. C. Lagarias, ``Linear Congruential Generators Do Not Produce Random Sequences,'' % \it Proc. 25th IEEE Symp. on Foundations of Computer Science, % \rm 1984 pp. 480-484. \bibitem{48} J. Gait, ``Short Cycling in the Kravitz-Reed Public Key Encryption System,'' % \it Electronics Letters% \rm , vol. 18, 1982, pp. 706-707. \bibitem{49} M. R. Garey and D. S. Johnson,% \it Computers and Intractability: A Guide to the Theory of NP - Completeness% \rm , W. H. Freeman and Company, San Francisco, 1979. \bibitem{50} J. von zur Gathen, D. Kozen, and S. Landau, ``Functional Decomposition of Polynomials,'' \it Proc. 28th IEEE Symposium on Foundations of Computer Science, \rm 1987. pp. 127-131. \bibitem{51} J. M. Goethals and C. Couvreur, ``A cryptanalytic attack on the Lu-Lee public-key cryptosystem,'' % \it Philips J. Res.% \rm , vol. 35, 1980, pp. 301-306. \bibitem{52} R. M. Goodman and A. J. McAuley, ``A New Trapdoor Knapsack Public Key Cryptosystem,'' % \it Advances in Cryptology, Proc. EUROCRYPT'84, \rm Lecture Notes in Computer Science, vol. 209, Springer-Verlag, New York, 1985, pp. 150-158. Also % \it IEE Proceedings% \rm , Vol. 132, pt. E, No. 6, Nov. 1985, pp. 289-292. \bibitem{Gord} D. M. Gordon, ``Discrete logarithms in $GF(p)$ using the number field sieve,'' to be published. \bibitem{53} J. A. Gordon, ``Strong primes are easy to find,'' % \it Advances in Cryptology, Proc. EUROCRYPT'84, \rm Lecture Notes in Computer Science, vol. 209, Springer-Verlag, New York, 1985, pp. 216-223. \bibitem{54} E. Grossman and B. Tuckerman, ``Analysis of a Feistel-like Cipher Weakened by Having No Rotating Key,'' IBM Research Report, % \bf RC 6375% \rm , January 31, 1977; also, % \it Proceedings ICC % \rm 78. \bibitem{H1} J. Hastad, personal communication. \bibitem{55} J. Hastad, B. Just, J. Lagarias, and C. P. Schnorr, ``Polynomial Time Algorithms for Finding Integer Relations among Real Numbers,'' % \it SIAM J. Comput., % \rm vol. 18, 1989, pp. 859-881. \bibitem{56} J. Hastad and A. Shamir, ``The Cryptographic Security of Truncated Linearly Related Variables,'' % \it Proceedings 17th ACM Symposium on Theory of Computing, % \rm 1985, pp. 356-362. \bibitem{57} M. E. Hellman, ``Another Cryptanalytic Attack on 'A Cryptosystem for Multiple Communication','' % \it Information Processing Letters% \rm , vol. 12, 1981, pp. 182-183. \bibitem{58} M. E. Hellman, R. C. Merkle, R. Schroeppel, L. Washington, W. Diffie, S. Pohlig, and P. Schweitzer, ``Results on an Initial Attempt to Cryptanalyze the NBS Data Encryption Standard,'' Technical Report SEL 76-042, Stanford University, 1976. \bibitem{59} P. S. Henry, ``Fast Implementation of the Knapsack Cipher,'' \it Bell Labs Tech. Journal, \rm Vol. 60, May/June 1981, pp. 767-773. \bibitem{60} T. Herlestam, ``Critical Remarks on Some Public Key Cryptosystems,'' % \it BIT% \rm , vol. 18, 1978, pp. 493-496. \bibitem{61} P. J. M. Hin, ``Channel-Error-Correcting Privacy Cryptosystems,'' Thesis, Delft Univ. of Techn. (1986, in Dutch). \bibitem{62} I. Ingemarsson, ``A New Algorithm for the Solution of the Knapsack Problem,'' \it Cryptography, Proc. Burg Feuerstein 1982, \rm Lecture Notes in Computer Science, vol. 149, Springer-Verlag, New York, 1983, pp. 309-315. \bibitem{63} N. S. James, R. Lidl, and H. Niederreiter, ``Breaking the Cade Cipher,'' % \it Advances in Cryptology-CRYPTO'86, \rm Lecture Notes in Computer Science, vol. 263, Springer-Verlag, New York, 1987, pp. 60-63. \bibitem{64} R. R. Jueneman, ``Analysis of Certain Aspects of Output Feedback Mode,'' % \it Advances in Cryptology: Proc. Crypto 82, % \rm Plenum Press, New York, 1983, pp. 99-127. \bibitem{65} R. R. Jueneman, ``Electronic Document Authentication,'' % \it IEEE Networks, % \rm vol 1 \#2, April '87, \bibitem{66} B. S. Kaliski, R. L. Rivest, and A. T. Sherman, "Is the Data Encryption Standard a Group? (Results of Cycling Experiments on DES),'' \it Journal of Cryptology, \rm Vol. 1, No. 1, 1988, pp. 3-36. \bibitem{67} R. Kannan, ``Improved Algorithms for Integer Programming and Related Lattice Problems,'' % \it Proc. 15th ACM Symposium on Theory of Computing% \rm , 1983, pp. 193-206. \bibitem{68} D. E. Knuth, % \it Deciphering a Linear Congruential Encryption, % \rm Technical Report 024800, Stanford University, 1980. \bibitem{69} N. Koblitz, ``Elliptic Curve Cryptosystems,'' % \it Mathematics of Computation% \rm , vol. 48, 1987, pp. 203-209. \bibitem{70} M. J. Kochanski, ``Remarks on Lu and Lee's proposals,'' % \it Cryptologia,% \rm , vol. 4, no. 4, 1980, pp. 204-207. \bibitem{71} M. J. Kochanski, ``A Survey of Data Insecurity Packages,'' % \it Cryptologia% \rm , vol 11, no.1, January 1987, pp. 1-15. \bibitem{72} A. G. Konheim, \it Cryptography, A Primer, \rm John Wiley, New York, 1981. \bibitem{73} D. Kravitz and I. Reed, ``Extension of RSA Cryptostructure: A Galois Approach,'' % \it Electronics Letters% \rm , vol. 18, 1982, pp. 255-256. \bibitem{74} H. Krawczyk, ``How to Predict Congruential Generators,'' in % \it Advances in Cryptology-CRYPTO'89, \rm Lecture Notes in Computer Science, vol. 435, Springer-Verlag, New York, 1990, pp. 138-153. \bibitem{75} J. C. Lagarias, ``Knapsack Public Key Cryptosystems and Diophantine Approximation,'' % \it Advances in Cryptology, Proc. Crypto 83% \rm , Plenum Press, New York, 1984, pp. 3-23. \bibitem{76} J. C. Lagarias, ``Performance Analysis of Shamir's Attack on the Basic Merkle-Hellman Knapsack Cryptosystem,'' % \it Proc. 11th Intern. Colloquium on Automata, Languages and Programming (ICALP)% \rm , Lecture Notes in Computer Science, vol. 172, Springer-Verlag, Berlin, 1984. \bibitem{77} J. C. Lagarias and A. M. Odlyzko, ``Solving Low Density Subset Sum Problems,'' % \it J. Assoc. Comp. Mach.% \rm , vol. 32, 1985, pp. 229-246. \bibitem{78} J. C. Lagarias and J. Reeds, ``Unique Extrapolation of Polynomial Recurrences,'' % \it SIAM J. Comp.% \rm , vol. 17, 1988, pp. 342-362. \bibitem{LO} B. A. LaMacchia and A. M. Odlyzko, ``Computation of discrete logarithms in prime fields,'' to be published. \bibitem{79} P. J. Lee and E. F. Brickell, ``An Observation on the Security of McEliece's Public-Key Cryptosystem,'' \it Advances in Cryptology-EUROCRYPT'88, \rm Lecture Notes in Computer Science, vol. 330, Springer-Verlag, New York, 1988, pp. 275-280. \bibitem{80} A. K. Lenstra and H. W. Lenstra, Jr., ``Algorithms in Number Theory,'' % \it Handbook of Theoretical Computer Science% \rm , to appear. \bibitem{81} A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovasz, ``Factoring Polynomials with Rational Coefficients,'' % \it Mathematische Annalen 261% \rm , 1982, pp. 515-534. \bibitem{82} A. K. Lenstra, ``Factoring Multivariate Polynomials over Finite Fields,'' % \it J. Computer and System Sci.% \rm , Vol. 30, No. 2, April 1985, pp. 235-248. \bibitem{LLMP} A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, ``The number field sieve,'' % \it Proc. 22nd ACM Symposium on Theory of Computing % \rm (1990), 564-572. \bibitem{LM} A. K. Lenstra and M. S. Manasse, ``Factoring by electronic mail,'' to appear in % \it Advances in Cryptology: Proceedings of Eurocrypt '89, \rm Springer-Verlag, New York. \bibitem{83} H. W. Lenstra, Jr., ``Integer Programming with a Fixed Number of Variables,''% \it Math. Operations Research% \rm , Vol. 8, No. 4, November 1983, pp. 538-548. \bibitem{84} S. C. Lu and L. N. Lee, ``A Simple and Effective Public-key Cryptosystem,'' % \it COMSAT Tech. Rev., % \rm 1979, pp. 15-24. \bibitem{85} F. Luccio and S. Mazzone, ``A Cryptosystem for Multiple Communication,'' % \it Information Processing Letters% \rm , vol. 10, 1980, pp. 180-183. \bibitem{MS} Y. Matias and A. Shamir, ``A video scrambling technique based on space filling curves,'' \it Advances in Cryptology-CRYPTO'87, \rm Lecture Notes in Computer Science, vol. 293, Springer-Verlag, New York, 1988, pp.392-397. \bibitem{86} T. Matsumoto and H. Imai, ``A class of Asymmetric Crypto-Systems based on Polynomials over Finite rings,'' % \it Abstracts of Papers, IEEE Intern. Symp. Inform. Theory% \rm , St. Jovite, Quebec, Canada, Sep. 26-30, 1983, pp. 131-132. \bibitem{140} K. S. McCurley, ``A Key Distribution System Equivalent to Factoring,'' % \it J. Cryptology% \rm , vol. 1, 1988, pp. 95-106. \bibitem{McC} K. S. McCurley, ``The discrete logarithm problem,'' in % \it Cryptography and Computational Number Theory% \rm , C. Pomerance, ed., % \it Proc. Symp. Appl. Math.% \rm , Amer. Math. Soc., 1990, to appear. \bibitem{87} R. J. McEliece, ``A Public-Key Cryptosystem Based on Algebraic Coding Theory,'' DSN Progress Report 42-44, Jet Propulsion Laboratory, 1978, pp. 114-116. \bibitem{88} R. C. Merkle and M. E. Hellman, ``Hiding Information and Signatures in Trapdoor Knapsacks,'' % \it IEEE Trans. Inform. Theory% \rm , vol. 24, no. 5, September 1978, pp. 525-530. \bibitem{89} V. S. Miller, ``Use of Elliptic Curves in Cryptography,'' % \it Advances in Cryptology-CRYPTO'85, \rm Lecture Notes in Computer Science, vol. 218, Springer-Verlag, New York, 1986, pp. 417-426. \bibitem{90} J. H. Moore, ``Protocol Failures in Cryptosystems,'' % paper appears in this book. \bibitem{91} J. H. Moore and G. J. Simmons, ``Cycle Structure of the DES for Keys Having Palindromic (or Antipalindromic) Sequences of Round Keys,'' % \it IEEE Trans. on Software Engineering% \rm , vol. SE-13, no. 2, Feb. 1987, pp. 262-273. \bibitem{92} J. H. Moore and G. J. Simmons, ``Cycle Structure of the DES with weak and semiweak keys,'' % \it Advances in Cryptology-CRYPTO'86, \rm Lecture Notes in Computer Science, vol. 263, Springer-Verlag, New York, 1987, pp. 9-32. \bibitem{Mu} S. Murphy, ``The Cryptanalysis of FEAL-4 with Twenty Chosen Plaintexts,'' to appear in \it Journal of Cryptology, \rm vol. 2, no. 3, 1990. \bibitem{MSS} S. Miyaguchi, A. Shiraishi, and A. Shimizu, ``Fast Data Encipherment Algorithm FEAL-8,'' \it Review of the Electrical Communications Laboratories, \rm vol. 36, no. 4, 1988. \bibitem{93} National Bureau of Standards, ``Encryption Algorithm for Computer Data Protection,'' Federal Register, 40, March 17, 1975, pp. 12134-12139. \bibitem{94} National Bureau of Standards, ``DES Modes of Operation,'' % \it Federal Information Processing Standard, % \rm U. S. Department of Commerce, FIPS PUB 81, Washington, D. C., 1980. \bibitem{95} H. Niederreiter, ``Knapsack-Type Cryptosystems and Algebraic Coding Theory,'' % \it Problems of Control and Information Theory% \rm , vol. 15 (2), 1986, pp. 159-166. \bibitem{96} A. M. Odlyzko, ``Cryptanalytic Attacks on the Multiplicative Knapsack Cryptosystem and on Shamir's Fast Signature System,'' % \it IEEE Trans. Inform. Theory% \rm , vol. IT-30, no. 4, July 1984, pp. 594-601. \bibitem{97} A. M. Odlyzko, ``Discrete Logarithms in Finite Fields and Their Cryptographic Significance,'' % \it Advances in Cryptology, Proc. EUROCRYPT'84, \rm Lecture Notes in Computer Science, vol. 209, Springer-Verlag, New York, 1985, pp. 224-314. \bibitem{98} T. Okamoto, ``Fast Pubic-Key Cryptosystems Using Congruent Polynomial Equations,'' % \it Electronics Letters% \rm , vol. 22, no.11, 1986, pp. 581-582. \bibitem{O2} T. Okamoto, ``Modification of a public-key cryptosystem,'' \it Electronics Letters, \rm Vol. 23, No. 16, 1987, pp. 814-815. \bibitem{99} T. Okamoto and A. Shiraishi, ``A Fast Signature Scheme Based on Quadratic Inequalities,'' % \it Proc. of the IEEE Symposium on Security and Privacy% \rm , 1985, pp 123-132. \bibitem{100} H. Ong, C. P. Schnorr, ``Signatures through Approximate Representations by Quadratic Forms,'' % \it Advances in Cryptology: Proceedings of CRYPTO 83% \rm , Plenum Press, New York, 1984, pp. 117-132. \bibitem{101} H. Ong, C. P. Schnorr, and A. Shamir, ``An Efficient Signature Scheme Based on Quadratic Equations,'' % \it Proc. 16th ACM Symp. on Theory of Computing% \rm , 1984, pp.208-216. \bibitem{102} H. Ong, C. P. Schnorr, and A. Shamir, ``Efficient Signature Schemes Based on Polynomial Equations,'' % \it Advances in Cryptology: Proc. CRYPTO'84, \rm Lecture Notes in Computer Science, vol. 196, Springer-Verlag, New York, 1985, pp. 37-46. \bibitem{103} M. Petit, % \it Etude mathe\'{m}atique de certains syste\'{m}es de chiffrement: les sacs a\'{ }dos,% \rm (Mathematical study of some enciphering systems:the knapsack, in French), Ph.D. thesis, Universite\'{ }de Rennes, France. \bibitem{104} J. P. Pieprzyk, ``On Public-Key Cryptosystems Built Using Polynomial Rings,'' % \it Advances in Cryptology-EUROCRYPT'85, \rm Lecture Notes in Computer Science, vol. 219, Springer-Verlag, New York, 1986, pp. 73-80. \bibitem{105} J. Boyar Plumstead, ``Inferring a Sequence Generated by a Linear Congruence,'' % \it Proc. 23rd IEEE Symp. on Foundations of Computer Science% \rm , 1982, pp. 153-159. \bibitem{106} S. Pohlig and M. E. Hellman, ``An Improved Algorithm for Computing Logarithms over ${\bf GF} (p)$ and its Cryptographic Significance,'' % \it IEEE Transactions on Information Theory, % \rm vol. IT-24, 1978, pp. 106-110. \bibitem{107} J. M. Pollard and C. P. Schnorr, ``An Efficient Solution of the Congruence $x^2 \ +\ k\,y^2 \ =\ m ( {\rm mod} \, n)$,'' % \it IEEE Trans. Information Theory, % \rm vol IT-33, No. 5 Sept. 1987, pp. 702-709. \bibitem{108} C. Pomerance, ``Fast, Rigorous Factorization and Discrete Logarithm Algorithms,'' % \it Discrete Algorithms and Complexity% \rm , D. S. Johnson et al., eds., Academic Press, 1987, pp. 119-143. \bibitem{109} C. Pomerance, J. W. Smith, and R. Tuler, ``A Pipe-Line Architecture for Factoring Large Integers with the Quadratic Sieve Algorithm,'' % \it SIAM J. Comp.% \rm , vol. 17, 1988, 387-403. \bibitem{QD} J.J. Quisquater and J.P. Delescaille, ``How easy is collision search? Application to DES,'' to appear in \it Advances in Cryptology-EUROCRYPT'89, \rm Springer-Verlag, New York. \bibitem{110} M. Rabin, ``Digital Signatures,'' in % \it Foundations of Secure Computation, % \rm Academic Press, New York, 1978. \bibitem{111} M. Rabin, ``Digitalized Signatures and Public Key Functions as Intractable as Factorization,'' Laboratory for Computer Science, Massachusetts Institute of Technology, % \bf MIT/LCS/TR-212, % \rm January 1979. \bibitem{112} M. Rabin, ``Probabilistic Algorithms in Finite Fields,'' % \it SIAM J. Comp.% \rm , vol. 9, 1980. \bibitem{113} S. P. Radziszowski and D. L. Kreher, ``Solving Subset Sum Problems with the $L^3$ Algorithm,'' % \it J. Combin. Math. Combin. Comput., % \rm vol. 3, 1988, pp. 49-63. \bibitem{114} T. R. N. Rao and K. H. Nam, ``Private-Key Algebraic-Coded Cryptosystem,'' % \it Advances in Cryptology-CRYPTO'86, \rm Lecture Notes in Computer Science, vol. 263, Springer-Verlag, New York, 1987, pp. 35-48. \bibitem{115} J. A. Reeds and P. J Weinberger, ``File security and the UNIX System Crypt Command,'' % \it AT\&T Bell Laboratories Technical Journal% \rm , vol. 63, No. 8, Oct. 1984, pp.1673-1683. \bibitem{143} R. L. Rivest, L. Adleman, and M. L. Dertouzos, ``On Data Banks and Privacy Homomorphisms,'' in % \it Foundations of Secure Computation, % \rm R. A. DeMillo, D. P. Dobkin, A. K. Jones, and R. J. Lipton, eds. New York, NY: Academic Press, 1978, pp. 169-179. \bibitem{116} R. L. Rivest, A. Shamir and L. Adleman, ``A Method for Obtaining Digital Signatures and Public Key Cryptosystems,'' % \it Commun. ACM% \rm , vol 21, April 1978, pp. 120-126. \bibitem{Ru} R. A. Rueppel, ``On the Security of Schnorr's Pseudo Random Generator,'' to appear in \it Advances in Cryptology-EUROCRYPT'89, \rm Lecture Notes in Computer Science, Springer-Verlag, New York, 1988. \bibitem{117} C. P. Schnorr, ``A More Efficient Algorithm for a Lattice Basis Reduction,'' % \it Journal of Agorithms% \rm , vol. 9, 1988, pp. 47-62. \bibitem{118} C. P. Schnorr, ``A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms,'' % \it Theoretical Computer Science% \rm , vol. 53, 1987, pp. 201-224. \bibitem{Sc} C. P. Schnorr, ``On the Construction of Random Number Generators and Random Function Generators,'' \it Advances in Cryptology-EUROCRYPT'88, \rm Lecture Notes in Computer Science, vol. 330, Springer-Verlag, New York, 1988, pp. 225-232. \bibitem{119} P. Sch\"{o}bi and J. L. Massey, ``Fast authentication in a trapdoor-knapsack public key cryptosystem,'' % \it Cryptography, Proc. Burg Feuerstein 1982, \rm Lecture Notes in Computer Science, vol. 149, Springer-Verlag, New York, 1983, pp. 289-306. \bibitem{120} A. Shamir, ``A Fast Signature Scheme,'' MIT, Laboratory for Computer Science Report RM - 107, Cambridge, Mass., July 1978. \bibitem{121} A. Shamir, ``The strongest knapsack-based cryptosystem,'' presented at CRYPTO '82, Santa Barbara, California, U.S.A., August 23-25, 1982. \bibitem{122} A. Shamir, ``A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem,'' % \it IEEE Trans. Inform. Theory% \rm , vol. IT-30, no. 5, September 1984, pp. 699-704. \bibitem{123} A. Shamir, ``On the Security of DES,'' % \it Advances in Cryptology-CRYPTO'85, \rm Lecture Notes in Computer Science, vol. 218, Springer-Verlag, New York, 1986, pp. 280-281. \bibitem{124} A. Shamir, personal communication, Oct. 1985. \bibitem{125} A. Shamir, ``The Cryptographic Security of Compact Knapsacks,'' MIT/LCS/TM-164, MIT report, 1980. \bibitem{126} A. Shamir, ``On the Cryptocomplexity of Knapsack Systems,'' Proc. 11th % \it ACM Symp. Theory of Computing, % \rm 1979, pp. 118-129. \bibitem{127} A. Shamir and R. Zippel, ``On the Security of the Merkle-Hellman Cryptographic Scheme,'' % \it IEEE Trans. Inform. Theory, % \rm vol. 26, no.3, May 1980, pp. 339-340. \bibitem{SM} A. Shimizu and S. Miyaguchi, ``Fast Data Encipherment Algorithm FEAL,'' \it Advances in Cryptology-EUROCRYPT'87, \rm Lecture Notes in Computer Science, vol. 304, Springer-Verlag, New York, 1988, pp. 267-271. \bibitem{128} Z. Shmuely, ``Composite Diffie-Hellman Public-Key Generating Systems are Hard to Break,'' % \it Technion - Israel Institute of Technology% \rm , Technical Report \#356. \bibitem{129} G. J. Simmons, ``A Secure Subliminal Channel (?),'' % \it Advances in Cryptology-CRYPTO'85, \rm Lecture Notes in Computer Science, vol. 218, Springer-Verlag, New York, 1986, pp. 33-41. \bibitem{130} J. Stern, ``Secret Linear Congruential Generators are Not Cryptographically Secure,'' % \it Proc. 28th Symposium on Foundations of Computer Science% \rm , 1987, pp. 421-426 \bibitem{131} R. Struik and J. van Tilburg, ``The Rao-Nam Scheme is Insecure Against a Chosen-Plaintext Attack,'' \it Advances in Cryptology-CRYPTO'87, \rm Lecture Notes in Computer Science, vol. 293, Springer-Verlag, New York, 1988, pp. 445-457. \bibitem{139} S. Tsujii, K. Kurosawa, T. Itoh, A Fujioka, and T. Matsumoto, ``A Public-key Cryptosystem Based on the Difficulty of Solving a System of Non-linear Equations,'' TSUJII Laboratory Technical Memorandum, No. 1, 1986. \bibitem{132} B. Vallee, M. Girault, and P. Toffin, ``How to Guess $l$-th Roots Modulo $n$ when Reducing Lattice Basis,'' in % \it Proc. 1-st International Joint Conference of ISSAC-88 and AAECC-6, \rm July 1988.% \bibitem{VGT2} Brigitte Vallee, Marc Girault, Philippe Toffin, ``How to Break Okamoto's Cryptogystem by reducing lattice bases,'' \it Advances in Cryptology-EUROCRYPT'88, \rm Lecture Notes in Computer Science, vol. 330, Springer-Verlag, New York, 1988, pp.281-291. \bibitem{W1} Michael J. Wiener, ``Cryptanalysis of Short RSA Secret Exponents,'' \it IEEE Trans. Information Theory, \rm vol. IT-36, 1990, pp. 553-558. \bibitem{133} M. Willett, ``Trapdoor knapsacks without superincreasing structure,'' % \it Inform. Process. Letters% \rm , vol. 17, July 1983, pp. 7-11. \bibitem{134} H. C. Williams, ``A Modification of the RSA Pubic-Key Encryption,'' % \it IEEE Trans. Infor. Theory, % \rm vol. IT-26, no. 6, 1980, pp. 726-729. \bibitem{135} H. C. Williams and B. Schmid, ``Some Remarks Concerning the MIT Public-key Cryptosystem,'' % \it BIT% \rm , vol. 19, 1979, pp. 525-538. \bibitem{136} M. Yagisawa, ``A New Method for Realizing Public-Key Cryptosystem,'' % \it Cryptologia% \rm , vol.9, No.4, Oct. 1985, pp 360-380. \bibitem{137} G. Yuval, ``How to Swindle Rabin,'' % \it Cryptologia% \rm , vol 3., no.3, July 1979, pp. 187-190. \end{thebibliography} \end{document}