（计算机软件与理论专业论文）隐蔽检索相关技术的研究.pdf

摘要 摘要 随着信息技术的发展，网络已经成为人们生活中必不可少的一部分， 信息检索技术和电子商务被不同层次的人应用到生活中。但是在信息检索 中，用户所关心的内容对服务器是公开的，好奇的数据库管理员可以根据 用户的查询来获知用户今后要做的事情，对用户的隐私造成了极大的威胁。 因此人们迫切需要一种新的检索方式来解决检索中的这种弊端。为了保护 用户的查询隐私，人们提出隐蔽检索的方法。 本文首先对隐蔽检索技术和方法出现的背景、基本内容、特点作了简 单介绍，详细阐述了隐蔽检索的概念，并且对一些以往的隐蔽检索方法进 行了研究，总结出每种隐蔽检索方法的缺点。在此基础上提出一种新的隐 蔽检索方法，即极少必要信息共享的隐蔽检索技术，它是一种对称式的隐 蔽检索方法，不仅对用户的信息进行保密，而且对服务器的信息也进行了 有效的保密，从而达到安全查询的目的。 新的隐蔽检索方法利用了可交换的加密函数，这种函数对数据库中的 数据和用户查询的数据进行双重加密，通过加密后的密文匹配来找出用户 所需的记录。本文根据三次传输协议和m e n t a lp o k e r 算法等理论提出了交 集算法、等值连接算法、交集大小算法、等值连接大小算法、差算法、差 连接算法以及差大小算法，并且对这些算法的正确性和安全性进行了有效 的证明。 关键字隐蔽检索；可交换加密；三次传输协议：d i f f i e h e l l m a n 函数；h a s h 函数 燕山大学工学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , i n t e m e th a sb e c o m e m o r ea n dm o r ei n d i s p e n s a b l ei no u rl i f e ，a n dv a r i o u sp e o p l eu s ei n f o r m a t i o n r e t r i e v a la n de l e c t r o n i cc o m m e r c e b u ti ni n f o r m a t i o nr e t r i e v a l ，t h eu s e rp r e f e r - e n c e sw e r eo p e nf o rt h es e r v e r a n dt h ec u r i o u sd a t a b a s eo p e r a t o rc a l lf o l l o w t h eu s e r sq u e r i e sa n di n f e rw h a tt h eu s e ri sa f t e r , t h a tw i l lt h r e a t e nt h ep r i v a c y o f t h eu s e r a sar e s u l t ，an e w t y p eo f r e t r i e v a li su r g e n t l yr e q u i r e dt os o l v et h i s d e f e c t i no r d e rt op r e t e c tt h ep r i c a c yo ft h eu s e r , p e o p l ef o r m u l a tt h ep i r m e t h o d f i r s t l y , t h i sp a p e rs i m p l yi n t r o d u c e st h eb a c k g r o u n do ft h ep i rp r o b l e m ， t h ee l e m e n t a r yc o n t e n ta n dt h ec h a r a c t e r i s t i co ft h ep i rp r o b l e m ，e x p l a i nt h e c o n c e p t i o no ft h ep i rp r o b l e m ，a n dr e s e a r c ht h ep r e s e n tt e c h n o l o g i e s ，s u ml l p t h ed i s a d v a n t a g eo f t h ep r e s e n tt e c h n o l o g i e s o nt h i sc o n d i t i o n ，w ep u tf o r w a r d an e wp i rs o l u t i o nt h a ti st h em i n i m a ln e c e s s a r yi n f o r m a t i o ns h a r i n g ，i ti sa s y m m e t r i c a lp i rs o l u t i o nt h a tc a np r o t e c tn o to n l yt h ei n f o r m a t i o no f t h eu s e r s b u ta l s os e r v e r s ，s ot h eu s e r sc a nr e t r i e v a li n f o r m a t i o ni ns e c u r i t y t h en e wp i rs o l u t i o nu s e st h ec o m m u t a t i v ee n c r y p t i o nf u n c t i o nt oe n c r - y p tt h ed a t ao ft h ed a t a b a s ea n dt h ed a t ao ft h eu s e r a n dt h e nt h er e c o r dt h a t t h eu s e rn e e di sf o u n du s i n gt h em a t c ho f t h ec r y p t o g r a p h b a s e do nt h et h e o r y o ft h r e e - t i m et r a n s f e rp r o t o c o la n dm e n t a lp o k e ra l g o r i t h m ，t h i sp a p e rp u t f o r w a r dt h ea l g o r i t h m so fi n t e r s e c t i o n , e q n i j o i n ，i n t e r s e c t i o ns i z e ，e q u i j i o ns i z e i f f e r e n c e ，d i f f e r e n c ej o i na n dd i f f e r e n c es i z e a n dp r o v et h ec o r r e c t n e s sa n dt h e s e c u r i t y k e y w o r d sp r i v a t ei n f o r m a t i o nr e t r i e v a l ；c o m m u t a t i v ee n c r y p t i o n ；t h r e e - t i m e t r a n s f e rp r o t o c o l ；d i f f i e - h e l l m a nf u n c t i o n ；h a s hf u n c t i o n i i 第1 章绪论 1 1 研究背景 第1 章绪论 由于计算机与通信技术的发展，使得信息的存取，传播及使用变得十 分普及，并且在日常生活中占有重要的地位。 1 1 1 信息检索的发展 信息检索( i n f o r m a t i o nr e t r i e v a l ) ，是计算机科学与信息科学相交叉的 - - 1 3 实验与应用的学科。广义的信息检索包括文件检索、数据检索和事实 检索，狭义的信息检索是指在计算机中执行的文件检索。信息检索包括存 储数据的包括与解释( 如数据的收集与整理，存储位置的选择与利用，存储 与搜索例程，机械化准备，索引法等) 、数据编录、分类归栏、信息内容分 析、按用户要求查找、向用户提供与分发，以及涉及计算机活动一整套计 算机技术与信息工作。信息检索的核心是信息内容分析、信息存储与检索 结构和信息检索评估这三个理论与技术问题。信息检索流程分四个步骤： 信息分析与加工、信息存储、信息检索、信息提供与发展。具体来说，信 息检索指可以有选择的安置存储数据，以便改变或复查字处理机的操作或 设施。 信息检索系统能从大量的数据中查找并且取出用户所需的信息。信息 检索系统一般由硬件、软件、各种数据库、系统管理者和信息吸收源r 用户) 等五个要素构成。它采用数据处理技术，致力于信息的产生、收集、评估、 存储、检索和分发的有机整体。 在信息检索过程中，处理文件数据库的技术有：混合法、倒排文件法 及顺序法等，对于不同的文件数据库可以采用不同的检索法。检索基本过 程是以系统规定的基本形式所表示的提问标志与存取与文件库中各种信息 标志进行比较处理，由检索程序自动完成，它涉及提问的表示与判读，文 燕山大学工学硕士学位论文 件库的查询方法，索引字之间的比较方法等。图1 1 说明了信息检索的整 个过程。 文档模型 图1 - 1 检索信息的过程【1 f i g 1 - 1t h ep r o g e s so f r e t r i e v i n gi n f b 眦a t i o n i l 】 从历史上看，信息检索经历了手工检索、计算机检索到目前网络化、 智能化检索等多个发展阶段。 目前，信息检索已经发展到网络化和智能化的阶段。信息检索的对象 从相对封闭、稳定一致、由独立数据库集中管理的信息内容扩展到开放、 动态、更新快、分布广泛、管理松散的w e b 内容；信息检索的用户也由原 来的情报专业人员扩展到包括商务人员、管理人员、教师学生、各专业人 士等在内的普通大众，他们对信息检索从结果到方式提出了更高、更多样 化的要求，他们不但要求找到最新的信息，而且要求在查询的整个过程中 能够有效的保护自己的查询隐私。适应网络化、智能化以及个性化的需要 是目前信息检索技术发展的新趋势，同时信息检索中的用户隐私权的保护 也逐步受到重视。 1 1 2目前信息检索的热点技术 1 1 2 1 智能检索或知识检索传统的全文检索技术基于关键词匹配进行 检索，往往存在查不全、查不准、检索质量不高的现象，特别是在网络信 息时代，利用关键词匹配很难满足人们检索的要求。智能检索利用分词词 第l 章绪论 典、同义词典，同音词典改善检索效果，比如用户查询“计算机”，与“电 脑”相关的信息也能检索出来；进一步还可在知识层面或者说概念层面上 辅助查询，通过主题词典、上下位词典、相关同级词典，形成一个知识体 系或概念网络，给予用户智能知识提示，最终帮助用户获得最佳的检索效 果，比如用户可以进一步缩小查询范围至“微机”、“服务器”或扩大查询 至“信息技术”或查询相关的“电子技术”、“软件”、“计算机应用” 等范畴。另外，智能检索还包括歧义信息和检索处理，如“苹果”，究竟 是指水果还是电脑品牌，“华人”与“中华人民共和国”的区分，将通过 歧义知识描述库、全文索引、用户检索上下文分析以及用户相关性反馈等 技术结合处理，高效、准确地反馈给用户最需要的信息。然而在隐蔽检索 过程中，目前还无法做到智能的隐蔽检索。 1 1 2 2 知识挖掘 目前主要指文本挖掘技术的发展，目的是帮助人们更 好的发现、组织、表示信息，提取知识，满足信息检索的高层次需要。知 识挖掘包括摘要、分类( 聚类) 和相似性检索等方面。 1 1 2 ，3 异构信息整合检索和全息检索在信息检索分布化和网络化的趋 势下，信息检索系统的开放性和集成性要求越来越高，需要能够检索和整 合不同来源和结构的信息，这是异构信息检索技术发展的基点，包括支持 各种格式化文件，如t e x t 、h t m l 、x m l 、r t f 、m so f f i c e 、p d f 、p s 2 p s 、 m a r c 、1 s 0 2 7 0 9 等处理和检索；支持多语种信息的检索；支持结构化数 据、半结构化数据及非结构化数据的统一处理；和关系数据库检索的无缝 集成以及其它开放检索接口的集成等。所谓“全息检索”的概念就是支持 一切格式和方式的检索，从目前实践来讲，发展到异构信息整合检索的层 面，基于自然语言理解的人机交互以及多媒体信息检索整合等方面尚有待 取得迸一步突破。 1 1 2 4 隐蔽检索虽然信息检索技术已经得到了充分发展，但是用户的 隐私却始终没有考虑到信息检索过程中。用户往往因为自己的隐私没有得 到充分的保护，而给用户带来了巨大的损失。尤其是在一些关于知识产权 和商业投资的信息检索中，用户的隐私必须受到重视。因为在这些信息检 索中，如果用户所关心的内容被服务器知道，那么很有可能服务器会利用 燕山大学工学硕士学位论文 用户所感兴趣的内容，做出对用户不利的事情，例如，一个投资者想查询 某一股票市场数据库中的某个股票的数据，但是他不希望别人知道他对哪 种股票感兴趣，如果别人知道了他所感兴趣的股票，这将会给他的投资带 来不利的影响。 随着互联网的普及和电子商务的发展，企业和个人可获取、需处理的 信息量呈爆发式增长，而且其中绝大部分都是非结构化和半结构化数据。 内容管理的重要性日益凸现，而信息检的索作为内容管理核心支撑技术， 随着内容管理的发展和普及，亦将应用到各个领域，成为人们日常工作生 活的密切伙伴，然而企业和个人的隐私保护也应时刻受到关注。 1 1 3 电子商务 目前电子商务1 2 j 已逐渐成为了人们进行商务活动的新方式。电子商务 可以改善信息的流动、协调不同的活动、降低不确定性、减少交易成本、 增加利润等。总之，电子商务的好处可以惠及整个社会，越来越多的人通 过i n t e m e t 进行商务活动。 1 1 3 1 电子商务的特点电子商务作为一种全新的商务模式，与传统商 务模式相比较具有如下特点： ( 1 ) 电子商务的虚拟性电子商务就是交易双方通过互联网平台交换 信息从而达成交易的过程。电子商务的虚拟性源于其依赖的技术基础网络 的虚拟性。通过计算机互联网络进行交易，买卖双方从样品查看、交易磋 商、确认订单到支付等，无需当面进行，均通过计算机互联网络完成，购 物者和销售者没有面对面的交流，整个交易完全虚拟化，既没有现实的货 架柜台也不必展示样品实物，甚至虚拟的商店里一件实物也没有，卖方可 能要等到收到订单后再到代理商或厂家处提货，实现所谓的“零仓储”。 与此同时，为了保证网络中的商务活动能够正常进行，电子商务网站必须 实施各种安全措施，保障客户的权益不受到侵犯。 ( 2 ) 电子商务的开放性和全球性i n t e r n e t 的开放性和全球性也决定了 电子商务的开放性与全球性，交易的内容广泛，交易可能发生在任何地点、 任何时间和任何人之间。电子商务中交易双方时间和空间分离程度大大加 4 第】苹绪论 剧，匿名性、虚拟社会大量出现，由此加速了从“熟人社会”转变到“陌 生人社会”的进程。在这个过程中不仅服务器的隐私需要保护，而且顾客 的隐私也需要被保护。 1 1 3 2 电子商务中的安全服务销售者和消费者会要求电子商务提供相 应的安全保障，即电子商务必须利用安全技术为电子商务活动的参与者提 供可靠的安全服务。 ( 1 ) 鉴别服务对人或实体的身份进行鉴别，为身份的真实性提供保 证。即当某人或实体声称自己是某个特定身份时，鉴别服务可提供一种方 法来验证其声明的正确性。如数字证书可用来验证服务器身份，用户登录 时输入的i d 和密码可验证用户的身份。 ( 2 ) 访问控制服务访问控制服务通过授权来对使用资源的方式进行 控制，防止非授权行为对资源的滥用和破坏。它有助于达到机密性、完整 性、可控性和建立责任机制。 ( 3 ) 机密性服务保护电子商务参与者的信息，为其在存储、处理、传 输、使用过程中提供机密性保证，防止信息泄露给非授权的实体或个人， 造成直接或间接的经济损失。 ( 4 ) 用户的隐私保护服务一直以来，用户的隐私始终都不能得到很好 的保护。虽然用户的身份，用户的兴趣等一些隐私虽然对于服务器以外的 其他人是保密的，但是对于服务器却是公开的，对于用户的隐私的保护， 就不得不通过对服务器的信任来实现。然而服务器完全可以利用用户的隐 私信息来做一些对用户不利的事情，服务器可以把用户的隐私作为一个新 的商业项目。为了能够更好的保护用户的隐私，要求用户不仅要在他人面 前保护自己的隐私，同样也不能向服务器透露自己的隐私。 1 1 4 数据库加密技术 目前，计算机大批量数据存储的安全问题、敏感数据的防窃取和防篡 改问题越来越引起人们的重视。数据库系统被认为是计算机信息系统的核 心部件，数据库文件被认为是信息的聚集体，其安全性将是信息产业的重 中之重。 燕山大学工学硕士学位论文 大型数据库管理系统的运行平台一般是w i n d o w sn t 和u n i x ，这些操 作系统的安全级别通常为c 1 、c 2 级。它们具有用户注册、识别用户、任 意存取控铝i i ( d a c ) 、审计等安全功能。虽然d b m s 在o s 的基础上增加了 不少安全措施，例如基于权限的访问控制等，但o s 和d b m s 对数据库文 件本身仍然缺乏有效的保护措施，有经验的网上黑客会“绕道而行”，直 接利用o s 工具窃取或篡改数据库文件内容。这种隐患被称为通向d b m s 的“隐秘通道”，它所带来的危害一般数据库用户难以觉察。分析和堵塞 “隐秘通道”被认为是b 2 级的安全技术措施。对数据库中的敏感数据进 行加密处理，是堵塞这一“隐秘通道”的有效手段。 据有关资料报道，8 0 的计算机犯罪来自系统的内部。在传统的数据 库系统中，数据库管理员的权力是至高无上的，他不但负责各项系统管理 工作，例如资源分配、用户授权、系统审计等，还可以查询数据库中的一 切信息。因此，许多系统将会以种种手段来削弱系统管理员的权力。实现 数据库加密以后，各用户的数据由用户用自己的密钥加密，数据库管理员 获得的信息无法进行正常脱密，从而保证了用户信息的安全。另外，通过 加密数据库中的备份内容，使其成为密文，从而能够减少因备份介质失窃 或丢失而造成的损失。由此可见，数据库加密对于企业内部安全管理也是 不可或缺的。 人们往往认为数据库加密以后将会严重影响数据库系统的效率，使系 统不堪重负，从而影响了程序执行速度。事实并非如此，如果在数据库客 户端进行数据加，解密运算，对数据库服务器的负载及系统运行几乎没有影 响。在普通p c 机上，用纯软件实现d e s 加密算法的速度超过2 0 0 k 字节 秒，如果对一篇一万汉字的文章进行加密，其加解密时间仅需1 1 0 秒， 这种时间延迟用户几乎无感觉。目前，加密卡的加解密速度一般为1 m 位 秒，对中小型数据库系统来说，这个速度即使在服务器端进行数据的加 解密运算也是可行的，因为一般的关系数据项都不会太长( 多媒体数据另当 别论) 。例如，在同一时间里有1 0 个用户并发查询，每个用户平均查找1 0 0 0 个汉字的数据，最先得到结果的用户延迟时间小于0 0 2 秒，最后得到结果 的用户也仅需等待约0 1 6 秒。 6 第1 章绪论 1 2 研究意义 信息集成【3 ，4 j 在数据库研究领域中存在很长时间了，迄今为止，在通常 情况下每个数据库中的信息可以被自由的共享。然而，现在独立实体数据 库间的计算查询的需求增加，这样就不希望把更多的信息暴露给对方。这 是由于下面几个原因： ( 1 ) 端到端的集成从供应链到面向用户的系统中，电子商务要求信息 系统点对点的集成。这种集成发生在独立的企业之间，他们各自的数据库 都是私有的，每个数据库都保存自己企业的信息。所以每个数据库都被暴 露是不受欢迎的，他们希望在查询过程中只暴露所需的信息。 ( 2 ) p b 部采购一些企业为缩减开支从外界供货商或制造商那里获得 服务或产品( 如制造机动车的零件) ，在企业间的外部采购时，他们需要对 其数据库系统进行集成用于处理像库存控制这样的操作，因为这些企业之 间是合作与竞争并存的关系，所以在采购的时候必须用到隐蔽检索方法。 ( 3 ) 竞争与合作的同步对于企业之间，在某一领域中的合作在另一领 域可能是竞争，这种现象现在非常普遍，这就要求选择性的进行信息共享。 ( 4 ) 安全在同一政府内部和在政府之间，政府代理需要共享信息来设 计有效的安全尺度。然而，一个代理不能向其他所有代理无差别的开放它 们的数据库。它们必须根据不同的用户的身份，分别开放数据库的不同信 息，而且要求查询时得到有效的保密。 ( 5 ) 私有性目前的大多数数据库都具有私有性，保密立法和声明保密 规则的地方限制了信息的共享。然而，在尊重保密限制的情况下，数据库 间的数据检索是受到欢迎的。 目前，用户所感兴趣的知识是那些既有价值又备受关注的信息。如果 这些信息被别人利用来做一些对用户不利的事情，那么这些信息将会带来 很坏的影响。 以前，用户所关心的内容对服务器以外的每个人都是保密的，服务器 很可能利用用户所关心的信息来做一些不利于用户的事，这种情况已经存 在很长时间了。然而，这种情况对于用户来说是不合理的。一个最大的在 7 燕山大学工学硕士学位论文 线媒体商拥有一个关于用户形象和用户购买倾向的数据库，然而这个数据 库可以被看作是一个商业项目，例如，这个数据库可以未经用户同意卖给 其它公司。更糟的是，服务器很可能是“h o n e s tb u ts t u p i d ”。意思就是， 服务器在它的安全水平上存在缺陷，因此就会导致入侵者对用户的隐私进 行访问，这样也会给用户带来很大的损失。据报道，有一半以上的服务器 在某种程度上都会泄漏用户的隐私。最终，公司因为破产而不得不出卖用 户的隐私数据库。用户不仅要在他人面前保护自己的隐私，同样也不能向 服务器透露自己的隐私，这样才能更有效的保护用户的隐私安全，从而实 现绝对的安全查询，因此解决隐蔽检索问题是非常必要的。 1 3 研究现状 最初人们为了有效的保护自己的隐私而不得不下载整个数据库，在理 论上，完整的数据库下载解决了隐蔽检索问题，这样客户就可以在本地的 数据库副本上处理请求，得到自己想要的数据信息。而且服务器不知道用 户的查询请求的内容，这样服务器也就不知道用户所感兴趣的内容是什么。 但是这个方法并不实用，因为用户必须为下载数据库中所有的记录付出高 额的费用，而且也需要大量的通信开销，这里的通信开销等于数据库的大 小。但是与下载整个数据库所需要支付的巨额费用相比，通信开销是可以 忽略的。 后来又采用匿名技术来对用户的隐私进行保密，一个用户可以向服务 器匿名地发送请求，并且匿名地接受回答。另外还可以利用一种匿名支付 系统在它匿名请求时进行一次匿名支付。这看上去很像一个隐蔽检索的解 决方法，但实际上它不是，因为服务器可以搜集一个关于用户兴趣的统计 表。例如，服务器可以计算出哪条记录的访问次数要多于其它记录，或者 服务器可以计算出多少条确切的记录在给定的段时间内被访问。在这个 统计表上进行一些数据挖掘和进行一些额外的努力都可以泄漏用户的隐 私。 c h o r 等人在1 9 9 5 年系统的提出隐蔽检索【5 ( p i r ，p r i v a t ei n f o r m a t i o n 第1 章绪论 r e t r i e v a l ) 的概念，他认为在服务器中存有n 位串，从这个n 位串中隐蔽地 检索出第i 位，这里“隐蔽”的含义是服务器不知道i 是多少，也就是说， 服务器根本不知道用户对哪一位感兴趣。c h o r 等人证明任何p i r 解决方法 的通信量不可能低于数据库的大小。同时又提出了一种基于多个数据库模 式的p i r 解决方法，然而这种方法也存在缺陷，因为服务器可以通过合作 来知道用户的隐私。 目前已经出现了很多关于隐蔽检索的方法，如基于多个数据库模式的 p i r 方法，基于单一数据库的p i r 方法，基于硬件的p i r 方法，对称p i r 方法等。但是大多数方法都是理论上，还没有应用于实践。而且它们在保 护用户的隐私上都存在一些缺陷，需要迸一步解决。 1 4 本文研究内容 本文研究了以往的一些p i r 解决方法，并对以前的一些方法进行分析， 总结出每种隐私检索方法的缺点，并在此基础上提出一种新的隐蔽检索方 法。它是一种对称式的隐蔽检索方法，它不仅对用户的隐私进行保密而且 对，而且还对服务器的隐私也加以保护，并且同时提出了“极少必要信息 共享”的概念。 与以往的p i r 方法比较，新的p i r 解决方法具有以下特点： ( 1 ) 对称的隐蔽检索解决方法新的隐蔽检索方法是对称的隐蔽检索 方法【“，它不仅对用户的隐私进行有效的保护而且还对服务器的隐私进行 保护。 ( 2 ) 利用可交换加密函数新的p i p , 方法利用可交换的加密函数对数据 库中的数据和用户查询的数据进行双重加密，通过加密后的密文匹配来找 出用户所需的记录，然后再经过双方解密，使用户得到自己真正想要的数 据。 ( 3 ) 极少必要信息共享当用户查询数据库时，隐蔽检索技术直接计算 出结果，而无需暴露结果以外的其他信息。有时为了缓和这种约束，允许 暴露一些极少的必要额外信息。 燕山大学工学硕士学位论文 本文提出了一些相关的操作：交集、交集的大小、等值连接以及等值 连接的大小，并在此基础上提出了差算法、差的大小和差连接算法的研究。 本文主要对这些算法的正确性和安全性进行分析和验证，并说明算法的局 限性以及其未来发展方向。 1 5 本文结构 第2 章介绍了p i r 发展现状，这些内容作为第3 、4 章研究的基础。 第3 章主要阐述现有极少必要信息共享的隐蔽检索技术，这章介绍了 极少必要信息共享的概念、安全模型、相关概念和一些相关算法。 第4 章提出了基于极少必要信息共享的相关算法和分析，主要对交集 算法、等值连接算法、交集的大小算法、差算法、差的大小算法和差连接 算法进行了研究与分析。 第5 章对本文研究内容进行实验验证，并根据实验对算法的复杂度进 行分析。 最后，总结本文的工作以及未来的研究方向。 第2 章隐蔽检索的研究现状 第2 章隐蔽检索的研究现状 2 1 隐蔽检索简介 在电子商务中，用户的隐私通常不能够得到有效的保护。目前，没有 什么更好的方法可以保护用户的隐私。例如，一个投资者想查询某一股票 市场数据库中的某个股票的数据，但是他不希望别人知道他对哪种股票感 兴趣。当然，当用户希望自己的意图被保密的时候，他通常非常谨慎地访 问数据库。这就要求在访问单个数据库的时候，为了保护用户的隐私，用 户就不得不下载整个数据库，也就是说需要传递整个数据库的数据。但是 这种方法的通信开销太大，而且用户不得不为数据库的每一条记录支付巨 额资金，以至于无法接受。 目前，用户所感兴趣的知识是那些既有价值又备受关注的信息。如果 这些信息被别人利用来做一些对用户不利的事情，那么这些信息将会给用 户带来很坏的影响。 在p i r 提出以前，用户所关心的内容对服务器以外的每个人都是保密 的，服务器很可能利用用户所关心的信息来做一些不利于用户的事情，这 种情况已经存在很长时间了。然而，这种情况对于用户来说是不合理的。 例如，一个最大的在线媒体商，他拥有一个关于用户形象和用户购买倾向 的数据库，然而这个数据库可以被看作是一个商业项目，这个数据库可以 未经用户同意卖给其它公司m 】。更糟的是，服务器很可能是“h o n e s tb u t s t u p i d ”。意思就是，服务器在它的安全水平上存在缺陷，因此就会导致入 侵者对用户信息数据库进行访问。据报道，有一半以上的服务器在某种程 度上都会泄漏用户的隐私 9 a o 。最终，公司因为破产而不得不出卖用户信 息数据库【1 1 - 1 3 1 。 用户不仅要在他人面前保护自己的隐私，同样也不能向服务器透露自 己的隐私信息。为了解决这个问题，便产生了p i r 解决方法，即在信息检 燕山大学工学硕士学位论文 索过程中，服务器不知道用户对哪一条信息感兴趣。 p i r 解决方法允许用户从数据库中检索一条记录，同时对数据库服务 器而言，隐藏了这条记录的身份，服务器不知道用户对哪条记录感兴趣， 用户在得到自己所需信息的同时也达到对自己隐私保密的目的，真正实现 安全的查询。 2 2p i r 应用领域 在这部分将用一些实例来说明p i r 方法的必要性。接下来将描述一些 具体的例子，这里假定p i r 方法是有效的。 2 2 1 专利数据库 如果专利服务器知道用户对哪个专利感兴趣，这将会给用户带来许多 麻烦，因为服务器将会利用用户的查询内容做一些不利于用户的事情，如 利用用户查询内容抢先申请专利等。如果用户是一个研究者、一个发明者 或者是一个投资商，那么我们想象一下，如果一个科学家发现了一个伟大 的观点“2 + 2 = 4 ”，他很想申请专利，但是在申请专利之前，他必须查找一 下国际专利数据库中是否已经存在一个这样专利，或者存在一个与其相似 的专利。在检索过程中，服务器的管理者将会读取这位科学家的查询“a r e t h e r ep a t e n t sl i k e2 + 2 = 4 ”，并且管理员将从这个查询中得到以下信息： ( 1 ) “2 + 2 = 4 ”或许是个发明，为什么不抢先申请专利。 ( 2 ) 这个科学家所工作的领域也许是很显著的领域。 以上两个推测都是非常关键的，而且不应该让服务器知道这些信息。 p i r 解决了这个问题：用户可以公开的用信用卡为他所下载的专利付费， 与此同时服务器并不知道用户下载了哪一个专利。 2 2 2 药品数据库 通常药品公司致力于药品研制以及对药品的基础成分的收集。药品公 司为了配制一种新型药品，需要获取药品信息数据库中若干种基本成分的 第2 章隐蔽检索的研究现状 信息，在查询的过程中，公司要求保密计划，而且还要得到所需的信息。 为了达到这个目的，药品设计者不得不用巨资买下整个药品数据库。如果 药品设计者利用p i r 协议来购买他们所需的几种药品基础成分信息，那么 他们将会避免巨大的开销，并且安全获得信息【1 4 l 。 2 2 3 媒体数据库 目前存在许多商业性的档案文件，它们包括电子出版物、音乐文件 ( m p 3 ) 、相片、视频等等。如果把顾客的信息资料放在服务器中，实在是太 危险了，因为，顾客信息资料数据库可以被看作是一个商业项目，这个数 据库可以未经用户同意卖给其它公司。更糟的是，服务器很可能在它的安 全水平上存在缺陷，因此就会导致入侵者对用户信息的数据库进行访问， 窃取用户的资料信息。这就意味着用户只有遵循p i r 协议，才能在服务器 上隐藏自己所感兴趣的信息，真正保护自己的合法权益。 2 2 4 学术例子 安全部门的特殊行动组计划在区域r 进行一次特殊的行动，为了得到 r 地区的高分辨率的地图，他们向i t 部门的图像数据库发出一个请求，那 么i t 的职员就能够知道在r 地区很快就会有一次特殊行动。这里如何保 证既在特殊行动部门内部保守秘密，同时又可以在外部数据库处理查询。 我们可以利用p i r 来实现【”j 。 另一个理想的应用是i s a b e l l ed u c h e s n a y 在文献 1 6 1 中提出的多种秘密 探测器，在它的目录中，每个秘密都可以用一个能引起注意的标题来描述。 例如，“w h e r ei sa b un i d a l ”。它不会接受用一个秘密的价钱来获取两个秘 密，更不会透露超过一个的部分信息。当然，用户都不情愿让它知道哪一 个秘密是用户想要获得的，因为，如果探测器知道了你的确切喜好，它就 会把你的喜好变成一个有价值的秘密，可以告诉别人，像这样的标题：“谁 正在寻找恐怖主义”。那么客户可以利用p i r 方法来秘密地检索想要的秘 密，这样在商家进行交易，购买自己所需的商品的同时，也对用户的隐私 进行了保密，两者都会合作得很愉快。 燕山大学工学硕士学位论文 2 3 简单而又不正确的p i r 方法 这里至少有两种解决p i r 问题的简单方法，在现实中，这两种方法是 不可行的，但它们向我们指出了p i p 应该具备的性质。 2 3 1完整的数据库下载 在理论上，完整的数据库下载解决了p i r 问题，这样客户就可以在本 地的数据库副本上处理请求。同时服务器不知道用户查询请求的内容，结 果服务器也就不知道用户的兴趣信息。但是这个方法不能应用于现实，因 为用户必须为数据库中所有的记录付出高额的费用，而且也需要大量的通 信开销，通信开销等于数据库的大小。但是与下载整个数据库所需要支付 的巨额费用相比，通信开销是可以忽略的。 2 3 2 匿名技术 应用一种匿名技术( 如l p w a 系统旧) 来实现隐蔽检索解决方法，一个 用户可以向服务器匿名地发送请求，并且匿名地接受回答。另外还可以利 用一种匿名支付系统( i p r i v a c y 系统【嘲) 在它匿名购买数字商品时进行一次 匿名支付。 这看上去很像一个p i r 解决方法，但实际上它不是，因为服务器可以 搜集一个总的关于用户兴趣的统计表。例如，服务器可以计算出哪条记录 的访问次数要多于其它记录，或者服务器可以计算出多少条确切的记录在 给定的一段时间内被访问。在这个统计表上进行一些数据挖掘或者进行 些额外的努力都可以发现用户的隐私。 这个方法还有其它的缺陷，除了匿名支付技术以外用的最多的匿名网 络技术是：依靠可信的第三方口外，结合上文我们可以知道，这种方法只不 过是把用户对服务器的信任变成了对第三方的信任，实际上并没有改变什 么。 但是这些匿名技术都是不可靠的，当所有的参与者合伙攻击用户时， 用户也同样处于不安全的状态 2 0 , 2 1 l 。 1 4 第2 章隐蔽检索的研究现状 2 4 隐蔽检索的当前技术 自从1 9 9 5 年c h o r 等人系统地提出p i r 概念以后，已经有超过2 0 篇 相关文章发表。由于篇幅关系，这里不能一一介绍每一个算法，只是介绍 一些算法的基本观点。 2 4 1 理论的p i r 理论是支持实践的，用户的隐私权是不可侵犯的。c h o r 等人证明任何 理论p i r 解决方法的通信量都不可能低于数据库的大小。因此就通信总数 而言，下载整个数据库的p i r 解决方法是一个优化的解法。这种解法被称 为是“平凡”的，所以“不平凡”的解法就是通信总数小于数据库的大小 的解法。表2 1 总结了一些理论p i r 模式的通信开销 表2 - 1 一些具体模式的比较【5 】 t a b 2 - 1c o m p a r i s o no f s o m ec o n c r e t es c h e m e s 阁 总的通信量 数据库个数 方法通信复杂度 n 2 2 2 0n = 2 ”n = 2 ” k = 2 覆盖编码1 2 瓶 1 2 2 41 2 3 0 01 2 3 8 6 4 k - 2 多项式插入6 3 4 艏 6 4 9 32 0 7 7 4 56 6 4 7 8 1 5 k = 4 覆盖编码2 8 靠 9 2 45 0 9 62 8 7 0 0 k = 4 多项式插入2 6 7 拓 8 2 74 6 3 52 6 1 3 6 k = 4 改进插入2 67 拓 8 0 94 6 1 62 6 1 1 8 k = 7 覆盖编码6 0 拓 1 0 2 03 9 0 01 5 4 2 0 k = 7 多项式插入8 3 8 7 孤 6 5 11 6 3 84 3 2 6 k = 7 改进插入8 38 7 乏，n 5 4 61 5 3 34 2 2 l k = 1 6 覆盖编码2 2 4 n 1 7 9 24 4 8 01 1 8 7 2 k = 1 5多项式插入 4 8 5 5 蛎 1 6 3 52 2 2 43 2 0 5 k = 1 6改进插入 4 8 55 岬n 7 2 01 3 0 82 2 8 9 为了得到不平凡的理论p i r 解法，c h o r 等人放松了问题的初始条件， 燕山大学工学硕士学位论文 他们假设存在几个互不通信的数据库，这些数据库中都存储着相同的数据。 这个假设使得非平凡的理论p i r 成为可能。基本理论为：用户同时向这几 个数据库发送一些请求，这些请求的结构与通常的查询语句不同，它们不 向服务器提供用户所关心的记录信息，而是从每个查询的回答上构建出所 希望的记录。在这里我们必须考虑一种情况，服务器可以通过合作来知道 用户的隐私。 a m b a i n i s l 2 2 1 改善了c h o r 等人提出的方法，导出下面的非平凡理论p i r 解法： ( 1 ) k 个数据库模式是指一个带有k 个不能互相通信的数据库模式。对 于任意一个常数k 2 ，其通信复杂度为o ( n l f ( 2 “) 。 ( 2 ) ( 1 0 9 n ) 个数据库模式的通信复杂度为o ( 1 0 9 2 n * l o g l o g n ) 。 在某种意义上，块的隐蔽检索( p i ro f b l o c k s ) 是p i r 问题的一个延伸， 数据库中的记录被看成是几位的组块( 替代1 位) 。c h o r 介绍了理论p i r 块， 并在文献 2 3 1 中进行了进一步的研究。为了使p i r 能够用于实践，块的p i r 技术就非常重要了。 2 4 2 可计算的p i r “可计算”的意思是认为数据库服务器是有计算界限的，也就是说在 一个恰当的难处理的情况下，数据库不可能获得i 的信息。对于每个 0 ， 都存在一个可计算的p i r 双数据库模式，这种方法的通信复杂度为o ( n 1 。 在文献 2 4 1 5 b ，o s t r o v s k y 和s h o u p 构建了一个协议，这个协议在某种 程度上可以在数据库中写入第i 条记录，而不被数据库服务器知道i 是多 少，这个协议既可以用于理论的p i r ，又可以用于可计算的p i r ，而且它 们都带有两个或更多的服务器。例如，对于带有三个服务器的理论p i r ， 每个服务器都执行了一个复杂度为o ( n “3l 0 9 3n ) 的协议。而可计算p i r 带 有多个算法的通信，这些算法复杂度都要求是o ( | o g n ) 。 在文献 2 5 中证明了单个数据库模式的p i r 解决方法中是不存在非平 凡的解决方法。奇怪的是，当用难处理的情况来替代信息理论安全时，将 会实现用于单一数据库模式的非平凡p i r 协议。对于任意的s 0 ，它的通 第2 章隐蔽检索的研究现状 信复杂度为o ( n 。) ，这里所说的难处理假设在文献【2 6 】中有介绍。它的基 本方法是：以某种方式加密查询语句，服务器仍然可以用专门的算法来处 理它，然而服务器不知道查询语句的清晰文本是什么，也不会知道结果， 而结果只能由客户端来进行解密。这也是第一个单一数据库模式的p i r 协 议，在这里设计者提出了数据库隐私。 c a c h i n 等人利用另一个难处理的假设【2 7 】演示了一个单数据库模式 的可计算p i r 协议，它具有多种算法的通信。与文献 2 8 】中的多项式通信 复杂度比较，这是一个改进的算法。这个结果看起来特别有效，用户最少 需要发送l o g n 位的数据，仅仅是为了处理数据库的第i 位( 用户想要接收 的位) 。在文献【2 9 中提出了一种改进模式。 2 4 3 对称的p i r 对称p i r 也是p i r 的一种，这种p i r 方法不但要对用户的隐私进行保 密，同时还要对服务器的隐私进行保密。并且在对话期间，必须防止用户 从数据库中获得一条记录以外的更多信息。很明显，对称p i r ( 数据库的隐 蔽检索) 在实践应用中非常重要。用于单一服务器的对称p i r 是在文献 2 8 1 中首次提出的。多个服务器模式的对称p i r 是在文献 3 0 】中提出的，其它 的对称p i r 在文献【3 1 ，3 2 】中提出。 2 4 4 基于硬件的p i r s m i t h 和s a f o r d 3 3 1 提出了一种单一数据库的p i r f 司题，它应用了一种专 门的t a m p e r - p r o o 做备，在服务器端设置了一个安全协同处理器【3 4 】f s c ， s e c u r ec o p r o c e s s o r ) 。用户加密一条语句“g i v em et h ei - t hr e c o r d ”，并把这 条语句发送给安全协同处理器处理。安全协同处理器解密查询语句，对其 进行处理，并且加密回答，然后把加密好的回答发送给用户。在这个过程 中，服务器没有发现查询是什么，因为： ( 1 ) 在服务器上设疑了安全协同处理器，而服务器不能访问安全协同处 理器的r a m ( r a n d o m a c c e s sm e m o r y ，随机存取存储器) ，服务器就不能知 道用户的查询是什么样的。 1 7 燕山大学工学硕士学位论文 ( 2 ) 为了处理查询，安全协同处理器不得不读取数据库中的所有记录， 但不暴露用户感兴趣的记录。 2 4 5 问题设置的进一步扩展 综上所述，最初的p i r 工作重点在于优化通信，因为传输通信被认为 是非常昂贵的资源( 因为当时的网络传输速度比较慢) 。尽管大多数情况下 都能成功的实现这个目的，但是在实际应用中，提出的解决方法仍然是不 可靠的。这是因为在众多的方法中，服务器所要求的计算与数据库大小至 少成线性关系。为了响应一条记录，服务器必须读取整个数据库，如果服 务器发现有一条记录没有被读取，那么服务器就能够推出这条记录是用户 所不感兴趣的，从而泄漏用户的隐私。 为了解决这个问题，g e r t n e r 等人提出了一个模式，这里的主要计算是 从一个数据库服务器被转移到另一个专用服务器中【3 5 。当协议把数据库服 务器的计算减到d ( 1 ) 时，专用计算仍然是线性的。 d i - c r e s c e n z o 等人展示了另一个p i r 模式 3 6 1 ，这个模式利用了一个专