% -*-latex-*-
% Document name: /fs1/bal/papers/sumpap.tex
% Creator: bal [bal@gauss]
% Creation Date: Thu Dec  6 11:40:25 1990
%
% $Header: /zu/bal/papers/RCS/sumcc.tex,v 1.4 1992/07/31 13:51:48 bal Exp bal $
%
% The following 3 lines should be uncommented only if this file is being
% processed at Bell Labs.  
%
%\documentstyle[12pt,/n/gauss/fs1/bal/papers/bal-att,amstex,righttag,ctagsplt,amssymb]{attart}
%\input amssym.def
%\input amssym.tex
%
% The following line should be uncommented only if this file is being
% processed at the MIT AI Lab.
%
%\documentstyle[12pt,amstex,twoside,righttag,ctagsplt,amssymb,amscc]{article}
\documentstyle[12pt,amstex,twoside,righttag,ctagsplt,amssymb]{article}
%
% Remaining lines are common to both Bell Labs and MIT
%
\newcommand{\R}[1]{{\Bbb R}^{{#1}}}
%\newcommand{\QED}{{\raisebox{-5pt}{$\square$}}}
\def\Z{{\Bbb Z}}
\def\xh{\hat{x}}
\def\eh{\hat{e}}
\def\half{\tfrac{1}{2}}
\def\quarter{\tfrac{1}{4}}
%\@addtoreset{equation}{section} 
%\def\theequation{\thesection.\arabic{equation}}
%\def\footnoterule{\kern-3\p@
% \hrule width .2\columnwidth
% \kern 2.6\p@}
\newcommand{\nd}[1]{\boldsymbol{#1}}
\newcommand{\X}[1]{{#1}\index{{#1}}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]

\begin{document}

\vspace*{2ex}
\begin{center}
{\Large{\bf Improved Low-Density Subset Sum Algorithms}} \\
\vspace*{+.25in}
Matthijs~J.~Coster, Antoine~Joux, \\ 
Brian~A.~LaMacchia, Andrew~M.~Odlyzko, \\
Claus-Peter~Schnorr and Jacques~Stern
\end{center}

\paragraph{Astract.}
The general subset sum problem is NP-complete.  However, there are two
algorithms, one due to Brickell and the other to Lagarias and Odlyzko,
which in polynomial time solve almost all subset sum problems of
sufficiently low density.  Both methods rely on basis reduction
algorithms to find short non-zero vectors in special lattices.  The
Lagarias-Odlyzko algorithm would solve almost all subset sum problems of
density $< 0.6463\ldots{}$ in polynomial time if it could invoke a
polynomial-time algorithm for finding the shortest non-zero vector in a
lattice.  This paper presents two modifications of that algorithm,
either one of which would solve almost all problems of density $<
0.9408\ldots{}$ if it could find shortest non-zero vectors in lattices.
These modifications also yield dramatic improvements in practice when
they are combined with known lattice basis reduction algorithms.

\vspace*{+.1in}
\noindent{\bf Key words.} subset sum problems; knapsack cryptosystems; lattices; lattice basis reduction.

\vspace*{+.1in}
\section{Introduction}

The {\it knapsack\/} or {\it subset sum\/} problem is to find, given
positive integers $a_1,\ldots{},a_n$ (the weights) and $s$, some subset
of the $a_i$ that sum to $s$, or equivalently to find variables
$e_1,\ldots{},e_n$, with $e_i \in \{0,1\}$, such that
\begin{equation}
\sum_{i=1}^n e_ia_i = s. \label{eq:eqn1} 
\end{equation}
This problem is known to be NP-complete \cite{GaJo} (in its feasibility
recognition form), and so is thought to be very hard in general.  This
has led to the invention of several public-key cryptosystems based on the
knapsack problem.  Almost all of these have been broken by now, however.
(See \cite{Br88,BrOd,De,Od} for surveys of this field.)  Most of the attacks
exploited specific constructions of the relevant cryptosystems.  In
addition, two algorithms have been proposed, one by Brickell \cite{Br84}
and the other by Lagarias and Odlyzko \cite{LaOd} which show that almost
all low-density subset sum problems can be solved in polynomial time.
The {\it density\/} of a set of weights $a_1,\ldots{},a_n$ is defined by
\begin{equation}
d = \frac{n}{{\displaystyle \log_2 \max\begin{Sb}1 \leq i \leq n\end{Sb}
a_i}}. \label{eqn2} 
\end{equation}
The interesting case is $d \leq 1$, since for $d > 1$ there will in
general be many subsets of weights with the same sum, and so such sets
of weights could not be used for transmitting information.  The Brickell
and Lagarias-Odlyzko algorithms solve almost all subset sum problems
with $d$ sufficiently small.

Both the Brickell and Lagarias-Odlyzko algorithms reduce the subset sum
problem to that of finding a short vector in a lattice.  The exact
complexity of finding short vectors in lattices is not known, and expert
opinion appears to be divided as to whether this problem is polynomial
or not.  At the moment, the best known polynomial time method in this
area is the $L^3$ lattice basis reduction algorithm of Lenstra, Lenstra,
and Lov\'asz \cite{LeLeLo}, which is only guaranteed to find a non-zero
vector in an $n$-dimensional lattice that is at most an exponential
times the length of the shortest non-zero vector in that lattice.  If
one uses that algorithm, the Lagarias-Odlyzko method can be shown
rigorously to solve almost all subset sum problems of density $< c/n$
for large $n$ and for a fixed constant $c$, as is done in \cite{LaOd}.
(See \cite{Fr} for a simplified analysis of the algorithm.)  Using more
recent algorithms of Schnorr \cite{Schn88}, one can improve the cutoff
bound to $c' /n$ for arbitrarily small constants $c' > 0$, but at the
cost of increasing the degree of the polynomial that bounds the running
time.

Finding short vectors in lattices may be very hard in general.  On the
other hand, published algorithms, such as the $L^3$ one, perform much
better in practice than is guaranteed by their worst case bounds,
especially when they are modified \cite{LaOd,LaM,RaKr,ScEu}, and new
algorithms are being invented \cite{Schn87,Schn88,Se}.  Thus it is
possible that on average, the problem of finding short vectors in
lattices is easy, even if it is hard in the worst case.  Therefore it
seems worthwhile to separate the issues of efficiency of lattice basis
reduction algorithms from the question of how well the subset sum
problem can be reduced to that of finding a short vector in a lattice.
(Note that Paz and Schnorr \cite{PaSc} have shown that the general
problem of finding the shortest non-zero vector in a lattice is reducible
to that of solving some subset sum problem, but with some loss of
efficiency.)

Consider a {\it lattice oracle\/} that, given a basis for a lattice,
with high probability yields in polynomial time the shortest non-zero
vector in that lattice.  We do not know how to construct such an oracle,
but it might be possible to do so, and in any case in relatively low
dimensions, known polynomial time algorithms act like such an oracle.
The analysis of \cite{LaOd} showed that availability of such an oracle
would let the Lagarias-Odlyzko algorithm solve almost all
subset sum problems of density $< 0.6463\ldots{}$, but not higher than that.
(Similar analyses are not available for the Brickell algorithm \cite{Br84},
although it seems to require even lower densities. See also \cite{FuKa}.)

In this note we analyze two simple modifications of the part of the
Lagarias-Odlyzko algorithm that reduces the subset sum problem to a
short vector in a lattice problem. We show that with either of these
modifications, a single call to a lattice oracle would lead to
polynomial time solutions of almost all problems of density $<
0.9408\ldots{}$.  Empirical tests show that these modifications also lead
to dramatic improvements in the performance of practical algorithms.  We
present some results on this in Section~\ref{sec:discussion}.  More data
and fuller comparisons are given in \cite{LaM}.

In Section~\ref{sec:oldbound} we derive the Lagarias-Odlyzko bound using
the approach in \cite{Fr}.  We show in Section~\ref{sec:newbound} that
this bound may be increased to $0.9408\ldots{}$ using a simple
modification of the Lagarias-Odlyzko attack.  Section~\ref{sec:js}
sketches the other modification, which appears to be quite different,
but which yields the same bound, and its analysis reduces to essentially
the same lattice point counting problem.  Finally,
Section~\ref{sec:discussion} discusses possible improvements on the new
bound and practical results.

This paper is based on the results of two independent investigations of
the same problem.  The modification of the Lagarias-Odlyzko attack
described in Section~\ref{sec:newbound} is due to Coster, LaMacchia,
Odlyzko and Schnorr, and an extended abstract of it appears in
\cite{CoLaOdSc}.  The other modification, outlined in
Section~\ref{sec:js}, is due to Joux and Stern, and was presented
earlier in \cite{JoSt}.

\section{Previous results}\label{sec:oldbound}

In \cite{LaOd}, Lagarias and Odlyzko show that if the density is bounded
by $0.6463\ldots{}$, the lattice oracle is guaranteed to find the
solution vector with high probability.  This section derives the
$0.6463\ldots{}$ bound using simpler techniques due to Frieze \cite{Fr}.
Our presentation differs from that of \cite{Fr} in a few technical details.

Let $A$ be a positive integer and let $a_1,\ldots{},a_n$ be random
integers with $0 < a_i \leq A$ for $1 \leq i \leq n$.  Let
$\nd{e}=(e_1,\ldots{},e_n) \in \{0,1\}^n$, $\nd{e} \neq (0,0,\ldots{},0)$
depending only on $n$, be fixed and let
\begin{xalignat*}{2}
s & = \sum_{i=1}^n e_ia_i, & t & = \sum_{i=1}^n a_i. \notag
\end{xalignat*}
We may assume that $s \geq t/n$, since if $s < t/n$ any $a_i \geq
t/n$ cannot be in the subset, and may be removed from consideration.
Similarly, $s \leq (1-(1/n))t$, otherwise any $a_i \geq t/n$ must be
in the subset.  Thus,
\begin{equation}
\frac{1}{n} t \leq s \leq \frac{n-1}{n} t. \label{eq:sbounds} 
\end{equation}

We recall the Lagarias-Odlyzko attack on low-density subset sum
problems.  Define the vectors $\nd{b_1},\ldots{},\nd{b_{n+1}}$ as
follows: 
\begin{align*}
\nd{b_1} & = (1,0,\ldots{},0,Na_1), \\
\nd{b_2} & = (0,1,\ldots{},0,Na_2), \\
& \phantom{=}\vdots \\
\nd{b_n} & = (0,0,\ldots{},1,Na_n), \\
\nd{b_{n+1}} & = (0,0,\ldots{},0,Ns),
\end{align*}
where $N$ is a positive integer which will be chosen later.  Let $L$ be
the lattice spanned by the vectors $\nd{b_1},\ldots{},\nd{b_{n+1}}$
(i.e.\ $L = \{ \sum_{i=1}^{n+1} z_i\nd{b_i} \colon z_i \in \Z
\quad\text{for } 1 \leq i \leq n+1 \}$).

Notice that the solution vector $\nd{\eh}=(e_1,\ldots{},e_n,0)$ is in
$L$.  Following the proof in \cite{Fr} we are interested in vectors
$\nd{\xh} = (x_1,x_2,\ldots{},x_{n+1})$ which satisfy:
\begin{equation}
\begin{split}
\|\nd{\xh}\| & \leq \|\nd{\eh}\|, \\
\nd{\xh} & \in L, \\
\nd{\xh} & \not\in \{\nd{0},\nd{\eh},\nd{-\eh}\}.
\end{split} \label{eq:xbounds}
\end{equation}
We may assume that 
\begin{equation}
\sum_{i=1}^n e_i \leq \half n,
\end{equation}
(i.e.\  the subset contains at most one-half of the $a_i$'s).  If
$\sum_{i=1}^n e_i > \half n$, we may replace $s$ by $t-s$, $\nd{b_{n+1}}$
by $\nd{b_{n+1}'} = (0,\ldots{},0,N(t-s))$, and $\nd{\eh}$ by
$\nd{\eh'}=(1-e_1,1-e_2,\ldots{},1-e_n,0)$.  Solving this problem is
equivalent to solving the given problem, $\sum_{i=1}^n (1-e_i) \leq
\half n$, and $s' = t-s \geq t/n$.
(To be fully rigorous, we actually apply the basic method to two problems,
at least one of which is covered by the condition
$\sum_{i=1}^n e_i \leq \half n$, and our analysis below applies to this case.)

Choose $N > \sqrt{n}$.  It is clear that $\nd{\xh}$
satisfies Equation~(\ref{eq:xbounds}) only if $x_{n+1} = 0$.
(Otherwise, $\|\nd{\xh}\|\geq |x_{n+1}| \geq N > \sqrt{n} \geq
\|\nd{\eh}\|$, which contradicts Equation~(\ref{eq:xbounds}).)  Let $y$ be
defined by
\begin{equation}
ys = \sum_{i=1}^n x_ia_i, \label{eq:ydef}
\end{equation}
and deduce that
\begin{equation}
|y|s = \left| \sum_{i=1}^n x_ia_i \right| \leq \|\nd{\xh}\| \left|
\sum_{i=1}^n a_i \right| \leq t\sqrt{\half n}.
\end{equation}
Hence, using Equation~(\ref{eq:sbounds}) above,
\begin{equation}
|y| \leq n\sqrt{\half n}.
\end{equation}
Note that since $-y$ is the coefficient of $\nd{b}_{n+1}$ in the expansion of
$\nd{\xh}$ in terms of the basis vectors, $y \in \Z$.

We will show that the probability $P$ --- that a lattice $L$ contains a short
vector which satisfies Equation~(\ref{eq:xbounds}) --- is:
\begin{align}
P &= \Pr(\exists\ \nd{\xh} \text{ which satisfies
Equation~(\ref{eq:xbounds})}) \notag \\
& \leq n \left(2n\sqrt{\half n}+1\right)\frac{2^{c_0n}}{A}, \quad\text{for }
c_0 = 1.54724\ldots{} \label{eq:oldresult}
\end{align}
This implies that, if $A = 2^{cn}$ with $c > c_0$, ${\displaystyle
\lim_{n\rightarrow \infty} P = 0}$.  If the density of a subset sum problem is
less than $0.6463\ldots{}$, then
\begin{align*}
\frac{n}{{\displaystyle \log_2\max\begin{Sb}1 \leq i \leq n\end{Sb}
a_i}} < 0.6463\ldots{} 
&\Longrightarrow \max\begin{Sb} 1 \leq i \leq n \end{Sb} a_i >
2^{n/0.6463\ldots{}} \\ & \Longrightarrow A > 2^{c_0n}.   
\end{align*}
Thus, all subset sum problems with density $< 0.6463\ldots{}$ could be
solved in polynomial time, given the existence of a lattice oracle.

We will now prove Equation~(\ref{eq:oldresult}).  Let $\nd{x} =
(x_1,\ldots{},x_n)$ denote an element of $\Z^n$.  (Note that if
$\nd{\xh} = (x_1,\ldots{},x_n,0)$, then $\|\nd{\xh}\| = \|\nd{x}\|$ and
as a special case we have $\|\nd{\eh}\| = \|\nd{e}\|.)$ First we
estimate the probability $P$ by
\begin{align}
P & \leq \Pr(\exists\ \nd{x},y \text{ s.t. } \|\nd{x}\| \leq \|\nd{e}\|, |y|
\leq n\sqrt{\half n}, \nd{x} \not\in \{\nd{0},\nd{e},\nd{-e}\}, \sum_{i=1}^n 
x_ia_i = ys), \notag \\
\begin{split}
& \leq \Pr\left(\sum_{i=1}^n a_ix_i = ys \colon 0 < \|\nd{x}\| \leq
\|\nd{e}\|,\; |y| \leq n\sqrt{\half n},\; \nd{x} \not\in
\{\nd{0},\nd{e},\nd{-e}\}\right) \\ &\phantom{\leq\quad}\cdot
\left|\left\{\nd{x} \colon \|\nd{x}\| \leq \|\nd{e}\| \right\}\right|
\cdot \left|\left\{ y \colon |y| \leq n\sqrt{\half n} \right\}\right|.
\end{split} \label{eq:prob1}
\end{align}

We have to estimate three factors in the right side of
Equation~(\ref{eq:prob1}). For the first factor of Equation~(\ref{eq:prob1}) we
may rewrite $\sum_{i=1}^n a_ix_i = ys$ as:
\begin{equation*}
\sum_{i=1}^n a_iz_i = 0, \quad\text{where } z_i=x_i-ye_i.
\end{equation*}
Since $\nd{x}$ is non-zero and $\|\nd{x}\| \leq \| \nd{e} \|$, we have
$\nd{z}=(z_1,\ldots{},z_n) \neq \nd{0}$, and so we may assume without
loss of generality (by increasing the bound for the probability by a
factor of at most $n$) that $z_1 \neq 0$.  If $z'$ is defined as
$-(\sum_{i=2}^n a_iz_i/z_1)$, then
\begin{align*}
\Pr\left(\sum_{i=1}^n a_iz_i = 0\right) & = \Pr(a_1 = z'), \\
&= \sum_{j=1}^A \Pr(a_1 = z' | z'=j)\Pr(z' = j), \\
&= \sum_{j=1}^A \Pr(a_1 = z')\Pr(z'=j), \quad\text{($a_1$ and $j$ are
independent)}, \\
&= \sum_{j=1}^A \frac{1}{A} \Pr(z' = j), \\
&\leq \frac{1}{A}.
\end{align*}

Now we consider the second factor of Equation~(\ref{eq:prob1}). From
\cite{LaOd} (which borrowed the technique from a preliminary version
of \cite{MaOd}) we know that
\begin{equation}
\left|\left\{\nd{x} \colon \|\nd{x}\| \leq \|\nd{e}\| \right\}\right| \leq
\left|\left\{\nd{x} \colon \|\nd{x}\| \leq \sqrt{\half n} \right\}\right| \leq
2^{c_0n}, \quad\text{where } c_0 = 1.54724\ldots{}
\end{equation}

It is clear that the last factor of Equation~(\ref{eq:prob1}) can be estimated
by $2n\sqrt{\half n}+1$. This proves Equation~(\ref{eq:oldresult}).

\section{A new, improved bound on the density}\label{sec:newbound}

The main result of this note is an improvement in the maximum density of
subset sum problems which can ``almost always'' be solved: 

\begin{theorem} 
Let $A$ be a positive integer, and let $a_1,\ldots{},a_n$ be random
integers with $0 < a_i \leq A$ for $1 \leq i \leq n$.  Let
$\nd{e}=(e_1,\ldots{},e_n) \in \{0,1\}^n$ be arbitrary, and let $s
= \sum_{i=1}^n e_ia_i$.  If the density $d < 0.9408\ldots{}$, then the
subset sum problem defined by $a_1,\ldots{},a_n$ and $s$ may ``almost
always'' be solved in polynomial time with a single call to a lattice
oracle.
\end{theorem} 

\noindent{\bf Proof.}
We need to make only minor changes to the
proof presented in Section~\ref{sec:oldbound}.  As above, $A$ is a fixed
positive integer and $a_1,\ldots{},a_n$ are random integers with $0 <
a_i \leq A$ for $1 \leq i \leq n$.  Let $\nd{e}=(e_1,\ldots{},e_n) \in
\{0,1\}^n$ be fixed, let $s= \sum_{i=1}^n e_ia_i$, and let $t=
\sum_{i=1}^n a_i$.  Vectors $\nd{b_1},\ldots{},\nd{b_n}$ are defined as
in Section~\ref{sec:oldbound}.  Vector $\nd{b_{n+1}}$ is replaced,
however, by
\begin{equation*}
\nd{b_{n+1}'} = (\half,\half,\ldots{},\half,Ns).
\end{equation*}
Let $L'$ be the lattice spanned by the vectors
$\nd{b_1},\ldots{},\nd{b_n},\nd{b_{n+1}'}$. 

In Section~\ref{sec:oldbound}, we knew that the vector
$\nd{\eh}=(e_1,\ldots{},e_n,0)$ was in the lattice $L$.  Notice that the new
lattice $L'$ does not contain $\nd{\eh}$ but instead contains the vector
$\nd{\eh'}$:
\begin{equation*}
\nd{\eh'} = (e_1',\ldots{},e_n',0), \quad\text{where } e_i' = e_i-\half~.
\end{equation*}
Since $e_i \in \{0,1\}$ for $1 \leq i \leq n$, we know that $e_i' \in
\{-\half,\half\}$ for $1 \leq i \leq n$.  Notice that $\|\nd{\eh'}\|^2 \leq
\quarter n$ independent of the number of $e_i$'s which are equal to 1.

Again, we are interested in the number of vectors $\nd{\xh}$ which satisfy
conditions similar to Equation~(\ref{eq:xbounds}):
\begin{equation}
\begin{split}
\|\nd{\xh}\| & \leq \|\nd{\eh'}\|, \\
\nd{\xh} & \in L', \\
\nd{\xh} & \not\in \{\nd{0},\nd{\eh'},-\nd{\eh'}\}.
\end{split} \label{eq:xpbounds}
\end{equation}
Setting $N > \half \sqrt{n}$ implies that $x_{n+1} = 0$ for any
$\nd{\xh}$ which satisfies Equation~(\ref{eq:xpbounds}).
Suppose that $\nd{\xh} = \sum_{i=1}^n y_i\nd{b_i} + y\nd{b_{n+1}'}$ satisfies
Equation~(\ref{eq:xpbounds}), then we can express $x_i$ in terms of $y_i$ and
$y$ in the following way
\begin{align*}
x_i & = y_i + \half y, \quad\text{for } 1\leq i \leq n, \\
0 = x_{n+1} & = N \cdot \left\{\sum_{i=1}^n a_iy_i + ys\right\}.
\end{align*}
This implies that
\begin{displaymath}
\sum_{i=1}^n a_iy_i = -ys.
\end{displaymath}
Therefore, Equation~(\ref{eq:ydef}) can be replaced by:
\begin{equation}
\sum_{i=1}^n x_ia_i = \half y(t-2s), \label{eq:ypdef}
\end{equation}
since $(\sum_{i=1}^n \nd{b_i}) - 2\nd{b_{n+1}'} =
(0,0,\ldots{},0,N(t-2s))$.

We now establish a bound on the size of $|y|$.  From above,
\begin{align}
|y(t-2s)| & = 2 \left| \sum_{i=1}^n x_ia_i \right| \notag \\
& \leq n \alpha \sqrt{n}, \quad\text{where } \alpha = \max_{1 \leq i
\leq n} a_i. \label{eq:alphadef}
\end{align}
If $|t-2s| \geq \half \alpha$, then $|y||t-2s| \geq \half |y|\alpha$, and
\begin{equation}
|y| \leq 2n\sqrt{n}, \label{eq:ypbound}
\end{equation}
by Equation~(\ref{eq:alphadef}).  If $|t-2s| < \half \alpha$, then we can
solve two problems: one where $\alpha$ is assumed to be part of the
subset which sums to $s$, and one where $\alpha$ is assumed to be part
of the subset which sums to $t-s$.  In the first case, the new problem
has $s' = s-\alpha, t'=t-\alpha$, and
\begin{equation}
|t'-2s'| = |t-\alpha-2s+2\alpha| = |t-2s+\alpha| \geq \half \alpha.
\end{equation}
For the second case, the new problem has $s' = s, t'=t-\alpha$, and
\begin{equation}
|t'-2s'| = |t-2s-\alpha| \geq \half \alpha.
\end{equation}
Thus we may always assume $|t-2s| \geq \half \alpha$ and that the bound in
Equation~(\ref{eq:ypbound}) holds.

We may now calculate the bound on probability $P$ that there exists a
vector $\nd{\xh}$ which satisfies Equation~(\ref{eq:xpbounds}).  We now let
$\nd{x} = (x_1,\ldots{},x_n)$ be any vector such that $2 \; \nd{x} \in
\Z^n$.  We obtain the following bound, similar to
Equation~(\ref{eq:prob1}):
\begin{equation}
P \leq \Pr\left(\sum_{i=1}^n a_ix_i = \half y(t-2s)\right) \cdot
\left|\left\{\nd{x} \colon \|\nd{x}\| \leq \half\sqrt{n}\right\}\right|
\cdot \left(4n\sqrt{n}+1\right).
\label{eq:prob3}
\end{equation}
As in Section~\ref{sec:oldbound}, $\Pr(\sum_{i=1}^n a_ix_i = \half
y(t-2s)) \leq n/A$.  The extra factor of $n$ in the estimate comes from
assuming that the vector $\nd{x}$ has $x_1 \neq 0$. To estimate the
number of vectors $\nd{x}$ with $\|\nd{x}\| \leq \half\sqrt{n}$, we
again use the technique in \cite{LaOd,MaOd}, but in a more complicated
way.  The number of $\nd{x}$ with $\|\nd{x}\| \leq \sqrt{n}/2$ is
bounded above by
\begin{multline}
\left|\left\{\nd{w} = \left( w_1,\ldots{},w_n \right) \colon w_i \in \Z
\quad\text{for all } i, \|\nd{w}\| \leq \half \sqrt{n} \right\}\right| \\ +
\left|\left\{ \nd{w} = \left( w_1,\ldots{},w_n \right) \colon w_i \in \Z
\quad\text{for all } i, \|\nd{w} - (\half,\half,\ldots{},\half)\| \leq \half
\sqrt{n} \right\}\right|.  \label{eq:half-translate}
\end{multline}
In \cite{MaOd} it is shown that for $n$ sufficiently large, the second
summand in Equation~(\ref{eq:half-translate}) above is smaller than the
first summand by a factor that is exponential in $n$.  In any case,
the second summand equals $2^n$.  By the method of \cite{LaOd,MaOd}, the
first summand is bounded, for every $u > 0$, by
\begin{equation*}
2^{(\log_2 e)\delta(u)n}, 
\end{equation*}
where
\begin{equation*}
\delta(u) = \quarter u + \ln \theta(e^{-u}), \quad\text{for }
\theta(z)= 1+ 2\sum_{k=1}^\infty z^{k^2}.
\end{equation*}
Numerically, we may calculate the minimum value of $\delta(u)$, and
obtain
\begin{alignat*}{2}
\delta(u) \geq \delta(u_0) & = 0.7367\ldots{}, & & \text{for } u_0 =
1.8132\ldots{} \\
\intertext{Thus, for large $n$, we have}
\left|\left\{\nd{x} \colon \|\nd{x}\| \leq \half\sqrt{n} \right\}\right| & \leq
2^{c_0'n}, & \quad & \text{for } c_0' = 1.0628\ldots{}, \\
P & \leq n \left(4n\sqrt{n}+1\right)\frac{2^{c_0'n}}{A}.
\end{alignat*}
Thus, any subset sum problem with density $d < 1/c_0' = 0.9408\ldots{}$
may be solved in polynomial time, given the existence of a lattice
oracle.~~$\Box$

\section{Another improvement on the critical density}\label{sec:js}

The preceding section showed one way to improve on the critical density
below which a lattice oracle would enable one to solve most subset sum
problems.  This was achieved by replacing the lattice $L$ in the
Lagarias-Odlyzko attack by the lattice $L'$.  Here we sketch how a
comparable increase in the critical density can be accomplished by using
a lattice $L''$, which is very different.  The lattice $L''$ is
generated by the following vectors in $\R{n+2}$:
\begin{align*}
\nd{b_1} & = (n+1,-1,-1,\ldots{},-1,Na_1), \\
\nd{b_2} & = (-1,n+1,-1,\ldots{},-1,Na_2), \\
& \phantom{=}\vdots \\
\nd{b_n} & = (-1,\ldots{},-1,n+1,-1,Na_n), \\
\nd{b_{n+1}} & = (-1,\ldots{},-1,-1,n+1,-Ns),
\end{align*}
where $N$ is a large positive integer ($N \geq n^2$, say).

If we consider
\begin{align}
\nd{w} & = \sum_{i=1}^{n+1} x_i\nd{b_i} = (w_1,\ldots{},w_{n+2}), \\
\intertext{then for $1 \leq j \leq n+1$,}
w_j & = (n+1) x_j - \sum\begin{Sb} i = 1 \\ i \neq j\end{Sb}^{n+1}
x_i, \\
\intertext{while}
w_{n+2} & = N \left( \sum_{i=1}^n x_ia_i - x_{n+1}s \right).
\end{align}
Simple manipulation yields
\begin{align}
\|\nd{w}\|^2 & = (n+2)^2 \sum_{i=1}^{n+1} x_i^2 - (n+3)
\left(\sum_{i=1}^{n+1} x_i \right)^2 + N^2 \cdot E^2, \\
\intertext{where}
E & = \sum_{i=1}^n x_ia_i - x_{n+1} s.
\end{align}
If $x_i = e_i$ for $1 \leq i \leq n$, $x_{n+1} = 1$, then $E = 0$ and
$\|\nd{w}\|^2$ is bounded by approximately $n^3/4$ (and even less if the
$e_i$ are mostly 1's or mostly 0's).  We next indicate how to show that
most of the time there will be no shorter vectors.  If $E \neq 0$, then
$\|\nd{w}\|^2 \geq N^2 \geq n^4$, so we only have to worry about the
case $E = 0$, and by the method of the preceding two sections, it
suffices to bound the number of $\nd{x} \in \Z^{n+1}$ such that
\begin{equation}
F(\nd{x}) = (n+2)^2 \sum_{i=1}^{n+1} x_i^2 - (n+3) \left(
\sum_{i=1}^{n+1} x_i \right)^2
\end{equation}
satisfies $F(\nd{x}) \leq n^3/4$.  Now
\begin{equation}
F(\nd{x}) = \sum_{i=1}^{n+1} x_i^2 + (n+3) \sum_{1 \leq i < j \leq n+1}
(x_i - x_j)^2. \label{eq:f-def}
\end{equation}
Suppose that
\begin{equation*}
t = \frac{1}{n+1} \sum_{i=1}^{n+1} x_i.
\end{equation*}
Then
\begin{equation*}
F(\nd{x}) = \sum_{i=1}^{n+1} x_i^2 + (n+1)(n+3) \sum_{i=1}^{n+1}
(x_i-t)^2.
\end{equation*}
Therefore if $F(\nd{x}) \lesssim n^3/4$, then 
\begin{equation*}
\sum_{i=1}^{n+1} (x_i - t)^2 \lesssim n/4,
\end{equation*}
and so $\nd{x}$ lies in a sphere of radius $\half \sqrt{n}$ with center
at $(t,t,\ldots{},t)$, and the bounds quoted before for the number of
lattice points in such a sphere apply.  It remains to show that not too
many different values of $t$ can occur.  If $F(\nd{x}) \lesssim n^3/4$,
then clearly $\sum_{i=1}^{n+1} x_i^2 \lesssim n^3/4$, and so by the
Cauchy-Schwartz inequality,
\begin{equation*}
\left(\sum_{i=1}^n x_i\right)^2 \leq (n+1) \sum_{i=1}^{n+1} x_i^2
\lesssim n^4/4,
\end{equation*}
so $|t| \lesssim n/2$.  Furthermore, $(n+1)t \in \Z$, so we have
$\lesssim n^2$ different values of $t$, and this yields the desired
bound for the number of $\nd{x} \in \Z^{n+1}$ with $F(\nd{x}) \lesssim
n^3/4$. 

The critical density for this method is exactly the same as for the
method of Section~\ref{sec:newbound} since both depend on the number of
lattice points in any sphere in $\R{n}$ (for the method of
Section~\ref{sec:newbound}) or $\R{n+1}$ (for the method of this
section) that have radius approximately $\half \sqrt{n}$ being smaller
than $A$.  However, the lattice $L''$ used in this section is very
different from the lattice $L'$ of Section~\ref{sec:newbound}.

The main reason $L$ performs so much more poorly than lattices $L'$ and
$L''$ is that it contains many short vectors in which some of the first
$n$ coordinates are $-1$.  In lattice $L'$, corresponding vectors are
not all that short, since distance is in effect measured from a vector
with coordinates mostly $\half$, so a $-1$ contributes much more to the
length than a 0 or 1.  In lattice $L''$, a similar effect is attained by
arranging the distance to contain the term $F(\nd{x})$ of
Equation~(\ref{eq:f-def}); the last sum penalizes vectors $\nd{x}$ with
the $x_i$ far from their mean.

\section{Discussion}\label{sec:discussion}

The analysis of Section~\ref{sec:newbound} shows that it is possible to
improve the density bound from $0.6463\ldots{}$ to $0.9408\ldots{}$ by
modifying one vector in the lattice basis.  We now consider the
possibilities of improving on this bound.

Solving subset sum problems with basis reduction is closely connected to
lattice covering problems.  In particular, we want to cover the vertices
of the $n$-cube (representing the possible $\nd{e}$ solution vectors)
with a polynomial number of $n$-spheres of radius $\sqrt{\alpha n}$.
Lagarias and Odlyzko showed that it was possible to cover the $n$-cube
with two $n$-spheres of radius $\sqrt{\half n}$.  The two spheres
(centered at $(0,0,\ldots{},0)$ and $(1,1,\ldots{},1)$) correspond to
the two basis reduction problems which must be solved for any given
subset sum problem.  Our analysis in Section~\ref{sec:newbound} uses one
$n$-sphere of radius $\half\sqrt{n}$ centered at
$(\half,\half,\ldots{},\half)$ to cover all the points.

One way to improve the bound presented above would be to show that
it is possible to cover the vertices of the $n$-cube with a polynomial
number of $n$-spheres of radius $\sqrt{\alpha n}$ with $\alpha <
\quarter$.  We show that this is not possible, and that the asymptotic
bound of $0.9408\ldots{}$ cannot be improved in this way.  The following
proposition shows that any $n$-sphere of radius $\sqrt{\alpha n}$ with
$\alpha < \quarter$ can cover only an exponentially small fraction of
the vertices of the $n$-cube.  Thus, no polynomial collection of such
spheres can satisfy our requirements.

\begin{proposition}
Any sphere of radius $\sqrt{\alpha n}, \alpha
< \quarter$, in $\R{n}$ contains at most $(2~-~\delta)^n$ points of
$\{0,1\}^n$, for some $\delta = \delta(\alpha) > 0$.
\end{proposition}

\noindent{\bf Proof.}
Suppose that the $n$-sphere is centered at the
point $\nd{c}=(c_1,\ldots{},c_n)$. We are interested in the number of
points $\nd{e} \in \{0,1\}^n$ for which $\|\nd{c}-\nd{e}\|^2 \leq \alpha
n$.  Using the upper bound technique of \cite{MaOd}, we show that $N$,
the number of points in $\{0,1\}^n$ inside the sphere, is bounded by
\begin{equation}
N \leq e^{\alpha n}\prod_{i=1}^n (e^{-c_i^2} + e^{-(c_i-1)^2}).
\label{eq:Nbound} 
\end{equation}
If the point $\nd{e}=(e_1,\ldots{},e_n)$ is inside the sphere, then
$\|\nd{c}-\nd{e}\|^2 = \sum_{i=1}^n (c_i-e_i)^2 \leq \alpha n$, and
after expanding the right side,
Equation~(\ref{eq:Nbound}) contains a term of the form
\begin{equation*}
\exp\left(\alpha n- \sum_{i=1}^n (c_i-e_i)^2\right) \geq 1,
\end{equation*}
for each such point $\nd{e}$, which proves Equation~(\ref{eq:Nbound})
since all terms in the expansion are nonnegative.

Since the terms in the product in Equation~(\ref{eq:Nbound}) are
independent, we know that the value of $N$ is bounded
by
\begin{equation*}
e^{\alpha n} \max_{\nd{c} \in \R{n}} \prod_{i=1}^n \left( e^{-c_i^2} +
e^{-(c_i-1)^2}\right) \leq e^{\alpha n} (2e^{-1/4})^n.
\end{equation*}
(It is easy to show that the maximum value of
$f(z)=e^{-z^2} + e^{-(z-1)^2}$ is $2e^{-1/4}$.)  Thus,
\begin{align*}
N \leq e^{n \alpha} 2^n e^{(-1/4)n} &= 2^n e^{n(\alpha - 1/4)} \\
&= (2-\delta(\alpha))^n, \quad\text{for } \delta(\alpha) = 2(1-e^{\alpha
- 1/4}) 
\end{align*}
For all $\alpha < \quarter$, $\delta(\alpha) > 0$,
which proves
the proposition.~~$\Box$

As $n\rightarrow \infty$, any $n$-sphere with radius $\sqrt{\alpha n}$,
$\alpha < \quarter$, will contain at most $(2~-~\delta(\alpha))^n$
points in $\{0,1\}^n$.  Thus, any polynomial-sized collection of spheres
cannot contain all the points in $\{0,1\}^n$.  Thus we cannot hope to
asymptotically improve the $0.9408\ldots{}$ bound by reducing a
polynomial number of bases with different $\nd{b_{n+1}}$ vectors.
However, for small dimensions it might be possible to improve the bound,
even though any such advantage will disappear as $n$ grows.

In cases where the subset sum problem (Equation~\ref{eq:eqn1}) to be
solved is known to have $\sum \, e_i$ small (as occurs in some knapsack
cryptosystems, such as the Chor-Rivest one \cite{CR}, which has still
not been broken), it is possible to again improve on the results of
\cite{LaOd} by the approach of Section~\ref{sec:newbound}.  For example,
if we know that
\begin{equation*}
\sum_{i=1}^{n} e_i = \beta n,
\end{equation*}
we can replace the vector $\nd{b_{n+1}}$ in the basis of $L$ by 
\begin{equation*}
\nd{b_{n+1}''} = (\beta,\beta,\ldots,\beta,Ns),
\end{equation*}
and then the lattice $L$ will contain a vector of length $\sqrt{n
\beta(1-\beta)}$, and our analysis shows that in this case it then
becomes possible to solve most problems with even smaller weights $a_i$.
The density bound for the approach in Section~\ref{sec:js} is similarly
improved if it is known that $\sum e_i = \beta n$; no modification of
lattice $L''$ is required to take advantage of this additional
information.  However, it appears that there are choices for the
parameters in the Chor-Rivest knapsack which yield subset sum problems
with densities above even these improved bounds.  Thus asymptotically
our algorithms do not threaten the security of this cryptosystem.  On
the other hand, for moderate sizes of the problem (such as a challenge
version of the Chor-Rivest knapsack with $n = 103$ that was constructed by
B.~Chor) solutions can be found with nonnegligible probability.  Thus to
obtain secure cryptosystems, one has to use very large values of the
basic parameters, which make this scheme less attractive.

When we consider the $L_{\infty}$ or sup-norm,
\begin{equation*}
\|(x_1,\ldots,x_n ) \|_{\infty} = \max_{1 \leq j \leq n} |x_j|,
\end{equation*}
then we find that the vector $\nd{\eh'}$ has norm 1/2.  Therefore, we
can solve all subset sum problems of any density if we have a lattice
oracle for the sup-norm, as was pointed out by Michael Kaib.

The general sup-norm shortest vector problem is known to be
NP-complete \cite{Em}; the complexity of the square-norm shortest
vector problem is an open problem.  That a sup-norm lattice
oracle yields a better density bound than a square-norm lattice oracle
suggests that the shortest vector problem for the sup-norm might be
harder than for the square-norm.

The discussion above dealt with the approach of
Section~\ref{sec:newbound} to improving the Lagarias-Odlyzko algorithm,
and showed that the simplest idea for improving on it further does not
work.  We do not see any way to improve on either that method or the one
in Section~\ref{sec:js}.

\begin{table}
\begin{center}
\begin{tabular}{|c|r|c|c|} \hline
$n$ & \hfill $b$ \hfill & $L$ & $L'$ \\ \hline \hline
50 &  50 & 0.05 & 1.00  \\ \hline
50 &  60 & 0.55 & 1.00  \\ \hline
50 &  75 & 1.00 & --    \\ \hline
66 &  76 & --   & 0.25  \\ \hline
66 &  84 & --   & 0.80  \\ \hline
66 &  92 & --   & 0.95  \\ \hline
66 & 100 & --   & 1.00  \\ \hline
66 & 104 & 0.30 & 1.00  \\ \hline
66 & 108 & 0.55 & 1.00  \\ \hline
66 & 112 & 0.60 & 1.00  \\ \hline
66 & 116 & 1.00 & --    \\ \hline
\end{tabular} 
\caption{Fraction of random subset sum problems solved by a
particular reduction algorithm applied to bases $L$ and $L'$,
respectively.}\label{tab:experiments}
\end{center}
\end{table}

Sections~\ref{sec:newbound} and \ref{sec:discussion} presented
theoretical results that assume the availability of an efficient method
for finding the shortest non-zero vector in a lattice.  When one uses
known algorithms for lattice basis reduction, applying them to lattice
$L'$ instead of lattice $L$ also yields dramatic improvements, although
the results are not as good as they would be in the presence of a
lattice oracle.  For example, Table~\ref{tab:experiments} presents the
comparison obtained in one particular set of experiments.  The lattices
used were not exactly $L$ and $L'$, and the reduction algorithm used a
combination of ideas from several sources.  More extensive data sets and
details of the computations are presented in \cite{LaM}.  For each
entry in Table~\ref{tab:experiments}, $n$ denotes the number of items,
and $b$ the number of bits (chosen at random) for each item.  For each
$(n,b)$ combination, 20 problems were attempted, where in each case $e_i
=1$ for exactly $n/2$ of the items.  The entries for the $L$ and $L'$
column indicate what fraction of the 20 problems were solved in each
case.  It would be of interest to obtain similar comparisons for 
implementations of other algorithms, such as that of \cite{HaJuLaSc}.
Combining the improved lattice $L'$ of this paper with variants of the
algorithms of \cite{Schn87} leads to solutions of subset sum problems of
even higher densities, as is shown in \cite{ScEu}.

\section*{Acknowledgements}
M.~Coster's visit to AT\&T Bell Laboratories was supported by a
Fulbright scholarship.  A.~Joux is supported by DGA.

\vspace{30pt}
%\clearpage
\begin{thebibliography}{99}

\bibitem{Br84} {\sc E.~F.~Brickell}, Solving low density knapsacks,
in {\sl Advances in Cryptology, Proceedings of Crypto~'83}, Plenum
Press, New York, 1984, 25-37.

\bibitem{Br88} {\sc E.~F.~Brickell}, The cryptanalysis of knapsack
cryptosystems, in {\sl Applications of Discrete Mathematics},
R.~D.~Ringeisen and F.~S.~Roberts, eds., SIAM, 1988, 3-23.

\bibitem{BrOd} {\sc E.~F.~Brickell and A.~M.~Odlyzko}, Cryptanalysis:
a survey of recent results, {\sl Proc. IEEE\/} {\bf 76} (1988),
578-593.

\bibitem{CR} {\sc B.~Chor and R.~Rivest}, A knapsack-type public key
cryptosystem based on arithmetic in finite fields, {\sl IEEE Trans.
Information Theory\/} {\bf IT-34} (1988), 901-909. 

\bibitem{CoLaOdSc} {\sc M.~J.~Coster, B.~A.~LaMacchia, A.~M.~Odlyzko
and \mbox{C.-P.} Schnorr}, An improved low-density subset sum algorithm, in
{\sl Advances in Cryptology: Proceedings of Eurocrypt '91},
D.~W.~Davies, ed., {\sl Lecture Notes in Computer Science\/} {\bf 547},
Springer-Verlag, New York, 1991, 54-67.

\bibitem{De} {\sc Y.~Desmedt}, What happened with knapsack cryptographic
schemes?, in {\sl Performance Limits in Communication, Theory and
Practice}, J.~K. Skwirzynski, ed., Kluwer, Boston, 1988, 113-134.

\bibitem{Em} {\sc P.~van~Emde~Boas}, {\sl Another NP-complete partition
problem and the complexity of computing short vectors in a lattice},
Rept. 81-04, Dept. of Mathematics, Univ. of Amsterdam, 1981.

\bibitem{Fr} {\sc A.~M.~Frieze}, On the Lagarias-Odlyzko algorithm for the
subset sum problem, {\sl SIAM J. Comput.\/} {\bf 15(2)} (1986), 536-539. 

\bibitem{FuKa} {\sc M.~L.~Furst and R.~Kannan}, Succinct certificates
for almost all subset sum problems, {\sl SIAM J. Comput.\/} {\bf 18}
(1989), 550-558.

\bibitem{GaJo} {\sc M.~R.~Garey and D.~S.~Johnson}, {\sl Computers and
Intractability: A Guide to the Theory of NP-Completeness},
W.~H.~Freeman and Company, New York, 1979.

\bibitem{HaJuLaSc} {\sc J.~H{\aa}stad, B.~Just, J.~C.~Lagarias, and
C.-P.~Schnorr}, Polynomial time algorithms for finding integer
relations among real numbers, {\sl SIAM J. Comput.\/} {\bf 18(5)}
(1989), 859-881.

\bibitem{JoSt} {\sc A.~Joux and J.~Stern}, Improving the critical
density of the Lagarias-Odlyzko attack against subset sum problems,
{\sl Proceedings of Fundamentals of Computation Theory '91}, L.~Budach,
ed., {\sl Lecture Notes in Computer Science\/} {\bf 529},
Springer-Verlag, New York, 1991, 258-264.

\bibitem{LaOd} {\sc J.~C.~Lagarias and A.~M.~Odlyzko}, Solving
low-density subset sum problems, {\sl J. Assoc. Comp. Mach.\/} {\bf
32(1)} (1985), 229-246.

\bibitem{LaM} {\sc B.~A.~LaMacchia}, {\sl Basis Reduction Algorithms
and Subset Sum Problems}, SM Thesis, Dept. of Elect. Eng. and Comp.
Sci., Massachusetts Institute of Technology, Cambridge, MA, 1991.  Also
available as AI Technical Report 1283, MIT Artificial
Intelligence Laboratory, Cambridge, MA, 1991.

\bibitem{LeLeLo} {\sc A.~K.~Lenstra, H.~W.~Lenstra, and L.~Lov\'asz},
Factoring polynomials with rational coefficients, {\sl Math. Ann.\/}
{\bf 261} (1982), 515-534.

\bibitem{MaOd} {\sc J.~E.~Mazo and A.~M.~Odlyzko}, Lattice points in
high-dimensional spheres, {\sl Monatsh. Math.\/} {\bf 110} (1990),
47-61.

\bibitem{Od} {\sc A.~M.~Odlyzko}, The rise and fall of knapsack
cryptosystems, in {\sl Cryptology and Computational Number Theory},
C.~Pomerance, ed., {\sl Proc. Symp. Appl. Math.} {\bf 42}, Amer. Math.
Soc., Providence, 1990, 75-88.

\bibitem{PaSc} {\sc A.~Paz and C.-P.~Schnorr}, Approximating integer
lattices by lattices with cyclic factor groups, in {\sl Automata,
Languages, and Programming: $14^{\text{th}}$ ICALP}, {\sl Lecture
Notes in Computer Science\/} {\bf 267}, Springer-Verlag, New York,
1987, 386-393.

\bibitem{RaKr} {\sc S.~Radziszowski and D.~Kreher}, Solving subset sum
problems with the $L^3$ algorithm, {\sl J. Combin. Math. Combin.
Comput.\/} {\bf 3} (1988), 49-63.

\bibitem{Schn87} {\sc C.-P.~Schnorr}, A hierarchy of polynomial time
lattice basis reduction algorithms, {\sl Theoretical Computer
Science\/} {\bf 53} (1987), 201-224.

\bibitem{Schn88} {\sc C.-P.~Schnorr}, A more efficient algorithm for
lattice basis reduction, {\sl J. Algorithms\/} {\bf 9} (1988), 47-62.

\bibitem{ScEu} {\sc C.-P.~Schnorr and M.~Euchner}, Lattice Basis
Reduction: Improved Practical Algorithms and Solving Subset Sum
Problems, in {\sl Proceedings of Fundamentals of Computation Theory
'91}, L. Budach, ed., {\sl Lecture Notes in Computer Science\/} {\bf
529}, Springer-Verlag, New York, 1991, 68-85.

\bibitem{Se} {\sc M.~Seysen}, Simultaneous reduction of a lattice basis
and its reciprocal basis, {\sl Combinatorica}, to appear.

\end{thebibliography}
\clearpage

\medskip\noindent {\small
\begin{tabular}{@{}l@{\hspace*{12pt}}l@{}}
\begin{tabular}[t]{@{}l}
{\sc Matthijs J. Coster}\\AT\&T Bell
Laboratories\\Murray Hill, NJ 07974\\USA
\end{tabular} & 
\begin{tabular}[t]{@{}l}
{\sc Antoine~Joux} \\ GRECC/DMI \\ Ecole Normale
Sup\'erieure \\ 45 rue d'Ulm \\ 75230 PARIS Cedex 05 \\ FRANCE \\ {\tt
joux@@frulm63.bitnet}
\end{tabular} \\
\\
\begin{tabular}[t]{@{}l}
{\sc Brian A. LaMacchia}\\AT\&T Bell
Laboratories\\Murray Hill, NJ 07974\\USA
\end{tabular} & 
\begin{tabular}[t]{@{}l}
{\sc Andrew M. Odlyzko}\\AT\&T Bell
Laboratories\\Murray Hill, NJ 07974\\USA\\{\tt amo@@research.att.com}
\end{tabular} \\
\\
\begin{tabular}[t]{@{}l}
{\sc Claus-Peter Schnorr}\\Universit\"at Frankfurt \\
Fachbereich Mathematik/Informatik \\ Postfach 11 19 32 \\ 6000
Frankfurt am Main \\ GERMANY \\ {\tt schnorr@@informatik.uni-frankfurt.de}
\end{tabular} & 
\begin{tabular}[t]{@{}l}
{\sc Jacques Stern} \\ GRECC/DMI \\ Ecole Normale Sup\'erieure \\ 45
rue d'Ulm \\ 75230 PARIS Cedex 05 \\ FRANCE \\ {\tt stern@@dmi.ens.fr}
\end{tabular} \\ 
\\ 
\begin{tabular}[t]{@{}l}
Current address of {\sc M.~Coster}: \\ Department of Economics \\ Room B-837 \\
University of Tilburg \\ P.O. Box 90153 \\ 5000 LE Tilburg \\ The
NETHERLANDS \\ {\tt coster@@kub.nl} \end{tabular} &
\begin{tabular}[t]{@{}l} Current address of {\sc B.~LaMacchia}: \\MIT
AI Laboratory \\ 545 Technology Square \\ Cambridge, MA 02139 \\ USA \\
{\tt bal@@mit.edu} 
\end{tabular} 
\end{tabular}}

\end{document}