A note on the minimal volume of almost cubic parallelepipeds

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.