Application Of Partial-CDH Problem Over Finite Fields In Cryptography

A long-standing interesting problem in cryptography is the Diffie-Hellman problem defined over finite fields. The difficulty of Diffie-Hellman problem is based on the difficulty of discrete logarithm problem, which is essential to establishing the security for some key exchange protocols and encryption schemes. There are two forms of Diffie-Hellman problem:the Computational Diffie-Hellman (CDH) Assumption and Decisional Diffie-Hellman (DDH) As-sumption, without having to make the stronger one-DDH Assumption, CDH Assumption is strong enough to guarantee the security for Diffie-Hellman key exchange protocol and ElGamal encryption scheme, which attracts more at-tentions from Cryptographic researchers.2013, Fazio, Gennaro, Perera and Skeith III(FGPS)[1] made a significant breakthrough by introducing a variant of the CDH problem over finite fields, i.e., the Partial-CDH problem. Instead of considering gab∈Fp2in Diffie-Hellman problem, FGPS computed [gab]1, which denote the coefficient of the degree-1term of the polynomial form of gab over F2p. Assuming the hardness of the Partial-CDH problem, FGPS proved the unpredictability of every single bit of one of the coordinates of the secret DH value gab. Meanwhile, FGPS left several open questions. The most natural one is to extend the results to Fpt(t>2). Other questions include the study of the hardness of the Partial-CDH problem in Fpt<(t>1). In particular, the future work can discuss the possibility of reducing the Partial-CDH problem over Fpt to the regular CDH problem over Fp. Recently, M.Q.Wang[2] extended the definition of Partial-CDH problem given in [1]. defined the following new Diffie-Hellman problems over finite fields Fp2:dual-Partial-CDH problem,(t, k)-Partial-CDH problem, dual-(t, k)-Partial-CDH problem. M.Q.Wang[2] also studied the hardness of the above new Diffie-Hellman problems and got some important results. He proved that the Partial-CDH problem and Dual Partial-CDH problem over finite fields Fp2is equivalent to the original CDH problem over finite fields Fp2. Assuming the hardness of the CDH problem, M.Q.Wang proved the unpredictability of every bit of the coordinate of the secret value.Considering conclusions in [1] and [2], we believe we can apply the equiv-alence between these new Diffie-Hellman problems in relevantkey exchange protocols and encryption schemes, which leads to the efficiency improvement and security consistency at the same time. In this paper, we modify some protocols based on the difficulty of the Diffie-Hellman assumption. For two party key exchange protocol, whose security is based on CDH assumption, the secret key is denoted by K=gab. Applying the difficulty equivalence we define the secret key as K’=[gab]1instead of the entire value of K. For two party key exchange protocol, we modify the secret key as K’=[gab]1in-stead of K=e(P, P)abc. Obviously, the length of K’is shorter than K, which means same security but shorter packet length and higher efficiency when the secret key is applied in block cipher. Besides, we improve the encryption scheme based on CDH problem by changing cipher text from C=(tP, M(?)H(e(P,aP)t)); to C=(tP, M(?)H([e(P,aP)t]0)); which combined with dual-Partial-CDH problem. We also give the proof of its security.