基于PACDP的全同态加密方案的一种攻击方法

doi:10.3969/j.issn.1000-0801.2013.03.016

电信科学 ›› 2013, Vol. 29 ›› Issue (3): 85-89.doi: 10.3969/j.issn.1000-0801.2013.03.016

基于PACDP的全同态加密方案的一种攻击方法

王政^1,²,丁勇^1,²,李新国³,柳毅⁴

¹ 桂林电子科技大学数学与计算科学学院桂林541004
² 西安电子科技大学综合业务网理论及关键技术国家重点实验室西安 710126
³ 深圳数字电视国家工程实验室股份有限公司深圳 518057
⁴ 广东工业大学计算机科学学院广州 510006

出版日期:2013-03-20 发布日期:2017-06-16
基金资助:
国家“863”项目基金资助项目;国家自然科学基金资助项目;广东省教育部产学研结合项目;广西无线宽带通信与信号处理重点实验室2012年开放基金资助项目，综合业务网理论及关键技术国家重点实验室2012年开放基金资助项目

A Method to Attack the FHE Schemes Based on the Hardness of PACDP

Zheng Wang^1,²,Yong Ding^1,²,Xinguo Li³,Yi Liu⁴

¹ Schoo1 of Mathematics and Computationa1 Science, Gui1in University of E1ectronic Techno1ogy, Gui1in 541004, China
² The State Key Laboratory of Integrated Services Networks,Xidian University,Xi'an 710126,China
³ Shenzhen Digita1 TV Nationa1 Engineering Laboratory Co.,Ltd.,Shenzhen 518057,China
⁴ Schoo1 of Computer Science,Guangdong University of Techno1ogy,Guangzhou 510006,China

Online:2013-03-20 Published:2017-06-16

摘要/Abstract

摘要：

针对汤等人设计的整数上具有更小公钥尺寸的全同态加密方案，研究安全性基于整数上部分近似公因子问题（PACDP）的全同态加密方案的攻击方法。通过对公钥噪声区间进行适当的分割，结合快速多项式多点求值，再利用GCD算法得到私钥，从而成功攻击安全性基于PACDP的全同态加密方案。

关键词: 全同态加密, 安全性, PACDP, 快速多项式多点求值

Abstract:

For the FHE scheme designed by Tang et a1, the security of the FHE schemes based on the hardness of a partia11y approximate integer common divisor prob1em（PACDP）was discussed.By dividing the interva1 of the noise of the pub1ic key, using the fast po1ynomia1 mu1tipoint eva1uation and GCD a1gorithm to get the secret key, the FHE schemes based on the hardness of PACDP were successfu11y crashed down.

Key words: fu11y homomorphic encryption, security, PACDP, fast po1ynomia1 mu1tipoint eva1uation

王政,丁勇,李新国,柳毅. 基于PACDP的全同态加密方案的一种攻击方法[J]. 电信科学, 2013, 29(3): 85-89.

Zheng Wang,Yong Ding,Xinguo Li,Yi Liu. A Method to Attack the FHE Schemes Based on the Hardness of PACDP[J]. Telecommunications Science, 2013, 29(3): 85-89.

图/表 4

表1

图1

图2

表2

参考文献 13

1	Rona1d L R , Len A , Michael L D , . On data banks and privacy homomorphisms. Foundations of Secure Computation, New York, 1978, 9: 169～180.
2	Gentry Craig . Fully homomorphic encryption using ideal lattices. STOC 2009, Bethesda, Maryland, USA, 2009: 169～178.
3	Gentry Craig . A fully homomorphic encryption scheme. PhD Thesis,Stanford University.
4	Van Dijk Marten , Gentry Craig , Ha1evi Shai , et al. Fully homomorphic encryption over the integers. EUROCRYPT 2010, LNCS, 2010 24～43.
5	Jean-Sebastien C , Avradip M , David N , et al. Fully homomorphic encryption over the integers with shorter public keys. P Rogaway（Ed）, CRYPTO 2011, LNCS, Springer, 2011: 487～504.
6	Gentry Craig , Ha1evi Shai . Implementing gentry's fully-homomorphic encryption scheme. Paterson, KG（ed）EUROCRYPT 2011, LNCS, Springer, Heidelberg, 2011: 129～148.
7	Jean-Sebastien C , David N , Mehdi T , . Pub1ic Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers. Cryptology ePrint Archive Report, 2011
8	Brakerski Zvika , Gentry Craig , Vaikuntanathan Vinod , . Fully Homomorphic Encryption without Bootstrapping. Cryptology ePrint Archive Report, 2011
9	汤殿华，祝世雄，曹云飞 . 一个较快速的整数上的全同态加密方案. 计算机工程与应用， 2011
10	Stehlé Damien , Steinfeld Ron . Faster fully homomorphic encryption. Asiacrypt2010，LNCS, 2010 377～394
11	古春生，景征骏，于志敏 . 破解较快速的整数上的全同态加密方案. 计算机工程与应用， 2012
10	Chen Y M , Nguyen P Q . Faster A1gorithms for Approximate Common Divisors:Breaking Fully-Homomorphic-Encryption Challenges over the Integers. Cryptology ePrint Archive Report, 2011
13	Howgrave-Graham Nick . Approximate integer divisors. CaLC'01, Lecture Notes in Computer Science, Springer, 2001: 51～66

γ	2²¹	2²²	2²³	2²⁴	2²⁵
GCD运算时间（s）	2.7	6.7	16.4	39.2	89.9
模乘运算时间（s）	0.5	1.2	2.8	6.7	15.4

γ	1.6×10⁵	0.86×10⁶	4.2×10⁵
ρ	16	24	32
GCD穷举搜索所需要时间	40 min	96天	623年
参考文献[12]中新方案所需时间	1.6 min	7.1 h	190天

[1]	谢石木林, 白杰, 张翔, 汤泽毅, 粘为帆, 刘旭杰. 基于5G+MEC的电网边缘计算平台任务安全性调度方法[J]. 电信科学, 2022, 38(12): 78-85.
[2]	惠宁,伍杰,周一青,刘玲,潘振岗. 未来车辆雾计算网络[J]. 电信科学, 2020, 36(6): 14-27.
[3]	王兴鹏,许晓荣,胡安迪,冯维. Nakagami-m衰落信道下存在窃听攻击的认知中继网络安全性与可靠性折中方案[J]. 电信科学, 2018, 34(12): 24-32.
[4]	邓旭. PTN网络架构中L2转L3设置方案[J]. 电信科学, 2017, 33(6): 164-170.
[5]	刘昀,刘国军,任建伟,李坚. 电力PTN设备网管安全性[J]. 电信科学, 2015, 31(Z1): 85-89.
[6]	高丽丹,孙凤杰,刘国军,李建岐. 基于电力应用的PTN安全综合评价[J]. 电信科学, 2015, 31(Z1): 90-94.
[7]	赖俊森,吴冰冰,李少晖,赵文玉,张海懿. 量子保密通信研究进展与安全性分析[J]. 电信科学, 2015, 31(6): 39-45.
[8]	张丽敏. 云环境下一种低成本的数据安全存储和处理框架[J]. 电信科学, 2015, 31(2): 46-51.
[9]	王崇霞,高美真,刘倩,周贤伟. 混合云联合身份认证与密钥协商协议设计[J]. 电信科学, 2014, 30(4): 95-99.
[10]	范盛超,章国安,费洪海,邱恭安. 一种WLAN Mesh网络漫游接入认证协议[J]. 电信科学, 2012, 28(2): 104-109.

基于PACDP的全同态加密方案的一种攻击方法

A Method to Attack the FHE Schemes Based on the Hardness of PACDP

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 13

相关文章 10

Metrics

推荐阅读 0