This is not a direct answer, but a closely related problem is known to be NP-hard:
Das, Goodrich. "On the Complexity of Approximating and Illuminating Three-Dimensional Convex Polyhedra." 1995. (ACM link; PDF download)
This paper establishes several results, including this:
Theorem 4.2. The problem of fitting a polyhedron with a minimum number of faces between two given nested convex polyhedra is NP-hard.
This question was first posed by Victor Klee, and I coauthored a paper that provided an efficient algorithm in $\mathbb{R}^2$. But the above result shows it is already intractable in $\mathbb{R}^3$. I do not remember the Das-Goodrich proof well enough to know if it can achieve the same result with the outer polyhedron a cube.
There are many approximation algorithms available, as this is an important practical problem. For example:
Mitchell, Suri. "Separation and approximation of polyhedral surfaces." In Proc. 3rd ACM-SIAM Sympos. Discrete Algorithms, pages 296-306, 1992. (CiteSeer link)