高级搜索

基于容错学习的属性基加密方案的具体安全性分析

赵建 高海英 胡斌

引用本文: 赵建, 高海英, 胡斌. 基于容错学习的属性基加密方案的具体安全性分析[J]. 电子与信息学报, 2019, 41(8): 1779-1786. doi: 10.11999/JEIT180824 shu
Citation:  Jian ZHAO, Haiying GAO, Bin HU. Analysis Method for Concrete Security of Attribute-based Encryption Based on Learning With Errors[J]. Journal of Electronics and Information Technology, 2019, 41(8): 1779-1786. doi: 10.11999/JEIT180824 shu

基于容错学习的属性基加密方案的具体安全性分析

    作者简介: 赵建: 男,1989年生,博士生,研究方向为公钥密码的设计与分析;
    高海英: 女,1978年生,教授,博士生导师,研究方向为密码算法的设计与分析;
    胡斌: 男,1971年生,教授,博士生导师,研究方向为密码算法的设计与分析
    通讯作者: 赵建,back_zj@126.com
  • 基金项目: 国家自然科学基金(61702548, 61601515),河南省基础与前沿技术课题(162300410192)

摘要: 为了能全面研究基于容错学习(LWE)的属性基加密(ABE)方案的安全性,考察其抵抗现有攻击手段的能力,在综合考虑格上算法和方案噪声扩张对参数的限制后,利用已有的解决LWE的算法及其可用程序模块,该文提出了针对基于LWE的ABE方案的具体安全性分析方法。该方法可以极快地给出满足方案限制要求的具体参数及方案达到的安全等级,此外,在给定安全等级的条件下,该方法可以给出相应的具体参数值。最后,利用该方法分析了4个典型的基于LWE的属性基加密方案的具体安全性。实验数据表明,满足一定安全等级的基于LWE的属性基方案的参数尺寸过大,还无法应用到实际中。

English

    1. [1]

      SAHAI A and WATERS B. Fuzzy identity-based encryption[C]. The 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 2005: 457–473. doi: 10.1007/11426639_27.

    2. [2]

      AJTAI M. Generating hard instances of lattice problems (extended abstract)[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, Pennsylvania, USA, 1996: 99–108. doi: 10.1145/237814.237838.

    3. [3]

      REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]. The 37th Symposium on Theory of Computing, Baltimore, USA, 2005: 84–93. doi: 10.1145/1060590.1060603.

    4. [4]

      LYUBASHEVSKY V, PEIKERT C, and REGEV O. On ideal lattices and learning with errors over rings[J]. Journal of the ACM, 2010, 60(6): 43. doi: 10.1145/2535925

    5. [5]

      ALBRECHT M R, PLAYER R, and SCOTT S. On the concrete hardness of learning with Errors[J]. Journal of Mathematical Cryptology, 2015, 9(3): 169–203. doi: 10.1515/jmc-2015-0016

    6. [6]

      BECKER A, DUCAS L, GAMA N, et al. New directions in nearest neighbor searching with applications to lattice sieving[C]. The Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, Virginia, 2016: 10–24. doi: 10.1137/1.9781611974331.ch2.

    7. [7]

      SCHNEIDER M. Sieving for shortest vectors in ideal lattices[C]. The 6th International Conference on Cryptology in Africa, Cairo, Egypt, 2013: 375–391. doi: 10.1007/978-3-642-38553-7_22.

    8. [8]

      AGRAWAL S, BONEH D, and BOYEN X. Efficient lattice (H)IBE in the standard model[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France, 2010: 553–572. doi: 10.1007/978-3-642-13190-5_28.

    9. [9]

      BONEH D, NIKOLAENKO V, and SEGEV G. Attribute-based encryption for arithmetic circuits[EB/OL]. http://eprint.iacr.org/2013/669, 2013.

    10. [10]

      CHEN Yuanmi and NGUYEN P Q. BKZ 2.0: Better lattice security estimates[C]. The 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, 2011: 1–20. doi: 10.1007/978-3-642-25385-0_1.

    11. [11]

      BAI Shi and GALBRAITH S D. Lattice decoding attacks on binary LWE[C]. The 19th Australasian Conference on Information Security and Privacy, Wollongong, NSW, Australia, 2014: 322–337. doi: 10.1007/978-3-319-08344-5_21.

    12. [12]

      PAAR C and PELZL J. Understanding Cryptography: A Textbook for Students and Practitioners[M]. Berlin Heidelberg: Springer, 2010: 156.

    13. [13]

      LINDNER R and PEIKERT C. Better key sizes (and attacks) for LWE-based encryption[C]. The Cryptographers’ Track at the RSA Conference 2011 Topics in Cryptology, San Francisco, USA, 2011: 319–339. doi: 10.1007/978-3-642-19074-2_21.

    14. [14]

      ALBRECHT M R, CID C, FAUGèRE J, et al. On the complexity of the BKW algorithm on LWE[J]. Designs, Codes and Cryptography, 2015, 74(2): 325–354. doi: 10.1007/s10623-013-9864-x

    15. [15]

      ZHAO Jian, GAO Haiying, and ZHANG Junqi. Attribute-based encryption for circuits on lattices[J]. Tsinghua Science and Technology, 2014, 19(5): 463–469. doi: 10.3969/j.issn.1007-0214.2014.05.005

    16. [16]

      赵建, 高海英, 胡斌. 基于理想格的高效密文策略属性基加密方案[J]. 电子与信息学报, 2018, 40(7): 1652–1660. doi: 10.11999/JEIT170863
      ZHAO Jian, GAO Haiying, and HU Bin. An efficient ciphertext-policy attribute-based encryption on ideal lattices[J]. Journal of Electronics &Information Technology, 2018, 40(7): 1652–1660. doi: 10.11999/JEIT170863

    17. [17]

      ZHANG Jiang, ZHANG Zhenfeng, and GE Aijun. Ciphertext policy attribute-based encryption from lattices[C]. The 7th ACM Symposium on Information, Computer and Communications Security, Seoul, Korea, 2012: 16–17. doi: 10.1145/2414456.2414464.

    1. [1]

      赵建, 高海英, 胡斌. 基于理想格的高效密文策略属性基加密方案. 电子与信息学报, 2018, 40(7): 1652-1660.

    2. [2]

      毛可飞, 陈杰, 刘建伟. 层次身份基认证密钥协商方案的安全性分析和改进. 电子与信息学报, 2016, 38(10): 2619-2626.

    3. [3]

      陈艳玲, 陈鲁生, 符方伟. 两种群签名方案的安全性分析. 电子与信息学报, 2005, 27(2): 235-238.

    4. [4]

      闫玺玺, 刘媛, 李子臣, 汤永利, 叶青. 新的格上多机构属性基加密方案. 电子与信息学报, 2018, 40(4): 811-817.

    5. [5]

      王建华, 王光波, 徐旸, 胡一笑, 张越, 樊理文. 解密成本为常数的具有追踪性的密文策略属性加密方案. 电子与信息学报, 2018, 40(4): 802-810.

    6. [6]

      刘丹, 裴昌幸, 权东晓. 测量基对BB84协议安全性影响. 电子与信息学报, 2011, 33(1): 228-230.

    7. [7]

      胡国杰, 冯正进. 一类数字混沌加密系统的安全性分析. 电子与信息学报, 2003, 25(11): 1514-1518.

    8. [8]

      刘永亮, 高文, 姚鸿勋, 黄铁军. 用于多媒体加密的基于身份的密钥协商协议的安全性. 电子与信息学报, 2007, 29(4): 892-894.

    9. [9]

      王化群, 郭显久, 于红, 彭玉旭. 几种可转换环签名方案的安全性分析和改进. 电子与信息学报, 2009, 31(7): 1732-1735.

    10. [10]

      罗敏, 孙腾, 张静茵, 李莉. 两个无证书聚合签名方案的安全性分析. 电子与信息学报, 2016, 38(10): 2695-2700.

    11. [11]

      张玉磊, 李臣意, 王彩芬, 张永洁. 无证书聚合签名方案的安全性分析和改进. 电子与信息学报, 2015, 37(8): 1994-1999.

    12. [12]

      张明武, 杨波, 周敏, 张文政. 两种签密方案的安全性分析及改进. 电子与信息学报, 2010, 32(7): 1731-1736.

    13. [13]

      王化群, 张力军, 赵君喜. 两种环签名方案的安全性分析及其改进. 电子与信息学报, 2007, 29(1): 201-204.

    14. [14]

      张玉磊, 王欢, 刘文静, 王彩芬. 异构双向签密方案的安全性分析和改进. 电子与信息学报, 2017, 39(12): 3045-3050.

    15. [15]

      张永洁, 张玉磊, 王彩芬. 具有内部安全性的常数对无证书聚合签密方案. 电子与信息学报, 2018, 40(2): 500-508.

    16. [16]

      翁贻方, 翁莉娟, 张蕾. 提高混沌同步保密通信安全性的设计方案研究. 电子与信息学报, 2004, 26(7): 1057-1063.

    17. [17]

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

    18. [18]

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

    19. [19]

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

    20. [20]

      李龙, 古天龙, 常亮, 徐周波, 钱俊彦. 快速解密且私钥定长的密文策略属性基加密方案. 电子与信息学报, 2018, 40(7): 1661-1668.

  • 表 1  符号定义

    符号意义符号意义
    $d$整数值${{\mathbb{Z}}_q}$模$q$的剩余类环
    ${{a}}$列向量${{a}}$${{\mathbb{Z}}^{n \times m}}$$n \times m$整数矩阵集合
    ${{A}}$矩阵${{A}}$$\left\lceil {q/2} \right\rceil $大于$q/2$的最小整数
    ${{A}} ^{\rm{T}}$矩阵${{A}}$的转置$\left\lfloor {q/2} \right\rfloor $小于q/2的最大整数
    ${{A}}|{{B }}$矩阵${{A}}$和矩阵${{B }}$合并$\varTheta (n)$渐进精确界记号
    ${\mathbb{Z}}$整数域$\omega (n)$非渐进紧下界记号
    ${\mathbb{R}}$实数域$O(n)$渐进上界记号
    下载: 导出CSV

    表 2  密码算法的安全级别

    安全等级(${2^n}$)406480128192256
    安全级别薄弱(weak)传统(legacy)基准(baseline)标准(standard)较高(high)超高(ultra)
    下载: 导出CSV

    表 3  d, n=64时参数和最低安全等级${λ}$的关系

    $c$$q$$\log q \approx $$m$${\rm{Dis}}( \cdot )$?${λ}$
    8281474976710677 48 6144
    1173786976294838206459 66 844830.6
    1679228162514264337593543950319 961228831.1
    3262771017353866807638357894232076664161023554444640345130291922457632.0
    64394020061963944792122790401001436138050797392704654466679482934042457217714972106114142662548849156408066279903070473844872732.9
    下载: 导出CSV

    表 4  ${d} {= 1}$时参数和最低安全等级${λ}$的关系

    $n$$c$$q$$\log q \approx $$m$${\rm{Dis}}( \cdot )$?$\alpha $${λ} $
    12887205759403792793156 14336
    10 118059162071741130344970 179206.01e–1831.8
    5127922337203685477578363 64512
    8472236648286964521371172 737283.30e–1835.1
    10247118059162071741130344970143360
    81208925819614629174706189801638402.10e–2060.1
    12757547736009430541992187972184146
    86983634120239410400390599832104524.11e–2181.3
    40966472236648286964521371172589824
    719342813113834066795298819846881282.95e–21636.7
    下载: 导出CSV

    表 5  达到基准安全等级${λ} ' \approx{80}$时方案的参数

    $d$$n$$\log q \approx $$m$$\alpha $
    1127582.52104524.11e–21
    21375104.32866941.42e–27
    42925161.29430152.04e–44
    85500285.831435801.27e–81
    1611000537.011814906.32e–157
    下载: 导出CSV

    表 6  方案数据量大小(GB)

    $d$公钥主密钥密文密钥
    112.961719.550.0060982138.19
    243.398044.950.0175309050.57
    41716.67536681.890.302340553453.20
    8295332.43168482949.3726.900739168812017.63
    161064847265.921143637238342.2948402.5177271143645963601.98
    下载: 导出CSV

    表 7  方案中参数和最低安全等级${λ} $的关系

    方案AF$n$$\log q \approx $$m$$\alpha $$\lambda $
    文献[9]d = 1128103263684.28e–2532.5
    k = 210241202457603.71e–2940.6
    p = 10409613210813444.46e–32335.3
    文献[16]$r = 2$1289388364.46e–2231.9
    1024102106092.94e–2450.3
    4096108118811.03e–25511.2
    文献[17]$l = 3$12887676322.91e–2831.7
    1024965910003.48e–3137.8
    409610124836464.18e–33185.8
    下载: 导出CSV

    表 8  方案达到基准安全等级${λ} ' \approx {80}$时方案的参数

    方案$n$$\log q \approx $$m$$\alpha $
    文献[9]1750125 4375002.16e–30
    文献[16]1380104 110248.86e–25
    文献[17]2500 9914863592.03e–32
    下载: 导出CSV

    表 9  方案数据量大小(GB)

    方案公钥密文密钥
    文献[9]44.56520.02555570.6550
    文献[16] 1.10121.83541.4683
    文献[17]342.6093 0.13700.2056
    下载: 导出CSV
  • 加载中
计量
  • PDF下载量:  46
  • 文章访问数:  958
  • HTML全文浏览量:  355
文章相关
  • 通讯作者:  赵建, back_zj@126.com
  • 收稿日期:  2018-08-22
  • 录用日期:  2019-01-23
  • 网络出版日期:  2019-02-15
  • 刊出日期:  2019-08-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章