Hensel-lifting Computational Problem Based on Part Information Leaking

doi:10.3969/j.issn.1000-3428.2013.08.008

Computer Engineering ›› 2013, Vol. 39 ›› Issue (8): 38-43,54. doi: 10.3969/j.issn.1000-3428.2013.08.008

• Networks and Communications • Previous Articles Next Articles

Hensel-lifting Computational Problem Based on Part Information Leaking

ZANG Tong-zheng ¹, LV Ke-wei ²

(1. State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, Beijing 100049, China; 2. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100195, China)

Received:2012-03-26 Online:2013-08-15 Published:2013-08-13

基于部分信息泄露的Hensel提升计算问题

臧统政¹，吕克伟²

(1. 中国科学院研究生院信息安全国家重点实验室，北京 100049；2. 中国科学院信息工程研究所，北京 100195)

作者简介:臧统政(1986－)，男，硕士研究生，主研方向：隐藏数问题；吕克伟，副教授
基金资助:
国家自然科学基金资助项目(60970154)；中国科学院战略性先导专项基金资助项目“海云信息安全共性关键技术研究”(DXA06010702)

Abstract

Abstract:

The original Hidden Number Problem(HNP) usually works with a prime modules or a special form composite number modulus. To break through the limitation, this paper presents a method which can resolve the HNP in regular non-prime modulus case. It promotes the HNP in prime modulus case to the HNP in prime powers modulus case by introducing the Hensel-lifting method and lattice rounding technique in a creative way, and combines the Chinese remainder theorem to receive the achievement. Analysis result shows that the discrete logarithm computational problem under the Hensel-lifting situation can be reduced to the HNP in prime modulus case.

Key words: Hidden Number Problem(HNP), Hensel-lifting, lattice rounding, Most Significant Bit(MSB), discrete logarithm, Chinese remainder theorem

摘要：

针对传统隐藏数仅局限于模素数或模特定形式合数的问题，利用Hensel提升和格归约技术，提出一种隐藏数问题由模素数向模一般形式合数提升的方法。将隐藏数问题由模素数向模素数方幂提升，运用中国剩余定理得到模一般形式合数下的隐藏数问题。利用该方法证明Hensel提升的离散对数计算，可归约到模素数情况下的隐藏数问题。

关键词: 隐藏数问题, Hensel提升, 格归约, 最大有意比特, 离散对数, 中国剩余定理

CLC Number:

TP311

CANG Tong-Zheng, LV Ke-Wei. Hensel-lifting Computational Problem Based on Part Information Leaking[J]. Computer Engineering, 2013, 39(8): 38-43,54.

臧统政, 吕克伟. 基于部分信息泄露的Hensel提升计算问题[J]. 计算机工程, 2013, 39(8): 38-43,54.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2013.08.008

http://www.ecice06.com/EN/Y2013/V39/I8/38

References

[1] Boneh D, Venkatesan R. Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes[C]//Proc. of Crypto’96. [S. 1.]: Springer-Verlag, 1996.
[2] Nguyen P Q, Shparlinski I E. The Insecurity of the Digital Signature Algorithm with Partially Known Nonces[EB/OL]. (2012-04-08). http://www.di.ens.fr/~pnguyen.
[3] Vasco M I G, Naslund M, Shparlinski I E. The Hidden Number Problem in Extension Fields and Its Applications[C]//Proc. of the 5th Latin American Symposium on Theoretical Informatics. London, UK: Springer-Verlag, 2002: 105-117.
[4] Hlavac M, Rosa T. Extend Hidden Number Problem and its Cryptanalytic Applications[C]//Proc. of the 13th International Conference on Selected Areas in Cryptography. Germany, Berlin: Springer-Verlag, 2007.
[5] Moreno C J, Moreno O. Exponential Sums and Goppa Codes//Proc. of AMS’91. [S. 1.]: IEEE Press, 1991: 523-531.
[6] Babai L. On Lovasz Lattice Reduction and the Nearest Lattice Point Problem[J]. Combinatorica, 1986, 6(1): 1-13.
[7] Garefalakis T. The Hidden Number Problem with Non-prime Modulus[C]//Proc. of Progress in Computer Science and Applied Logic, Basel, Switzerland: Birkhauser-Verlag, 2001.
[8] Catalano D, Nguyen P Q, Stern J. The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm[C]//Proc. of ASIACRYPT’02. Germany, Berlin: Springer-Verlag 2002: 299-310.
[9] Nguyen P Q, Stern J. Lattice Reduction in Cryptology: An Update[C]//Proc. of ANTS-IV’00. [S. 1.]: Springer-Verlag, 2000: 85-112.
[10] Nguyen P Q, Stern J. The Two Faces of Lattices in Crypto- logy[C]//Proc. of CALC’01. [S. 1.]: Springer-Verlag, 2001: 146-180.
[11] Ajtai M, Kumar R, Sivakumar D. A Sieve Algorithm for the Shortest Lattice Vector Problem[C]//Proc. of the 33rd ACM Symp. on Theory of Computation. [S. 1.]: ACM Press, 2001: 601-610.
[12] Kannan R. Algorithmic Geometry of Numbers[J]. Annual Review of Computer Science, 1987, 2: 231-267.
[13] Drmota M, Tichy R. Sequences, Discrepancies and Appli- cations[M]. Germany, Berlin: Springer-Verlag, 1997.
[14] Niederreiter H. Random Number Generation and Quasi Monte Carlo Methods[M]. Philadelphia, USA: Society for Industrial and Applied Mathematics, 1992.
(下转第54页)
(上接第43页)

[15] Kuipers R, Niederreiter H. Uniform Distribution of Seque- nces[C]//Proc. of Wiley-Interscience. New York, USA: [s. n.], 1974.
[16] Nguyen P Q, Stern J. The Two Faces of Lattices in Crypto- logy[C]//Proc. of CALC’01. [S. 1.]: Springer-Verlag, 2001.
[17] Lenstra A K, Lenstra H W, Lovasz J L. Factoring Polynomials with Rational Coefficients[J]. Journal of Mathematische Annalen, 1982, 261(4): 515-534.
[18] Grotschel M, Lovasz L, Schrijver A. Geometric Algorithms and Combinatorial Optimization[M]. [S. 1.]: Springer-Verlag, 1993.
[19] 苏东, 王克, 吕克伟. Paillier陷门函数的两个变体的比特安全性分析[J]. 计算机学报, 2010, 33(6): 1050-1059.
[20] 苏东, 吕克伟. 基于隐藏数问题对广义SRA智力扑克协议的安全性研究[C]//第十八届全国信息保密学术会议论文集. 北京: 金城出版社, 2008.
[21] 谢晓蓉, 吕克伟, 王鲲鹏. ax+b mod p比特安全的列表译码证明[J]. 系统科学与数学, 2012, 32(11): 1366-1376.
[22] Shparlinski I E, Steinfeld R. Chinese Remaindering with Multiplicative Noise[D]. Sydney, Australia: Department of Computing, Macquarie University Sydney, 2005.
编辑索书志

Please choose a citation manager

Content to export

Hensel-lifting Computational Problem Based on Part Information Leaking

基于部分信息泄露的Hensel提升计算问题

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	CAO Suzhen,SUN Han,DAI Wenjie,WANG Xiuya. Selectively Linkable and Convertible Ring Signature Scheme Based on DLP [J]. Computer Engineering, 2019, 45(2): 144-147,153.
[2]	CHEN Huiyan,LIU Le,ZHANG Chenchen. An Identity-based Signature Scheme with CDH Problem Security [J]. Computer Engineering, 2018, 44(4): 174-180.
[3]	MA Min,LI Zhihui,XU Tingting. Verifiable (n,n) Threshold Quantum Secret Sharing Scheme [J]. Computer Engineering, 2017, 43(8): 169-172.
[4]	ZUO Liming,ZHANG Tingting,GUO Hongli,CHEN Zuosong. Certificateless Aggregate Signature Scheme Based on No Pairing Mapping [J]. Computer Engineering, 2017, 43(5): 313-316.
[5]	YANG Xiaodong,GAO Guojuan,ZHOU Qixu,LI Yanan,WANG Caifen. E-government Data Security Exchange Scheme Based on Proxy Re-signature [J]. Computer Engineering, 2017, 43(2): 183-188.
[6]	TANG Yongli,WANG Feifei,YAN Xixi,LI Zichen. Efficient and Provably Secure Certificateless Signature Schemes [J]. Computer Engineering, 2016, 42(3): 156-160.
[7]	FANG Xuefeng,WANG Xiaoming. Outsourced Encryption and Decryption CP-ABE Scheme with User Revocation [J]. Computer Engineering, 2016, 42(12): 124-128,132.
[8]	WANG Caifen,JIANG Hong,YANG Xiaodong,ZHANG Yulei,NIU Shufen. Multi-message and Multi-receiver Hybrid Signcryption Scheme Based on Discrete Logarithm [J]. Computer Engineering, 2016, 42(1): 150-155.
[9]	FENG Zeyu,GONG Boru,ZHAO Yunlei. Comparative Study of Digital Signature Standards Based on Discrete Logarithm [J]. Computer Engineering, 2016, 42(1): 145-149.
[10]	WU Yujie,YU Xiuqing,LI Xiong. Threshold Secret Sharing Scheme Based on Internal P-sets Theory [J]. Computer Engineering, 2015, 41(9): 159-163.
[11]	HE Junjie,ZHANG Xuefeng,QI Chuanda. A Certificateless Blind Signature Scheme Without Bilinear Pairing [J]. Computer Engineering, 2015, 41(7): 171-176.
[12]	ZHANG Wei,DU Weizhang. Dynamic Multi-secret Sharing Scheme Based on LUC Cryptosystem [J]. Computer Engineering, 2015, 41(6): 130-135.
[13]	YIN Fengmei,HOU Zhengfeng,PU Guangning,CHEN Hong. (t,n) Threshold Tracing Anonymous Authentication Scheme [J]. Computer Engineering, 2015, 41(5): 149-152,158.
[14]	NIU Shufen,WANG Caifen,ZHANG Yulei,CAO Suzhen. Data Integrity Verification Scheme for Multi-source Network Coding [J]. Computer Engineering, 2015, 41(3): 21-25.
[15]	DANG Jiali,YU Huifang. Group Signature Scheme Using Chinese Remainder Theorem [J]. Computer Engineering, 2015, 41(2): 113-116.

模态框（Modal）标题

Please choose a citation manager

Content to export

Hensel-lifting Computational Problem Based on Part Information Leaking

基于部分信息泄露的Hensel提升计算问题

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments