We show that private shared reference frames can be used to perform private quantum and private classical communication over a public quantum channel. Such frames constitute a novel type of private shared correlation (distinct from private classical keys or shared entanglement) useful for cryptography. We present optimally efficient schemes for private quantum and classical communication given a finite number of qubits transmitted over an insecure channel and given a private shared Cartesian frame and/or a private shared reference ordering of the qubits. We show that in this context, it is useful to introduce the concept of a decoherence-full subsystem, wherein every state is mapped to the completely mixed state under the action of the decoherence. ; Comment: 13 pages, published version