高级搜索

区块链上基于B+树索引结构的密文排序搜索方案

牛淑芬 王金风 王伯彬 贾向东 杜小妮

引用本文: 牛淑芬, 王金风, 王伯彬, 贾向东, 杜小妮. 区块链上基于B+树索引结构的密文排序搜索方案[J]. 电子与信息学报, 2019, 41(10): 2409-2415. doi: 10.11999/JEIT190038 shu
Citation:  Shufen NIU, Jinfeng WANG, Bobin WANG, Xiangdong JIA, Xiaoni DU. Ciphertext Sorting Search Scheme Based on B+ Tree Index Structure on Blockchain[J]. Journal of Electronics and Information Technology, 2019, 41(10): 2409-2415. doi: 10.11999/JEIT190038 shu

区块链上基于B+树索引结构的密文排序搜索方案

    作者简介: 牛淑芬: 女,1976年生,博士,副教授,研究方向为云计算、大数据和区块链上的数据安全;
    王金风: 女,1992年生,硕士,研究方向为区块链上的数据检索;
    王伯彬: 男,1992年生,硕士,研究方向为车联网隐私保护;
    贾向东: 男,1971年生,博士,教授,研究方向为无线传感器;
    杜小妮: 女,1972年生,博士,教授,研究方向为流密码和分组密码
    通讯作者: 牛淑芬,sfniu76@nwnu.edu.cn
  • 基金项目: 国家自然科学基金资助项目(61562077, 61462077, 61662071, 61662069),西北师范大学青年教师科研提升计划(NWNU-LKQN-14-7),甘肃省杰出青年项目(1308RJDA007)

摘要: 为了克服云存储不可信及云存储中密文检索效率低的问题,该文提出区块链上基于B+树的密文排序可搜索加密方案。该方案结合区块链技术解决了在互不了解的多方建立可靠信任的问题;使用向量空间模型降低了文本的复杂性实现了高效的文本检索系统;采用B+树的索引结构提高了区块链上密文交易的检索速度;利用加权统计(TF-IDF)算法实现了多关键词查询结果的排序。在随机预言机模型下,证明该方案是适应性不可区分安全的,通过效率对比分析,表明该方案在区块链上实现了高效的密文检索。

English

    1. [1]

      SONG D X, WAGNER D, and PERRIG A. Practical techniques for searches on encrypted data[C]. 2000 IEEE Symposium on Security and Privacy, Berkeley, USA, 2000: 44–55.

    2. [2]

      CURTMOLA R, GARAY J, KAMARA S, et al. Searchable symmetric encryption: Improved definitions and efficient constructions[C]. The 13th ACM Conference on Computer and Communications Security, Alexandria, USA, 2006: 79–88.

    3. [3]

      GOLLE P, STADDON J, and WATERS B. Secure conjunctive keyword search over encrypted data[C]. The 2nd International Conference on Applied Cryptography and Network Security, Yellow Mountain, 2004: 31–45.

    4. [4]

      MA Mimi, HE Debiao, KHAN M K, et al. Certificateless searchable public key encryption scheme for mobile healthcare system[J]. Computers & Electrical Engineering, 2018, 65: 413–424.

    5. [5]

      HUANG Qiong and LI Hongbo. An efficient public-key searchable encryption scheme secure against inside keyword guessing attacks[J]. Information Sciences, 2017, 403-404: 1–14. doi: 10.1016/j.ins.2017.03.038

    6. [6]

      XIA Zhihua, WANG Xinhui, SUN Xingming, et al. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(2): 340–352. doi: 10.1109/tpds.2015.2401003

    7. [7]

      杨旸, 刘佳, 蔡圣暐, 等. 云计算中保护数据隐私的快速多关键词语义排序搜索方案[J]. 计算机学报, 2018, 41(6): 1346–1359. doi: 10.11897/SP.J.1016.2018.01346
      YANG Yang, LIU Jia, CAI Shengwei, et al. Fast multi-keyword semantic ranked search in cloud computing[J]. Chinese Journal of Computers, 2018, 41(6): 1346–1359. doi: 10.11897/SP.J.1016.2018.01346

    8. [8]

      NAKAMOTO S. Bitcoin: A peer-to-peer electronic cash system[EB/OL]. https://bitcoin.org/en/bitcoin-paper, 2016.

    9. [9]

      Healthbank[EB/OL]. http://www.healthbank.coop, 2016.

    10. [10]

      LVAN D. Moving toward a blockchain-based method for the secure storage of patient records[EB/OL]. https://www.healthit.gov/sites/default/files/9-16-drew_ivan_20160804_blockchain_for_healthcare_final.pdf, 2016.

    11. [11]

      ANDRYCHOWICZ M, DZIEMBOWSKI S, MALINOWSKI D, et al. Fair two-party computations via Bitcoin deposits[C]. 2014 International Conference on Financial Cryptography and Data Security, Christ Church, Barbados, 2014: 105–121.

    12. [12]

      DAGHER G G, MOHLER J, MILOJKOVIC M, et al. Ancile: Privacy-preserving framework for access control and interoperability of electronic health records using blockchain technology[J]. Sustainable Cities and Society, 2018, 39: 283–297. doi: 10.1016/j.scs.2018.02.014

    13. [13]

      XIA Qi, SIFAH E B, SMAHI A, et al. BBDS: Blockchain-based data sharing for electronic medical records in cloud environments[J]. Information, 2017, 8(2): 44. doi: 10.3390/info8020044

    14. [14]

      LI Huige, TIAN Haibo, ZHANG Fangguo, et al. Blockchain-based searchable symmetric encryption scheme[J]. Computers & Electrical Engineering, 2019, 73: 32–45. doi: 10.1016/j.compeleceng.2018.10.015

    15. [15]

      ZHANG Yinghui, DENG R H, SHU Jiangang, et al. TKSE: Trustworthy keyword search over encrypted data with two-side[J]. IEEE Access, 2018, 6: 31077–31087. doi: 10.1109/access.2018.2844400

    16. [16]

      王尚平, 刘利军, 张亚玲. 可验证的基于词典的可搜索加密方案[J]. 软件学报, 2016, 27(5): 1301–1308. doi: 10.13328/j.cnki.jos.004912
      WANG Shangping, LIU Lijun, and ZHANG Yaling. Verifiable dictionary-based searchable encryption scheme[J]. Journal of Software, 2016, 27(5): 1301–1308. doi: 10.13328/j.cnki.jos.004912

    1. [1]

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

    2. [2]

      曹素珍, 王斐, 郎晓丽, 汪锐, 刘雪艳. 基于无证书的多方合同签署协议. 电子与信息学报, 2019, 41(0): 1-8.

    3. [3]

      张玉磊, 刘祥震, 郎晓丽, 张永洁, 陈文娟, 王彩芬. 云存储环境下多服务器的密钥聚合可搜索加密方案. 电子与信息学报, 2019, 41(3): 674-679.

    4. [4]

      张天骐, 张华伟, 刘董华, 李群. 基于区域增长校正的频域盲源分离排序算法. 电子与信息学报, 2019, 41(3): 580-587.

    5. [5]

      徐金甫, 吴缙. 一种基于动态环形振荡器物理不可克隆函数统计模型的频率排序算法. 电子与信息学报, 2019, 41(3): 717-724.

    6. [6]

      苏玉泽, 孟相如, 康巧燕, 韩晓阳. 核心链路感知的可生存虚拟网络链路保护方法. 电子与信息学报, 2019, 41(7): 1587-1593.

    7. [7]

      邹虹, 高毅爽, 闫俊杰. 带有卸载时延感知的边缘云增强FiWi网络节能机制. 电子与信息学报, 2019, 41(2): 394-401.

    8. [8]

      张骥先, 谢宁, 张学杰, 李伟东. 基于监督学习的可信云计算资源拍卖机制研究. 电子与信息学报, 2019, 41(5): 1243-1250.

    9. [9]

      孙远, 李春国, 黄永明, 杨绿溪. 基于带缓存的云接入网络最优能效设计. 电子与信息学报, 2019, 41(7): 1525-1532.

    10. [10]

      孙瑾, 王小静, 王尚平, 任利利. 支持属性撤销的可验证多关键词搜索加密方案. 电子与信息学报, 2019, 41(1): 53-60.

    11. [11]

      曹素珍, 郎晓丽, 刘祥震, 张玉磊, 王斐. 抗关键词猜测的授权可搜索加密方案. 电子与信息学报, 2019, 41(9): 2180-2186.

    12. [12]

      闫贺, 王珏, 黄佳, 王旭东. 基于二维速度搜索的星载SAR运动目标聚焦算法研究. 电子与信息学报, 2019, 41(6): 1287-1293.

    13. [13]

      伊鹏, 谢记超, 张震, 谷允捷, 赵丹. 抗侧信道攻击的服务功能链部署方法. 电子与信息学报, 2019, 41(0): 1-9.

    14. [14]

      陈曦, 张坤. 一种基于树增强朴素贝叶斯的分类器学习方法. 电子与信息学报, 2019, 41(8): 2001-2008.

    15. [15]

      王汝言, 徐宁宁, 吴大鹏. 能耗和时延感知的虚拟化云无线接入网络资源分配机制. 电子与信息学报, 2019, 41(1): 83-90.

    16. [16]

      冯霞, 唐菱, 卢敏. 基于禁忌搜索算法的机场外航服务人员班型生成研究. 电子与信息学报, 2019, 41(0): 1-7.

    17. [17]

      唐伦, 魏延南, 马润琳, 贺小雨, 陈前斌. 虚拟化云无线接入网络下基于在线学习的网络切片虚拟资源分配算法. 电子与信息学报, 2019, 41(7): 1533-1539.

    18. [18]

      路新华, MANCHÓNCarles Navarro, 王忠勇, 张传宗. 大规模MIMO系统上行链路时间-空间结构信道估计算法. 电子与信息学报, 2019, 41(0): 1-7.

    19. [19]

      卢昱, 刘益岑, 李玺, 陈兴凯, 乔文欣, 陈立云. 面向软件定义网络的服务功能链优化部署算法研究. 电子与信息学报, 2019, 41(1): 74-82.

    20. [20]

      陈前斌, 杨友超, 周钰, 赵国繁, 唐伦. 基于随机学习的接入网服务功能链部署算法. 电子与信息学报, 2019, 41(2): 417-423.

  • 图 1  区块链系统检索图

    图 2  搜索相关度排序

    表 1  B+树算法

     算法1 BuildIndexTree(${{I} }$)
     if($u$是叶子节点)then
     将密文交易标识符$\rm{TXid} $放到叶子节点,并计算叶子节点的${\text{D}}$的
    向量
     return
     else
     根据新节点的位置,向下查找该节点插入的子节点$\rm{ul} $
     if(节点$\rm{ul} $的数值为最大)then
     对节点进行分割,重新确定向下插入的子节点$\rm{ul} $
     end if
    下载: 导出CSV

    表 2  效率对比分析

    方案$\left| {{\rm{Trapdoor}} } \right|$$\left| {{\rm{SearchComplexity}} } \right|$公平性搜索结果是否排序
    文献[6]$O\left( {{m^2}} \right)$$O\left( {{\varphi _m}\log n} \right)$
    文献[14]$O\left( 1 \right)$$O\left( {\left| {D\left( w \right)} \right|} \right)$
    文献[16]$O\left( 1 \right)$$O\left( {\left| {D\left( w \right)} \right|} \right)$
    本文方案$O\left( {{m^2}} \right)$${O}\left( { {\varphi _m}{ {\log }_{\left\lceil {\tfrac{m}{2} } \right\rceil } }\tfrac{ {n + 1} }{2} } \right)$
    下载: 导出CSV
  • 加载中
图(2)表(2)
计量
  • PDF下载量:  32
  • 文章访问数:  482
  • HTML全文浏览量:  341
文章相关
  • 通讯作者:  牛淑芬, sfniu76@nwnu.edu.cn
  • 收稿日期:  2019-01-15
  • 录用日期:  2019-06-05
  • 网络出版日期:  2019-06-12
  • 刊出日期:  2019-10-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章