实用的私有信息检索及其应用研究

摘要

现如今，网络通信的快速发展和电子商务活动的蓬勃兴起，各种网络设施也与之进步。数据库，作为信息的存储系统，是IT设施的基石之一，为用户提供了数据存储和共享服务。为了获得最新的信息，数据库是必不可少的访问资源。然而，用户从数据库或网络服务中查询的内容往往是非常敏感的，例如专利数据库，医药数据库，股票报价等等，这些查询内容随时随地都有可能将用户的私有信息或兴趣爱好等隐私暴露给数据库提供商。因此，在用户查询数据库的过程中保护用户的查询隐私至关重要。私有信息检索(Private Information Retrieval，PIR)就是用户在检索数据库记录时，向数据库服务器方隐藏查询记录的身份信息，从而保护用户的查询隐私不被泄露。私有信息检索由Chor于1995年首次提出概念和模型，并于1998年给出规范化定义：数据库拥有n比特字符串d1d2…dn，其中i∈{1，2…，n}为数据项索引。用户向数据库发出请求q(i)，要求查询第i个数据项di，数据库服务器在不知道i的任何信息的情况下将di发送给用户。此后，私有信息检索问题吸引了大量研究者的关注。一个有效的私有信息检索主要由用户检索出一条记录时的通信复杂度和计算开销来衡量。私有信息检索不仅可以保护用户的查询隐私，还可以应用于公钥加密系统查询、匿名认证，PIR-Writing等各种场合中。
　　 保护用户的查询隐私是非常重要，但是随着云存储服务的流行，越来越多的用户喜欢将他们的加密信息存储在云数据库中。当用户需要更新数据库数据时，保护用户的更新隐私不被泄露于数据库服务器也是必要的。PIR-Wring就是用户在更新数据库的记录时，保护更新记录的索引及更新的内容不会泄露给数据库服务器。PIR-Writing是私有信息检索中一个重要的分支。2007年，Boneth，D等人首次提出一个有效的PIR-Writing方案。PIR-Writing的数学模型如下：私有数据f={f1，f2，…fn}被(用户)加密后存储在数据库上，其中i∈{1，2…，n}为数据项索引，每条记录为ιbits。用户将第i(1≤i≤n)条记录fi更新为y，而数据库服务器不知道“i”的信息，也不知道更新的内容y。
　　 由于对私有信息检索逐渐深入地研究，根据安全模型，可将已存在的PIR方案大致划分为三类：信息论PIR(Information Theoretical Private Information Retrieval，IPIR)；计算安全的PIR(Computational Private Information Retrieval，CPIR；基于安全硬件的PIR(Hardware-based PIR，HW-PIR)。但是，当前已存在的PIR协议由于较高的通信复杂度和计算复杂度(与数据库的大小n相关)大多数都只具有理论意义，不适合用于实际的应用环境或大型数据库中。在半诚实模型下，从实用性和安全性角度出发，本文主要进行了如下研究工作：
　　 1.基于安全处理器(Secure Coprocessor，SC)，结合CPIR中计算难题的安全性，提出一个新的加密数据库的HW-PIR协议。通过比特流置换和代理重加密思想，保证了HW-PIR在线查询的最高效率O(1)，同时降低安全处理器SC预处理阶段的计算量。该方案使用户的查询隐私不会泄露给数据库服务器，还防止用户查询内容与数据库的隐私泄露给SC和恶意攻击者，安全性更强。特别地，方案中SC可以负载其它宿主，减轻查询服务器的负载，对被频繁查询的数据库来说，具有实用价值。
　　 2.对PIR-Writing深入研究。目前PIR-Writing的通信复杂度(O(klogn+kι))和计算复杂度(O(nlogn+ιn))还比较高，并且大部分适用于单个用户的数据库更新情形，例如快盘，Hotmail邮箱服务等。本文借鉴HW-PIR模型，提出一个新的PIR-Writing方案，保持了目前最优的通信复杂度O(logn)，降低在线更新阶段的计算复杂度为O(nlogn+ιn)至O(1)。因此，减少数据库更新响应时间，具有实用价值。特别是，该方案不仅适用于单用户的数据库更新，还支持多个用户共享数据库信息的应用。