Cryptology ePrint Archive: Report 2006/174

Frobenius expansion and the Diffie Hellman problem

V. R. Sule

Abstract: This paper proposes investigation of special sessions of the Diffie Hellman (DH) key exchange scheme on elliptic curves for which the shared key can be computed by a polynomial time algorithm. Such sessions are called \emph{singular}. Existence of singular sessions are demonstrated using the Frobenius expansion and polynomial representation of public keys which lead to an expression for the shared key. When the Weil pairing can be computed on the elliptic curve along with a modified pairing defined by a distortion map efficiently, a sufficient condition is obtained for sessions to be singular which can be verified in polynomial time. Hence this condition identifies sessions whose singular nature can be determined in polynomial time. A single round three party key exchange scheme is proposed using singular sessions in which efficient computation of the shared key of a pair of users by the third party is a necessary requirement. This scheme is thus a positive application of singular sessions and offers a possible alternative to the need for using super singular curves on which pairings can be computed efficiently.

Category / Keywords: public-key cryptography / Diffie Hellman scheme, Frobenius expansion, Tri-party key exchange.

Publication Info: Not submitted for publication

Date: received 11 May 2006, withdrawn 9 Jun 2006

Contact author: vrs at ee iitb ac in

Available format(s): (-- withdrawn --)

Note: PDF file frobenius&dhp.pdf

Version: 20060610:020949 (All versions of this report)

Short URL: ia.cr/2006/174

Discussion forum: Show discussion | Start new discussion