http://www.paper.edu.cn -1- 一种基于秘密共享的对称私有信息检索协议1 廖干才1,3，罗守山2,3 1北京邮电大学理学院，北京 (100876) 2北京邮电大学软件学院，北京 (100876) 3西安电子科技大学综合业务网理论及关键技术国家重点实验室，西安 (710071） E-mail：gancailiao@gmail.com 摘 要：对称私有信息检索是安全多方计算协议一个重要的研究方向, 是指在不泄漏各自的私有信息的情况下，参与查询的用户与数据库拥有者完成对数据库的查询操作。将秘密共享和安全多方计算结合, 提出了半诚实模型下的单项对称私有信息检索协议，它能够保证查询者无法通过多次查询获取更多的信息。并将以上协议推广至多项对称私有信息检索协议，并对协议的正确性，安全性，效率进行了分析。 关键词：密码学，对称私有信息检索，安全多方计算，半诚实模型，秘密共享 中图分类号：TN309
1．引言 私有信息检索问题(简称PIR)是指在用户的私有信息不被泄露的情况下，对数据库完成查询. 该协议在文献[1]中被首次扩展为对称私有信息检索(SPIR),即需要满足数据库的私有信息也不能够被泄露. 私有信息检索问题是安全多方计算的一个重要研究方向，有广阔的应用前景,例如,多个公司之间的合作查询、专利数据库查询、股票数据库查询，在商业竞争、军事合作、国家情报部门等多个领域对称私有信息检索问题也普遍存在. 实现私有信息检索的平凡算法是将数据库的存储信息全部发送给用户, 用户在本地查询其所要的信息，但是通讯的数据量太大.目前大多数PIR研究致力于如何设计保护用户的私有信息，而对数据库私有信息的保护关注的比较少。1995 年Chor等[3]首次提出了PIR的
概念,并给了一个有效的解决方案,该方案通过K个互不通信的数据库副本共同协作完成查询,这种通过多个数据库副本实现的PIR的研究方法称作是信息论私有信息检索。自此以后，文献[5] [11-15]在不同的方面对私有信息检索做了不少研究。文献[5]在单数据库模型下，提出了一个可计算的PIR。C. Cachin等人在文献[13]中提出了一个通信复杂度较低的可计算PIR。1998年Yael Gertner等人[10]首次提出了SPIR的概念，并从形式上证明了任何的PIR在一定的条件下都可能转化成SPIR，并保证通信复杂度在同一数量级，轮数也不变。2002年Erica Y. Yang等[2]将秘密共享技术应用到私有信息检索领域，解决了抵抗数据库所有者的恶意攻击
问题。 目前，私有信息检索大都是通过多个互不通信的数据库副本服务器, 允许用户向不同的服务器提交不同的查询, 然后合并这些服务器的应答消息得到最终的查询结果, 整个过程中任何单一的服务器都没有得到关于用户的私有信息.在理论上PIR的研究已经比较成熟，但是在保护数据库隐私方面的研究不是很多，同时关于SPIR的执行协议效率不高。 本文运用秘密共享技术，提出了一种低复杂度的对称私有信息检索协议。本文主要的贡献如下： (1) 提出了一种利用秘密共享技术的对称私有信息检索协议，并给出了安全性证明； (2) 为了提高协议效率和实际应用的需求，将单项对称私有信息检索协议推广到一次能
1本课题得到国家自然科学基金（项目编号：60672132）的资助。 http://www.paper.edu.cn -2- 够查询多条记录的多项对称私有信息检索协议； (3) 在通信复杂度和计算复杂度两方面而言，本文的方案是目前比较高效。 本文结构如下，第二节简单介绍几个基本概念如秘密分享，半诚实模型等；第三节提出了单项对称私有信息检索协议并分析了该协议的正确性，安全性等；第四节将单项对成私有信息检索协议扩展到多项对称私有信息检索协议，并对它的正确性，安全性等作了分析；第五节给出了效率分析；第六节做出结论。
2．基本概念
我们首先简要介绍协议要用到的几个概念： 2.1秘密分享 简单介绍一种研究与应用最广泛秘密分享方案---Shamir(n,t)门限秘密分享方案。 假定n是分享者的数目，t是门限值，p是一个大素数，均在有限域中)(pGF计算。 秘密分发者D给n个分享者iP(1in)≤≤分配份额的过程如下： （1） D随机选择一个)(pGF上的1−t次多项式 ][)(1110xZxaxaaxfptt∈+⋅⋅⋅++=
−
−
使得kfa==)0(0，k是需n个分享者分享的秘密；D对)(xf保密；
（2） D在p
Z中选择n个非零且互不相同的元素12nxxx…、，计算()iiyfx=
（3） 将(,)iixy分配给分享者iP，值ix是公开知道的，iy作为iP
的秘密份额
恢复过程如下： 给定任何t个点),(11llyx、),(22llyx、……、),(ltltyx
，易于计算出秘密k；因为
）（）（）（）（，pxxxyfkljliljtitijjlimodΠ011−−⋅==∑=≠=
同理也容易恢复出多项式其他的系数。
2.2半诚实模型 该模型假定所有参与者都是半诚实参与者，本文方案的安全性均假设参与者(查询者和数据库所有者）为半诚实的.简单地说,所谓半诚实参与者是指参与者在协议执行过程中将不
折不扣地执行协议,但他们也会保留计算的中间结果并且试图推导出其他参与者的输入.
2.3 PIR和SPIR问题描述 假设A是查询者、B是数据库所有者,B存储的数据表示为一个n-bits的字符串123.....nXxxxx=
,查询者A的查询索引为{1,2...}in∈. A对B提出查询请求, 希望从B那里
检索得到ix,但A不希望B知道自己对i
x感兴趣，即不泄漏“i”的信息; 这样的问题就是PIR，
但是若B也不愿意A知道除i
x以外的数据库信息,在这种情况下完成的查询就是SPIR问题。
我们可以将SPIR可以看作是PIR的一种特殊情况，即通讯的双方在都不泄漏自己的信息情况下完成查询，而PIR只是不泄漏查询者信息下完成的查询。 http://www.paper.edu.cn -3- 3．单项对称私有信息检索协议 本文基于信息论私有信息检索的研究方法, 结合秘密共享技术，提出了一个对称私有信息检索方案，并首次提出了一次查询多条记录的对称私有信息检索方案，分析了方案正确性，安全性及效率。
3．1单项对称私有信息检索协议 协议设计的思路，在信息论私有信息检索的模型下，数据库之间不通讯，若查询信息在安全信道下传送，那么数据库无法对查询信息进行拦截，恢复。而数据库方由于不能够通信就必须解决多项式形式上的一致性问题（即在同一次应答中每个数据库使用的是同一个多项式），以及多项式随机性的问题（即每次应答使用不同的多项式）。如果数据库方各自随机的生成多项式这样就不能够满足多项式在形式上的一致性。如果固定数据库的多项式又不能够满足多项式的随机性。 本协议是采取这样的方式解决这个问题，首先用户通过生成特殊形式的多项式把查询信息(i)隐藏在多项式里，然后与数据库记录的Hash值进行线形组合，将多项式随机性转移到
Hash值变化上来。而Hash值的改变，是通过累计变量的自增改变Hash的输入值来改变Hash值的。从而多项式的一致性依赖于累计变量的一致性。具体协议如下： 输入：用户输入i； 输出：在满足对称私有信息检索的条件下，用户得到i
x；
系统参数描述：
12....LSSS：L个拥有相同数据记录且互不通信的数据库服务器。
j：用来记录数据当前被访问的次数，被访问一次自增1。
123.....nXxxxx=
：数据库记录看作是一个长度为n的字符串，一般情况下L远小于n。
()Hx：所有数据库服务器共享的杂凑函数。
2(1)12(1)()**...*LkkkkLgxbxbxbx−
−=+++ (1,2...)kn=
：是所有数据库服务器共享
的n个多项式。 协议中的所有运算都在GF(q)上进行。 协议的执行过程如下： 1． 用户生成n个（L-1）阶多项式。即： 2(1)12(1)()()**...*LkkkkLfxikaxaxax−
−=++++
如果k=i;则i(k)=1;否则，i(k)=0。多项式系数随机生成。 2． 为每一个)(xfk从GF(q)中任意选取L个互不相同的非零数12,,......Lzzz。对c=1,2....L计算)(),....,(),(
21cncczfzfzf
，并保存cz。
3． 对c=1,2....L，用户把)(),....,(),(21cncczfzfzf和cz发送给cS数据库服务器。 4． cS数据库服务器计算
()mod1()(()*()*())nckckkckjnFzfzxgzHx
k+
=
=+∑发送给用户。
5． 用户收集所有的返回信息，选取其中L个返回信息。运用秘密分享方案求出(0)F即
为检索的记录i
x。