Phase-contrast X-ray imaging can improve the visibility of weakly absorbing objects (e.g. soft tissues) by an order of magnitude or more compared to conventional radiographs. Combining phase retrieval with computed tomography (CT) can increase the signal-to-noise ratio (SNR) by up to two orders of magnitude over conventional CT at the same radiation dose, without loss of image quality. Our experiments reveal that as the radiation dose decreases, the relative improvement in SNR increases. We show that this enhancement can be traded for a reduction in dose greater than the square of the gain in SNR. Upon reducing the dose 300 fold, the phase-retrieved SNR was still up to 9.6 ± 0.2 times larger than the absorption contrast data with spatial resolution in the tens of microns. We show that this theoretically reveals the potential for dose reduction factors in the tens of thousands without loss in image quality, which would have a profound impact on medical and industrial imaging applications.