The D-th CDH Problem Over Finite Fields

In 1976, Diffie and Hellman defined Diffie-Hellman problem in their paper-New Directions in Cryptography[6]. It included two parts:Computational-Diffie-Hellman problem and Decisional Diffie-Hellman problem. Of particular interest is the CDH problem.In 2013, FGPS[3]first defined a new CDH problem over Fp2, i.e. Partial-CDH problem, but they did not certify its difficulty. In 2015, WZZ[1] gave the definition of its dual variant, i.e. Dual-Partial-CDH problem over Fp2 and proved that their hardness was equal to the traditional CDH problem. Meanwhile, WZZ generalized the extension of this problem over Fp2 to the d-th CDH problem over Fpt (t> 1) and reduced traditional CDH problem to this problem. In fact, as for the equivalence of d-th CDH problem and regular CDH problem, Verheul gave his deduction in 2000. His conclusion was that given an oracle function which can compute a coefficient of Diffie-Hellman key, then there existed efficient polynomial time algorithm to solve Diffie-Hellman problem. However, he didn’t take the oracle with noise into consideration and the complexity of his reduction had exponential running time in t which was the extension degree of finite field Fp. Therefore, this resulted in a strict restriction that parameter t should be very small. And WZZ[1] used a different reduction to verify their equivalence. His results were that for d={0,t-1}, CDH adversary could achieve advantage at least for other d (1≤d≤t- 2), his advantage was at least With perfect oracle, using WZZ reduction, CDH adversary can efficiently break Diffie-Hellman key by polynomial operations. By contrast, WZZ algorithm has more advantages. Its complexity is not exponential time in t and their algorithm considers the oracle with noise. But, the process of WZZ reduction is rather complex and only certify that matrices Mh,d are invertible for d={0, t-1}. In fact, for all 0< d< t-1, matrices Mh,d are definitely invertible with the probability 1. Besides, their paper didn’t give the computational formula for every entry of matrices Mh,d.Compared with Verheul’s reduction, we have reduced the computational com-plexity from exponential time to polynomial time; compared with WZZ’s method, this paper has improved the reduction efficiency of traditional CDH problem to d-th CDH problem. WZZ’s reduction can be expressed by O*d()=XM’. The advantage of its CDH adversary is computed by analyzing the probability of matrix M’ being invertible. In this paper, using polynomial base representation of finite fields and the introduction of d-th base multiplication matrix make the reduction more clear and the expression more concise. The improved reduction equation is represent-ed as Od*l()0≤l≤t-1= XMd(Yl)0≤l≤t-1T We consider the invertible probability of matrix Md and random matrix (Yl)0<l<t-1T respectively. The improved algorithm has given the computational formula for every entry of base multiplication matri-ces Md(0≤d÷t-1), and used its invertibility to obtain this conclusion:CDH adversary achieves advantage at least for all 0< d< t-1. With perfect oracle, the improved algorithm can still compute Diffie-Hellman key by polynomial operations; with loss of probability, the advantage of CDH adversary increases by (1-1/p)t compared with original reduction. Besides, we have proved all the Mh,d in WZZ’s algorithm are invertible theoretically and have gotten a bigger lower bound of attack advantage.