基于格的可搜索公钥加密研究进展

doi:10.3969/j.issn.1671-1122.2024.06.008

摘要/Abstract

摘要：

随着数据的爆发式增长和云计算的快速发展，用户对数据安全共享和查询的需求逐渐增加。可搜索公钥加密技术允许资源受限的用户高效地搜索云服务器中存储的加密数据，为云数据安全查询问题提供了一种有效的解决方法。然而随着量子时代的到来，现有密码体制面临巨大的冲击，格密码由于具有可归约到最坏情况困难假设、抗量子攻击、安全性高等优势受到广泛关注。文章从安全性、功能性角度对基于格的可搜索公钥加密技术的研究进展进行综述，首先概述了基于格理论的公钥密码研究进展，介绍了可搜索公钥加密的定义及安全模型。然后重点分析现有格上可搜索公钥加密方案，以攻击手段为出发点对方案的安全性研究进行分析，从通信开销和计算复杂度两方面对方案的算法效率进行对比。最后总结了格上可搜索公钥加密技术的应用场景和未来研究趋势。

关键词: 格密码, 公钥加密, 可搜索加密, 云计算

Abstract:

With the explosive growth of data and the rapid development of cloud computing, the demand for data secure sharing and querying is gradually increasing among users. Public-key encryption with keyword search allows resource-constrained users to efficiently search for encrypted data stored in the cloud servers, providing an effective solution for cloud data secure queries. However, with the arrival of the quantum era, the existing cryptosystems are facing a huge impact. Lattice-based cryptography has received widespread attention for the advantages of being reducible to the worst-case difficulty assumption, resistance to quantum attacks, and high security. The article provided an overview of the recent research progress of lattice-based public-key encryption with keyword search from the perspective of security and functionality. Firstly, it outlined the research progress of lattice-based public key cryptography, the definition and the security model of public-key encryption with keyword search. Then, it focused on analyzing the recent lattice-based public-key encryption with keyword search schemes, analyzed the research on the security of the schemes from the starting point of attacking means, and compared the algorithmic efficiencies of the schemes in terms of the communication overhead and the computational complexity. Finally, it summarized the application scenarios and the future research trends.

Key words: lattice-based cryptography, public-key encryption, searchable encryption, cloud computing

中图分类号:

TP309

叶清, 何俊霏, 杨智超. 基于格的可搜索公钥加密研究进展[J]. 信息网络安全, 2024, 24(6): 903-916.

YE Qing, HE Junfei, YANG Zhichao. Research Progress in Lattice-Based Public-Key Encryption with Keyword Search[J]. Netinfo Security, 2024, 24(6): 903-916.

图/表 10

表1

表2

图1

图2

表3

表4

表5

图3

表6

表7

参考文献 77

[1]	Laminar. 2023 Public Cloud Data Security Situation Survey Report[EB/OL]. (2023-06-15)[2024-03-12]. https://www.51cto.com/article/757733.html.
	Laminar. 2023年公有云数据安全态势调查报告[EB/OL]. (2023-06-15)[2024-03-12]. https://www.51cto.com/article/757733.html.
[2]	BONEH D, DICRESCENZO G, OSTROVSKY R, et al. Public Key Encryption with Keyword Search[C]// Springer. International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2004). Heidelberg: Springer, 2004: 506-522.
[3]	SHOR P W. Algorithms for Quantum Computation: Discrete Logarithms and Factoring[C]// IEEE. The 35th Annual Symposium on Foundations of Computer Science. New York: IEEE, 1994: 124-134.
[4]	ARUTE F, ARYA K, BABBUSH R, et al. Quantum Supremacy Using a Programmable Superconducting Processor[J]. Nature, 2019, 574(7779): 505-510.
[5]	MICCIANCIO D, REGEV O. Worst-Case to Average-Case Reductions Based on Gaussian Measures[J]. SIAM Journal on Computing, 2007, 37(1): 267-302.
[6]	REGEV O. The Learning with Errors Problem[C]// IEEE. The 25th Annual IEEE Conference on Computational Complexity (CCC2010). New York: IEEE, 2010: 191-204.
[7]	AJTAI M. Generating Hard Instances of Lattice Problems[C]// ACM. The Twenty-Eighth Annual ACM Symposium on Theory of Computing. New York: ACM, 1996: 99-108.
[8]	AJTAI M, DWORK C. A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence[C]// ACM. The Twenty-Ninth Annual ACM Symposium on Theory of Computing. New York: ACM, 1997: 284-293.
[9]	GOLDREICH O, GOLDWASSER S, HALEVI S. Public-Key Cryptosystems from Lattice Reduction Problems[C]// Springer. 17th Annual International Cryptology Conference Santa Barbara(CRYPTO’97). Heidelberg: Springer, 1997: 112-131.
[10]	NGUYEN P Q. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto’97[C]// Springer. The 19th Annual International Cryptology Conference (CRYPTO 1999). Heidelberg: Springer, 1999: 288-304.
[11]	HOFFSTEIN J, PIPHER J, SILVERMAN J H. NTRU: A Ring-Based Public Key Cryptosystem[C]// Springer. The 3rd Biennial International Algorithmic Number Theory Symposium (ANTS 1998). Heidelberg: Springer, 1998: 267-288.
[12]	NGUYEN P Q, POINTCHEVAL D. Analysis and Improvements of NTRU Encryption Paddings[C]// Springer. The 22nd Annual International Cryptology Conference (CRYPTO 2002). Heidelberg: Springer, 2002: 210-225.
[13]	HOWGRAVE-GRAHAM H, SILVERMAN J H, WHYTE W. Choosing Parameter Sets for NTRU Encrypt with NAEP and SVES-3[C]// Springer. The Cryptographers’ Track at the RSA Conference (CT-RSA 2005). Heidelberg: Springer, 2005: 118-135.
[14]	STEINFELD R, LING San, PIEPRZYK J, et al. NTRUCCA: How to Strengthen NTRU Encrypt to Chosen Ciphertext Security in the Standard Model[C]// Springer. The 15th International Cryptology Conference on Practice and Theory in Public Key Cryptography (PKC 2012). Heidelberg: Springer, 2012: 353-371.
[15]	REGEV O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[J]. Journal of the ACM, 2009, 56(6): 84-93.
[16]	KAWACHI A, TANAKA K, XAGAWA K. Multi-Bit Cryptosystems Based on Lattice Problems[C]// Springer. The 10th International Cryptology Conference on Practice and Theory in Public-Key Cryptography 2007. Heidelberg: Springer, 2007: 315-329.
[17]	GENTRY C, PEIKERT C, VAIKUNTANATHAN V. Trapdoors for Hard Lattices and New Cryptographic Constructions[C]// ACM. The 40th Annual ACM Symposium on Theory of Computing. New York: ACM, 2008: 197-206.
[18]	PEIKERT C, WATERS B. Lossy Trapdoor Functions and Their Applications[C]// ACM. The 40th Annual ACM Symposium on Theory of Computing. New York: ACM, 2008: 187-196.
[19]	PEIKERT C. Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem[C]// ACM. The 41st Annual ACM Symposium on Theory of Computing. New York: ACM, 2009: 333-342.
[20]	LYUBASHEVSKY V, PEIKERT C, REGEV O. On Ideal Lattices and Learning with Errors Over Rings[C]// Springer. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2010: 1-23.
[21]	NIST. FrodoKEM Learning with Errors Key Encapsulation: Algorithm Specifications and Supporting Documentation[EB/OL]. (2020-07-30)[2024-03-12]. https://frodokem.org/files/FrodoKEM-specification-20200930.pdf.
[22]	ZHENG Zhongxiang, WANG Anyu, FAN Haining, et al. SCloud: Encryption and Key Encapsulation Algorithm Based on LWE[EB/OL]. (2019-12-27)[2024-03-12]. https://sfjs.cacrnet.org.cn/site/cont-ent/430.html.
	郑中翔, 王安宇, 樊海宁, 等. SCloud: 基于LWE的加密与密钥封装算法[EB/OL]. (2019-12-27)[2024-03-12]. https://sfjs.cacrnet.org.cn/site/cont-ent/430.html.
[23]	ALKIM E, DUCAS L, PÖPPELMANN T, et al. Post-Quantum Key Exchange-A New Hope[C]// USENIX. The 25th USENIX Security Symposium (USENIX Security 16). Berlin:USENIX, 2016: 327-343.
[24]	NIST. NewHope[EB/OL]. (2019-04-10)[2024-03-12]. https://www.newhopecrypto.org/data/NewHope_2019_04_10.pdf.
[25]	NIST. LAC: Lattice-Based Cryptosystems[EB/OL]. (2019-11-13)[2024-03-12]. https://sfjs.cacrnet.org.cn/site/content/432.html#.
[26]	PAN Yanbin, LI Haoyu, XIE Tianyuan, et al. TALE: A Lattice Based Public Key Encryption Algorithm[EB/OL]. (2019-10-26)[2024-03-12]. https://sfjs.cacrnet.org.cn/site/content/408.html.
	潘彦斌, 李昊宇, 谢天元, 等. TALE:一种基于格的公钥加密算法[EB/OL]. (2019-10-26)[2024-03-12]. https://sfjs.cacrnet.org.cn/site/content/408.html.
[27]	ZHAO Yunlei, LIU Zhe, JIN Zhengzhong, et al. AKCN-E8: New Lattice Encoding and Strong Secure, Efficient, and Flexible Key Encapsulation Algorithm Based on Ideal Lattices[EB/OL]. (2019-10-26)[2024-03-12]. https://sfjs.cacrnet.org.cn/site/content/408.html.
	赵运磊, 刘哲, 金正中, 等. AKCN-E8:新型格编码及基于理想格的强安全、高效、灵活的密钥封装算法[EB/OL]. (2019-10-31)[2024-03-12]. https://sfjs.cacrnet.org.cn/site/c-ontent/429.html.
[28]	NIST. CRYSTALS-Kyber Algorithm Specifications and Supporting Documentation[EB/OL]. (2020-10-01)[2024-03-12]. https://pq-crystals.org/kyb-er/data/kyber-specification-round3.pdf.
[29]	BOS J, DUCAS L, KILTZ E, et al. CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM[C]// IEEE. 2018 IEEE European Symposium on Security and Privacy (EuroS&P). New York: IEEE, 2018: 353-367.
[30]	ZHANG Jiang, YU Yu, FAN Shuqin, et al. Aigis: A Class of Digital Signature and Key Encapsulation Mechanisms Based on Asymmetric (M) LWE and (M) SIS[EB/OL]. (2019-02-28)[2024-03-12]. https://sfjs.cacrnet.org.cn/site/cont-ent/407.html.
	张江, 郁昱, 范淑琴, 等. Aigis:一类基于非对称(M)LWE和(M)SIS的数字签名和密钥封装机制[EB/OL]. (2019-02-28)[2024-03-12]. https://sfjs.cacrnet.org.cn/site/cont-ent/407.html.
[31]	ZHAO Yunlei, CHENG Leixiao, JIN Zhengzhong, et al. AKCN-MLWE: General and Modular Key Encapsulation Based on Lattice[EB/OL]. (2019-11-08)[2024-03-12]. https://sfjs.cacrnet.org.cn/si-te/content/428.html.
	赵运磊, 程蕾晓, 金正中, 等. AKCN-MLWE:基于格的通用和模块化的密钥封装[EB/OL]. (2019-11-08)[2024-03-12]. https://sfjs.cacrnet.org.cn/si-te/content/428.html.
[32]	BYUN J W, RHEE H S, PARK H A, et al. Off-Line Keyword Guessing Attacks on Recent Keyword Search Schemes Over Encrypted Data[C]// Springer. 2006 Workshop on Secure Data Management. Heidelberg: Springer, 2006: 75-83.
[33]	RHEE H S, PARK J H, SUSILO W, et al. Improved Searchable Public Key Encryption with Designated Tester[C]// ACM. The 4th International Symposium on Information, Computer and Communications Security. New York: ACM, 2009: 376-379.
[34]	ZHANG Yupeng, KATZ J, PAPAMANTHOU C. All Your Queries are Belong to Us: the Power of {File-Injection} Attacks on Searchable Encryption[C]// USENIX. The 25th USENIX Security Symposium. Berlin:USENIX, 2016: 707-720.
[35]	FANG Liming, SUSILO W, GE Chunpeng, et al. Public Key Encryption with Keyword Search Secure against Keyword Guessing Attacks without Random Oracle[J]. Information Sciences, 2013, 238: 221-241.
[36]	CHEN Rongmao, MU Yi, YANG Guoming, et al. A New General Framework for Secure Public Key Encryption with Keyword Search[C]// Springer. The 20th Australasian Conference Information Security and Privacy-ACISP. Heidelberg: Springer, 2015: 59-76.
[37]	HUANG Qiong, LI Hongbo. An Efficient Public-Key Searchable Encryption Scheme Secure against Inside Keyword Guessing Attacks[J]. Information Sciences, 2017, 403: 1-14.
[38]	ZHANG Yuan, XU Chunxiang, NI Jianbing, et al. Blockchain-Assisted Public-Key Encryption with Keyword Search against Keyword Guessing Attacks for Cloud Storage[J]. IEEE Transactions on Cloud Computing, 2019, 9(4): 1335-1348.
[39]	PARK D J, KIM K, LEE P J. Public Key Encryption with Conjunctive Field Keyword Search[C]// Springer. The 5th International Workshop on Information Security Applications. Heidelberg: Springer, 2004: 73-86.
[40]	YANG Yang, MA Maode. Conjunctive Keyword Search with Designated Tester and Timing Enabled Proxy Re-Encryption Function for E-Health Clouds[J]. IEEE Transactions on Information Forensics and Security, 2016, 11(4): 746-759.
[41]	XU Lingling, LI Jin, CHEN Xiaofeng, et al. TC-PEDCKS: Towards Time Controlled Public Key Encryption with Delegable Conjunctive Keyword Search for Internet of Things[J]. Journal of Network and Computer Applications, 2019, 128: 11-20. doi: 10.1016/j.jnca.2018.12.003
[42]	SHAO Zhiyi, YANG Bo. On Security against the Server in Designated Tester Public Key Encryption with Keyword Search[J]. Information Processing Letters, 2015, 115(12): 957-961.
[43]	HAN Fei, QIN Jing, ZHAO Huawei, et al. A General Transformation from KP-ABE to Searchable Encryption[J]. Future Generation Computer Systems, 2014, 30: 107-115.
[44]	ZHENG Qingji, XU Shouhuai, ATENIESE G. VABKS: Verifiable Attribute-Based Keyword Search Over Outsourced Encrypted Data[C]// IEEE. The 2014-IEEE Conference on Computer Communications. New York: IEEE, 2014: 522-530.
[45]	ZHANG Jiuling, DENG Beixing, LI Xing. Learning with Error Based Searchable Encryption Scheme[J]. Journal of Electronics (China), 2012, 29(5): 473-476.
[46]	HOU Changjiang, LIU Fei, BAI Hongtao, et al. Public-Key Searchable Encryption from Lattices[J]. International Journal of High Performance Systems Architecture, 2014, 5(1): 25-32.
[47]	GU Chunxiang, GUANG Yan, ZHU Yuefei, et al. Public Key Encryption with Keyword Search from Lattices[J]. International Journal of Information Technology, 2013, 19(1): 1-10.
[48]	YU Xiaoling, XU Chungen, XU Lei, et al. Lattice-Based Searchable Encryption Scheme against Inside Keywords Guessing Attack[J]. Computers, Materials & Continua, 2020, 64(2): 1107-1125.
[49]	LIU Ziyuan, TSENG Y F, TSO R, et al. Public-Key Authenticated Encryption with Keyword Search: Cryptanalysis, Enhanced Security, and Quantum-Resistant Instantiation[C]// ACM. The 2022 ACM on Asia Conference on Computer and Communications Security. New York: ACM, 2022: 423-436.
[50]	EMURA K. Generic Construction of Public-Key Authenticated Encryption with Keyword Search Revisited: Stronger Security and Efficient Construction[C]// ACM. The 9th ACM on ASIA Public-Key Cryptography Workshop. New York: ACM, 2022: 39-49.
[51]	CHENG Leixiao, MENG Fei. Public Key Authenticated Encryption with Keyword Search from LWE[C]// Springer. The 27th European Symposium on Research in Computer Security. Heidelberg: Springer, 2022: 303-324.
[52]	CANETTI R, HALEVI S, KATZ J. A Forward-Secure Public-Key Encryption Scheme[J]. Journal of Cryptology, 2007, 20: 265-294.
[53]	ZHANG Xiaojun, XU Chunxiang, WANG Huaxiong, et al. FS-PEKS: Lattice-Based Forward Secure Public-Key Encryption with Keyword Search for Cloud-Assisted Industrial Internet of Things[J]. IEEE Transactions on Dependable and Secure Computing, 2021, 18(3): 1019-1032.
[54]	YANG Xinmin, CHEN Xinjian, HUANG Jianye, et al. FS-IBEKS: Forward Secure Identity-Based Encryption with Keyword Search from Lattice[EB/OL]. (2023-08-01)[2024-03-12]. https://dl.acm.org/doi/10.1016/j.csi.2023.103732.
[55]	XU Shiyuan, CAO Yibo, CHEN Xue, et al. Post-Quantum Public-Key Authenticated Searchable Encryption with Forward Security:General Construction, and Applications[C]// Springer. The 19th International Conference on Information Security and Cryptology. Heidelberg: Springer, 2023: 274-298.
[56]	QI Lijun, ZHUANG Jincheng. Efficient Public Key Searchable Encryption Schemes from Standard Hard Lattice Problems for Cloud Computing[EB/OL]. (2022-10-12)[2024-03-12]. https://eprint.iacr.org/2022/1374.
[57]	KUCHTA V, MARKOWITCH O. Identity-Based Threshold Encryption on Lattices with Application to Searchable Encryption[C]// Springer. The 6th International Conference on Applications and Techniques in Information Security. Heidelberg: Springer, 2016: 117-129.
[58]	WU Daini, WANG Xiaoming, GAN Qingqing. Public Key Encryption with Keyword Search from Lattices in Multiuser Environments[EB/OL]. (2016-11-23)[2024-03-12]. https://onlinelibrary.wiley.com/doi/full/10.1155/2016/6549570.
[59]	YANG Yang, YANG Shulve, WANG Fenghe, et al. Post-Quantum Secure Public Key Broadcast Encryption with Keyword Search[J]. Journal of Information Science & Engineering, 2017, 33(2): 485-497.
[60]	YANG Yang, ZHENG Xianghan, CHANG V, et al. Lattice Assumption Based Fuzzy Information Retrieval Scheme Support Multiuser for Secure Multimedia Cloud[J]. Multimedia Tools and Applications, 2018, 77(8): 9927-9941.
[61]	MAO Yaojun, FU Xingbing, GUO Chen, et al. Public Key Encryption with Conjunctive Keyword Search Secure against Keyword Guessing Aattack from Lattices[J]. Transactions on Emerging Telecommunications Technologies, 2019, 30(11): 1-14.
[62]	WANG Peng, XIANG Tao, LI Xiaoguo, et al. Public Key Encryption with Conjunctive Keyword Search on Lattice[EB/OL]. (2020-04-01)[2024-03-12]. https://www.sciencedirect.com/science/article/abs/pii/S2214212619304910.
[63]	YANG Yang, MA Maode. Semantic Searchable Encryption Scheme Based on Lattice in Quantum-Era[J]. Journal of Information Science and Engineering, 2016, 32(2): 425-438.
[64]	BEHNIA R, OZMEN M O, YAVUZ A A. Lattice-Based Public Key Searchable Encryption from Experimental Perspectives[J]. IEEE Transactions on Dependable and Secure Computing, 2020, 17(6): 1269-1282.
[65]	XU Lei, YUAN Xingliang, STEINFELD R, et al. Multi-Writer Searchable Encryption: An LWE-Based Realization and Implementation[C]// ACM. The 2019 ACM Asia Conference on Computer and Communications Security. New York: ACM, 2019: 122-133.
[66]	ZHANG Xiaojun, TANG Yao, WANG Huaxiong, et al. Lattice-Based Proxy-Oriented Identity-Based Encryption with Keyword Search for Cloud Storage[J]. Information Sciences, 2019, 494: 193-207. doi: 10.1016/j.ins.2019.04.051
[67]	BAEK J, SAFAVI-NAINI R, SUSILO W. Public Key Encryption with Keyword Search Revisited[C]// Springer. The International Conference on Computational Science and Its Applications-ICCSA 2008. Heidelberg: Springer, 2008: 1249-1259.
[68]	RHEE H S, SUSILO W, KIM H J. Secure Searchable Public Key Encryption Scheme against Keyword Guessing Attacks[J]. IEICE Electronics Express, 2009, 6(5): 237-243.
[69]	RHEE H S, PARK J H, SUSILO W, et al. Trapdoor Security in a Searchable Public-Key Encryption Scheme with a Designated Tester[J]. Journal of Systems and Software, 2010, 83(5): 763-771.
[70]	NIU Shufen, SONG Mi, FANG Lizhi, et al. Cloud Storage Data Sharing Based on Attribute Encryption in Smart Healthcare[J]. Journal of Electronics & Information Technology, 2022, 44(1): 107-117.
	牛淑芬, 宋蜜, 方丽芝, 等. 智慧医疗中基于属性加密的云存储数据共享[J]. 电子与信息学报, 2022, 44(1):107-117.
[71]	WANG Zheng, WANG Jingwei, YIN Xinchun. Searchable Electronic Health Record Sharing Scheme with User Revocation[J]. Journal of Computer Applications, 2024, 44(2): 504-511. doi: 10.11772/j.issn.1001-9081.2023030272
	王政, 王经纬, 殷新春. 支持用户撤销的可搜索电子健康记录共享方案[J]. 计算机应用, 2024, 44(2):504-511. doi: 10.11772/j.issn.1001-9081.2023030272
[72]	GAO Mengjie, WANG Huaqun. Blockchain-Based Searchable Healthcare Data Sharing Solution[J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2019, 39(6): 94-103.
	高梦婕, 王化群. 基于区块链的可搜索医疗数据共享方案[J]. 南京邮电大学学报(自然科学版), 2019, 39(6):94-103.
[73]	LIU Ziyuan, TSENG Y F, TSO R, et al. Public-Key Authenticated Encryption with Keyword Search: A Generic Construction and Its Quantum-Resistant Instantiation[J]. The Computer Journal, 2022, 65(10): 2828-2844.
[74]	NIU Shufen, WANG Jinfeng, WANG Bobin, et al. Ciphertext Sorting Search Scheme Based on B+ Tree Index Structure on Blockchain[J]. Journal of Electronics & Information Technology, 2019, 41(10): 2409-2415.
	牛淑芬, 王金风, 王伯彬, 等. 区块链上基于B+树索引结构的密文排序搜索方案[J]. 电子与信息学报, 2019, 41(10):2409-2415.
[75]	YAN Xixi, YUAN Xiaohan, TANG Yongli, et al. Verifiable Attribute-Based Searchable Encryption Scheme Based on Blockchain[J]. Journal on Communications, 2020, 41(2): 187-198. doi: 10.11959/j.issn.1000-436x.2020011
	闫玺玺, 原笑含, 汤永利, 等. 基于区块链且支持验证的属性基搜索加密方案[J]. 通信学报, 2020, 41(2): 187-198. doi: 10.11959/j.issn.1000-436x.2020011
[76]	ZHU Xiping, LAI Yu, LONG Wentao, et al. Electronic Medical Record Sharing and Verifiable Scheme Based on Blockchain[J]. Science Technology and Engineering, 2023, 23(14): 6113-6122.
	朱西平, 赖宇, 龙文涛, 等. 基于区块链的电子病历共享与可验证方案[J]. 科学技术与工程, 2023, 23(14):6113-6122.
[77]	DU Ruizhong, TAN Ailun, TIAN Junfeng. Public Key Searchable Encryption Scheme Based on Blockchain[J]. Journal on Communications, 2020, 41(4): 114-122. doi: 10.11959/j.issn.1000-436x.2020070
	杜瑞忠, 谭艾伦, 田俊峰. 基于区块链的公钥可搜索加密方案[J]. 通信学报, 2020, 41(4):114-122. doi: 10.11959/j.issn.1000-436x.2020070

基于格的公钥密码体制	主要特点	局限性
A-D密码体制	格公钥加密方案，具有可证明安全性	运行效率低，不能满足实际应用需求
GGH密码体制	基于CVP困难问题构造，直观、容易理解	缺乏安全保证，当维数小于350时，易被攻破
NTRU密码体制	基于多项式环构造，运行效率较高	原始方案缺乏安全性证明，没有进行困难问题归约

格困难问题	主要特点	代表算法
LWE	计算效率较低，密文、密钥尺寸大，无明显代数结构、安全强度高	FrodoKEM^[21]、SCloud^[22]
RLWE	参数取自特定环结构，密钥尺寸较小、效率更高，特定结构带来潜在的安全威胁	Newhope^[23,24]、 LAC^[25]、TALE^[26]、 AKCN-E8^[27]
MLWE	兼顾安全性和运算效率	KYBER^[28,29]、 Aigis-enc^[30]、 AKCN-MLWE^[31]

PEKS方案	CI	MCI	TI	MTI	FS	安全定义	安全模型	困难假设
文献[64]方案	√	√	×	×	×	IND-CKA	ROM	NTRU
文献[64]方案	√	√	×	×	×	IND-CKA	SM	LWE
文献[53]方案	√	√	×	×	√	IND-CKA	ROM	LWE
文献[49]方案	√	√	√	√	×	IND-CKA IND-IKGA	SM	LWE
文献[51]方案	√	√	√	√	×	IND-CKA	ROM/SM	LWE
文献[55]方案	√	√	√	√	√	IND-CKA IND-IKGA	ROM	LWE
文献[65]方案	√	√	√	√	√	IND-CKA IND-IKGA	ROM	LWE
文献[56]方案	√	√	√	√	√	IND-CPA	SM	RLWE&SIS

PEKS方案	通信开销
PEKS方案	公钥	私钥	密文	陷门
文献[64]方案	n\|q\|	4n²\|q\|	3n\|q\|	2n\|q\|
文献[64]方案	m((l+2)n+1)\|q\|	n²\|q\|	ε(2n\|q\|+\|q\|+1)	2n\|q\|
文献[53]方案	nm\|q\|	nm\|q\|	(l+nl+n)\|q\|	n\|q\|
文献[49]方案	(2m+nε+ nm(l+2))\|q\|	(n+mk+n²)\|q\|	ε(2n\|q\|+ \|q\|+1)	2n\|q\|
文献[51]方案	3mn\|q\|	(3mn+m²)\|q\|	8ml\|q\|	8ml\|q\|
文献[55]方案	m\|q\|+kn\|q\|	n+k\|q\|	ε(\|q\|+(d+ 3)n\|q\|+1)	(d+3)n\|q\|
文献[65]方案	(l+k+2(n+ 1)m)\|q\|	n²\|q\|	(2n+1)\|q\|	2n\|q\|
文献[56]方案	n\|q\|(2\|q\|+2)	n\|q\|(\|q\|+2)	n\|q\|(6\|q\|+5)	n\|q\|(2\|q\|+2)

PEKS方案	存储空间/KB
PEKS方案	公钥	私钥	密文	陷门
文献[64]方案	0.375	384	1.125	0.750
文献[64]方案	19156.790	96	7.520	0.750
文献[53]方案	74.250	74.250	96.750	0.375
文献[49]方案	1043.830	280.180	7.520	0.750
文献[51]方案	222.750	280.180	594	594
文献[55]方案	4.040	0.046	41.266	4.125
文献[65]方案	154.690	96	0.751	0.750
文献[56]方案	9.750	5.235	28.875	9.722