高级搜索

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

      黄海平, 杜建澎, 戴华, 王汝传. 一种基于云存储的多服务器多关键词可搜索加密方案. 电子与信息学报, 2017, 39(2): 389-396.

    2. [2]

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

    3. [3]

      刘通, 唐伦, 何小强, 陈前斌. 融合区块链与雾计算系统中基于网络时延和资源管理的优化任务卸载方案. 电子与信息学报, 2020, 42(0): 1-6.

    4. [4]

      纪倩, 杨超, 赵文红, 张俊伟. 一种新的云存储数据容错存储方式检验方法. 电子与信息学报, 2016, 38(10): 2640-2646.

    5. [5]

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

    6. [6]

      刘振华, 周佩琳, 段淑红. 支持关键词搜索的属性代理重加密方案. 电子与信息学报, 2018, 40(3): 683-689.

    7. [7]

      赵志远, 朱智强, 王建华, 孙磊. 云存储环境下无密钥托管可撤销属性基加密方案研究. 电子与信息学报, 2018, 40(1): 1-10.

    8. [8]

      朱小玉, 刘琴, 王国军. 云存储中一种支持可验证的模糊查询加密方案. 电子与信息学报, 2017, 39(7): 1741-1747.

    9. [9]

      刘建, 王会梅, 鲜明, 黄昆. 云存储中一种抗窃听攻击的弱安全再生码. 电子与信息学报, 2014, 36(5): 1221-1228.

    10. [10]

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

    11. [11]

      赵志远, 王建华, 徐开勇. 定长密文且快速解密的分布式属性基加密方案研究. 电子与信息学报, 2017, 39(11): 2724-2732.

    12. [12]

      陈兰香. 一种基于同态Hash的数据持有性证明方法. 电子与信息学报, 2011, 33(9): 2199-2204.

    13. [13]

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

    14. [14]

      王光波, 王建华. 基于属性加密的云存储方案研究. 电子与信息学报, 2016, 38(11): 2931-2939.

    15. [15]

      张磊, 潘泉, 张洪才, 戴冠中. 基于二叉树搜索的小波变换信号压缩. 电子与信息学报, 2002, 24(5): 615-620.

    16. [16]

      崔大富, 李亚亭, 王保国, 蔡金娥, 范杰. 一兆比特汉字信息存储管. 电子与信息学报, 1984, 6(1): 64-69.

    17. [17]

      隋厚堂. 存储器的编码增益. 电子与信息学报, 1996, 18(5): 479-486.

    18. [18]

      郁滨, 冯力, 龚碧, 孔志印. 多密级交互存储控制器设计与实现. 电子与信息学报, 2018, 40(1): 18-24.

    19. [19]

      田新远, 董戈, 朱敏慧. 波形存储LFM信号源设计误差分析. 电子与信息学报, 2005, 27(8): 1240-1243.

    20. [20]

      曹蕾, 张欣, 杨大成. 频域均衡联合基于能量排序的部分并行干扰删除检测算法. 电子与信息学报, 2008, 30(6): 1416-1419.

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

/

返回文章