Diffie-Hellman Problems in Cryptography
Diffie-Hellman Problems
Slides by Prof. Jonathan Katz.
Lightly edited by me.
Diffie-Hellman problems
•
Fix cyclic group G and generator g
•
Define DH
g
(h
1
, h
2
) = DH
g
(g
x
, g
y
) = g
xy
Diffie-Hellman assumptions
•
Computational
Diffie-Hellman (CDH) problem:
•
Given g, h
1
, h
2
, compute DH
g
(h
1
, h
2
)
•
Decisional
Diffie-Hellman (DDH) problem:
•
Given g, h
1
, h
2
, distinguish DH
g
(h
1
, h
2
) from a uniform element of G
Example
•
In
ℤ
*
11
•
<2> = {1, 2, 4, 8, 5, 10, 9, 7, 3, 6}•
So DH
2
(7, 5) = ?
•
In
ℤ
*
3092091139
•
What is DH
2
(1656755742, 938640663)?
•
Is 1994993011 the answer, or is it just a random element of
ℤ
*
3092091139
?
DDH problem
•
Let
G
be a group-generation algorithm
•
On input 1
n
, outputs a cyclic group G, its order q (with
ǁqǁ
=n), and a generator
g
•
The DDH problem is hard relative to
G
if for all PPT algorithms A:
| Pr[A(G, q, g, g
x
, g
y
, g
xy
)=1] – Pr[A(G, q, g, g
x
, g
y
, g
z
)=1] | ≤
(n)
Relating the Diffie-Hellman problems
•
Relative to
G:
•
If the discrete-logarithm problem is easy, so is the CDH problem
•
If the CDH problem is easy, so is the DDH problem
•
I.e., the DDH assumption is
stronger
than the CDH assumption
•
I.e., the CDH assumption is
stronger
than the dlog assumption
Exploring Diffie-Hellman assumptions and problems including Computational Diffie-Hellman (CDH) and Decisional Diffie-Hellman (DDH). Discusses the difficulty of solving the DDH problem compared to CDH and discrete logarithm assumptions. Covers examples and implications of these cryptographic challenges.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Diffie-Hellman Problems Slides by Prof. Jonathan Katz. Lightly edited by me.
Diffie-Hellman problems Fix cyclic group G and generator g Define DHg(h1, h2) = DHg(gx, gy) = gxy
Diffie-Hellman assumptions Computational Diffie-Hellman (CDH) problem: Given g, h1, h2, compute DHg(h1, h2) Decisional Diffie-Hellman (DDH) problem: Given g, h1, h2, distinguish DHg(h1, h2) from a uniform element of G
Example In *11 <2> = {1, 2, 4, 8, 5, 10, 9, 7, 3, 6} So DH2(7, 5) = ? In *3092091139 What is DH2(1656755742, 938640663)? Is 1994993011 the answer, or is it just a random element of *3092091139 ?
DDH problem Let G be a group-generation algorithm On input 1n, outputs a cyclic group G, its order q (with q =n), and a generator g The DDH problem is hard relative to G if for all PPT algorithms A: | Pr[A(G, q, g, gx, gy, gxy)=1] Pr[A(G, q, g, gx, gy, gz)=1] | (n)
Relating the Diffie-Hellman problems Relative to G: If the discrete-logarithm problem is easy, so is the CDH problem If the CDH problem is easy, so is the DDH problem I.e., the DDH assumption is stronger than the CDH assumption I.e., the CDH assumption is stronger than the dlog assumption
