  The combination of electromagnetically induced transparency (EIT) with the
nonlinear interaction between Rydberg atoms provides an effective interaction
between photons. In this paper, we investigate the storage of optical pulses as
collective Rydberg atomic excitations in a cold atomic ensemble. By measuring
the dynamics of the stored Rydberg polaritons, we experimentally demonstrate
that storing a probe pulse as Rydberg polaritons strongly enhances the Rydberg
mediated interaction compared to the slow propagation case. We show that the
process is characterized by two time scales. At short storage times, we observe
a strong enhancement of the interaction due to the reduction of the Rydberg
polariton group velocity down to zero. For longer storage times, we observe a
further, weaker enhancement dominated by Rydberg induced dephasing of the
multiparticle components of the state. In this regime, we observe a non-linear
dependence of the Rydberg polariton coherence time with the input photon
number. Our results have direct consequences in Rydberg quantum optics and
enable the test of new theories of strongly interacting Rydberg systems.
