（计算机软件与理论专业论文）隐私保护数据查询系统的研究与实现.pdf

中文摘要 摘要：随着信息技术的不断发展，数据库系统的应用日益普及，利用数据库系统 实现数据共享，可以使人们的日常生活和工作更加方便、快捷，但同时也给非正 当地获取数据库的数据信息提供了更多的机会，数据库系统中的敏感数据保护问 题日趋严重。 在诸多针对敏感数据的保护方法中，对数据库中的数据信息进行加密是一种 非常有效的方案。但是另一方面，数据库中的数据经过加密后，原来相同的关键 字可能变成了不同的密文信息，关键字之间的序关系也被破坏，从而使基于这些 关键字进行查询的算法无法正常工作，如何在不对密文数据进行解密的条件下， 针对密文数据的查询是一个非常有挑战性的工作。近几年，国内外学者围绕该问 题进行了一系列的研究工作，并取得了一些成果，其中主要包括：基于对称密码 的隐私保护数据查询方法；基于公钥密码的隐私保护数据查询方法；基于同态加 密理论，对有序数据进行保序加密的数据查询方法。 本文首先分析了现有基于对称密码的隐私保护数据查询方法的优缺点，并根 据隐私保护数据查询中的最小信息泄露( m i n i m u mi n f o r m a t i o nr e v e l a t i o n ) 原则， 利用安全散列函数的特点，设计了一种基于对称密码与安全散列函数的隐私保护 数据查询方案，该方案在实现效率上明显优于现有的基于对称密码的隐私保护数 据查询方案；然后根据保序数据加密方案( o p e s ) 原理，借鉴了同态加密理论， 设计了有序数据的密文保序存储和区间查询方案，该方案通过第一种方案确定查 询区间的端点值，再根据所保持的序关系确定满足查询条件的区间中的所有数据； 随后利用u s b k e y 设计并实现了基于硬件的双因子认证查询客户端，将加密密钥 和查询密钥存储在硬件中，增加了查询客户端的可控性；最后对所设计和实现的 方案进行了效率分析并与已有方案进行了对比。 关键词：隐私保护查询；密文数据；最小信息暴露；安全散列函数；o p e s 。 a b s t r a c t 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 , t h ea p p l i c a t i o no f d a t a b a s es y s t e mb e c o m e sm o r ea n dm o r ep o p u l a r u s i n gd a t a b a s es y s t e mf o rd a t a s h a r i n gc a l lm a k ep e o p l e sl i f em o r ec o n v e n i e n t b u t i ta l s op r o v i d e sm o r eo p p o r t u n i t i e s t on o n - l e g i t i m a t ea c c e s st ot h ei n f o r m a t i o ni nt h ed a t a b a s e t h ep r o b l e mo fs e n s i t i v e i n f o r m a t i o np r o t e c t i o ni si n c r e a s i n g l ys e r i o u s a m o n gv a r i o u sp r o t e c t e dm e t h o d sh a v eb e e np r o p o s e dr e c e n t l yf o rs e n s i t i v ed a t a , e n c r y p t i o ni sa ne f f e c t i v em e t h o dt op r o t e c td a t ai n f o r m a t i o ni nd a t a b a s e b u to nt h e o t h e rh a n d ，t h eo r i g i n a l l ys a m ek e y w o r d sp o s s i b l yb e c o m ed i f f e r e n te n c r y p t e d i n f o r m a t i o na f t e rt h ed a t ai se n c r y p t e di nt h ed a t a b a s e ，a n dt h eo r d e rb e t w e e nt h e k e y w o r d si sa l s od e s t r o y e d s ot h es e a r c h i n ga l g o r i t h mb a s e d o nt h ek e y w o r d sc o u l d n o tw o r ka g a i n q u e r yo ne n c r y p t e dd a t ai nt h ec o n d i t i o n so fn o td e c r y p t i n gt h e e n c r y p t e dd a t ai sav e r yc h a l l e n g i n gt a s k i nr e c e n ty e a r s ，d o m e s t i ca n df 0 r e i g ns c h o l a r s c o n d u c tas e r i e so fr e s e a r c hw o r ko nt h i si s s u e , a n dt h e ym a k es o m er e s e a r c h a c h i e v e m e n t s t h ea c h i e v e m e n t si n c l u d e ：p r i v a c y - p r e s e r v i n gq u e r ys c h e m eb a s e d o n s y m m e t r i ce n c r y p t i o na l g o r i t h m ，p r i v a c y - p r e s e r v i n gq u e r ys c h e m e b a s e d o np k i e n c r y p t i o na l g o r i t h ma n dq u e r ys c h e m ef o rt h eo r d e rp r e s e r v i n ge n c r y p t i o no fo r d i n a l d a t ab a s e d o np h s f i r s t l y , t h i sp a p e ra n a l y z e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ee x i s t i n g p r i v a c y - p r e s e r v i n gq u e r ys c h e m eb a s e d - o ns y m m e t r i ce n c r y p t i o na l g o r i t h m ，a n dt h e n d e s i g n sap r i v a c y - p r e s e r v i n g d a t aq u e r ys c h e m eb a s e d - o ns y m m e t r i ce n c r y p t i o n a l g o r i t h ma n ds e c u r eh a s hf u n c t i o n , i na c c o r d a n c ew i t ht h ep r i n c i p l eo fm i n i m u m i n f o r m a t i o nr e v e l a t i o na n du s i n gt h ef e a t u r e so fs e c u r eh a s ha l g o r i t h m t h i ss c h e m e i ss u p e r i o rt oe x i s t i n gs c h e m e su s i n gs y m m e t r i ce n c r y p t i o na l g o r i t h mi no p e r a t i o n a l e f f i c i e n c yt h e n ，a c c o r d i n gt ot h ep r i n c i p l eo fo r d e rp r e s e r v i n ge n c r y p t i o ns c h e m e , t h e p a p e rd e s i g n so p e sa n dr a n g eq u e r ys c h e m eo nt h eb a s i so fp h s t h i ss c h e m e d e t e r m i n e st h ee n dp o i n t so ft h er a n g et h r o u g ht h ea b o v eq u e r ys c h e m e ，a n dd e t e r m i n e s a 1 1o ft h ed a t am e e t i n gq u e r yc o n d i t i o n si nt h er a n g ea c c o r d i n gt ot h er e t a i n e do r d e r t h e nt h ep a p e ri m p l e m e n t st w o f a c t o ra u t h e n t i c a t i o na c c e s sc o n t r o lw i t hu s b k e y k e y w o r d s ：p r i v a c y - p r e s e r v i n gq u e r y ；e n c r y p t e dd a t a ；m i n i m u mi n f o r m a t i o n r e v e l a t i o n ；s h a ；o p e s 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：并豸易 签字日期：砂蕊年舌月多日 导师签名： 签字日期： 纱 日 朝研 为舻f 月6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字日期：年月日 致谢 深深感谢我的导师刘吉强副教授，正是刘老师对我的指导、关怀和严格要求， 使我顺利完成了硕士阶段的学习和研究。在导师丰富的知识、严谨的治学态度、 敏锐的洞察力和高尚的师德的熏陶下，我的学识快速增长，提高了科研技能，树 立了正确的人生观和世界观。在两年的硕士研究生学习中，刘老师对我悉心培养， 使我对信息安全技术产生浓厚的兴趣，并在加密数据隐私保护数据查询方向上进 行了初步的研究，提出了一些见解和实施方案，完成了论文相关的科研工作和撰 写工作。在此衷心感谢两年来刘吉强老师对我的关心和指导。 感谢北京交通大学对我的培养，感谢北京交通大学信息安全体系结构实验室 为我所提供的学习条件和科研环境。特别要感谢韩臻教授两年来在学习态度与科 研方向上对我的指导，韩老师严谨的学术作风、精益求精的钻研精神是我学习的 榜样。 我还要感谢与我一起攻读硕士研究生的同学们，特别是陈勋、何帆、刘博同 学给予我的帮助和支持，我将永远记住在一起学习、生活的美好时光 另外我要感谢我的亲人们，是你们给予我物质上、精神上极大的支持和关怀， 你们的理解和支持使我能够在学校专心完成我的学业。 1 引言 1 1 研究背景 随着计算机技术的飞速发展和信息全球化的发展方向，互联网以及互联网上 信息的应用是政府及企业最重要的战略性资产之一，是实现生产率和竞争优势最 大化的关键所在。同时，由于开放互联技术的原因，信息系统的诸多信息，尤其 是政府、企业、个人的敏感信息，如客户数据库、专有科研成果、人员档案和其 他关键性信息资源，遭受着严重的威胁。仅最近三年，数据库大量信息泄漏事件 层出不穷。这其中相当大的一部分是个人、企业的敏感信息。例如，2 0 0 5 年6 月， 万事达信用卡中心，4 0 0 0 多万信用卡用户的姓名和卡号被泄漏。2 0 0 6 年5 月，美 国退伍军人事务处理部门，2 6 0 0 多万退伍军人的姓名、社保号码、出生日期存放 的磁盘从这个部门的一个雇员家中被窃取。2 0 0 7 年5 月，金士顿公司掌握的全球 近2 7 万客户的在线资料( 包括客户的姓名、通讯地址以及信用卡号等详细信息) 受到黑客攻击，存在泄漏的可能性。同年，香港娱乐圈爆出丑闻一“艳照门事 件，一男艺人的个人隐私照片被窃取，其非常重要的个人隐私信息被公之于众。 这种敏感信息泄露，可能造成身份被盗用、个人财产丢失或者其他严重损害个人 的欺诈活动，并造成恶劣的社会影响。除此以外，许多与我们日常生活密切相关 的信息系统存在着安全隐患，例如，医院的医院信息管理系统( h i s ) ，系统中保 存的病人个人档案及详细病历记录均为高等级个人隐私，同时h i s 系统中保存了 药品、医疗器械等的采购与使用记录，这些信息一旦被非法盗取或使用，将给患 者、医院带来无法弥补的损失。因此，如何保证和加强数据库中大量数据的安全 问题、敏感数据的防窃取和防篡改问题，越来越受到社会各界的高度重视。 典型的数据库系统的防护，主要是采用访问控制和入侵检测等技术阻止对敏 感数据的非法访问，但是这些技术提供的安全性已经不能满足数据库安全的需要。 为了防止用户以及内部人员非法使用，必须对数据库中存储的重要敏感数据进行 保护，而当前最为有效的最后一道保护屏障是数据加密技术。入侵者即使从数据 库中获得了数据信息也无法解密密文，从而保证了敏感信息的安全，减少因隐私 公开和身份盗窃为数据所有者带来的损失。加密数据的隐私保护查询已经成为信 息安全领域的一个新的研究方向。 加密数据的隐私保护查询希望实现的目标为，通过使用加密算法对原始数据 进行加密处理，数据库服务器能够在不解密的情况下，直接对密文数据表中的字 段进行相关查询，数据在网络上能够进行密文传输，并且数据的加解密都不在服 务器上进行。当数据库服务器返回查询结果后，查询者使用保存在客户端的加密 密钥解密查询结果，从而获得原始数据。当个数据库被部署在网络中时，面临 的一个关键问题是在服务器不进行解密的情况下，如何直接对密文数据表中的字 段进行相关查询。因为在对数据库中的数据进行加密后，其原来用于进行查询处 理的关键字被处理成了不可识别的编码，关键字之间的序关系也完全被破坏，从 而使基于这些关键字进行查询的算法无法正常工作。那么，在一个存储加密数据 的数据库中，如何进行查询昵? 理论上，如果不考虑效率，用户可以检索库中所 有的表格，解密表格，然后对明文表格进行查询。但是，对于现代使用的大型数 据库中的海量信息，这显然是不切实际的。 在这篇文章中，我将设计一种对加密数据执行查询的有效方法，当入侵者获 得服务器的系统管理员权限时，这种方法仍然可以保护服务器中数据的安全。这 样的方法对于加强数据库中的敏感数据保护有非常重要的意义。 1 2 研究现状 近几年，针对敏感数据的保护问题，国内外学者提出了多种研究方法。加密 技术，作为保护敏感信息的重要手段，最早由g i d a v i d a 等在【l 】中应用，随后得到 了一系列重要的结果。 l b o u g a n i m 和ep u c h e r a l 等基于智能卡讨论了一种保护数据机密性以及个人 隐私的有效机制，并提出了在不可信的服务器上存储机密数据的有效方案1 2 。 j k a r l s s o n 利用加密技术针对移动数据库系统给出了数据安全存储的方案【3 1 。 g o z s o y o g l u 等提出了防窜改数据库的概念，并给出了如何在加密数据库上进行检 索的方法【4 】。而b i y e r 等在 5 】中分析了在关系数据库管理系统中安全存储的相关问 题，并提出了一个新的安全存储模型。数据库厂商也充分认识到加密技术的重要 性，o r a c l e 和i b m 都已经在他们的产品中包含了加密功能 6 ，7 】。考虑到敏感数据 记录由于密级不同需要不同的隐私策略，r a g r a w a l 等在 8 】中为敏感数据提供分级 隐私策略的新型数据库，对于阻止非法用户访问敏感信息是非常有效的。 加密数据库中一个关键的问题就是如何进行数据查询。h h a c i g u m u s 等研究 了当敏感信息暴露在非可信的服务器上时 9 a o ，对d a s ( d a t a b a s e a s s e r v i c e ) 系统 中的加密数据进行查询的问题，也给出了一种在加密的关系数据库上如何进行有 效查询的方法。他们的解决办法是把属性域划分成区间，并且把所分区间的标识 符映射成随机数以实现隐私保护。该想法简单、直观并且实用，但是在安全性和 效率之间存在着一种潜在的折中关系。尤其，如果区间较大，希望信息泄露的更 2 少，那么服务器需要向用户发送更多的错误信息( 例如：查询的数据并不在返回 的结果中) ，反之，则泄露更多的信息。b h o r c 在 1 1 中给出了改进的方案。此外， 【9 没有精确的量化信息泄露与分区大小或者通信量开销之间的关系。相比较， z y a n g 等在 2 6 】中的解决方案没有做折中方案，该解决方案在强调隐私保护的同 时并不会返回错误的查询值，浪费通信资源。另外，尽管在 1 0 】中区间信息识别码 能够用于检索密文以提高查询速度，可是这样的检索可能导致推理和关联攻击【1 2 】。 相比之下，【2 6 】中提出的解决方案，在提高查询效率、减少通信资源浪费的同时， 并未暴露更多的信息。 a g r a w a l 等在 1 3 】中提出一种对有序实数进行保序加密的解决方案。他们的解 决方案借鉴了同态加密的理论，在维持每一列实数顺序的基础上，对实数进行加 密处理。因此，如果入侵者观察到加密的数据，他能得知每一个列所有单元的顺 序，但是并不能根据顺序推导出实数的值。这个解决方案对本文的方案设计非常 有帮助，在本文中我借鉴了其解决方案的核心思想，只向一个潜在的入侵者显示 有序列的顺序，但是根据序号不能推导出存储数据的值。 在文章 5 ，1 3 】考虑的场景中，假设对手可以访问存储的数据，而无权访问用 户和数据库间传送的消息。在 9 】设置的d a s 模型中，由于数据库服务器是不可信 的，因此服务器自身就是一个设法破坏数据隐私性的潜在敌人。服务器可以访问 所有加密数据以及用户与服务器问的所有消息。因此，服务器对于数据的隐私性 具有很强的破坏能力。相比之下， 2 6 】中假设对手能访问服务器中所有加密数据， 也能监控所有在服务器和用户之间传送的消息。z y a n g 等也提供了攻击模型，并 分析了所提出的解决方案在该模型下可以保护隐私。 另外，s o n g , w a g n e r , a n dp e r r i g 1 4 1 提出在加密文件中查找关键字的实际技术， 这种技术允许当用户提交一个关键字时，可以通过一种隐秘的方式在文件中查找 键字的存在。但他们的方法要顺序的扫描整个文件，并且没有提供可证明的安全 索引技术。c h a n g 和m i t z e n m a c h e r 1 5 随后分析了这一方案并提出了解决方案，但 他们的方案局限于从一个预先设定的集合中搜索一个选择的关键字。b o n e h 等提出 一种基于公钥密码的方案 1 6 】；他们考虑的情景与 1 4 】中的类似，但是使用公共密 钥加密而不是对称密钥加密增加了计算量从而影响了效率。 与 1 7 ，1 8 ，2 6 类似，我们希望从用户发起请求开始到取回隐私信息对于数据 库服务器和用户与服务器之间的通信是完全隐藏的。而且我们希望实现一种更为 高效的方案。 与本文研究工作密切相关的是隐私保护数据挖掘( p r i v a t ep r e s e r v i n gd a t a m i n i n g ) 技术，隐私保护数据挖掘提供了无需暴露任何关于数据的敏感信息，就 可以计算出或近似计算出数据挖掘算法结果的方法。其算法逻辑与数据结构与本 文的研究相关。现有的解决方案主要可以分为两种方法，一种方法是在分布网络 环境中采取加密技术提供安全解决方案 1 9 】。原则上，安全多方计算强大的范例为 所有分布的计算 2 1 ，2 2 提供通用的加密解决方案( g e n e r i cp r o t o c o l s ) 。然而，因为 数据挖掘算法输入信息量是巨大的，以上的通用解决方案对于实际的应用是相当 困难的。在 1 9 】中，y e h u d al i n d e l l 等基于决策树分类器i d 3 ，运用安全多方计算的 理论设计了一种查询协议，l i n d e u 将信息熵的计算引入分类器的处理中，用熵值 作为属性值的编码，设计一个近似于1 d 3 算法的决策树算法，并且应用这个算法 设计了一个满足安全双方计算( s e c u r et w o p a r t yc o m p u t a t i o n ) 的隐私保护挖掘协 议。并验证了其比通用解决方案更实用，同时可以占用更少的通信带宽。另一种 方法是随机化原始数据，使某些潜在的模式( 比如分配的价值) 保留在随机数中 2 0 。通常，加密的方法可以提供具有完善准确性和隐私的解决方案。相比之下， 随机的方法比加密的方法更加有效，但似乎在隐私性和准确性上受到一定的制约。 1 3 研究内容与论文结构 本文首先分析了现有加密数据隐私保护查询方法的优缺点，并根据隐私保护 查询中的最小信息泄露( m i n i m u mi n f o r m a t i o nr e v e l a t i o n ) 原则，利用安全散列函 数的特点，设计了一种基于对称密码与安全散列函数的加密数据隐私保护查询方 案，然后根据保序数据加密方案( o p e s ) 原理，借鉴了同态加密理论，设计了有 序数据的密文保序存储和区间查询方案，该方案可以在不脱密的条件下，返回满 足查询条件的区间中的所有数据；随后利用令牌设计并实现了基于硬件的双因子 认证查询客户端，将加密密钥和查询密钥存储在硬件中，增加了查询客户端的可 控性；最后对所设计和实现的方案进行了效率分析并与基于对称密码的方案进行 了对比，用实验数据说明该方案在实现效率上明显优于对比方案。 论文内容共分为七章，各章内容简要描述如下： 第一章是“引言，分析了加密数据隐私保护查询研究的产生背景，发展过程； 并且从加密数据查询和隐私保护数据挖掘两个方面介绍了现阶段的研究成果。最 后给出了论文的研究内容、论文的选题意义以及组织结构。 第二章是“预备知识 ，介绍了加密数据隐私保护查询关联的标准密文数据库 查询系统、攻击与信任模型、以及隐私保护查询概念，并描述现有基于对称密码 的隐私保护数据查询方法，分析其优缺点。 第三章是“基于散列函数的隐私保护数据查询方案 ，基于现有的对称密码的 隐私保护数据查询方法，利用安全散列函数的特点，设计了一种基于对称密码与 安全散列函数的隐私保护数据查询方案，该方案在继承了已有方案的优点的基础 4 上，对基于对称密码的隐私保护数据查询方案进行了改进。最后分析了该方法的 可信性与安全性。 第四章是“隐私保护数据查询系统设计 ，围绕第三章设计的查询方案，设计 出具体的查询系统，该系统包括三个子系统“数据表生成子系统 “客户端查询子 系统 和“服务器端受理子系统 。 第五章是“隐私保护数据查询系统实现，将实现各种功能的功能模块依据各 功能的程序结构和涉及到的子系统划分为三个部分、九个功能模块。 第六章是“系统部署与性能测试 ，介绍了系统的硬件支持，搭建系统环境并 进行系统初始化。然后，对系统进行性能测试，并与现有的方案进行了对比实验， 总结结果并论述结果的合理性。 第七章是“成果与展望，总结我们的隐私保护数据查询系统的优点和创新， 并提出希望改进的地方和继续研究的方向。 2 预备知识 在这篇文章中，需要考虑的环境是入侵者可能成功地入侵服务器。本文的工 作目标是当一个入侵者成功入侵服务器后，尽量少的使之获得数据库中的数据信 息和查询数据时的请求信息。为了可以更好的解释加密数据隐私保护查询的方法， 在这一章中我们沿用文献【2 6 】中所用基本概念和模型，以及系统实现时使用的密码 算法。 一个标准的密文数据库查询系统如图2 1 所示。数据单元被加密存储于数据库 服务器中，在客户端，当用户发起一个查询请求时，查询被转化为一个或多个消 息，发送到数据库服务器。在收到消息后，数据库寻找与查询条件相同的加密单 元并且返回这些单元给客户端。最后，客户端解密收到的数据。为了方便描述， 我没有区分客户端程序和使用者，当说到用户时，指的既是使用者也是客户端程 序。 图2 1 标准密文数据库查询系统 f i g2 1s t a n d a r dc r y p t o g r a p hd a t a b a s eq u e r ys y s t e m 2 1 攻击与信任模型 本文研究专注于入侵者可能成功的入侵服务器，本文希望达到的目标是当一 个入侵者成功入侵服务器一段时间后，仍然只能获得很少与数据库中的数据信息 以及查询数据请求信息相关的信息，在此基础上建立的可信与攻击模型要达到以 下三个基本要求1 2 0 j ： 1 用户不完全信任可能存在入侵危险的数据库服务器，而且，假设一旦数 据库入侵者侵入数据库后，他能够观察的不只是加密的数据还能够控制 整个数据库系统( 例如：获得数据库管理员权限) 一段时间。在这段时 6 间中，许多用户发送查询消息给数据库服务器，数据库处理这些消息的 全过程能够被入侵者监视。从实际出发，这种假设的情况是完全可以实 现的。 假设用户与数据库之间的通信通道是安全的，例如用s s l 或者i p s e c 协议加密。客户端程序是可信的；保护客户端程序如何不受入侵不是本 文讨论的范围。 要求所有的数据和索引值加密保存，包括数据表中属性列的名称和数据 库服务器系统日志，否则，这些有可能为入侵者获得数据提供相关信息。 2 2 隐私保护查询 为了方便本文对本节的重要概念以及隐私保护数据查询方案进行描述与设 计，在本节中我需要先将描述与设计时用到的对象进行说明。 假设用t 代表数据库中存储的一张数据表，本文所要讨论的是在表t 加密后 的数据表上进行查询。假定t 有n 行( 即n 条记录) 和m 列( 即m 个属性) 。用 t i j 表示第i 行、第j 列的元素值；( “) 表示该元素的坐标。用t i 表示第i 行的记 录。对于第j 列的属性a j ，用d j 表示该属性包含的全部属性值。 本文中，对于一个表格t ，在数据库中存储t i j ( 1 剑，1 匀蛳) 加密后的表 格t ，其中每个t i 。j 是t i ，j 的一个密文值。在不失普遍性的前提下，假设明文平台 上的每个元素t i ，j 是一个k l 字节的字符串。当我4 1 j n 密一个元素时，加密算法在明 文末尾添加了一个k 2 字节的随机串。1 因此，一个加密算法的输入是一个l ( o 字节的 串，并且k o _ k l + k 2 。为了设计的简单化和遵循大多数对称加密算法的程序接口要求， 我们假设加密算法的输出和密钥也是k 字节的串。因此，我们注意到k o 应该足够 长，才能抵抗暴力破解攻击。 假设一个使用者要在平台t 上进行查询q 。为了使查询过程尽可能的高效， 假定查询协议为向使用者精确返回在数据库中满足查询条件的加密存储单元 t i o j o 。在本文中，把这样的查询协议定义为精确查询协议。 用r ( q ) 表示满足查询q 的元素坐标集，即，满足查询q 的元素为 t i j ：( i j ) r ( q ) ) 。在任何一个精确查询协议中，如果存在如2 1 节中所描述类型 的数据库入侵，那么r ( q ) 就必然暴露给入侵者。因为入侵者能够轻易地检查t 来 确认哪一个加密单元处于返回结果中。因此，称r ( q ) 为查询q 的最小信息泄露。 在任何一种数据查询中，最小信息泄露都必然存在，隐私保护数据查询方案在理 1 使用一个随机位串的目的是一个明文的多重啦现会导向不同的暗记文。 7 想情况下，是不再有额外信息泄露的解决方案。 隐私保护查询的定义描述了用隐私保护查询协议进行数据加密的方法。假设 一个入侵者可能监视服务器接受到的t 个查询q l ，q t ，t 是关于k o 的多项式有界的 函数p o l y ( ) 。用一个随机变量口来量化协议泄露的信息。如果在这些查询得到 处理之后，数据库入侵者所察看到的信息，能够用仅使用仅，r ( q ) 和t 的概率 多项式时间算法模拟，那么就可以确定除最小信息泄露外，该协议只泄露6 c 。为方 便描述，沿用 2 6 】中有关隐私保护查询协议的定义。 定义l ( 隐私保护查询) 2 6 ：查询协议在，如果对于任意多项式p o l y ( ) 和所有足够大的l ( o ，存在一个概率多项式时间算法s ，s 被称为模拟器，使得对于 任意t p o l y ( k o ) 、任意多项式大小的电路族 a k o ) 、任意多项式p ( ) 、以及任意 q 1 ，q t ，满足： 广，、1 ip r l 氏( q 1 ，q ，q q ，t 。) = 1i - p r l 氏( q ，q ，s ( a ，r ( q ，) ，r ( q ；) ，t 。) ) = lil 数据格式。令e ( ，l c ) 为分组加密算法，其密钥空间、明文空间和密文空间均 为 0 ，1 ) 。使用符号e s ( m 1 ，m 2 ) 表示用密钥s 加密的信息( m l ，m 2 ) ，其 中m t 、m 2 分别是一个k 。、k 2 位串( 满足k 。+ k 2 = k o ) 。用d 表示相对应的解密 算法，密钥s 从密钥空间 0 ，1 ) 知中随机产生。 为在数据库中创建数据表t ，使用者首先从 o ，1 ) 中随机选择两个密钥 s 。、s 2 ，并由使用者保管。使用者从 o ，1 ) 屹中为每个单元t i ，j 随机选择r i ，i 并按 ( t i i ，r i d ) 的格式存储，使用分组加密算法加密存储的( t i ，；，r i ，i ) ，加密密钥 为s ，得到的密文数据存储在t ( i j ) 中；然后把每个单元t i ，i 与所属列的列 号j 按( t i ，j ，j ) 的格式存储，并对存储的值进行加密，加密密钥为s ：，以得到的 密文值作为加密密钥，即隐含等式中的秆) ，依据隐