  The construction of a perfectly secure private quantum channel in dimension d
is known to require 2 log d shared random key bits between the sender and
receiver. We show that if only near-perfect security is required, the size of
the key can be reduced by a factor of two. More specifically, we show that
there exists a set of roughly d log d unitary operators whose average effect on
every input pure state is almost perfectly randomizing, as compared to the d^2
operators required to randomize perfectly. Aside from the private quantum
channel, variations of this construction can be applied to many other tasks in
quantum information processing. We show, for instance, that it can be used to
construct LOCC data hiding schemes for bits and qubits that are much more
efficient than any others known, allowing roughly log d qubits to be hidden in
2 log d qubits. The method can also be used to exhibit the existence of quantum
states with locked classical correlations, an arbitrarily large amplification
of the correlation being accomplished by sending a negligibly small classical
key. Our construction also provides the basic building block for a method of
remotely preparing arbitrary d-dimensional pure quantum states using
approximately log d bits of communication and log d ebits of entanglement.
