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

华东师范大学学报(自然科学版) ›› 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]. 华东师范大学学报（自然科学版）, 2021, 2021(2): 151-159.
[2]	毕艳芳, 王焘. 修正牛顿动力学中的平面圆形限制性三体问题[J]. 华东师范大学学报（自然科学版）, 2021, 2021(1): 53-59.
[3]	KOUROSH NIYA Ali, 黄金良. 利用遥感和GIS对伊朗最大红树林群体的变化进行检测和模拟[J]. 华东师范大学学报（自然科学版）, 2020, 2020(S1): 94-98.
[4]	王晶晶, 路艳琼. 二阶差分方程周期边值问题正解存在的最优条件[J]. 华东师范大学学报（自然科学版）, 2020, 2020(2): 41-49.
[5]	吴雪, 黄力, 靳程, 钱深华, 杨永川. 重庆主城区杂草物种组成特征及多样性格局[J]. 华东师范大学学报（自然科学版）, 2020, 2020(2): 98-109.
[6]	杨庆松, 刘何铭, 朱彤彤, 张首和, 王希华. 浙江天童国家森林公园常绿阔叶林种间关联和种-生境关联[J]. 华东师范大学学报（自然科学版）, 2020, 2020(2): 110-119.
[7]	沈力健. 与实二次域上的亏格理论相关的恒等式[J]. 华东师范大学学报(自然科学版), 2019, 2019(6): 7-20.
[8]	张煊宜, 施润和. 城市服务设施对房价分布格局的影响力探究[J]. 华东师范大学学报(自然科学版), 2019, 2019(6): 169-178.
[9]	蔡静. 严格次对角占优线性方程组迭代法的收敛性分析[J]. 华东师范大学学报(自然科学版), 2019, 2019(2): 1-6,55.
[10]	张德英, 周云云, 冷燮, 李龙, 周嘉源, 施润和. 基于精细化人口格网的城市机构养老设施供需分析——以上海市浦东新区为例[J]. 华东师范大学学报(自然科学版), 2019, 2019(2): 174-183.
[11]	廖瑜欣, 张勇, 古润竹. 用水效率目标约束下的省市用水差异及分区对策探讨[J]. 华东师范大学学报(自然科学版), 2019, 2019(1): 136-143.
[12]	陈海珍, 周圣武, 孙祥艳. 混合分数布朗运动下的回望期权定价[J]. 华东师范大学学报(自然科学版), 2018, 2018(4): 47-58.
[13]	庞立华, 孔范龙, 郗敏, 李悦. 胶州湾海岸带生态脆弱性时空变化分析[J]. 华东师范大学学报(自然科学版), 2018, 2018(3): 222-233.
[14]	陈晓静; 胡志华; 李功君; 滕炜超;. 成组集中策略下滚装汽车堆场车位分配优化[J]. 华东师范大学学报(自然科学版), 2017, 2017(1): 11-18.
[15]	齐林明, 李金波, 李卫奇. 平面图的3-hued 染色[J]. 华东师范大学学报(自然科学版), 2017, 2017(1): 32-37.