Cryptography and iterations

Question

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

Answer 1

What makes Diffie-Hellman work is that the secret maps $x \mapsto x^n$ and $x \mapsto x^m$ commute with each other and are both easy to compute (even if $n$ and $m$ are huge), but knowing $g^n$ doesn't let you easily raise other numbers to the $n$-th power.

Your scheme achieves the commutativity by making both maps powers of a given function $T$, but generically it won't make them easy enough to compute, so it doesn't offer any computational advantage for the participants compared with an attacker. Without some special structure, computing $T^n(x)$ will take about $n$ operations, since you'll have to compute each of $T^1(x)$, $T^2(x)$, etc. in turn. Breaking the scheme by computing $n$ from $T^n(x)$ will be just as fast.

Diffie-Hellman would have the same problem if you had to compute $g^n$ naively (using $n$ operations), but you can use repeated squaring to handle much larger values of $n$. You can certainly use repeated squaring to compute powers of $T$, too, but the underlying set $X$ will be huge, so you'll need a more efficient way to represent powers of $T$ than just as permutations of $X$. This will depend on having some structure, for example knowing that $T$ is in some smaller group, and then the question becomes whether this structure helps break the system.

In principle, I don't see why this shouldn't be secure, because Diffie-Hellman is a special case:

Typically, $g$ will be chosen to have prime order $p$. If $h$ is a primitive root modulo $p$, then all exponentiation maps mod $p$ are powers of $x \mapsto x^h$, so Diffie-Hellman becomes isomorphic to your scheme with $T(x) = x^h$. Maybe I'm overlooking something, but I don't see offhand why knowing a primitive root modulo $p$ would let one break Diffie-Hellman. In that case, your scheme can be as secure as Diffie-Hellman.

However, the security would depend delicately on how you choose $T$, and I wouldn't trust other choices without a lot of thought and cryptanalysis.

Answer 2

Shuffling the bits around "according to your fancy" sounds dangerous. I vaguely recall an example (probably by Knuth) where a sequence of very random-looking choices, to produce a complicated coding, ended up being absurdly easy to break.

Answer 3

I mean this as a comment under Adreas Blass response: I believe the example to which you are referring can be found in Knuth's Volume 2 of The Art of Computer Programming, 3rd ed. on page 5 where he talks about his '"super random" number generator' algorithm.