Hiding classical data in multi-partite quantum states

We present a general technique for hiding a classical bit in multipartite quantum states. The hidden bit, encoded in the choice of one of two possible density operators, cannot be recovered by local operations and classical communication without quantum communication. The scheme remains secure if quantum communication is allowed between certain partners, and can be designed for any choice of quantum communication patterns to be secure, but to allow near perfect recovery for all other patterns. The maximal probability of unwanted recovery of the hidden bit, as well as the maximal error for allowed recovery operations can be chosen to be arbitrarily small, given sufficiently high dimensional systems at each site. No entanglement is needed since the hiding states can be chosen to be separable. A single ebit of prior entanglement is not sufficient to break the scheme.