随着蜂窝网络、GPS等技术的普及,人们可以快速方便地使用手持设备向服务提供商请求基于位置的服务。这大大方便了人们的生活,但也带来了很多隐私泄露问题。如何在不影响用户快捷方便的使用服务的同时,仍能很好的避免用户的敏感信息暴露给不可信的服务提供商或者其它攻击者仍是极具现实意义的课题。目前已经提出了许多方案,但是仍没有一个方案可以同时兼顾隐私保护强度和查询效率。本课题使用加密的方法保护用户隐私,同时使用分布式的存储减低系统开销,并使用同态加密与树结构解决最近邻查询难问题。本文第三章利用分布式存储和二次剩余假设,提出了一种既具有安全性又具有有效性的基于位置的服务中用户隐私保护方案。虽然传统的PIR(private information retrieval)方法会给服务器端带来较高的通信成本和计算压力,但是其具有不需要可信第三方和隐私保护强度高的优点。而近些年出现的分布式存储系统架构可以大大减少网络开销,并降低服务器识别用户实际位置的风险。本文通过构建索引表帮助中间存储设备正确响应用户加密请求,将PIR方法成功应用于分布式存储系统中,设计了一种面向分布式存储的用户隐私保护方案。通过分析和实验验证,该方案能够有效地减少用户通信开销和网络负载。本文第四章研究基于密码学的近邻查询难问题,提出了适用于所设计的面向分布式存储的用户隐私保护方案的k近邻查询策略。所设计的策略没有使用传统的希尔伯特曲线存储地图中兴趣点的信息,而是利用Z-order曲线与四叉树结构相结合来存储目标地图的位置信息,这样做不仅使其支持分布式存储并且提高了定位的效率。同时,使用支持加法和乘法的同态加密方法保密用户位置信息,借助中间存储设备在位置密文上计算距离,节约用户开销。通过实验和结果分析,虽然策略增加了中间存储设备的计算开销,但是其能保证查询准确率且用户加密解密开销低。