Amitabh Just Arrived
Joined: 24 Aug 2004 Posts: 0 Location: Australia
|
Posted: Fri Nov 25, 2005 8:28 pm Post subject: Diffie-Hellman related Problems Trivia |
|
|
Hi everyone,
For all you people who like asymmetric cryptography, here are a few questions to brainstrom about. All these questions involve the use of oracles. Basically when I say reduce problem A to problem B, I mean; given oracle B, you need to efficiently construct oracle A.
1) Diffie-Hellman Problem (DHP) Given any three pairs (g, g^x, g^y) output g^(xy).
Thus a DHP(g, g^x, g^y) oracle takes arbitrary three inputs, it assigns the first arguement to g, the second to g^x and the third to g^y. It accordingly outputs g^xy.
2) Inverse Diffie-Hellman Problem (IDHP) Given any three pairs (g, g^x, g^xy) output g^y.
Thus a IDHP(g, g^x, g^xy) oracle takes arbitrary three inputs, it assigns the first arguement to g, the second to g^x and the third to g^xy. It accordingly outputs g^y.
3) Extended Diffie-Hellman Problem (EDHP) Given any three pairs (g, g^x, g^xy) output g^(y^2).
4) Inverse-Extended-Diffie-Hellman Problem (IEDHP) Given any three pairs (g, g^x, g^(y^2)) output g^(xy).
Your tasks:
-------------
(Easy)
(a) Reduce IDHP to DHP (i.e. using DHP oracle, make an IDHP oracle)
(b) Reduce DHP to IDHP (if you are able to do (a) you should be able to do this too)
(Medium)
(c) Reduce EDHP to DHP
(d) Reduce DHP to EDHP
(e) Reduce DHP to IEDHP
(Hard)
(f) Reduce IEDHP to DHP
As a proper solution, you must give a proper algorithm rather than a heuristic arguement. Best of luck.
|
|
Amitabh Just Arrived
Joined: 24 Aug 2004 Posts: 0 Location: Australia
|
Posted: Sat Dec 03, 2005 7:31 am Post subject: |
|
|
Part Solutions
We assume that our group elements are taken from a prime order subgroup G thus all elements of G except 1 are generators. Let |G| = q. The exponents are taken from Z*_q
Let DHP(g , g^x , g^y) be output of the DHP oracle and IDHP(g, g^x, g^xy) be the output of an IDHP oracle for arbitrary parameters (as long as they are elements of G)
a) IDHP (g, g^x, g^xy) = DHP(g^x, g, g^xy)
b) DHP (g, g^x, g^y) = IDHP(g^x, g, g^y)
c) EDHP (g, g^x, g^xy) = IDHP(g, IDHP(g, IDHP (g, g^x, g^xy), g^x), g^xy) and we already know that IDHP <=> DHP
d) IDHP(g, g^x, g^xy) = sqrt(EDHP(g, g^x, g^xy.g^x)/(EDHP(g, g^x, g^xy).g)) and we already know that IDHP <=> DHP
|
|