• RSS
  • Twitter
  • FaceBook

Security Forums

Log in

FAQ | Search | Usergroups | Profile | Register | RSS | Posting Guidelines | Recent Posts

Diffie-Hellman related Problems Trivia

Users browsing this topic:0 Security Fans, 0 Stealth Security Fans
Registered Security Fans: None
Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

View previous topic :: View next topic  
Author Message
Amitabh
Just Arrived
Just Arrived


Joined: 24 Aug 2004
Posts: 0
Location: Australia

Offline

PostPosted: Fri Nov 25, 2005 8:28 pm    Post subject: Diffie-Hellman related Problems Trivia Reply with quote

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.
Back to top
View user's profile Send private message Visit poster's website
Amitabh
Just Arrived
Just Arrived


Joined: 24 Aug 2004
Posts: 0
Location: Australia

Offline

PostPosted: Sat Dec 03, 2005 7:31 am    Post subject: Reply with quote

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
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   

Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security All times are GMT + 2 Hours
Page 1 of 1


 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Community Area

Log in | Register