基于格的公钥加密与证书基加密

华东师范大学学报(自然科学版) ›› 2014, Vol. 2014 ›› Issue (1): 47-59.

基于格的公钥加密与证书基加密

李君, 钱海峰, 李祥学

华东师范大学计算机科学与技术系，上海 200241

收稿日期:2013-05-01 修回日期:2013-08-01 出版日期:2014-01-25 发布日期:2015-09-25

Public-key encryption and certificate-based encryption from lattice

LI Jun, QIAN Hai-feng, LI Xiang-xue

Department of Computer Science & Technology, East China Normal University, Shanghai 200241, China

Received:2013-05-01 Revised:2013-08-01 Online:2014-01-25 Published:2015-09-25

摘要/Abstract

摘要： 证书基加密(CBE)结合了基于身份加密和公钥基础设施的各自优点，然而基于传统数学假设的CBE不能有效抵御量子算法的攻击.为此构建了一个基于格的CBE方案，可有效抵御量子算法的攻击.首先构建出一个基于格的公钥加密(PKE)方案，之后利用该PKE构建出基于格的CBE方案.该方案可被规约为格上的学习误差(LWE)问题，因此得到的CBE为随机不可区分选择明文攻击安全的.该方案是目前为止已知的第一个基于格的CBE方案.

关键词: 证书基加密, 公钥加密, 随机不可区分选择明文安全, 学习误差假设, 格

Abstract: Certificate-based encryption (CBE) combines the advantages of identity-based encryption and that of public key infrastructure. However, CBE based on traditional mathematical assumptions cannot defeat quantum attacks. This paper aims at constructing a lattice-based CBE which is post-quantum: First constructed a lattice-based public key encryption (PKE); then used this PKE to construct a lattice-based CBE. Finally, it was proved that the ciphertexts generated by our CBE are indistinguishable from random against chosen-plaintext attacks (namely, INDr-CBE-CPA secure) by assuming that the learning with errors (LWE) problem is hard. This scheme is the first known lattice-based CBE so far.

Key words: CBE, PKE, INDr-CBE-CPA, LWE, Lattice

中图分类号:

TP309.7

李君, 钱海峰, 李祥学. 基于格的公钥加密与证书基加密[J]. 华东师范大学学报(自然科学版), 2014, 2014(1): 47-59.

LI Jun, QIAN Hai-feng, LI Xiang-xue. Public-key encryption and certificate-based encryption from lattice[J]. Journal of East China Normal University(Natural Sc, 2014, 2014(1): 47-59.

参考文献

［1］ AJTAI M. Generating hard instances of lattice problems［C］//Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, 1996: 99-108.

［2］ AJTAI M. The shortest vector problem in L2 is NP-hard for randomized reductions［C］//Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 1998: 10-19.

［3］ SHAMIR A. Identity-based cryptosystems and signature schemes［C］//Advances in cryptology. Berlin: Springer, 1985: 47-53.

［4］ BONEH D, FRANKLIN M. Identity-based encryption from the Weil pairing［C］//Advances in Cryptology- CRYPTO 2001. Berlin: Springer, 2001: 213-229.

［5］ COCKS C. An identity based encryption scheme based on quadratic residues［M］//Cryptography and Coding. Berlin: Springer, 2001: 360-363.

［6］ AGRAWAL S, BONEH D, BOYEN X. Efficient lattice (H)IBE in the standard model［M］//Advances in Cryp- tology-EUROCRYPT 2010. Berlin: Springer, 2010: 553-572.

［7］ SHOR P W. Algorithms for quantum computation: discrete logarithms and factoring［C］//Foundations of Com- puter Science, 1994 Proceedings., 35th Annual Symposium on. IEEE, 1994: 124-134.

［8］ GENTRY C. Certificate-based encryption and the certificate revocation problem［M］//Advances in Cryp- tology-EUROCRYPT 2003. Berlin: Springer, 2003: 272-293.

［9］ BONEH D, CANETTI R, HALEVI S, et al. Chosen-ciphertext security from identity-based encryption［J］. SIAM Journal on Computing, 2006, 36(5): 1301-1328.

［10］ REGEV O. On lattices, learning with errors, random linear codes, and cryptography［J］. Journal of the ACM (JACM), 2009, 56(6): 34.

［11］ BELLARE M, BOLDYREVA A, DESAI A, et al. Key-privacy in public-key encryption［M］//Advances in Cryptology-ASIACRYPT 2001. Berlin: Springer, 2001: 566-582.

［12］ ALWEN J, PEIKERT C. Generating shorter bases for hard random lattices［J］. Theory of Computing Systems, 2011, 48(3): 535-553.

［13］ AJTAI M. Generating hard instances of the short basis problem［M］//Automata, Languages and Programming. Berlin: Springer, 1999: 1-9.

［14］ GENTRY C, PEIKERT C, VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions［C］//Proceedings of the 40th annual ACM symposium on Theory of computing. ACM, 2008: 197-206.

［15］ DODIS Y, OSTROVSKY R, REYZIN L, et al. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data［J］. SIAM Journal on Computing, 2008, 38(1): 97-139.

［16］ CRAMER R, DAMGRD I. On the amortized complexity of zero-knowledge protocols［M］//Advances in Cryptology-CRYPTO 2009. Berlin: Springer, 2009: 177-191.

［17］ PEIKERT C. Public-key cryptosystems from the worst-case shortest vector problem［C］//Proceedings of the 41st annual ACM symposium on Theory of computing. ACM, 2009: 333-342.

[1]	王美玲, 左承毅, 李燕. 自旋扭曲光晶格中的玻色-爱因斯坦凝聚体[J]. 华东师范大学学报（自然科学版）, 2024, 2024(3): 64-72.
[2]	彭曼, 邵一平, 裴蓓, 杨梦杰, 李根, 文婉若, 杨凯. 长三角一体化示范区生态系统服务供需格局演变及区域调控探讨[J]. 华东师范大学学报（自然科学版）, 2023, 2023(6): 145-157.
[3]	岳文静, 魏启. 光晶格中极性分子链的量子纠缠[J]. 华东师范大学学报（自然科学版）, 2023, 2023(4): 74-85.
[4]	张婷玉, 袁琳, 张超, 李阳, 赵志远, 史宇骁, 张利权, 顾靖华. 海岸工程及生物入侵对上海南汇东滩海岸带格局演变的影响[J]. 华东师范大学学报（自然科学版）, 2023, 2023(3): 167-180.
[5]	高雅, 孙伟东, 赵国锋, 刘晔, 路勇. 化学链甲烷氧化偶联载氧体催化剂Na₂WO₄/Mn₇SiO₁₂-SiO₂的研究[J]. 华东师范大学学报（自然科学版）, 2023, 2023(1): 95-103.
[6]	何祝清, 廖欣怡, 丁诺. 天目山不同海拔的螽斯和蟋蟀多样性时空特征[J]. 华东师范大学学报（自然科学版）, 2022, 2022(6): 123-129.
[7]	班启敏, 吴雯, 胡文心, 林晖, 郑巍, 贺樑. 基于学习者知识和性格的个性化课程推荐[J]. 华东师范大学学报（自然科学版）, 2022, 2022(6): 87-101.
[8]	谭继清, 王强强, 谢微. 量子点超晶格激子系综中的超荧光行为[J]. 华东师范大学学报（自然科学版）, 2022, 2022(4): 163-168.
[9]	范大龙, 曹卫东, 王雪微. 中国汽车零部件供应网络时空格局演化研究[J]. 华东师范大学学报（自然科学版）, 2022, 2022(1): 109-121.
[10]	杨慧, 曾进, 杨乃, 孔凡敏. 空间视域下义务教育质量对房价的影响[J]. 华东师范大学学报（自然科学版）, 2022, 2022(1): 97-108.
[11]	黄冬晴, 俞黎阳, 陈珏, 魏同权. 面向移动边缘计算的联合计算卸载和资源分配策略研究[J]. 华东师范大学学报（自然科学版）, 2021, 2021(6): 88-99.
[12]	孙文, 韩玉洁, 殷杉. 城市公园不同植物群落内空气负离子变异格局及影响因素[J]. 华东师范大学学报（自然科学版）, 2021, 2021(2): 151-159.
[13]	毕艳芳, 王焘. 修正牛顿动力学中的平面圆形限制性三体问题[J]. 华东师范大学学报（自然科学版）, 2021, 2021(1): 53-59.
[14]	KOUROSH NIYA Ali, 黄金良. 利用遥感和GIS对伊朗最大红树林群体的变化进行检测和模拟[J]. 华东师范大学学报（自然科学版）, 2020, 2020(S1): 94-98.
[15]	王晶晶, 路艳琼. 二阶差分方程周期边值问题正解存在的最优条件[J]. 华东师范大学学报（自然科学版）, 2020, 2020(2): 41-49.