Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore.

Additionally, libraries can receive an extra 5% discount. Learn More

Additionally, libraries can receive an extra 5% discount. Learn More

Kannan Balasubramanian (Mepco Schlenk Engineering College, India)

Copyright: © 2018
|Pages: 15

DOI: 10.4018/978-1-5225-2915-6.ch003

Chapter Preview

TopIn 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* = 2*q* + 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*, computing^{y}*g*. An algorithm that solves the computational Diffie-Hellman problem is a probabilistic polynomial time Turing machine, on input^{xy}*g*,*g*,^{x}*g*, outputs^{y}*g*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.^{xy}*•***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*, computing . An algorithm that solves the square computational Diffie-Hellman problem is a probabilistic polynomial time Turing machine, on input^{x}*g*,*g*, outputs^{x}*g*^{x}with non-negligible probability. The square computational Diffie- Hellman assumption means that there no such a probabilistic polynomial time Turing machine does not exist.^{2}

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved