Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
It's possible that your question might be better suited for the Crypto StackExchange site: crypto.stackexchange.com –  Timothy Chow Apr 13 '12 at 23:03

3 Answers 3

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.

share|improve this answer
    
Ah! I thought something like this was going on. You are right, computing $T^n$ has no reason to be easy (I was aware that computing $g^n$ in a group was fast). In other words, requiring from $T$ that computing $T^n$ be very fast, AND that the log-problem be hard, gives serious constrains which possibly mean that we will not find anything besides examples coming from groups. Thanks! –  Pierre Apr 13 '12 at 16:19
    
P.S. In hindsight, knowing a primitive root $h$ obviously can't help you break Diffie-Hellman. If you pick $h$ at random, then there's at least a $c/\log \log p$ chance it will be a primitive root (for some constant $c$), so you could pick a small number of candidates at random and pretend each was a primitive root, and probably you'd be right at least once. –  Henry Cohn Apr 13 '12 at 17:22

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.

share|improve this answer
    
I would be very interested in seeing this example, if anyone knows a reference. My intuition with these things needs maturing. –  Pierre Apr 13 '12 at 16:56

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.