Mixing
Is there a group where CDH is easy but DLog is hard?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
The question is quite simple:
Is there a group where solving the CDH problem can be shown to be easy but solving the discrete logarithm problem is assumed to be hard?
Refresher on the problems:
CDH: Let $mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $gin G$ and $g^a,g^b$ with $a,bstackrel$gets0,ldots,p-1$, that is with uniformly random exponents, find $g^ab$.
DLog: Let $mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $gin G$ and $g^a$ with $astackrel$gets0,ldots,p-1$, that is with a uniformly random exponent, find $a$.
discrete-logarithm hardness-assumptions
asked 3 hours ago
SEJPM♦
27k351129
add a comment |Â
up vote
3
down vote
favorite
The question is quite simple:
Is there a group where solving the CDH problem can be shown to be easy but solving the discrete logarithm problem is assumed to be hard?
Refresher on the problems:
CDH: Let $mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $gin G$ and $g^a,g^b$ with $a,bstackrel$gets0,ldots,p-1$, that is with uniformly random exponents, find $g^ab$.
DLog: Let $mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $gin G$ and $g^a$ with $astackrel$gets0,ldots,p-1$, that is with a uniformly random exponent, find $a$.
discrete-logarithm hardness-assumptions
asked 3 hours ago
SEJPM♦
27k351129
And yes, I did perform a (admittedly quick) search over the site and via google and yes I do realize that for DDH / CDH (instead of CDH / DLog) the answer is "yes". Also I do know that apparently there are groups where CDH and DLog are equivalent.
– SEJPM♦
3 hours ago
Using pairings maybe? I'll try tomorrow morning
– ddddavidee
2 hours ago
As of 2014, none were known: crypto.stackexchange.com/questions/13034/…
– rikhavshah
1 hour ago
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
The question is quite simple:
Is there a group where solving the CDH problem can be shown to be easy but solving the discrete logarithm problem is assumed to be hard?
Refresher on the problems:
CDH: Let $mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $gin G$ and $g^a,g^b$ with $a,bstackrel$gets0,ldots,p-1$, that is with uniformly random exponents, find $g^ab$.
DLog: Let $mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $gin G$ and $g^a$ with $astackrel$gets0,ldots,p-1$, that is with a uniformly random exponent, find $a$.
discrete-logarithm hardness-assumptions
asked 3 hours ago
SEJPM♦
27k351129
The question is quite simple:
Is there a group where solving the CDH problem can be shown to be easy but solving the discrete logarithm problem is assumed to be hard?
Refresher on the problems:
CDH: Let $mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $gin G$ and $g^a,g^b$ with $a,bstackrel$gets0,ldots,p-1$, that is with uniformly random exponents, find $g^ab$.
DLog: Let $mathbb G=(G,+,0,p)$ be a public cyclic group of order $p$. Given any $gin G$ and $g^a$ with $astackrel$gets0,ldots,p-1$, that is with a uniformly random exponent, find $a$.
discrete-logarithm hardness-assumptions
discrete-logarithm hardness-assumptions
asked 3 hours ago
SEJPM♦
27k351129
asked 3 hours ago
SEJPM♦
27k351129
asked 3 hours ago
SEJPM♦
27k351129
asked 3 hours ago
SEJPM♦
27k351129
asked 3 hours ago
SEJPM♦
27k351129
27k351129
And yes, I did perform a (admittedly quick) search over the site and via google and yes I do realize that for DDH / CDH (instead of CDH / DLog) the answer is "yes". Also I do know that apparently there are groups where CDH and DLog are equivalent.
– SEJPM♦
3 hours ago
Using pairings maybe? I'll try tomorrow morning
– ddddavidee
2 hours ago
As of 2014, none were known: crypto.stackexchange.com/questions/13034/…
– rikhavshah
1 hour ago
add a comment |Â
And yes, I did perform a (admittedly quick) search over the site and via google and yes I do realize that for DDH / CDH (instead of CDH / DLog) the answer is "yes". Also I do know that apparently there are groups where CDH and DLog are equivalent.
– SEJPM♦
3 hours ago
Using pairings maybe? I'll try tomorrow morning
– ddddavidee
2 hours ago
As of 2014, none were known: crypto.stackexchange.com/questions/13034/…
– rikhavshah
1 hour ago
And yes, I did perform a (admittedly quick) search over the site and via google and yes I do realize that for DDH / CDH (instead of CDH / DLog) the answer is "yes". Also I do know that apparently there are groups where CDH and DLog are equivalent.
– SEJPM♦
3 hours ago
And yes, I did perform a (admittedly quick) search over the site and via google and yes I do realize that for DDH / CDH (instead of CDH / DLog) the answer is "yes". Also I do know that apparently there are groups where CDH and DLog are equivalent.
– SEJPM♦
3 hours ago
Using pairings maybe? I'll try tomorrow morning
– ddddavidee
2 hours ago
Using pairings maybe? I'll try tomorrow morning
– ddddavidee
2 hours ago
As of 2014, none were known: crypto.stackexchange.com/questions/13034/…
– rikhavshah
1 hour ago
As of 2014, none were known: crypto.stackexchange.com/questions/13034/…
– rikhavshah
1 hour ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Here is something that is close but not exactly what you're asking for. But it may be enough for what you have in mind.
This paper uses indistinguishability obfuscation to construct a group with self-bilinear map -- i.e., a map $e : G times G to G$ (same source & target groups).
Yamakawa et al., Self-bilinear Map on Unknown Order Groups from Indistinguishability Obfuscation and Its Applications, CRYPTO 2014.
Although I don't completely understand their hardness assumption, and they don't explicitly talk about discrete log, the fact that the "obvious" generalization of Diffie-Hellman gives secure multi-party non-interactive key agreement suggests that discrete log must be hard.
Unfortunately, having a self-bilinear map $e : G times G to G$ is not quite the same as a CDH solution! Indeed, their construction uses $e(g^x, g^y) = g^2xy$ which is bilinear, but they are in (a subgroup of) an RSA group $mathbbZ_pq$ where computing square roots is hard. They explicitly still want CDH to be hard in the group!
answered 1 hour ago
Mikero
4,71711520
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Here is something that is close but not exactly what you're asking for. But it may be enough for what you have in mind.
This paper uses indistinguishability obfuscation to construct a group with self-bilinear map -- i.e., a map $e : G times G to G$ (same source & target groups).
Yamakawa et al., Self-bilinear Map on Unknown Order Groups from Indistinguishability Obfuscation and Its Applications, CRYPTO 2014.
Although I don't completely understand their hardness assumption, and they don't explicitly talk about discrete log, the fact that the "obvious" generalization of Diffie-Hellman gives secure multi-party non-interactive key agreement suggests that discrete log must be hard.
Unfortunately, having a self-bilinear map $e : G times G to G$ is not quite the same as a CDH solution! Indeed, their construction uses $e(g^x, g^y) = g^2xy$ which is bilinear, but they are in (a subgroup of) an RSA group $mathbbZ_pq$ where computing square roots is hard. They explicitly still want CDH to be hard in the group!
answered 1 hour ago
Mikero
4,71711520
add a comment |Â
up vote
2
down vote
Here is something that is close but not exactly what you're asking for. But it may be enough for what you have in mind.
This paper uses indistinguishability obfuscation to construct a group with self-bilinear map -- i.e., a map $e : G times G to G$ (same source & target groups).
Yamakawa et al., Self-bilinear Map on Unknown Order Groups from Indistinguishability Obfuscation and Its Applications, CRYPTO 2014.
Although I don't completely understand their hardness assumption, and they don't explicitly talk about discrete log, the fact that the "obvious" generalization of Diffie-Hellman gives secure multi-party non-interactive key agreement suggests that discrete log must be hard.
Unfortunately, having a self-bilinear map $e : G times G to G$ is not quite the same as a CDH solution! Indeed, their construction uses $e(g^x, g^y) = g^2xy$ which is bilinear, but they are in (a subgroup of) an RSA group $mathbbZ_pq$ where computing square roots is hard. They explicitly still want CDH to be hard in the group!
answered 1 hour ago
Mikero
4,71711520
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Here is something that is close but not exactly what you're asking for. But it may be enough for what you have in mind.
This paper uses indistinguishability obfuscation to construct a group with self-bilinear map -- i.e., a map $e : G times G to G$ (same source & target groups).
Yamakawa et al., Self-bilinear Map on Unknown Order Groups from Indistinguishability Obfuscation and Its Applications, CRYPTO 2014.
Although I don't completely understand their hardness assumption, and they don't explicitly talk about discrete log, the fact that the "obvious" generalization of Diffie-Hellman gives secure multi-party non-interactive key agreement suggests that discrete log must be hard.
Unfortunately, having a self-bilinear map $e : G times G to G$ is not quite the same as a CDH solution! Indeed, their construction uses $e(g^x, g^y) = g^2xy$ which is bilinear, but they are in (a subgroup of) an RSA group $mathbbZ_pq$ where computing square roots is hard. They explicitly still want CDH to be hard in the group!
answered 1 hour ago
Mikero
4,71711520
Here is something that is close but not exactly what you're asking for. But it may be enough for what you have in mind.
This paper uses indistinguishability obfuscation to construct a group with self-bilinear map -- i.e., a map $e : G times G to G$ (same source & target groups).
Yamakawa et al., Self-bilinear Map on Unknown Order Groups from Indistinguishability Obfuscation and Its Applications, CRYPTO 2014.
Although I don't completely understand their hardness assumption, and they don't explicitly talk about discrete log, the fact that the "obvious" generalization of Diffie-Hellman gives secure multi-party non-interactive key agreement suggests that discrete log must be hard.
Unfortunately, having a self-bilinear map $e : G times G to G$ is not quite the same as a CDH solution! Indeed, their construction uses $e(g^x, g^y) = g^2xy$ which is bilinear, but they are in (a subgroup of) an RSA group $mathbbZ_pq$ where computing square roots is hard. They explicitly still want CDH to be hard in the group!
answered 1 hour ago
Mikero
4,71711520
answered 1 hour ago
Mikero
4,71711520
answered 1 hour ago
Mikero
4,71711520
answered 1 hour ago
Mikero
4,71711520
4,71711520
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f62944%2fis-there-a-group-where-cdh-is-easy-but-dlog-is-hard%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
And yes, I did perform a (admittedly quick) search over the site and via google and yes I do realize that for DDH / CDH (instead of CDH / DLog) the answer is "yes". Also I do know that apparently there are groups where CDH and DLog are equivalent.
– SEJPM♦
3 hours ago
Using pairings maybe? I'll try tomorrow morning
– ddddavidee
2 hours ago
As of 2014, none were known: crypto.stackexchange.com/questions/13034/…
– rikhavshah
1 hour ago