Create a Free IGI Global Library Account to Receive a 25% Discount on All Purchases

Exclusive benefits include one-click shopping, flexible payment options, free COUNTER 4 and MARC records, and a 25% discount on all titles as well as the award-winning InfoSci^{®}-Databases.

InfoSci^{®}-Journals Annual Subscription Price for New Customers: As Low As US$ 4,950

This collection of over 175 e-journals offers unlimited access to highly-cited, forward-thinking content in full-text PDF and XML with no DRM. There are no platform or maintenance fees and a guarantee of no more than 5% increase annually.

Encyclopedia of Information Science and Technology, Fourth Edition (10 Volumes) Extended Offer

Receive the complimentary e-books for the first, second, and third editions with the purchase of the Encyclopedia of Information Science and Technology, Fourth Edition e-book. Plus, take 20% off when purchasing directly through IGI Global's Online Bookstore.

Balasubramanian, Kannan. "Variants of the Diffie-Hellman Problem." Algorithmic Strategies for Solving Complex Problems in Cryptography. IGI Global, 2018. 40-54. Web. 24 Apr. 2018. doi:10.4018/978-1-5225-2915-6.ch003

APA

Balasubramanian, K. (2018). Variants of the Diffie-Hellman Problem. In K. Balasubramanian, & M. Rajakani (Eds.), Algorithmic Strategies for Solving Complex Problems in Cryptography (pp. 40-54). Hershey, PA: IGI Global. doi:10.4018/978-1-5225-2915-6.ch003

Chicago

Balasubramanian, Kannan. "Variants of the Diffie-Hellman Problem." In Algorithmic Strategies for Solving Complex Problems in Cryptography, ed. Kannan Balasubramanian and M. Rajakani, 40-54 (2018), accessed April 24, 2018. doi:10.4018/978-1-5225-2915-6.ch003

Many variations of the Diffie-Hellman problem exist that can be shown to be equivalent to one another. We consider following variations of Diffie-Hellman problem: square computational and Square decisional Diffie-Hellman problem, inverse computational and inverse computational decisional Diffie-Hellman problem and divisible computational and divisible decisional Diffie-Hellman problem. It can be shown that all variations of computational Diffie-Hellman problem are equivalent to the classic computational Diffie-Hellman problem if the order of a underlying cyclic group is a large prime. We also describe other variations of the Diffie-Hellman problems like the Group Diffie-Hellman problem, bilinear Diffie-Hellman problem and the Elliptic Curve Diffie-Hellman problem in this chapter.

In this chapter, we are considering useful variations of Diffie-Hellman problem: square Computational (and decisional) Diffie-Hellman problem, inverse computational (and decisional) Diffie-Hellman problem and divisible computational (and decisional) Diffie-Hellman problem. We are able to show that all variations of computational Diffie-Hellman problem are equivalent to the classic computational Diffie-Hellman problem if the order of an underlying cyclic group is a large prime (Bao et al., 2003).

Let p be a large prime number such that the discrete logarithm problem defined in is hard. Let G be a cyclic group of prime order q and g is assumed to be a generator of G. It is assumed that G is prime order, and security parameters p; q are defined as the fixed form p = 2q + 1 and ord(g) = q. A remarkable computational problem has been defined on this kind of set by Diffie and Hellman (Diffie, 1976). The Diffie-Hellman assumption (CDH assumption) is stated as follows:

•

Computational Diffie-Hellman Problem (CDH): On input g, g^{x}, g^{y}, computing g^{xy}. An algorithm that solves the computational Diffie-Hellman problem is a probabilistic polynomial time Turing machine, on input g, g^{x}, g^{y}, outputs g^{xy} with non-negligible probability. The Computational Diffe-Hellman assumption means that such a probabilistic polynomial time Turing Machine does not exist. This assumption is believed to be true for many cyclic groups, such as the prime sub-group of the multiplicative group of finite fields.

•

Square Computational Diffie-Hellman Assumption: The square computational Diffie-Hellman problem, introduced in (Maurer et al., 1998) is defined as follows:

•

Square Computational Diffie-Hellman Problem (SCDH): On input g, g^{x}, computing . An algorithm that solves the square computational Diffie-Hellman problem is a probabilistic polynomial time Turing machine, on input g, g^{x}, outputs g^{x}^{2} with non-negligible probability. The square computational Diffie- Hellman assumption means that there no such a probabilistic polynomial time Turing machine does not exist.