单断言的密文区间检索方案的安全分析

《单断言的密文区间检索方案的安全分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、单断言的密文区间检索方案的安全分析摘要：为保护用户数据隐私，用户通常将敏感数据加密后外包存储在半可信的服务器上。为防止泄露用户隐私信息，蔡克等（蔡克，张敏，冯登国.基于单断言的安全的密文区间检索[J].计算机学报，2011，34（11）：2093-2103）首次提出单断言密文区间检索方案，而之前在密文数据上的区间检索都通过多次断言实现。使用三角函数关系和矩阵理论，通过密文区间索引直接产生敏感数据的排列信息，证明该单断言密文检索方案不是唯密文安全的。为避免这种安全缺陷，通过引入随机元素构造了安全的单断言密文检索改进方案，并分析了改进方案的复杂性。关键词：密文检

2、索；区间检索；区间索引；区间陷门；密码分析0引言7近年来，Google、Salesforce、Amazon等数据服务公司均发生过外包数据泄密事件[1]。为保护数据隐私，用户通常将数据加密后外包存储在半可信的服务提供商，但敏感数据的密文区间检索可能泄露用户隐私信息。目前密文区间检索主要采用为敏感数据建立区间索引的方法实现。由于区间索引包含了敏感数据的相关信息，区间索引外包增大了敏感数据外泄的可能。目前设计密文区间检索方案主要有两种方法：1）基于保序加密的密文区间检索方案[2-3]。这类方案的区间索引保留了敏感数据的大小排列性质，存在服务器可以直接获得敏感数据的

3、大小排列信息问题，安全隐患较大。2）基于敏感数据分桶的密文区间检索方案[4-7]。这类方案的区间索引包含了敏感数据的划分，存在服务器可以直接获得敏感数据的归并特征问题，使得服务器易于获得敏感数据的分布规律。1相关工作为实现密文区间检索，现有密文区间检索方案都需要服务器对区间索引实行多次断言。密文区间检索断言次数越多，计算效率越低，而且泄露敏感数据的信息也越多，安全隐患较大。为提升安全性，文献[8]通过编码方式实现密文区间检索，但该方案在敌手得到多个区间陷门时，敌手还是可以获得敏感数据的排列信息，仍然存在安全性缺陷。Wang等[9]构造了加密云数据上安全的关键

4、字排序方案；在公钥密码环境下，Boneh等[10]和Shi等[11]设计密文数据上的区间检索方案；为了实行更复杂的密文操作，Boldyreva等[3，12]设计了密文上次序保持的对称加密方案；Wong等[13]提出新的非对称数量积保持方案，该方案支持在密文上计算k最接近邻域。7针对现有密文区间检索方案存在的安全问题，蔡克等在文献[1]中首次提出了单断言的密文区间检索方案（以下简称蔡克方案），并证明该方案是唯密文安全的，即该方案不会泄露敏感数据大小排列信息和归并特征信息，而且使用文献[13]中矩阵相乘方法对区间索引和区间陷门进行保护。本文主要分析蔡克方案的安全

5、性。研究思路如下：首先利用两个密文区间索引产生的行列式大小反映了敏感数据的大小信息，从而证明蔡克方案存在通过区间索引泄露敏感数据大小排列信息的安全缺陷；然后，通过区间陷门获取密钥和敏感数据的部分信息，证明蔡克方案中区间陷门存在安全隐患；最后，为避免蔡克方案的安全缺陷，设计了单断言密文区间检索改进方案。为描述简单，本文使用蔡克方案中同样符号表示。设λ为安全参数，[n]为集合[n]={1，2，…，n}。与文献[1]一样，本文在分析蔡克方案安全性和设计改进方案时也使用实数。由标准计算机数字表示方法可知，方案实现时各个参数值宜取长度为λ的多项式的近似有理数。5结语使

6、用三角函数关系和矩阵理论，本文证明单断言密文检索方案[1]不是唯密文安全的。为避免这种安全缺陷，本文通过引入随机元素构造了安全的单断言密文检索改进方案。改进方案与原方案[1]相比，存储空间和计算时间复杂性都略有增加，但方案的安全性得到较大提升。参考文献：7[1]CAIK，ZHANGM，FENGD.Securerangequerywithsingleassertiononencrypteddata[J].ChineseJournalofComputers，2011，34（11）：2093-2103.（蔡克，张敏，冯登国.基于单断言的安全的密文区间检索[J].计

7、算机学报，2011，34（11）：2093-2103.）[2]AGRAWALR，KIERNANJ，SRIKANTR，etal.Oderpreservingencryptionfornumericdata[C]//SIGMOD04：Proceedingsofthe2004ACMSIGMODInternationalConferenceonManagementofData.NewYork：ACM，2004：563-574.[3]BOLDYREVAA，CHENETTEN，LEEY，etal.Orderpreservingsymmetricencryption[C]

8、//EUROCRYPT09：Proceedingso