In patients bearing metallic implants, CT images reconstructed by the filtered back-projection algorithm usually suffer substantially from streaking metal artifacts. The CT-based attenuation correction of PET using such images can lead to pseudo-uptakes and thus equivocal findings. In this paper, we introduce a new metal artifact reduction (MAR) algorithm based on Bayesian iterative restoration techniques applied in the sinogram space. We proposed a Sobolev prior in the maximum a posteriori (MAP) estimation of the projections corrupted by metallic implants. The Sobolev prior was invoked in order to impose the a priori knowledge that a CT sinogram is a smooth dataset in which it is highly probable that neighboring projections have similar photon counts. We compared the proposed prior with a total variation (TV) one which imposes piece-wise smoothness on the sinograms being restored. We also compared it with a smoothed TV (TVs) prior which ranks between the Sobolev and TV ones. We formulated the MAP estimation as a convex constrained optimization problem and solved it for the Sobolev and TVs priors by a projected gradient descent algorithm and for the TV/s priors by a sophisticated primal-dual projected gradient algorithm. The results of artifact simulations in a real CT image showed that the Sobolev-based MAR algorithm outperforms its TV and TVs-based counterparts in terms of convergence rate and is comparable with the TVs in projection recovery. It was demonstrated that the proposed MAR algorithm has high applicability in fast and efficient CT-based attenuation correction of PET data.