**Author:**Daniele Micciancio

Discrete
and Computational Geometry, **29**(1):133-138
(Dec. 2002)

[BibTeX] [Postscript] [PDF] [doi:10.1007/s00454-002-2825-1]

**Abstract:** We prove that the best way to
reduce the volume of the *n*-dimensional unit cube by a linear
transformation that maps each of the main vertices **e**_i
to a point
within distance *ε < sqrt{(1/n) - (1/n^2)}* from
**e**_i is to
shorten all edges by a factor *(1 - ε)*. In particular, the
minimal volume of such an almost cubic parallelepiped is *(1-
ε)^n*. This problem naturally arises in the construction of
lattice based one-way functions with worst-case/average-case
connection.