云计算实现了人们长期以来把计算作为一种资源的梦想,它给人们带来了诸多便利,比如按需自助服务,无处不在的网络访问,快速资源伸缩,计量付费及外包计算等。其中,云计算最显著的优势就是外包模式。也就是说,资源受限的用户可以将昂贵的计算任务外包给云服务器,并通过按需付费的方式享受云计算无尽的计算和存储服务。作为外包计算的一个重要分支,数据库外包允许数据拥有者委托其数据库管理权给云服务器并由云服务器来向数据库用户提供各种数据库服务,已经引起了学术界的持续关注。然而,外包数据库在为人们带来诸多益处的同时,也不可避免地面临着一些新的安全挑战。首先,由于云服务器是不完全可信的,数据外包之前需要进行加密操作,这就使得如何完成数据高效检索变得困难。其次,出于自身利益的驱动或者受软硬件运行故障等因素影响,云服务器可能会诚实地执行部分检索操作并返回给用户不正确/不完整的检索结果。因此,外包数据库的安全审计问题成为我们面临的又一挑战问题。在本文中,我们主要围绕安全数据外包中的关键问题展开研究。主要包括：(1)如何实现外包数据库的可验证检索；(2)如何实现高维加密数据的近似最近邻检索；(3)如何实现安全数据去重中的恶意用户身份追踪。具体来说,本文主要贡献可总结为以下几个方面：1.我们首次解决了外包数据库场景中云服务器返回空集时检索结果的验证问题。通过引入一个新的密码学原语-布隆过滤器树,我们提出了一种新的可验证外包数据库审计方案。即使在云服务器有意返回空集作为检索结果时,该方案仍然能够同时保证检索结果的正确性和完整性。和现有的工作相比,所提出的方案能够确保数据的机密性,适用于加密数据库场景。(第三章)2.我们进一步研究了外包数据库可验证检索问题。利用可翻转布隆过滤器(Invertible Bloom Filter),我们提出了一种灵活的可验证外包数据库检索方案。该方案能够同时达到检索结果可验证性和支持高效的数据更新操作。也就是说,当新的数据记录插入时,当前数据记录无需做任何改变操作。这一特性使得其适用于动态外包数据库场景中。此外,借助于多用户可搜索加密技术,我们将该方案扩展到了多用户场景。由于索引中分别为数据拥有者和其他授权用户存储不同的可搜索内容,该方案能够有效抵抗云服务器和恶意用户勾结攻击。(第四章)3.我们研究了外包数据库近似最近邻检索问题。通过利用局部敏感哈希和保序加密相结合的方法,我们提出了一种新的高维密文数据最近邻检索方案。该方案能够同时实现高效的近似最近邻检索和数据机密性。此外,我们提出的方案能够支持高效的密文范围查找。(第五章)4.我们研究了安全数据去重中的恶意用户身份追踪问题。我们首次将用户身份追踪性引入到安全数据去重中。当发生副本伪造攻击(Duplicate Faking Attack)时,该方法能够追踪恶意用户的身份。进一步地,我们构造了一个具体的支持恶意用户身份追踪的去重方案-TrDupo具体来说,每个用户上传文件时伴随着一种基于可追踪签名技术的匿名签名。一旦发生副本伪造攻击,追踪代理者(Tracing Agent)能够揭露恶意用户的身份信息同时不会泄露其他用户的身份信息或指向文件的链接信息。(第六章)