The Security of Polynomial Information of Diffie-Hellman Key

详细信息    查看全文

• 关键词：Diffie ; Hellman key ; m ; sparse polynomial ; Polynomial information ; n ; DH problem
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9543
• 期：1
• 页码：71-81
• 全文大小：214 KB
• 参考文献：1.Shparlinski, I.E.: Security of polynomial transformations of the Diffie-Hellman key. Finite Fields Appl. 10(1), 123–131 (2004)MathSciNet CrossRef MATH
  2.Boneh, D., Venkatesan, R.: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 129–142. Springer, Heidelberg (1996)
  3.Vasco, M.I.G., Shparlinski, I.E.: On the security of Diffie-Hellman bits. In: Proceedings of the Workshop on Cryptography and Computer Number Theory, Singapore, 1999, pp. 257–268. Birkhauser, Basel (2001)
  4.Vasco, M.I.G., Naslund, M.: A survey of hard core functions. In: Proceedings of the Workshop on Cryptography and Computational Number Theory, Singapore, 1999, pp. 227–256. Birkhauser, Basel (2001)
  5.Verheul, E.R.: Certificates of recoverability with scalable recovery agent security. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 258–275. Springer, Heidelberg (2000)CrossRef
  6.Brouwer, A.E., Pellikaan, R., Verheul, E.R.: Doing more with fewer bits. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 321–332. Springer, Heidelberg (1999)CrossRef
  7.Cash, D.M., Kiltz, E., Shoup, V.: The twin Diffie-Hellman problem and applications. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 127–145. Springer, Heidelberg (2008)CrossRef
  8.Chen, L., Chen, Y.: The n-Diffie-Hellman problem and its applications. In: Lai, X., Zhou, J., Li, H. (eds.) ISC 2011. LNCS, vol. 7001, pp. 119–134. Springer, Heidelberg (2011)CrossRef
  
• 作者单位：Yao Wang (17) (18) (19)
  Kewei Lv (17) (18)
  
  17. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100093, China
  18. Data Assurance Communication Security Research Center, Chinese Academy of Sciences, Beijing, 100093, China
  19. University of Chinese Academy Sciences, Beijing, 100049, China
  
• 丛书名：Information and Communications Security
• ISBN：978-3-319-29814-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In this paper, we study the relations between the security of Diffie-Hellman (DH) key and the leakage of polynomial information of it again. Given a fixed sparse polynomial F(X) and an oracle, which returns value of polynomial of DH key i.e., \(F(g^{xy})\) when called by \(g^{x}\) and \(g^{y}\), we obtain a probabilistic algorithm to recover the key. It is an extension of Shparlinski’s result in 2004. This shows that finding polynomial information of DH key is as difficult as the whole key again. Furthermore, we study a variant of DH problem given 2 and \(g^{y}\) to compute \(2^{y}\) and the n-DH problem with this method respectively, and obtain similar results.