The Security of Polynomial Information of Diffie-Hellman Key

摘要

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.