A Note on the Minimal Volume of Almost Cubic Parallelepipeds

   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 to a point within distance ɛ < from is to shorten all edges by a factor (1-ɛ) . In particular, the minimal volume of such an almost cubic parallelepiped is (1-ɛ) ⁿ . This problem naturally arises in the construction of lattice-based one-way functions with worst-case/ average-case connection.