The Decision Diffie-Hellman Problem

The Decision Diffie-Hellman Problem

| Dan Boneh
The Decision Diffie-Hellman (DDH) problem is a key concept in cryptography, enabling the construction of secure cryptographic systems. This paper surveys recent applications of DDH and known results about its security, while also highlighting open problems in the area. The Diffie-Hellman key exchange protocol relies on the Computational Diffie-Hellman (CDH) assumption, which states that no efficient algorithm can compute the shared secret $ g^{ab} $ from $ g^a $ and $ g^b $. However, CDH alone is insufficient to prove the security of the protocol, as an eavesdropper might still gain useful information about the secret. The DDH assumption, which is stronger, ensures that no efficient algorithm can distinguish between the distributions $ \langle g^a, g^b, g^{ab} \rangle $ and $ \langle g^a, g^b, g^c \rangle $, where $ a, b, c $ are random. This makes DDH a stronger assumption than CDH. While CDH allows the extraction of one unpredictable bit (a hard core bit) from $ g^{ab} $, this process is inefficient. In contrast, DDH allows the extraction of $ n/2 $ bits from a single Diffie-Hellman exchange, which are indistinguishable from random bits. This is achieved using the leftover hash lemma. Cryptographic systems that derive multiple bits from the Diffie-Hellman secret implicitly rely on DDH, not CDH. The DDH assumption is very strong and not always valid. For example, in the multiplicative group $ \mathbb{Z}_p^* $, DDH is trivially false because the Legendre symbol of $ g^{ab} $ can be determined from $ g^a $ and $ g^b $. To prevent such attacks, the group order should not have small prime divisors. DDH has been successfully used to simplify many cryptographic schemes. The paper discusses some of these applications and highlights the importance of DDH in modern cryptography.The Decision Diffie-Hellman (DDH) problem is a key concept in cryptography, enabling the construction of secure cryptographic systems. This paper surveys recent applications of DDH and known results about its security, while also highlighting open problems in the area. The Diffie-Hellman key exchange protocol relies on the Computational Diffie-Hellman (CDH) assumption, which states that no efficient algorithm can compute the shared secret $ g^{ab} $ from $ g^a $ and $ g^b $. However, CDH alone is insufficient to prove the security of the protocol, as an eavesdropper might still gain useful information about the secret. The DDH assumption, which is stronger, ensures that no efficient algorithm can distinguish between the distributions $ \langle g^a, g^b, g^{ab} \rangle $ and $ \langle g^a, g^b, g^c \rangle $, where $ a, b, c $ are random. This makes DDH a stronger assumption than CDH. While CDH allows the extraction of one unpredictable bit (a hard core bit) from $ g^{ab} $, this process is inefficient. In contrast, DDH allows the extraction of $ n/2 $ bits from a single Diffie-Hellman exchange, which are indistinguishable from random bits. This is achieved using the leftover hash lemma. Cryptographic systems that derive multiple bits from the Diffie-Hellman secret implicitly rely on DDH, not CDH. The DDH assumption is very strong and not always valid. For example, in the multiplicative group $ \mathbb{Z}_p^* $, DDH is trivially false because the Legendre symbol of $ g^{ab} $ can be determined from $ g^a $ and $ g^b $. To prevent such attacks, the group order should not have small prime divisors. DDH has been successfully used to simplify many cryptographic schemes. The paper discusses some of these applications and highlights the importance of DDH in modern cryptography.
Reach us at info@study.space