Method and apparatus for authenticating location-based services without compromising location privacy
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.
1. A computer processor implemented method for a privacy-preserving query authentication comprising:
a comprehensive solution executed by one or more processors;
wherein the comprehensive solution preserves unconditional location privacy when authenticating queries by a client by including in a verification object one or more digests computed collaboratively by the client and a server such that the client cannot infer any information about locations of returned users beyond what is implied from results of the queries;
wherein the privacy-preserving query authentication comprising a complete set of authentication schemes for a tree based index, a grid-file based index, and a Voronoi Diagram based index;
wherein the privacy-preserving query authentication comprising authentication schemes including one or more of an Algorithm 1-based scheme, a tree based scheme, a grid-file based scheme, and an accumulative digest for grid-file based scheme; and
wherein the authentication schemes are for large queries, small queries, and queries on static datasets.
2. The method according to claim 1 wherein the queries comprising range queries and k-nearest neighbor queries; and wherein the unconditional location privacy is preserved for range queries and k-nearest neighbor queries without a pre-determined limit of the range queries or k-nearest neighbor queries.
3. The method according to claim 1 wherein the privacy-preserving query authentication is for location-based services.
4. The method according to claim 3 wherein the location-based services comprising mobile value-added services and spatial database services.
5. The method according to claim 1 wherein the privacy-preserving query authentication comprising a privacy-preserving kNN query authentication for location-based services.
6. The method according to claim 1 wherein the privacy-preserving query authentication comprising optimization techniques.
7. The method according to claim 6 wherein the optimization techniques are orthogonal to the privacy-preserving query authentication.
8. The method according to claim 6 wherein the optimization techniques comprising an x-ordering technique, and a Hilbert embedding technique.
9. The method according to claim 1 wherein the privacy-preserving query authentication comprising cryptographic constructs that can prove to the client a distance relation from at least two private location points to at least one public point.
10. The method according to claim 9 wherein the cryptographic constructs comprising a Paillier-Points based method and a pre-signed line based method.
11. The method according to claim 10 wherein the privacy-preserving query authentication comprising strategies for both a data owner; and a service provider to optimize the pre-signed line based method.
12. The method according to claim 1 wherein the comprehensive solution is implemented in at least one computer processor based system.
13. The method according to claim 1 wherein the comprehensive solution is implemented across a network of computer processor based system.
14. A computer processor based apparatus for a privacy-preserving query authentication comprising:
a comprehensive solution executed by a computing device having one or more computer processor;
wherein the comprehensive solution preserves unconditional location privacy when authenticating queries by a client by including in a verification object one or more digests computed collaboratively by the client and a server such that the client cannot infer any information about locations of returned users beyond what is implied from results of the queries; and
wherein the queries comprising range queries and k-nearest neighbor queries
wherein the privacy-preserving query authentication comprising a complete set of authentication schemes for a tree based index, a grid-file based index, and a Voronoi Diagram based index;
wherein the privacy-preserving query authentication comprising authentication schemes including one or more of an Algorithm 1-based scheme, a tree based scheme, a grid-file based scheme, and an accumulative digest for grid-file based scheme; and
wherein the authentication schemes are for lame queries, small queries, and queries on static datasets.
15. The apparatus according to claim 14 wherein the privacy-preserving query authentication is for location-based services; and wherein the location-based services further comprising mobile value-added services and spatial database services.
16. The apparatus according to claim 14 wherein the privacy-preserving query authentication comprising a privacy-preserving kNN query authentication for location-based service.
17. The apparatus according to claim 14 wherein the privacy-preserving query authentication comprising optimization techniques that are orthogonal to the privacy-preserving query authentication; and cryptographic constructs that can prove to the client a distance relation from at least two private location points to at least one public point.