Measurements of the birefringence of a single atom strongly coupled to a high-finesse optical resonator are reported, with nonlinear phase shifts observed for intracavity photon number much less than one. A proposal to utilize the measured conditional phase shifts for implementing quantum logic via a quantum-phase gate (QPG) is considered. Within the context of a simple model for the field transformation, the parameters of the "truth table" for the QPG are determined.