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

doi:10.3969/j.issn.1000-0801.2013.03.016

Abstract

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

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.

Figures/Tables 4

References 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

Metrics

Recommended 0

No Suggested Reading articles found!

γ	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]	Shengli ZHOU, Keyi JIANG, Bo XU, Rui XU, Xikang ZHANG, Quanzhe ZHAO, Yangdong XU. Research on the effectiveness evaluation of cyber security curriculum construction for combating telecom network fraud [J]. Telecommunications Science, 2023, 39(6): 122-128.
[2]	Le ZHANG, Hongyuan MA. Practice on edge cloud security of telecom operators [J]. Telecommunications Science, 2023, 39(4): 165-172.
[3]	Fuyuan CHEN, Zhenjiang DONG, Jiankuo DONG, Minjie XU. A survey of V2X security protection technologies [J]. Telecommunications Science, 2023, 39(3): 1-15.
[4]	Jingjie SHEN, Guangqiu LI, Yancui LUO, Huizhi LIU. Physical layer security of full-duplex relay-assisted D2D networks under outdated CSI [J]. Telecommunications Science, 2023, 39(3): 89-99.
[5]	Yu KANG, Yaqiong LIU, Tongyu ZHAO, Guochu SHOU. A survey on AI algorithms applied in communication and computation in Internet of vehicles [J]. Telecommunications Science, 2023, 39(1): 1-19.
[6]	Yifan DING, Guangqiu LI, Hui LI. Physical layer security of NOMA-D2D cooperative wireless system [J]. Telecommunications Science, 2022, 38(9): 83-94.
[7]	Jianwu ZHANG, Yanjun AN, Huangyan DENG. A survey on DNS attack detection and security protection [J]. Telecommunications Science, 2022, 38(9): 1-17.
[8]	Yusun FU, Jinhui TANG. A survey on 5G capabilities enabling the factories of the future [J]. Telecommunications Science, 2022, 38(9): 18-35.
[9]	Weixiong CHEN, Xiaochen YANG, Zengjun CHUN, Ruolan LI, Hua ZHANG. Research and practice of network security threat intelligence management system for power enterprise [J]. Telecommunications Science, 2022, 38(7): 184-189.
[10]	Hongbin LUO, Shan ZHANG, Zhiyuan WANG. Interconnection and coexistence of heterogeneous network:requirements, challenges, and architecture [J]. Telecommunications Science, 2022, 38(6): 18-30.
[11]	Yifan DING, Guangqiu LI, Hui LI. Physical layer security for SWIPT-NOMA system in presence of randomly located eavesdroppers [J]. Telecommunications Science, 2022, 38(3): 133-142.
[12]	Shimulin XIE, Ijie BA, Xiang ZHANG, Zeyi TANG, Weifan NIAN, Xujie LIU. Task security scheduling method for 5G+MEC based grid edge computing platform [J]. Telecommunications Science, 2022, 38(12): 78-85.
[13]	Yatian LIU, Bowen HU, Maofei CHEN, Dongxin LIU. Study on the 5GC security situational awareness system [J]. Telecommunications Science, 2022, 38(11): 73-85.
[14]	Yunyi LIU, Jianmin ZHANG, Xiaoli FENG, Liwei ZHANG. 5G MEC system security capability deployment scheme [J]. Telecommunications Science, 2022, 38(11): 143-152.
[15]	Jianfeng CHEN, Miao CUI, Guangchi ZHANG, Qingqing WU, Hui ZENG. Secure communication optimization for double-IRS assisted SWIPT system [J]. Telecommunications Science, 2022, 38(1): 47-60.

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

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 13

Related Articles 15

Metrics

Recommended 0