A method and an apparatus for authenticating location-based services without compromising location privacy, which comprises a comprehensive solution that preserves unconditional location privacy when authenticating either range queries using three authentication schemes for R-tree and grid-file index, together with two optimization techniques, or k-nearest neighbor queries using two authentication schemes for R-tree and Voronoi Diagram index.