## 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 ]