Location-based service (LBS) gives an ever increasing number of convenience to people. However, it brings opportunities to leak clients’ privacy. The greater part of the existing privacy-preserving LBS plans depend on traditional hardness issues, for example, the integer factorization or the discrete logarithm problems. However, with the advancement of a quantum calculation, these traditional hardness issues can be effectively solved by Shor’s calculations, consequently, the security of these LBS plans are threatened. In this project, we propose a privacy-preserving LBS scheme against quantum attacks in view of LWE-based key-homomorphic pseudorandom functions ((PRF). In our plan, because of the key-homomorphic property of the PRF, LBS clients only need to process one PRF estimation of the objective area and the target calculation is outsourced to a cloud server. Moreover, by isolating the key encoding LBS information into two sections and relegating the two sections to the cloud separate and every client individually, our plan maintains a strategic distance from the dangers of key manhandle and data spilling. Also, we utilize this PRF to understand a verified convention, which ensures the interchanges between the LBS clients and the cloud server. Since the security of our plan is constructed just in light of the security of the LWE-based key-homomorphic PRF, our plan is the first secure LBS scheme resisting quantum attacks.