高级搜索

区块链上基于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]

      李佩丽, 徐海霞. 区块链用户匿名与可追踪技术. 电子与信息学报, 2020, 42(5): 1061-1067.

    2. [2]

      毛秀海, 李凡, 左小磊. DNA数据存储. 电子与信息学报, 2020, 42(6): 1303-1312.

    3. [3]

      许鹏, 方刚, 石晓龙, 刘文斌. DNA存储及其研究进展. 电子与信息学报, 2020, 42(6): 1326-1331.

    4. [4]

      张玉磊, 陈文娟, 张永洁, 张雪微, 王彩芬. 支持关键字搜索的无证书密文等值测试加密方案. 电子与信息学报, 2020, 41(0): 1-7.

    5. [5]

      张玉磊, 文龙, 王浩浩, 张永洁, 王彩芬. 多用户环境下无证书认证可搜索加密方案. 电子与信息学报, 2020, 42(5): 1094-1101.

    6. [6]

      牛淑芬, 谢亚亚, 杨平平, 王彩芬, 杜小妮. 加密邮件系统中基于身份的可搜索加密方案. 电子与信息学报, 2020, 42(7): 1803-1810.

    7. [7]

      陈前斌, 管令进, 李子煜, 王兆堃, 杨恒, 唐伦. 基于深度强化学习的异构云无线接入网自适应无线资源分配算法. 电子与信息学报, 2020, 42(6): 1468-1477.

    8. [8]

      陈前斌, 谭颀, 魏延南, 贺兰钦, 唐伦. 异构云无线接入网架构下面向混合能源供应的动态资源分配及能源管理算法. 电子与信息学报, 2020, 42(6): 1428-1435.

    9. [9]

      李劲松, 彭建华, 刘树新, 季新生. 一种基于线性规划的有向网络链路预测方法. 电子与信息学报, 2020, 41(0): 1-9.

    10. [10]

      唐伦, 曹睿, 廖皓, 王兆堃. 基于深度强化学习的服务功能链可靠部署算法. 电子与信息学报, 2020, 42(0): 1-8.

    11. [11]

      达新宇, 张宏伟, 胡航, 潘钰, 井锦玲. 认知无人机网络中次级链路吞吐量优化研究. 电子与信息学报, 2020, 42(0): 1-8.

    12. [12]

      陈卓, 冯钢, 何颖, 周杨. 运营商网络中基于深度强化学习的服务功能链迁移机制. 电子与信息学报, 2020, 42(0): 1-7.

    13. [13]

      孙军伟, 李智, 王延峰. 基于DNA链置换的三级联组合分子逻辑电路设计. 电子与信息学报, 2020, 42(6): 1401-1409.

    14. [14]

      王延峰, 张桢桢, 王盼如, 孙军伟. 基于DNA链置换的两位格雷码减法器分子电路设计. 电子与信息学报, 2020, 42(0): 1-9.

  • 图 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下载量:  81
  • 文章访问数:  1855
  • HTML全文浏览量:  768
文章相关
  • 通讯作者:  牛淑芬, 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搜索

/

返回文章