In this paper, we present a novel framework for privacy-preserving anomaly-based data falsification attack detection in a smart grid advanced metering infrastructure (AMI). Specifically, we propose an anomaly detection framework over homomorphically encrypted data. Unlike existing privacy-preserving anomaly detectors, our framework detects the presence of not only energy theft (i.e., deductive attack), but also more advanced data integrity attacks (i.e., additive and camouflage attacks) over encrypted data without diminishing detection sensitivity. We optimize the anomaly detection procedure such that potentially expensive operations over homomorphically encrypted space are avoided. Moreover, we optimize the encryption method designed for a resource constrained device such as smart meters, and the time to complete encryption gets 40x faster over the naïve adoption of the encryption method. We also validate the proposed framework using a real dataset from smart metering infrastructures, and demonstrate that the data integrity attacks can be detected with high sensitivity, without sacrificing user privacy. Experimental results with a real dataset of 200 houses from an AMI in Texas showed that the detection sensitivity of the plaintext algorithm is not degraded due to the use of homomorphic encryption.