Large nonlinearity at the single-photon level can pave the way for the implementation of universal quantum gates. However, realizing large and noiseless nonlinearity at such low light levels has been a great challenge for scientists in the past decade. We present a proposal for using quantum memory to enhance the cross-phase modulation (XPM) of two optical fields. Our memory, which is based on the gradient echo memory (GEM) scheme, maps the optical fields into Fourier transformed polaritonic excitations in an atomic ensemble. We show that nonlinear interactions can be induced in GEM. Due to the slowing down and subsequent storage of light fields within a memory, nonlinear interaction time between the fields can be extended resulting in an enhancement of the effective nonlinearity. We present results showing noiseless cross-phase modulations and discuss plans to further increase the cross-phase modulation strength to a level useful for implementing quantum gates.