计算机科学 ›› 2021, Vol. 48 ›› Issue (6): 315-323.doi: 10.11896/jsjkx.200700215

所属专题: 信息安全 虚拟专题 密码学 虚拟专题

• 信息安全 • 上一篇    下一篇

基于R-SIS和R-LWE构建的IBE加密方案

钱心缘1,2, 吴文渊1   

  1. 1 中国科学院重庆绿色智能技术研究院自动推理与认知重庆市重点实验室 重庆400714
    2 中国科学院大学 北京101408
  • 收稿日期:2020-07-31 修回日期:2020-09-15 出版日期:2021-06-15 发布日期:2021-06-03
  • 通讯作者: 吴文渊(wuwenyuan@cigit.ac.cn)
  • 基金资助:
    重庆市科委项目(cstc2018jcyj-yszxX0002,cstc2019yszx-jcyjX0003);中科院前沿科学重点项目(QYZDB-SSW-SYS026);贵州省科技计划项目([2020]4Y056)

Identity-based Encryption Scheme Based on R-SIS/R-LWE

QIAN Xin-yuan1,2, WU Wen-yuan1   

  1. 1 Chongqing Key Laboratory of Automated Reasoning and Cognition,Chongqing Institute of Green and Intelligent Technology,Chinese Academy of Sciences,Chongqing 400714,China
    2 University of Chinese Academy of Sciences,Beijing 101408,China
  • Received:2020-07-31 Revised:2020-09-15 Online:2021-06-15 Published:2021-06-03
  • About author:QIAN Xin-yuan,born in 1995,postgra-duate.His main research interests include information security,lattice cryptography,IBE and ABE.(979454883@qq.com)
    WU Wen-yuan,born in 1976,Ph.D,professor.His main research interests include automated reasoning,hybrid computing and lattice cryptography.
  • Supported by:
    Chongqing Science and Technology Program(cstc2018jcyj-yszxX0002,cstc2019yszx-jcyjX0003), Key Research Program of Frontier Sciences of Chinese Academy of Sciences(QYZDB-SSW-SYS026) and Guizhou Science and Technology Program([2020]4Y056).

摘要: 格上基于身份的加密机制(Identity-Based Encryption,IBE)能够有效抵抗量子攻击,并且该机制将每个人的身份信息作为公钥,能够简化公钥基础设施(Public Key Infrastructure,PKI)对海量用户的公钥管理,这种加密机制是对传统PKI的改进,能够解决PKI在物联网环境下暴露的众多问题。然而,目前国内外学者提出的基于格的IBE方案大多比较笨重,并且实现的方案很少。针对上述问题,提出了一种基于R-SIS以及R-LWE困难问题的IND-sID-CPA安全的IBE低膨胀率方案。首先,提出了分块复用技术,通过重用占存储空间较大的辅助解密密文块,极大地降低了密文膨胀率并提高了加密效率。然后,利用了Kyber提出的压缩算法并引入明文扩张参数,对以上两个参数指标进行进一步优化。通过严格的理论推导分析了所提方案的安全性、正确性和计算复杂度,利用数值实验给出了该方案在3种场景下的较优参数取值。最后,通过C++程序实现新方案,对比了所提方案与BFRS18方案在3种场景下的性能。实验结果表明,该方案在保证正确性和安全性的同时,有效提高了原方案的加解密效率,降低了密文膨胀率。

关键词: 分块复用技术, 高斯采样, 格密码, 环容错学习问题, 环小整数解问题, 基于身份加密, 压缩技术

Abstract: The identity-based encryption(IBE) by lattice can effectively resist quantum attacks,and this mechanism takes users’ identity information as public keys,which can ease the management of public key infrastructure(PKI) with an extremely large number of users.The lattice-based IBE system is an improvement of the traditional PKI to solve some problems in the Internet of Things(IoT) environment.However,previous IBE schemes based on lattices are cumbersome,and there are few implementations of these schemes.Aiming at this problem,this paper proposes an IBE scheme based on R-SIS and R-LWE with advantages of low expansion rate,which is secure against IND-sID-CPA.Firstly,a block reusing technology is proposed to reuse a ciphertext block for auxiliary decryption which occupies a significant amount in storage so that the expansion rate of ciphertext decreases and the encryption efficiency improves in a large extent.Then,by using a compression algorithm and introducing a plaintext expansion parameter,the two indicators of the scheme have been further optimized.Next,the scheme’s security,correctness,and computing complexity are analyzed through rigorous theoretical derivation,and numerical experiments with Maple give the optimal parameter values of this scheme under three scenarios.Finally,the new scheme is implemented with C++,and the performance of the scheme and the BFRS scheme in three scenarios are compared.Experiments and comparisons show that,while ensuring the correctness and security,this scheme improves the encryption and decryption efficiency of the original scheme and reduces the ciphertext expansion rate effectively.

Key words: Block re-using technology, Compression technology, Gaussian sampling, Identity-based encryption, Lattice, Ring learning with errors problem, Ring small integer solution problem

中图分类号: 

  • TP309
[1]SHAMIR A.Identity-based crypto systems and signatureschemes[C]//Proceedings of CRYPTO 1984.Berlin:Springer,1984:47-53.
[2]BONEH D,FRANKLIN M.Identity-based encryption from the weil pairing[C]//Proceedings of CRYPTO 2001.Berlin:Sprin-ger,2001:213-229.
[3]SHOR P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer [J].Siam Journal on Computing,1997,26(5):1484-1509.
[4]YOU I,HORI Y,SAKURAI K.Enhancing SVO Logic for Mobile IPv6 Security Protocols [J].Journal of Wireless Mobile Networks,Ubiquitous Computing,and Dependable Applications,2011,2(3):26-52.
[5]COCKS C.An identity based encryption scheme based on quadratic residues[C]//Proc of Cryptography and Coding.Berlin:Springer,2001:360-363.
[6]AJTAI M.Generating hard instances of lattice problems[C]//Proceedings of STOC.1996:99-108.
[7]REGEV O.On lattices,learning with errors,random linear-codes,and cryptography [J].Journal of the ACM(JACM),2009,56(6):1-40.
[8]MICCIANCIO D.Generalized compact knapsacks,cyclic lat-tices,and efficient one-way functions [J].Computational Complexity,2007,16(4):365-411.
[9]STEHLE D,STEINFELD R,TANAKA K,et al.Efficient public key encryption based on ideal lattices[C]//Proceedings of ASIACRYPT.Berlin,Heidelberg:Springer,2009:617-635.
[10]BABAI L.On Lovász’lattice reduction and the nearest lattice point problem [J].Combinatorica,1986,6(1):1-13.
[11]KLEIN P.Finding the closest lattice vector when it’s unusually close[C]//Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms.2000:937-941.
[12]GENTRY C,PEIKERT C,VAIKUNTANATHAN V.Trap-doors for hard lattices and new cryptographic constructions[C]//Proceedings of the 40th ACM Symp on Theory of Computing.New York:ACM,2008:197-206.
[13]PEIKERT C.An efficient and parallel Gaussian sampler for lattices[C]//Annual Cryptology Conference.Berlin,Heidelberg:Springer,2010:80-97.
[14]MICCIANCIO D,PEIKERT C.Trapdoors for lattices:Simpler,tighter,faster,smaller[C]//Proceedings of EUROCRYPT 2012.Berlin:Springer,2012:700-718.
[15]GENISE N,MICCIANCIO D.Faster gaussian sampling fortrapdoor lattices with arbitrary modulus[C]//Proceedings of EUROCRYPT.Cham:Springer,2018:174-203.
[16]GENISE N,MICCIANCIO D,POLYAKOV Y.Building an efficient lattice gadget toolkit:Subgaussian sampling and more[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.Cham:Springer,2019:655-684.
[17]CASH D,HOFHEINZ D,KILTZ E,et al.Bonsai trees,or how to delegate a lattice basis[C]//Proceedings of EUROCRYPT 2010.Berlin:Springer,2010:523-552.
[18]AGRAWAL S,BONEH D,BOYEN X.Efficient lattice(H) IBE in the standard model[C]//Proceedings of EUROCRYPT 2010.Berlin:Springer,2010:553-572.
[19]DUCAS L,LYUBASHEVSKY V,PREST T.Efficient identity-based encryption over NTRU lattices[C]//Proceedings of ASIACRYPT 2014.Berlin:Springer,2014:22-41.
[20]MCCARTHY S,SMYTH N,O’SULLIVAN E.A practical implementation of identity-based encryption over NTRU lattices[C]//Proceedings of IMACC.Cham:Springer,2017:227-246.
[21]BERT P,FOUQAUE P A,ROUX-LANGLOIS A,et al.Practical implementation of ring-SIS/LWE based signature and IBE[C]//Proceedings of PQCrypto.Cham:Springer,2018:271-291.
[22]YAMADA S.Adaptively secure identity-based encryption from lattices with asymptotically shorter public parameters[C]//Proceedings of EUROCRYPT 2016.Berlin:Springer,2016:32-62.
[23]SINGH S,PADHYE S.Identity based blind signature schemeover NTRU lattices [J].Information Processing Letters,2020,155:105898.
[24]LU X,WEN Q,YIN W,et al.Quantum-Resistant Identity-Based Signature with Message Recovery and Proxy Delegation [J].Symmetry,2019,11(2):272.
[25]ZHANG Y,GAN Y,YIN Y,et al.Fuzzy Identity-Based Signature from Lattices for Identities in a Large Universe [C]//International Conference on Cloud Computing and Security.Cham:Springer,2018:573-584.
[26]KATSUMATA S,MATSUDA T,TAKAYASU A.Lattice-based revocable(hierarchical) IBE with decryption key exposure resistance [J].Theoretical Computer Science,2020,809:103-136.
[27]ZHANG Y,WANG S,DU Q.Revocable identity-based encryption scheme under LWE assumption in the standard model [J].IEEE Access,2018,6:65298-65307.
[28]SRIVASTAVA G,AGRAWALG R,SINGH K,et al.A hierarchical identity-based security for delay tolerant networks using lattice-based cryptography [J].Peer-to-Peer Networking and Applications,2020,13(1):348-367.
[29]DONG C,YANG K,QIU J,et al.Outsourced revocable identity-based encryption from lattices [J].Transactions on Emerging Telecommunications Technologies,2019,30(11):e3529.
[30]ZHANG X,TANG Y,WANG H,et al.Lattice-based proxy-orien-ted identity-based encryption with keyword search for cloud storage [J].Information Sciences,2019,494:193-207.
[31]ZHANG X,XU C,MU L,et al.Identity-based encryption with keyword search from lattice assumption [J].China Communications,2018,15(4):164-178.
[32]ZHU H,TAN Y,ZHU L,et al.An identity-based anti-quantum privacy-preserving blind authentication in wireless sensor networks [J].Sensors,2018,18(5):1663.
[33]REGEV O.Lecture 1 Intriduction [EB/OL].Tel Aviv Univer-sity,2004[2020-03-28].https://cims.nyu.edu/~regev/tea-ching/lattices_fall_2004/ln/introduction.pdf.
[34]LIU Y,WANG L C,LI L X,et al.Secure and Efficient Multi-Authority Attribute-Based Encryption Scheme From Lattices [J].IEEE Access,2019,7:3665-3674.
[35]LYUBASHEVSKY V,MICCIANCIO D.Generalized compactknapsacks are collision resistant[C]//Proceedings of ICALP.Berlin,Heidelberg:Springer,2006:144-155.
[36]PEIKERT C,ROSEN A.Efficient collision-resistant hashingfrom worst-case assumptions on cyclic lattices[C]//Proceedings of TCC.Berlin,Heidelberg:Springer,2006:145-166.
[37]LYUBASHEVSKY V,PEIKERT C,REGEV O.On ideal lattices and learning with errors over rings [C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Heidelberg:Springer,2010:1-23.
[38]AJTAI M.Generating hard instances of the short basis problem[C]//Proceedings of Int Colloquium on Automata,Languages and Programming.Berlin:Springer,1999:1-9.
[39]BOS J,DUCAS L,KILTZ E,et al.CRYSTALS-Kyber:a CCA-secure module-lattice-based KEM[C]//Proceedings of EuroS&P.IEEE,2018:353-367.
[40]KE C S,WU W Y,FENG Y.Low expension rate of encryption algorithm based on MLWE [J].Computer Science,2019,46(4):144-150.
[1] 梁懿雯, 杜育松.
抵御计时攻击的基于Knuth-Yao的二元离散高斯采样算法
Timing Attack Resilient Sampling Algorithms for Binary Gaussian Based on Knuth-Yao
计算机科学, 2022, 49(6A): 485-489. https://doi.org/10.11896/jsjkx.210600017
[2] 郑嘉彤, 吴文渊.
基于MLWE的双向可否认加密方案
Practical Bi-deniable Encryption Scheme Based on MLWE
计算机科学, 2021, 48(3): 307-312. https://doi.org/10.11896/jsjkx.200100024
[3] 张浩, 蔡英, 夏红科.
VANET中基于RSU辅助签名环形成的方案
RSU-based Assisting Ring Formation Scheme in VANET
计算机科学, 2020, 47(5): 301-305. https://doi.org/10.11896/jsjkx.190400119
[4] 李树全,刘磊,朱大勇,熊超,李锐.
一种面向云存储的数据动态验证方案
Protocol of Dynamic Provable Data Integrity for Cloud Storage
计算机科学, 2020, 47(2): 256-261. https://doi.org/10.11896/jsjkx.181202371
[5] 张襄松,刘振华.
具有消息恢复功能的无陷门格签名方案
Non-trapdoors Lattice Signature Scheme with Message Recovery
计算机科学, 2014, 41(9): 165-168. https://doi.org/10.11896/j.issn.1002-137X.2014.09.031
[6] 明洋,王育民,庞辽军.
标准模型下可证安全的多身份单密钥解密方案
Provably Secure Multi-identity Single-key Decryption Scheme in the Standard Model
计算机科学, 2010, 37(3): 73-75.
[7] .
一种改进的PETKS原型方案及其扩展

计算机科学, 2009, 36(3): 58-60.
[8] 刘振华,胡予濮,张襄松.
标准模型下选择密文安全的基于身份加密方案
Chosen Ciphertext Secure Identity-based Encryption in the Standard Model
计算机科学, 2009, 36(10): 64-67.
[9] .
移动Ad Hoc网络路径压缩技术研究与分析

计算机科学, 2008, 35(5): 73-77.
[10] 李维忠 贾小铁 徐志立.
用于空间数据系统的无损数据压缩技术

计算机科学, 2003, 30(11): 122-124.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!