Photons propagating in curved spacetime may, depending on their direction and polarisation, have velocities exceeding the ``speed of light'' c. This phenomenon arises through vacuum polarisation in QED and is a tidal gravitational effect depending on the local curvature. It implies that the Principle of Equivalence does not hold for interacting quantum field theories in curved spacetime and reflects a quantum violation of local Lorentz invariance. These results are illustrated for the propagation of photons in the Reissner-Nordstr\"om spacetime characterising a charged black hole. A general analysis of electromagnetic as well as gravitational birefringence is presented.