Cryptology ePrint Archive: Report 2006/291

Hard Homogeneous Spaces

Jean-Marc Couveignes

Abstract: {\it This note was written in 1997 after a talk I gave at the s{\'e}minaire de complexit{\'e} et cryptographie at the \'Ecole Normale Sup{\'e}rieure\footnote{http://www.di.ens.fr/~wwwgrecc/Seminaire/1996-97.html} After it was rejected at crypto97 I forgot it until a few colleagues of mine informed me that it could be of some interest to some researchers in the field of algorithmic and cryptography. Although I am not quite happy with the redaction of this note, I believe it is more fair not to improve nor correct it yet. So I leave it in its original state, including misprints. I just added this introductory paragraph. If need be, I will publish an updated version later.}

We introduce the notion of hard homogeneous space (HHS) and briefly develop the corresponding theory. We show that cryptographic protocols based on the discrete logarithm problem have a counterpart for any hard homogeneous space. Indeed, the notion of hard homogeneous space is a more general and more natural context for these protocols. We exhibit conjectural hard homogeneous spaces independant from any discrete logarithm problem. They are based on complex multiplication theory. This shows the existence of schemes for authentication and key exchange that do not rely on the difficulty of computing dicrete logarithm in any finite group nor factoring integers. We show that the concept of HHS fits with class field theory to provide a unified theory for the already used discrete logarithm problems (on multiplicative groups of finite fields or rational points on elliptic curves) and the HHS we present here. We discuss a few algorithmic questions related to hard homogeneous spaces.

The paper is looking for a wider point of view on the discrete logarithm problem both mathematically and cryptographically.

Category / Keywords: public-key cryptography / groups, protocoles, elliptic curves

Date: received 24 Aug 2006

Contact author: couveig at univ-tlse2 fr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20060824:194736 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]