We prove that in any dimension n there exists an origin-symmetric ellipsoid of volume $c n^2$ that contains no points of $Z^n$ other than the origin. Here $c > 0$ is a universal constant. Equivalently, there exists a lattice sphere packing in $R^n$ whose density is at least $c n^2 / 2^n$. Previously known constructions of sphere packings in $R^n$ had densities of the order of magnitude of $n / 2^n$, up to logarithmic factors. Our proof utilizes a stochastically evolving ellipsoid that accumulates at least  $c n^2$ lattice points on its boundary, while containing no lattice points in its interior except for the origin.