Computer Science ›› 2021, Vol. 48 ›› Issue (6): 315-323.doi: 10.11896/jsjkx.200700215

Special Issue: Information Security

• Information Security • Previous Articles     Next Articles

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).

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

CLC Number: 

  • 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] WANG Kun-shu, ZHANG Ze-hui, GAO Tie-gang. Reversible Hidden Algorithm for Remote Sensing Images Based on Hachimoji DNA and QR Decomposition [J]. Computer Science, 2022, 49(8): 127-135.
[2] XU Si-yu, QIN Ke-yun. Topological Properties of Fuzzy Rough Sets Based on Residuated Lattices [J]. Computer Science, 2022, 49(6A): 140-143.
[3] LIANG Yi-wen, DU Yu-song. Timing Attack Resilient Sampling Algorithms for Binary Gaussian Based on Knuth-Yao [J]. Computer Science, 2022, 49(6A): 485-489.
[4] WANG Xiao-min, SU Jing, YAO Bing. Algorithms Based on Lattice Thought for Graph Structure Similarity [J]. Computer Science, 2021, 48(6A): 543-551.
[5] SHEN Xia-jiong, YANG Ji-yong, ZHANG Lei. Attribute Exploration Algorithm Based on Unrelated Attribute Set [J]. Computer Science, 2021, 48(4): 54-62.
[6] ZHENG Jia-tong, WU Wen-yuan. Practical Bi-deniable Encryption Scheme Based on MLWE [J]. Computer Science, 2021, 48(3): 307-312.
[7] WEN Xin, YAN Xin-yi, CHEN Ze-hua. Minimal Optimistic Concept Generation Algorithm Based on Equivalent Relations [J]. Computer Science, 2021, 48(3): 163-167.
[8] NI Liang, WANG Nian-ping, GU Wei-li, ZHANG Qian, LIU Ji-zhao, SHAN Fang-fang. Research on Lattice-based Quantum-resistant Authenticated Key Agreement Protocols:A Survey [J]. Computer Science, 2020, 47(9): 293-303.
[9] YUE Xiao-wei, PENG Sha and QIN Ke-yun. Attribute Reduction Methods of Formal Context Based on ObJect (Attribute) Oriented Concept Lattice [J]. Computer Science, 2020, 47(6A): 436-439.
[10] ZHANG Hao, CAI Ying, XIA Hong-ke. RSU-based Assisting Ring Formation Scheme in VANET [J]. Computer Science, 2020, 47(5): 301-305.
[11] LV Xiao-jing, LIU Zhao, CHU Xue-sen, SHI Shu-peng, MENG Hong-song, HUANG Zhen-chun. Extreme-scale Simulation Based LBM Computing Fluid Dynamics Simulations [J]. Computer Science, 2020, 47(4): 13-17.
[12] GUO Qing-chun,MA Jian-min. Judgment Methods of Interval-set Consistent Sets of Dual Interval-set Concept Lattices [J]. Computer Science, 2020, 47(3): 98-102.
[13] LI Shu-quan,LIU Lei,ZHU Da-yong,XIONG Chao,LI Rui. Protocol of Dynamic Provable Data Integrity for Cloud Storage [J]. Computer Science, 2020, 47(2): 256-261.
[14] CUI Dan-dan, LIU Xiu-lei, CHEN Ruo-yu, LIU Xu-hong, LI Zhen, QI Lin. Named Entity Recognition in Field of Ancient Chinese Based on Lattice LSTM [J]. Computer Science, 2020, 47(11A): 18-23.
[15] XU Chuan-fu,WANG Xi,LIU Shu,CHEN Shi-zhao,LIN Yu. Large-scale High-performance Lattice Boltzmann Multi-phase Flow Simulations Based on Python [J]. Computer Science, 2020, 47(1): 17-23.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!