高级搜索

基于f-mOPE的数据库密文检索方案

周艺华 吉文 杨宇光

引用本文: 周艺华, 吉文, 杨宇光. 基于f-mOPE的数据库密文检索方案[J]. 电子与信息学报, 2019, 41(8): 1793-1799. doi: 10.11999/JEIT180805 shu
Citation:  Yihua ZHOU, Wen JI, Yuguang YANG. Database Ciphertext Retrieval Scheme Based on f-mOPE[J]. Journal of Electronics and Information Technology, 2019, 41(8): 1793-1799. doi: 10.11999/JEIT180805 shu

基于f-mOPE的数据库密文检索方案

    作者简介: 周艺华: 男,1969年生,副教授,研究方向为网络与信息安全;
    吉文: 男,1993年生,硕士,研究方向为信息安全;
    杨宇光: 女,1976年生,教授,研究方向为信息安全及信息安全与其他学科的交叉学科
    通讯作者: 吉文,jwnba24@163.com
  • 基金项目: 国家自然科学基金(61572053)

摘要: 在云数据库环境下,为保证云存储数据的安全性,通常将数据加密存储。针对加密存储数据查询开销大,不支持密文排序,查询等缺点,该文提出一种 f-mOPE数据库密文检索方案。该方案基于可变保序编码(mOPE),采用二叉排序树数据结构思想,生成明文一一对应的保序编码;基于AES加密方案将数据明文转化为密文存储;采用改进的部分同态加密算法提升保序加密方案的安全性。通过安全性分析及实验结果表明,该方案在保证数据隐私的基础上,不但能抵御统计型攻击,而且能够有效地降低服务器计算开销,提高数据库处理效率。

English

    1. [1]

      GABEL M and MECHLER J. Secure database outsourcing to the cloud: Side-channels, counter-measures and trusted execution[C]. The 2017 IEEE 30th International Symposium on Computer-Based Medical Systems, Thessaloniki, Greece, 2017: 799–804.

    2. [2]

      陆海宁. 可隐藏搜索模式的对称可搜索加密方案[J]. 信息网络安全, 2017(1): 38–42. doi: 10.3969/j.issn.1671-1122.2017.01.006
      LU Haining. Searchable symmetric encryption with hidden search pattern[J]. Netinfo Security, 2017(1): 38–42. doi: 10.3969/j.issn.1671-1122.2017.01.006

    3. [3]

      DEMERTZIS I and PAPAMANTHOU C. Fast searchable encryption with tunable locality[C]. 2017 ACM International Conference on Management of Data, Chicago, Illinois, USA, 2017: 1053–1067.

    4. [4]

      PENG Tianyue, LIN Yaping, YAO Xin, et al. An efficient ranked multi-keyword search for multiple data owners over encrypted cloud data[J]. IEEE Access, 2018, 6: 21924–21933. doi: 10.1109/ACCESS.2018.2828404

    5. [5]

      AGRAWAL R, KIERNAN J, SRIKANT R, et al. Order preserving encryption for numeric data[C]. 2004 ACM SIGMOD International Conference on Management of Data, Paris, France, 2004: 563–574.

    6. [6]

      BOLDYREVA A, CHENETTE N, LEE Y, et al. Order-preserving symmetric encryption[C]. The 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, 2009: 224–241.

    7. [7]

      LIU Zheli, CHEN Xiaofeng, YANG Jun, et al. New order preserving encryption model for outsourced databases in cloud environments[J]. Journal of Network and Computer Applications, 2016, 59: 198–207. doi: 10.1016/j.jnca.2014.07.001

    8. [8]

      TERANISHI I, YUNG M, and MALKIN T. Order-preserving encryption secure beyond one-wayness[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Taiwan, China, 2014: 42–61.

    9. [9]

      MAVROFORAKIS C, CHENETTE N, O’NEILL A, et al. Modular order-preserving encryption, revisited[C]. 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Australia, 2015: 763–777.

    10. [10]

      ZHANG Huanguo, HAN Wenbao, LAI Xuejia, et al. Survey on cyberspace security[J]. Science China Information Science, 2015, 58(11): 1–43. doi: 10.1007/s11432-015-5433-4

    11. [11]

      LIU Dongxi and WANG Shenlu. Programmable order-preserving secure index for encrypted database query[C]. The 2012 IEEE 5th International Conference on Cloud Computing, Honolulu, USA, 2012: 502–509.

    12. [12]

      LIU Dongxi and WANG Shenlu. Nonlinear order preserving index for encrypted database query in service cloud environments[J]. Concurrency and Computation: Practice and Experience, 2013, 25(13): 1967–1984. doi: 10.1002/cpe.2992

    13. [13]

      张成果. CryptDB密文数据库系统研究[D]. [硕士论文], 南京邮电大学, 2017.
      ZHANG Chengguo. The research of cryptDB encrypted database system[D]. [Master dissertation], Nanjing University of Posts and Telecommunications, 2017.

    14. [14]

      POPA R A, REDFIELD C M S, ZELDOVICH N, et al. processing queries on an encrypted database[J]. Communications of the ACM, 2012, 55(9): 103–111. doi: 10.1145/2330667.2330691

    15. [15]

      POPA R A, LI F H, and ZELDOVICH N. An ideal-security protocol for order-preserving encoding[C]. 2013 IEEE Symposium on Security and Privacy, Berkeley, USA, 2013: 463–477.

    16. [16]

      VAN DIJK M, GENTRY C, HALEVI S, et al. Fully homomorphic encryption over the integers[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, 2010: 24–43.

    1. [1]

      张玉磊, 刘文静, 刘祥震, 张永洁, 王彩芬. 基于授权的多服务器可搜索密文策略属性基加密方案. 电子与信息学报, 2019, 41(8): 1808-1814.

    2. [2]

      马华, 党乾龙, 王剑锋, 刘振华. 基于属性加密的高效密文去重和审计方案. 电子与信息学报, 2019, 41(2): 355-361.

    3. [3]

      李付鹏, 刘敬彪, 王光义, 王康泰. 基于混沌集的图像加密算法. 电子与信息学报, 2019, 41(0): 1-7.

    4. [4]

      田子建, 贺方圆. 一种基于分布式压缩感知的矿井目标指纹数据库建立方法. 电子与信息学报, 2019, 41(10): 2450-2456.

    5. [5]

      陈艳浩, 刘中艳, 周丽宴. 基于差异混合掩码与混沌Gyrator变换的光学图像加密算法. 电子与信息学报, 2019, 41(4): 888-895.

    6. [6]

      钟兆根, 于柯远, 孙雪丽. 基于序贯蒙特卡罗的非同步长码DS-CDMA信号扩频码及信息序列联合估计. 电子与信息学报, 2019, 41(6): 1365-1373.

    7. [7]

      牛淑芬, 王金风, 王伯彬, 贾向东, 杜小妮. 区块链上基于B+树索引结构的密文排序搜索方案. 电子与信息学报, 2019, 41(10): 2409-2415.

    8. [8]

      解培中, 孙锐, 李汀. 基于连续干扰消除的毫米波MIMO系统混合预编码算法. 电子与信息学报, 2019, 41(2): 409-416.

    9. [9]

      陈容, 陈岚, WAHLAArfan Haider. 基于公式递推法的可变计算位宽的CRC设计与实现. 电子与信息学报, 2019, 41(0): 1-7.

    10. [10]

      寇广, 王硕, 张达. 基于深度堆栈编码器和反向传播算法的网络安全态势要素识别. 电子与信息学报, 2019, 41(9): 2187-2193.

    11. [11]

      罗瑜, 张珍珍. 一种方向插值预测变长编码的帧存有损压缩算法. 电子与信息学报, 2019, 41(10): 2495-2500.

    12. [12]

      吕增威, 魏振春, 韩江洪, 孙仁浩, 夏成凯. 基于多目标优化的无线传感器网络移动充电及数据收集算法. 电子与信息学报, 2019, 41(8): 1877-1884.

    13. [13]

      王昊, 徐晓男, 马启明. 一种利用少快拍数据的宽带干扰鲁棒性抑制算法. 电子与信息学报, 2019, 41(4): 851-857.

    14. [14]

      王守华, 陆明炽, 孙希延, 纪元法, 胡丁梅. 基于无迹卡尔曼滤波的iBeacon/INS数据融合定位算法. 电子与信息学报, 2019, 41(9): 2209-2216.

    15. [15]

      马友, 贾树泽, 赵现纲, 冯小虎, 范存群, 朱爱军. 基于张量分解的卫星遥测缺失数据预测算法. 电子与信息学报, 2019, 41(0): 1-7.

    16. [16]

      王莉, 曹一凡, 杜高明, 刘冠宇, 王晓蕾, 张多利. 一种低延迟的3维高效视频编码中深度建模模式编码器. 电子与信息学报, 2019, 41(7): 1625-1632.

    17. [17]

      王练, 张贺, 张昭, 张勋杨. 基于自适应随机线性网络编码的优先级调度方案. 电子与信息学报, 2019, 41(8): 1861-1868.

    18. [18]

      周洋, 吴佳忆, 陆宇, 殷海兵. 面向三维高效视频编码的深度图错误隐藏. 电子与信息学报, 2019, 41(0): 1-8.

    19. [19]

      张瑞, 占友, 钱权. 一种新的基于虚拟队列的无线多播网络编码调度策略. 电子与信息学报, 2019, 41(0): 1-8.

    20. [20]

      牛淑芬, 杨喜艳, 王彩芬, 田苗, 杜小妮. 基于异构密码系统的混合群组签密方案. 电子与信息学报, 2019, 41(5): 1180-1186.

  • 图 1  保密数据分块处理方案

    图 2  平衡因子$k$对重平衡次数影响图

    图 3  mOPE方案和f-mOPE方案插入元素时间消耗对比

    图 4  元素个数与重平衡次数关系

    图 5  检索执行时间对比

    表 1  公式符号说明

     $\lambda $:安全参数;
     $\rho $:噪声长度,为抵抗暴力攻击$\rho = \omega (\lg \lambda )$;
     $\eta $:私钥二进制长度, $\eta $满足$\eta \ge \rho \varTheta (\lambda {\lg ^2}\lambda )$,这样才能保证压缩   解密可行;
     $\gamma $:公钥二进制长度,为抵抗格攻击,$\gamma = \omega ({\eta ^2}\lg \lambda )$;
     $\tau $:公钥个数,$\tau \ge \gamma + \omega (\lg \lambda )$,文中需要的公钥个数为$2\sqrt \tau $;
    下载: 导出CSV

    表 2  序号与保序编码对应关系表

    序号12345678
    保序
    编码
    [000]
    1=1
    [00]
    10=2
    [001]
    1=3
    [0]
    100=4
    [010]
    1=5
    [01]
    10=6
    [011]
    1=7
    [1]
    000=8
    [100]
    1=9
    [10]
    10=10
    [1]
    011=11
    [1]
    100=12
    [110]
    1=13
    [11]
    10=14
    [1111]
    =15
    下载: 导出CSV

    表 3  算法1: 保序编码调整算法

     符号定义:ord_num:数据的序号;index:数据十进制编码
     //将所有的数据排序后存入临时表tmp中
     insertIntoTmpTable(datas)
     h = lg(n)+1;
     index = 2(n-(2h-1 -1))+1;
     count = index-1;
     //更新临时表中数据索引编码
     if(ord_num > count):
        foreach():
         updateTmpTable(ord_num):
          index = ord_num + (ord_num-count);
        update tmp set index = index where ord_num=ord_num;
     else:
        foreach():
         update tmp set index = ord_num where ord_num=ord_num;
     //将临时表重平衡结果更新至数据表中,需要将临时表中index转换为二进制并加入子树标识,如式(7)描述
     foreach(data):
        update OPE_Table A inner join tmp B on A.ciper = B.ciper set A.ord_code = B.index;
    下载: 导出CSV

    表 4  算法2: 数据插入及检索算法

     插入元素算法: 查找元素算法:
     key,IV = generateInitAttr();//初始化加密参数 //确定子树编码
     //加密明文 treeIndex = partitionTree(plainText);
     ciphertext = encryptData(plainText); //查询子树根节点
     //构建保序编码 rootNode = searchTreeRootNode(treeIndex);
     foreach(plainTexts): //遍历子树寻找所有符合条件密文
       //确定子树编码 datalist = search(rootNode,tree,plainText):
       treeIndex = partitionTree(plainText); foreach(datalist)://解密所有密文
       //数据模糊化处理   data = decrypt(value,key);
       fuzzyData=FuzzyData(plainText); return datalist;
       //与服务端交互确定数据保序索引
       code_index=connectToServer(fuzzyData,treeIndex);
       //插入数据
       insertData(fuzzyData,code_index);
    下载: 导出CSV

    表 5  DGHV部分同态加密方案与本文改进方案对比

    DGHV部分同态加密方案本文改进部分同态加密方案
    加密效率1次加密1 bit明文1次加密$n$bit明文
    安全性$q$是对外开放的,那么如果 $pq$ 作为公钥,很容易计算出私钥$p$的值。加入一些明文为0加密得到的密文$\{ {x_i}:{x_i} = {2^n}{r_i} + p{q_i}\} $,将这些密文组成一个集合$s$,以$\sum\nolimits_{1 \le i,j \le \sqrt \tau } {{b_{i,j}}{x_{i,0}}} {x_{j,1}}$作为公钥,任意选取集合元素${x_i} \in S$加入运算,因为其明文都是0,不会改变加密结果,并且能够提高算法安全性。在运算过程中只需要将${2^n}$上传到服务器即可,把${2^n}\sum\nolimits_{1 \le i,j \le \sqrt \tau } {{b_{i,j}}{x_{i,0}}{x_{j,1}}} $作为公钥,即使获取${2^n}$也无法获取密钥$p$
    复杂度该方案公钥尺寸约为$O({\lambda ^{10}})$该方案中,参数取$\rho = \lambda $, $\eta = O({\lambda ^2})$,$\gamma = O({\lambda ^5})$,$\tau = O({\lambda ^3})$,所以该部分同态加密公钥尺寸为$r + \tau (\lambda + \eta ) = O({\lambda ^5})$
    下载: 导出CSV

    表 6  mOPE与f-mOPE查询开销对比

    数据个数mOPE查询开销f-mOPE查询开销
    500810
    50001110
    100001210
    200001310
    500001510
    下载: 导出CSV

    表 7  mOPE与f-mOPE时间复杂度比较

    时间复杂度mOPEf-mOPE
    计算OPE编码$O(\lg n)$$O(\lg n)$
    调整编码最好情况O(1)
    最坏情况O(n)
    O(1)
    检查是否平衡/需要调整最好情况O(1)
    最坏情况O(n)
    最好情况O(n)
    最坏情况O(n)
    下载: 导出CSV
  • 加载中
图(5)表(7)
计量
  • PDF下载量:  29
  • 文章访问数:  433
  • HTML全文浏览量:  213
文章相关
  • 通讯作者:  吉文, jwnba24@163.com
  • 收稿日期:  2018-08-16
  • 录用日期:  2019-01-29
  • 网络出版日期:  2019-02-21
  • 刊出日期:  2019-08-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章