**Hard Homogeneous Spaces**

*Jean-Marc Couveignes*

**Abstract: **
{\it This note was written in 1997 after a talk I gave at the séminaire
de complexité et cryptographie at the École Normale Supé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)

**Short URL: **ia.cr/2006/291

[ Cryptology ePrint archive ]