Variants of the Diffie-Hellman Problem

Variants of the Diffie-Hellman Problem

Kannan Balasubramanian (Mepco Schlenk Engineering College, India)
DOI: 10.4018/978-1-5225-2915-6.ch003
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

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.
Chapter Preview
Top

Diffie-Hellman Problem

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, gx, gy, computing gxy. An algorithm that solves the computational Diffie-Hellman problem is a probabilistic polynomial time Turing machine, on input g, gx, gy, outputs gxy 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, gx, computing . An algorithm that solves the square computational Diffie-Hellman problem is a probabilistic polynomial time Turing machine, on input g, gx, outputs gx2 with non-negligible probability. The square computational Diffie- Hellman assumption means that there no such a probabilistic polynomial time Turing machine does not exist.

Complete Chapter List

Search this Book:
Reset