We compute the electrical conductivity of the strongly interacting medium in the presence of strong magnetic background fields, eB=4, 9  GeV2, and for different values of the temperature, both in the confined and in the deconfined quark-gluon plasma (QGP) phase. The conductivity is obtained from the Euclidean lattice time correlator of the electrical current, computed on gauge configurations sampled from Monte-Carlo simulations of an improved staggered discretization of Nf=2+1 QCD. We perform the inverse Laplace transform of the correlator adopting a recently proposed version of the standard Backus-Gilbert procedure for the inversion. The results obtained in the QGP phase show a sizable enhancement of the conductivity in the direction parallel to the magnetic field, as well as a suppression in the direction orthogonal to it. The enhancement can interpreted through various different mechanisms, typically involving the chiral anomaly, among which the chiral magnetic effect (CME): for this reason we try to interpret our observations based on a CME-inspired , we extract the relaxation time of this process, extrapolate it to the continuum limit and compare it to previous results, finding it lower than expected in the explored range of temperatures.