Hi,

Here is a question in cryptography which is probably naive, and a reference request.

I was wondering about the following key-exchange scheme, which is a variant on Diffie-Hellman. Consider a set $X$ (finite but very large) and a map $T : X \to X$, both made public together with a point $x \in X$. Now A chooses an integer $n$ secretly and publishes $T^n(x)$, while B does the same with $m$. A and B can both compute the key $T^{n+m}(x)$, and assuming that it is difficult to find $n$ from $x$ and $T^n(x)$, then noone else can.

Traditionally one picks an element $g$ in a group $G$, then A publishes $g^n$, B publishes $g^m$, and A and B both know the key $g^{nm}$. For $G$ one picks $(\mathbf{Z}/p)^\times$, or an elliptic curve over a finite field, or a braid group, or what have you.

It seems that with the above variant, it is easy to produce examples: for example take $X$ to be a vector space over $\mathbf{F}_2$, and let $T$ be some map which shuffles the bits around according to your fancy. My intuition is that it is easier to make the "log-problem" difficult in this way than by choosing the right group $G$. I may be so completely wrong!

Is there an obvious weakness in this scheme? For example, is it very hard to prove that, for a given map $T$, the "log-problem" is indeed difficult?

It may well be that I'm only describing something standard.

What is a good reference, then?

(Basic searches with "cryptography and dynamics" were not satisfactory.)

Thanks for reading!

Pierre