Let G be a finite commutative group. A homogeneous space H for G is a finite set H of

the same cardinality S = #H = #G which is acted on simply transitively by G. This

means that there is a single orbite and for any g ∈ G not the identity, the permutation of

H induced by g has no fixed points. If the left action is denoted by a dot we thus have

(∃h ∈ H, g.h = h) =⇒ g = 1.

We assume one can compute efficiently the composition law, inversion of an element

and testing for equality. We also assume we can efficiently choose random elements in G

and compute efficiently the action of G on H.

Now, because of of the lack of fixed points, there is a unique g mapping a given h1 on

a given h2. We denote it by δ(h2, h1). We thus have

δ(h2, h1).h1 = h2.

We may like to compute this δ(h2, h1). A related problem would be to complete a

parallelogram namely, given h1, h2, h3 ∈ H compute the unique h4 such that δ(h2, h1) =

δ(h4, h3).

We will be interested in Homogeneous Spaces for which these two problems are difficult. We call these Hard Homogeneous Spaces (HHS). Examples of HHS are provided by

the discrete logarithm problem and many cryptographic protocols based on the discrete

logarithm problem have a counterpart for any hard homogeneous space. And they are

better discribed in this context.

I first discussed the notion of HHS in a 1997 talk and proposed new examples of HHS

that do not come from DL problems. In this talk I will try to see if there is anything new

to say about HHS almost ten years after.