随着移动互联网的迅速发展,在很多方面已经替代了传统互联网,基于位置的服务LBS(Location Based Service)得到了广泛的应用,是当前移动互联网下的主流服务之一。人们可以根据自己的需求方便高效的获得位置服务,例如定位导航、旅行线路制定、兴趣点搜索和陌生人社交等方面。然而,事物都有双面性,基于位置的服务给人们带来便利的同时,也对用户的隐私带来潜在的威胁。因为在使用位置服务时用户需要上传自己的位置信息,服务器根据用户的位置信息才能够提供相应的服务,如果对用户的位置信息没有进行很好的保护,一旦攻击者获取到了用户的位置信息,很多其他的敏感信息也可能会一并暴露,例如家庭住址、工作单位、健康状况以及消费习惯等等。出于上述考虑,本文针对位置服务中的k最近邻查询问题,提出了相关的位置隐私保护方案。k最近邻查询是指用户搜索附近距离最近的k个感兴趣的兴趣点的相关信息,对于如何更好地衡量位置服务与隐私度的矛盾,即能保证用户位置隐私的同时不降低服务质量进行了研究,主要内容如下:首先,提出了一种基于匿名空间的k最近邻查询的位置隐私保护方法。我们使用虚拟空间映射曲线和Voronoi图,提出了基于用户和兴趣点的伪位置进行k个最近兴趣点查询的方案。我们的方案主要解决了使用希尔伯特曲线对空间划分仍然存在被攻击者成功攻击的问题,通过可以选择不同的空间映射曲线,以及映射曲线单元格中特征值的随机性,使得恶意攻击者即使获取到了相关的背景知识,仍然有很大难度成功攻击。其次,提出了一种基于加密法的k最近邻查询的位置隐私保护方法。我们通过引入第三方云服务器,借助其强大的存储能力和计算能力,将位置服务器的数据和用户的位置数据经过加密后上传至第三方进行处理计算。我们的方案主要改进了现有的方案中的安全k最近邻搜索算法,使得能够抵御更高级别的恶意攻击者的攻击,即使攻击者掌握了较多的相关背景知识,成功破解密文仍然存在较大的难度。