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.