Quantum cryptography enables one to verify that the state of the quantum system has not been tampered with and thus one can obtain privacy regardless of the power of the eavesdropper. All previous protocols relied on the ability to faithfully send quantum states or equivalently to share pure entanglement. Here we show this need not be the case-one can obtain verifiable privacy even through some channels which cannot be used to reliably send quantum states.