The Johnson-Lindenstrauss lemma states that $n$ points in a high dimensional Hilbert space can be embedded with small distortion of the distances into an $O(\log n)$ dimensional space by applying a random linear transformation. We show that similar properties hold for certain random linear transformations over the Hamming cube. We use these transformations to solve several proximity problems in the cube as well as in geometric settings. In particular, we discuss the problem of preprocessing a dataset of $n$ points so as to allow quick search for an approximate match to a query point. We also discuss approximation algorithms for some NP-hard clustering problems.