云计算是继分布式计算、对等计算、网格计算之后出现的一种崭新的计算模式。其核心思想是资源租用、应用托管和服务外包。云具有很高的灵活性和可扩展性,其应用已经愈来愈普及。最近邻查询是数据库中的基础查询之一,在很多领域都有着广阔的应用前景,比如模式识别、机器学习、统计分类等领域。海明距离查询在许多领域都有广泛的应用,比如相似性检测、模式识别、病毒探测、DNA序列和蛋白质分析、错误纠正、文本分类等等。随着云计算和大数据时代的到来,把大规模的数据库外包给云服务器成了趋势,但是云是不完全可信的,其中存在很多潜在的威胁。为了保证数据的安全,用户往往是将数据加密后再存储到云服务器上。如何高效地实现在密文数据上进行最近邻检索和海明距离检索成了迫切需要解决的问题。本论文针对这两个问题分别提出了相应的安全检索协议,具体工作如下:本文首先提出了一种可以用于一维空间和二维空间的的安全最近邻查询方案。该方案的主要思想是把安全最近邻查询问题转化成为判断一个点是否在一个范围内的问题,进而转化成为判断两个集合是否相交的问题,从而可以在安全隐私的状态下进行判断两个集合是否相交的计算。为了达到亚线性级的查询时间,本文提出了一种空间划分方案和范围树的树形数据结构,为了达到可自适应的IND-CPA安全级别,本文提出了多窝布鲁姆过滤器和单窝布鲁姆过滤器,分别用于构建索引和陷门。分析和实验结果验证了所提出方案的有效性。其次,本文提出了一种隐私保护的海明距离查询方案。该方案首先生成一个可逆的随机矩阵,并运用该矩阵对数据进行转换,然后通过前缀编码对数据进行编码,并运用安全数据结构IBF进行存储和安全索引IBTree来构建索引。在安全性方面,可以满足自适应的IND-CKA安全,在查询时间方面,达到了亚线性级的查询时间。分析和实验结果验证了所提出方案的有效性。最后,本文对已完成的研究工作进行了总结,并对下一步的工作进行了展望。