3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ It's possible that your question might be better suited for the Crypto StackExchange site: crypto.stackexchange.com $\endgroup$ Apr 13, 2012 at 23:03

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – Pierre
    Apr 13, 2012 at 16:19
  • $\begingroup$ 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. $\endgroup$
    – Henry Cohn
    Apr 13, 2012 at 17:22
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ I would be very interested in seeing this example, if anyone knows a reference. My intuition with these things needs maturing. $\endgroup$
    – Pierre
    Apr 13, 2012 at 16:56
  • $\begingroup$ @Pierre This is in the first few pages of Knuth's The Art of Computer Programming Volume 2: Seminumerical Algorithms, section 3.1 (pages 5 and 6, followed by exercises). He concludes with "The moral of this story is that random numbers should not be generated with a method chosen at random. Some theory should be used." $\endgroup$
    – shreevatsa
    Oct 15, 2016 at 1:15
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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