随着无线通信和具有定位能力的移动设备的快速发展,基于位置的服务(Location-Based Service,LBS)已经广泛用于几乎所有社交和商业领域。为了享受位置服务,用户需要将准确的位置和查询内容发送给LBS提供商。然而,通过收集和分析这些位置和查询内容,不可信的LBS提供商可以推断出用户的许多敏感信息,例如行踪、健康状况和兴趣爱好等。出于隐私和效率考虑,现有研究工作还存在下面几个主要缺陷。其一是没有同时保护位置和内容隐私;其二是对于范围查询,存在查询效率不高的问题。此外,面对LBS数据的频繁更新,现有研究工作不能支持索引更新操作。因此,如何在LBS中设计一个安全高效的隐私保护范围查询协议仍然是一个具有挑战性的问题。本文围绕基于位置服务下的隐私保护、查询效率和索引更新展开研究,主要工作包括以下两个方面:1)针对隐私保护和查询效率,提出了一种基于布鲁姆过滤器(bloom filter)的安全高效的隐私保护范围查询协议,该协议满足以下三个要求:同时保护位置隐私和内容隐私、查询效率和可伸缩索引大小。为了实现位置隐私和内容隐私,采用前缀成员验证方法对索引元素进行编码,并使用布鲁姆过滤器存储编码后的索引元素。为了实现查询效率和可伸缩索引大小,提出了一种称为DBtree的动态平衡二叉树结构。此外,为了提高查询效率,提出了索引元素编码优化和遍历优化两个算法。最后,在模拟和真实的数据集上进行大量的性能评估。实验结果验证了所提方案的安全性和高效性。2)为了解决查询效率和索引更新问题,设计了一种基于布谷鸟过滤器(Cuckoo filter)的安全高效的隐私保护范围查询方案。为了保护隐私和查询高效,提出了一个动态的平衡二叉树结构,即DCtree,其中每个节点使用一个布谷鸟过滤器存储索引元素。DCtree能够在保护查询隐私和LBS数据隐私的同时,进行高效的查询处理。为了提高查询效率,提出一种DCtree查询优化方案。为了支持DCtree的更新,提出了DCtree索引更新算法,能够动态处理数据项的插入、删除和修改操作。最后,在真实和模拟数据集上进行了大量实验,以评估DCtree方案的性能。实验结果表明DCtree方案在索引大小和查询效率方面比DBtree方案更加高效。