Research on the Bit Security of Elliptic Curve Diffie-Hellman

Wei WEI; Jiazhe CHEN; Dan LI; Baofeng ZHANG

doi:10.11999/JEIT190845

Volume 42 Issue 8

Aug. 2020

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2020 > 42(8): 1820-1827

Wei WEI, Jiazhe CHEN, Dan LI, Baofeng ZHANG. Research on the Bit Security of Elliptic Curve Diffie-Hellman[J]. Journal of Electronics & Information Technology, 2020, 42(8): 1820-1827. doi: 10.11999/JEIT190845

Citation:

Wei WEI, Jiazhe CHEN, Dan LI, Baofeng ZHANG. Research on the Bit Security of Elliptic Curve Diffie-Hellman[J]. Journal of Electronics & Information Technology, 2020, 42(8): 1820-1827. doi: 10.11999/JEIT190845

Citation:

PDF( 537 KB)

Research on the Bit Security of Elliptic Curve Diffie-Hellman

doi: 10.11999/JEIT190845

Wei WEI¹,
Jiazhe CHEN¹,
Dan LI³,
Baofeng ZHANG^{1, 2
,
,}

1.
China Information Technology Security Evaluation Center, Beijing 100085, China
2.
Tsinghua University, Beijing 100084, China
3.
The Open University of China, Beijing 100039, China

Funds: The National Key Research and Development Program of China (2016YFB0800902), The National Natural Science Foundation of China (61802439, U1936209)

Received Date: 2019-11-01
Rev Recd Date: 2020-04-16

Available Online: 2020-04-24

Publish Date: 2020-08-18

Abstract

Abstract

The elliptic curve Diffie-Hellman key exchange protocol enjoys great advantages since it could achieve the same security level with significantly smaller size of parameters compared with other public key cryptosystems. In real-world scenarios, this type of protocol requires less bandwidth and storage which leads to more application especially to computing resource constrained environments. Hence, it is important to evaluate the threat aroused by the partial information leakage during the establishment of shared keys. In this paper, the bit security of elliptic curve Diffie-Hellman with knowledge of partial inner bits based on the combination of hidden number problem and lattice-based cryptanalysis technique is recisited. 11/12 of the inner bits of the x-coordinate of the elliptic curve Diffie-Hellman key are approximately as hard to compute as the entire key. Moreover, the explicit relationship between the leakage fraction and the leakage position is elaborated. This result which relaxes the restriction on the location of leakage position dramatically improves the trivial one which stemmed from prior work.
- Elliptic curve Diffie-Hellman,
- Bit security,
- Information leakage,
- Lattice,
- Hidden Number Problem(HNP)

FullText(HTML)

References(24)

References

KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987, 48(177): 203–209. doi: 10.1090/S0025-5718-1987-0866109-5

MILLER V S. Use of elliptic curves in cryptography[C]. Proceedings of Conference on the Theory and Application of Cryptographic Techniques, California, USA, 1986: 417–426.

BONEH D and VENKATESAN R. Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes[C]. The 16th Annual International Cryptology Conference, California, USA, 1996: 129–142.

LIU Mingjie, CHEN Jiazhe, and LI Hexin. Partially known nonces and fault injection attacks on SM2 signature algorithm[C]. The 9th International Conference on Information Security and Cryptology, Guangzhou, China, 2014: 343–358.

NGUYEN P Q and SHPARLINSKI I E. The insecurity of the elliptic curve digital signature algorithm with partially known nonces[J]. Designs, Codes and Cryptography, 2003, 30(2): 201–217. doi: 10.1023/A:1025436905711

FAN Shuqin, WANG Wenbo, and CHENG Qingfeng. Attacking OpenSSL implementation of ECDSA with a few signatures[C]. 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 2016: 1505–1515.

GANJI F, KRÄMER J, SEIFERT J P, et al. Lattice basis reduction attack against physically unclonable functions[C]. The 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, USA, 2015: 1070–1080.

BREITNER J and HENINGER N. Biased nonce sense: lattice attacks against weak ECDSA signatures in cryptocurrencies[J]. Financial Cryptography and Data Security, 2019: 3–20.

MOGHUMI D, SUNAR B, EISENBARTH T, et al. TPM-FAIL: TPM meets timing and lattice attacks[J]. arXiv: 2019, 1911.05673.

BONEH D, HALEVI S, and HOWGRAVE-GRAHAM N. The modular inversion hidden number problem[C]. The 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, 2001: 36–51.

XU Jun, SARKAR S, HU Lei, et al. New results on modular inversion hidden number problem and inversive congruential generator[C]. The 39th Annual International Cryptology Conference, Santa Barbara, USA, 2019: 297–321.

SHANI B. On the bit security of elliptic curve Diffie-Hellman[C]. The 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands, 2017: 361–387.

XU Jun, HU Lei, and SARKAR S. Cryptanalysis of elliptic curve hidden number problem from PKC 2017[J]. Designs, Codes and Cryptography, 2020, 88(2): 341–361. doi: 10.1007/s10623-019-00685-y

HLAVÁČ M and ROSA T. Extended hidden number problem and its cryptanalytic applications[C]. The 13th International Workshop on Selected Areas in Cryptography, Montreal, Canada, 2007: 114–133.

WEI Wei, CHEN Jiazhe, LI Dan, et al. Partially known information attack on SM2 key exchange protocol[J]. Science China Information Sciences, 2019, 62(3): 032105. doi: 10.1007/s11432-018-9515-9

张江, 范淑琴. 关于非对称含错学习问题的困难性研究[J]. 电子与信息学报, 2020, 42(2): 327–332. doi: 10.11999/JEIT190685

ZHANG Jiang and FAN Shuqin. On the hardness of the asymmetric learning with errors problem[J]. Journal of Electronics &Information Technology, 2020, 42(2): 327–332. doi: 10.11999/JEIT190685

NGUYEN P Q and SHPARLINSKI I E. The insecurity of the digital signature algorithm with partially known nonces[J]. Journal of Cryptology, 2002, 15(3): 151–176. doi: 10.1007/s00145-002-0021-3

谢天元, 李昊宇, 朱熠名, 等. FatSeal: 一种基于格的高效签名算法[J]. 电子与信息学报, 2020, 42(2): 333–340. doi: 10.11999/JEIT190678

XIE Tianyuan, LI Haoyu, ZHU Yiming, et al. FatSeal: An efficient lattice-based signature algorithm[J]. Journal of Electronics &Information Technology, 2020, 42(2): 333–340. doi: 10.11999/JEIT190678

LENSTRA A K, LENSTRA H W JR, and LOVÁSZ L. Factoring polynomials with rational coefficients[J]. Mathematische Annalen, 1982, 261(4): 515–534. doi: 10.1007/BF01457454

SCHNORR C P. A hierarchy of polynomial time lattice basis reduction algorithms[J]. Theoretical Computer Science, 1987, 53(2/3): 201–224.

MICCIANCIO D and GOLDWASSER S. Complexity of Lattice Problems: A Cryptographic Perspective[M]. Boston, USA: Kluwer Academic Publishers, 2002.

NGUYEN P Q. Hermite’s Constant and Lattice Algorithms[M]. NGUYEN P Q and VALLÉE B. The LLL Algorithm: Survey and Applications. Berlin, Germany: Springer, 2009: 19–69.

GAMA N, NGUYEN P Q, and REGEV O. Lattice enumeration using extreme pruning[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France, 2010: 257–278.

AONO Y and NGUYEN P Q. Random sampling revisited: Lattice enumeration with discrete pruning[C]. The 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, 2017: 65–102.

Relative Articles

Supplements(0)

Cited By

Proportional views